No desired output for code.

[James349]

Hello, I am working on a tic-tac-toe project for python for a 7 by 7 grid and I am supposed to define a specific depth and use alpha-beta pruning for the user to defeat the computer or vice-versa. So far, I have the code, but the results are disappointing. The winning combination is four consecutive diagonal, horizontal or vertical symbols of 'X' or 'O'. Please, please, please help review my code to run.

import math

def evaluate(board, player):
    # Evaluate the current state of the board for the given player
    # Returns a positive value if the player is winning, negative if losing, and 0 if it's a draw

    # Check rows
    for i in range(0, 49, 7):
        for j in range(i, i + 4):
            if all(board[k] == player for k in range(j, j + 4)):
                return math.inf if player == 'X' else -math.inf

    # Check columns
    for i in range(1, 8):
        for j in range(i, i + 21, 7):
            if all(board[k] == player for k in range(j, j + 28, 7)):
                return math.inf if player == 'X' else -math.inf

    # Check diagonals
    for i in range(3, 24, 7):
        if all(board[i - j] == player for j in range(0, 25, 8)):
            return math.inf if player == 'X' else -math.inf
        if all(board[i + j] == player for j in range(0, 19, 6)):
            return math.inf if player == 'X' else -math.inf

    return 0

def minimax(board, depth, alpha, beta, maximizingPlayer):
    # Recursive function to perform Alpha-Beta search

    # Base cases
    score = evaluate(board, 'X')
    if score != 0:
        return score - depth
    if depth == 0:
        return 0

    if maximizingPlayer:
        maxEval = -math.inf
        for move in get_empty_cells(board):
            board[move] = 'X'
            eval = minimax(board, depth - 1, alpha, beta, False)
            board[move] = '_'  # Undo move
            maxEval = max(maxEval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break
        return maxEval
    else:
        minEval = math.inf
        for move in get_empty_cells(board):
            board[move] = 'O'
            eval = minimax(board, depth - 1, alpha, beta, True)
            board[move] = '_'  # Undo move
            minEval = min(minEval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break
        return minEval

def get_empty_cells(board):
    # Returns a list of indices for all empty cells in the board
    return [key for key, value in board.items() if value == '_']

def find_best_move(board):
    # Find the best move for the AI player using the Alpha-Beta algorithm
    bestEval = -math.inf
    bestMove = None

    for move in get_empty_cells(board):
        board[move] = 'X'
        eval = minimax(board, 5, -math.inf, math.inf, False)  # Set the desired search depth here
        board[move] = '_'  # Undo move

        if eval > bestEval:
            bestEval = eval
            bestMove = move

    return bestMove

# Example usage
board = {1: '_', 2: '_',   3: '_',  4: '_',  5: '_',  6: '_', 7: '_',
         8: '_', 9: '_',  10: '_', 11: '_', 12: '_', 13: '_', 14: '_', 
        15: '_', 16: '_', 17: '_', 18: '_', 19: '_', 20: '_', 21: '_',
        22: '_', 23: '_', 24: '_', 25: '_', 26: '_', 27: '_', 28: '_', 
        29: '_', 30: '_', 31: '_', 32: '_', 33: '_', 34: '_', 35: '_', 
        36: '_', 37: '_', 38: '_', 39: '_', 40: '_', 41: '_', 42: '_', 
        43: '_', 44: '_', 45: '_', 46: '_', 47: '_', 48: '_', 49: '_'}

def printBoard(board):
    # Print the tic-tac-toe board
    for i in range(1, 50, 7):
        row = [board[j] for j in range(i, i + 7)]
        print("_" + "_|_".join(row) + "_")
    print("\n")

print("WELCOME TO TIC-TAC-TOE!!")
printBoard(board)

player = input("Choose your symbol, uppercase (X or O): ")

# Example usage
best_move = find_best_move(board)
board[best_move] = 'X'
print("Best move:", best_move)
printBoard(board)

Larz60+ write May-17-2023, 04:38 PM:
It is against forum rules to post multiple threads on the same subject.
Thus duplicates have been deleted

[deanhystad]

Your evaluate function is messed up. The diagonal check gets index out of range errors. You cannot start in the same squares looking for an upward or downward diagonal. Winning downward diagonals start in squares 0, 1, 2, 3, 7, 8, 9, 10, 14, 15, 16, 17, 21, 22, 23, 24. Winning upward diagonals start in squares 21, 22, 23, 24, 28, 29, 30, 31, 35, 36, 36, 37, 42, 43, 44, 45.

Your code assumes the player is "X" even though you let the player select "X" or "O". You should have a variable named "player" that is assigned the player's marker, and another variable (named computer?) that is assigned the other marker. The variables should be used in place of "X" and "O" literals in your code. Or you could force the player to play "X".

If you need 4 in a row to win, the minimum number of moves to win is 7. If the max search depth is 6, there is no reason to call minimax for the first move. All squares will run into the move limit and return 0, so all squares are equally good according to minimax. Theoretically the second move could find a winner, but that is unlikely because you are only looking at a tiny percentage of all the possible solutions. When I ran your code (modified to play a complete 4x4 game), minimax did not make an informed play until the sixth move when it realized it should place the "O" to block a vertical line of "X" forming in column 1.

Output:
['X', 'O', 'X', 'O']
['X', '_', '_', '_']
['O', '_', '_', '_']
['_', '_', '_', '_']

Prior to that all calls to minmax hit the depth limit and returned 0.

If you want a better computer player, you need to increase the searched depth. But if you increase the search depth it takes forever to find a solution for the board. I didn't even try playing on a 7x7 board because the 4x4 board was already too slow to be playable. This is the nature of brute-force solutions like minimax. The number of possible solutions grows very quickly. Just for fun I removed the depth limit and let minimax find the first move in a 4x4 board. Six hours later it is still searching.