Problem with a minimax algorith in Tic,Tac,Toe

[deanhystad]

Now that I found the problem I can't believe I didn't see it before. It was so obvious it took me almost a day to see it.

This is the code in minimax() for when isMaximizing is False:

                init[key]==1   # <- Does this look odd?
                score = minimax(init,True)
                init[key]==0   # <- How about this:

Fix this problem and I think it will work. I switched over to using minimax and have not beat the computer in 50 tries.

After the code is fixed the first move will be really quick compared to how it was. But the very first move still takes much longer than the second which takes far longer than the third and so on. To speed things up you could have the player go first so the robot only has to test 8 positions which takes much less time than 9 positions. If you still want the robot to go first you could just randomly pick a square for the first move, and by the time the robot plays again there are only 7 moves to test which takes no time at all.

This is my minimax implementation I added to a tkinter tic tac toe game I wrote a while back. I added a randomizer to randomly pick from equally good results. It doesn't come into play very often as there is usually one best answer, but it does prevent the robot always making the same first move.

    def robotMove(self):
        """Get robot move.  Robot choses square that gives it the best chance to win"""
        moves = []
        for move, mark in enumerate(self.board):
            if mark is None:
                self.board[move] = self.ROBOT
                moves.append((move, self.minimax(False)))
                self.board[move] = None
        # To make things less "robotic" randomly choose from equally good results
        random.shuffle(moves)
        moves.sort(key=lambda x:x[1], reverse=True)
        self.placeMarker(moves[0][0], self.ROBOT)
 
    def minimax(self, maximize):
        """Return a "score" for the current board using minimax algorithm.
        Score is computed by recursively calling the function and alternating
        between picking the best move for the robot and the player.  If
        the robot wins the board gets a positive score.  If the player wins the
        board gets a negative score.
        """
        if (win := self.winner()) is not None:
           # Sombody won.  Score +1 if it was the robot and -1 if it was the player.
            score = 1 if self.board[win[0]] == self.ROBOT else -1
        elif not None in self.board:
            score = 0  # Draw
        elif maximize:  # Pick best move for robot (maximum score)
            score = -10000
            for move, marker in enumerate(self.board):
                if marker is None:
                    self.board[move] = self.ROBOT
                    score = max(score, self.minimax(False))
                    self.board[move] = None
        else: # Pick best move for player (minimum score)
            score = 10000
            for move, marker in enumerate(self.board):
                if marker is None:
                    self.board[move] = self.PLAYER
                    score = min(score, self.minimax(True))
                    self.board[move] = None
        return score