0
\$\begingroup\$

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"))
\$\endgroup\$
  • \$\begingroup\$ Hi, sadly we only review working code. I encourage you to check the Help Center to see what kind of questions you may ask here :) \$\endgroup\$ – IEatBagels Jan 30 '19 at 15:22
  • \$\begingroup\$ I have rolled-back your question to the original. On Code Review, you cannot change your question once it has been answered, as doing so can invalidate any answers which have already been given. Code Review is also not for assistance locating and fixing bugs in code; it is for reviewing working code. A review may discover an previously unknown bug, but the code must be working to the best of your knowledge prior to posting it. \$\endgroup\$ – AJNeufeld Jan 30 '19 at 16:33
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ But i have one problem now when I tested more. \$\endgroup\$ – Samad Farooq Jan 30 '19 at 13:04
  • \$\begingroup\$ I update my quesiton. Please check my code @AJNeufeld \$\endgroup\$ – Samad Farooq Jan 30 '19 at 13:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.