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\$

closed as off-topic by Mathias Ettinger, Graipher, IEatBagels, Toby Speight, Sᴀᴍ Onᴇᴌᴀ Jan 30 at 18:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Mathias Ettinger, IEatBagels, Toby Speight, Sᴀᴍ Onᴇᴌᴀ
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\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 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 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 at 13:04
  • \$\begingroup\$ I update my quesiton. Please check my code @AJNeufeld \$\endgroup\$ – Samad Farooq Jan 30 at 13:12

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