CODEWITHSUNDEEP
algorithmartificial-intelligenceminimaxheuristicsalpha-beta-pruning
Alex
Alex

Reputation: 23

My alpha beta search algo is slow for ultimate tic tac toe AI bot

I am doing a school project where i am trying to write an alpha beta serach algorithm to solve ultimate tic tac toe. (ultimate tic tac toe is just a 3x3 grid of normal tic tac toes where each move you place, the next move (so opponent) gets sent to that grid placement).

The problem for it to not "infinitely" loop (basically the branching factor is too large), i have to limit search depth, so it isn't a great solution. Currently if I let it go over a search depth of 4, its basically useless. Can anyone please tell me better ways of doing my algorithm, or any improvements i would really appreciate it as I am new to the AI algorithm space.

FYI it can win games, but only against random bots (bots that place randomly). Against other AI bots it basically always loses. I am currently implementing a heuristic function to order moves, but im not so sure that this would solve my problem.

Below is snippets of the important functions from my code.

# choose a move to play - this is called everytime its the bots move
def play(max_rec_depth=4):

    n = execute_alp_bta(max_rec_depth)
    
    place(curr, n, 1)
    return n
    
    
# Call to execute
def execute_alp_bta(max_rec_depth) -> int:
    global curr
    
    max_pos = -1 
    max_val = float('-inf') 
    
    moves = get_heuristic_ordered_moves(curr)
    # Iterate over possible moves on the current board
    for i in range(1, 10):
        if boards[curr][i] == 0:
            boards[curr][i] = 1  # Simulate place Maximiser (us)
            
            # Recurse starting from opponents view
            score = minimax(max_rec_depth, float('-inf'), float('inf'), is_maximising_player=False, curr_val=i)
            boards[curr][i] = 0  # Undo the simulated move
            
            # Update the best score and position if the current score is better
            if score > max_val:
                max_val = score
                max_pos = i

    # Return the position that gives the maximum value as per minimax
    if max_pos == -1:
        raise ValueError("Error with Minimax recursion")
    
    # print(f"found max val of {max_val} for pos {max_pos}")
    return max_pos


# MAXIMISING PLAYER - should be the US the computer
def minimax(depth, alpha, beta, is_maximising_player, curr_val) -> int:
    eval = evaluate() # returns win loss draw or none
    if depth == 0 or abs(eval) == 1:  # Terminal condition
        return eval
    
    if is_maximising_player:
        max_val = float('-inf')
        for i in range(1, 10):
            if boards[curr_val][i] == 0:
                boards[curr_val][i] = 1 # Maximisers move
                # print(f"placed at board: {curr_val} with index {i}")
                score = minimax(depth-1, alpha, beta, False, curr_val=i)
                # print(f"exited back out of recursion. Undid board: {curr_val} with index {i}")
                boards[curr_val][i] = 0 # Undo move
                max_val = max(max_val, score)
                alpha = max(alpha, score)
                if beta <= alpha:
                    break
            
        return max_val
    else: 
        min_val = float('inf')
        for i in range(1, 10):
            if boards[curr_val][i] == 0:
                boards[curr_val][i] = -1 # minimizers move
                # print(f"placed at board: {curr_val} with index {i}")
                score = minimax(depth-1, alpha, beta, True, curr_val=i)
                # print(f"exited back out of recursion. Undid board: {curr_val} with index {i}")
                boards[curr_val][i] = 0 # undo move
                min_val = min(min_val, score)
                beta = min(beta, score)
                if beta <= alpha:
                    break
        
            
        return min_val

picture of board in winning position

Upvotes: 2

Views: 197

Answers (1)

Mirella Greco
Mirella Greco

Reputation: 11

1- In tic-tac-toe there are some situations in which the player who starts the game will win. For example in a 3x3 board if X starts the game and fills two corners, he wins; or at least there will be a draw. So the rival must try to draw, he can never win. If your code loses in such situations, it’s ok, but if you lose in simpler situations, it means your code have a bug.

2- In this game your code has to check all the future moves for each move, so its normal that it takes time when your board is 10x10

3- You haven’t set any starting point for the time when the board is empty and you have to start the game. Your code checks all possible moves but its not necessary. You can specify a point for the code to choose when the board is empty (for example (0,0)).

4-in the “else” part in minimax() function, add a condition after calculating the score:

score = minimax(depth-1, alpha, beta, True, curr_val=i)
if score == -1:
    return -1

because when your rival finds a way to win (score == -1) he will absolutely use it. So you don’t need to check more moves.

5-if it is possible for your code to be the player who starts the game or the second player, your eval() func needs to know if you are the first player or the second. You need a function that returns the current player at each move and you should call it at the first time that you call minimax, so it returns your side (first player or second player (X or O)). (players are X and O and board is 3x3)

def player(board):
    # Returns player who has the next turn on a board.
    if sum(row.count(None) for row in board) == 9:
        return X
    elif terminal(board) == True:
        return "end"
    else:
        if sum(row.count(X) for row in board) > sum(row.count(O) for row in board):
            return O
        else:
            return X

You need a global variable AI-side and initialize it at the first time you call minimax.

AI_side = player(board)

Use AI-side in eval() to identify the player who should win.

I hope it can help you.

Upvotes: 1

Related Questions