Could someone check the Minimax Algorithm correctly implemented? I'm working on AI tic-tac-toe that computer make a move and I wanted to know that I correctly implemented the minimax algorithm. Please someone check my code to identify a problem or any kind of bug. Any help would be greatly appreciated.

I wanted to know that my code is correctly running the minimax algorithm according to this image.

test-cases-for-tic-tac-toe

from math import inf as infinity

def winner(game, turn):
    win_game = [
        [game[0][0], game[0][1], game[0][2]],
        [game[1][0], game[1][1], game[1][2]],
        [game[2][0], game[2][1], game[2][2]],
        [game[0][0], game[1][0], game[2][0]],
        [game[0][1], game[1][1], game[2][1]],
        [game[0][2], game[1][2], game[2][2]],
        [game[0][0], game[1][1], game[2][2]],
        [game[2][0], game[1][1], game[0][2]],
    ]
    if [turn, turn, turn] in win_game:
        return True
    else:
        return False


def draw(game):
    """ Check whether the board is full """
    counter = 0
    for i in range(3):
        for j in range(3):
            if game[i][j] == "X" or game[i][j] == "O":
                counter+=1
    return counter == 9


def game_over(game, turn):
    return winner(game, turn) or draw(game)


def available_moves(game):
    cell = []
    for i in range(3):
        for j in range(3):
            if not(game[i][j] == "X" or game[i][j] == "O"):
                cell.append([i, j])
    return cell


def minimax(game, turn):
    if winner(game, "X"):
        return 1
    elif winner(game, "O"):
        return -1
    elif draw(game):
        return 0

    moves = available_moves(game)
    print(moves)

    if turn == "X":
        value = -infinity
        for move in moves:
            tmp = game[:][:]
            tmp[move[0]][move[1]] = "X"
            value = max(value, minimax(game, "O"))
            tmp[move[0]][move[1]] = None
            x, y = move[0], move[1]
    else:
        value = infinity
        for move in moves:
            tmp = game[:][:]
            tmp[move[0]][move[1]] = "O"
            value = min(value, minimax(game, "X"))
            tmp[move[0]][move[1]] = None
            x, y = move[0], move[1]
    return value


if __name__ == '__main__':


    game = [
        ["O", None, None],
        ["O", "X", "X"],
        [None, "O", "X"]]



    print(minimax(game, "X"))
tmp = game[:][:] is not doing what you think it is doing.  game[:] returns a slice of all the rows of game (so a list of columns).  To that, you apply the slice operator [:], which takes the slice of the row list (of columns), and returns a row list (of columns).  In short, game[:] is the same as game[:][:], which is the same as game[:][:][:][:][:].

In particular, tmp is list which contains references to the same column lists as game, so tmp[row][col] accesses exactly the same entry as game[row][col].  You have not created a temporary copy of game; you have created a copy of references to the same column list objects.

As such, you can remove tmp, and just set game[row][col] directly, and set it back to None like you are doing via tmp.



The code x, y = move[0], move[1] seems to be useless, since x and y are never used.



The minimax() function returns the best possible outcome for that player, but doesn’t return the move that corresponds to that outcome.  “You have a guaranteed winning move, but I’m not going to tell you what it is.”

You might want to return the move that corresponds to that outcome.