Minimax algorithm for Tic Tac Toe Python

Some problems:

• Execution is interrupted from loop for
  
  c return
  
  on the first iteration: this is premature since you never check any of the other available moves. What return
  
  should happen after the cycle.

• It is wrong to increase the depth value in each loop iteration for
  
  . Instead, pass depth+1
  
  to a recursive call so that when you return from it, you continue at the same depth.

• The movement performed before the recursive call must return immediately after it, otherwise the next iteration of the loop for
  
  will not start from the same position.

• The value for best
  
  must be initialized on every call to the minimax method, not just at the top of the recursion tree. This initial value should not be 0, because the best value for the current user might be worse than 0. Therefore, you need to initialize it to an extremely bad value.

• The minimax method does not return the best move, only the estimated value. Since the whole purpose of the method is to tell you which move to play, you need both. So let the method return a tuple with both values: the score value and the move that generated that value.

Some non-critical issues:

• How do you want to postpone an inevitable loss or speed up a forced win, the formula for calculating the value for when a player's winner should move closer to 0 is further, not closer. Therefore, a change is required in this formula.

• Since you have to rebuild the board by returning the moves, there is no need to work with duplicated boards and duplicated squares. If everything is correctly coded, after the top minimax method call is completed, the board should be in the same state as before this call.

• The tip prints better if you don't use a None
  
  single character, for example, "." For empty squares. So wherever you refer to empty square values, put this symbol.

• You have print()
  
  here and there to separate the exit. Put it in a method showBoard
  
  and the rest of your code can do without them.

• For some of the above items you do not need a parameter node
  
  , and first
  
  for the method minimax
  
  .

Here is the commented, revised version. I left your original lines in place, but commented out where appropriate.

# *** not needed:
# from copy import deepcopy

class TicTacToeBrain :

    def __init__(self, player = "x") :
        self._squares = {}
        self._copySquares = {}
        self._winningCombos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8],
        [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6])

    def createBoard(self) :
        for i in range(9) :
            # *** use a single character, ... easier to print
            self._squares[i] = "."
        print(self._squares)

    def showBoard(self) :
        # *** add empty line here, instead of in minimax
        print ()
        print(self._squares[0], self._squares[1], self._squares[2])
        print(self._squares[3], self._squares[4], self._squares[5])
        print(self._squares[6], self._squares[7], self._squares[8])


    def getAvailableMoves(self) :
        self._availableMoves = []
        for i in range(9) :
            # *** see above
            if self._squares[i] == "." :
                self._availableMoves.append(i)
        return self._availableMoves

    def makeMove(self, position, player) :
        self._squares[position] = player
        self.showBoard()

    def complete(self) :
        # *** see above
        if "." not in self._squares.values() :
            return True
        if self.getWinner() != None :
            return True
        return False

    def getWinner(self) :
        for player in ("x", "o") :
            for combos in self._winningCombos :
                if self._squares[combos[0]] == player and self._squares[combos[1]] == player and self._squares[combos[2]] == player :
                    return player
        # *** see above
        if "." not in self._squares.values() :
            return "tie"
        return None

    def getEnemyPlayer(self, player) :
        if player == "x" :
            return "o"
        return "x"

    # *** no need for `node` argument, nor `first`
    # *** use `self` instead of `node` in all this method
    def minimax(self, player, depth = 0) :
        # *** not needed
        # if first :
            # best = 0
            # *** not needed
            # self._copySquares = deepcopy(self._squares)
        # *** always start with initilisation of `best`, but with worst possible value
        #     for this player
        if player == "o": 
            best = -10
        else:
            best = 10
        if self.complete() :
            if self.getWinner() == "x" :
                # *** don't do this, you may still need the position to try other moves 
                # self._squares = self._copySquares
                # *** value should be closer to zero for greater depth!
                # *** expect tuple return value
                return -10 + depth, None
            elif self.getWinner() == "tie" :
                # self._squares = self._copySquares
                # *** expect tuple return value
                return 0, None
            elif self.getWinner() == "o" :
                # self._squares = self._copySquares
                # *** value should be closer to zero for greater depth!
                # *** expect tuple return value
                return 10 - depth, None
            # *** Execution can never get here
            # best = None
        for move in self.getAvailableMoves() :
            # *** don't increase depth in each iteration, instead pass depth+1 to
            #    the recursive call
            # depth += 1
            self.makeMove(move, player)
            # *** pass depth+1, no need for passing `node` nor `first`.
            # *** expect tuple return value
            val, _ = self.minimax(self.getEnemyPlayer(player), depth+1)
            print(val)
            # *** undo last move
            self.makeMove(move, ".")
            if player == "o" :
                if val > best :
                    # *** Also keep track of the actual move
                    best, bestMove = val, move
            else :
                if val < best :
                    # *** Also keep track of the actual move
                    best, bestMove = val, move
            # *** don't interrupt the loop here!
            # return best
            # *** this is dead code:
            # print()
            # print()
        # *** Also keep track of the actual move
        return best, bestMove

    def printCopy(self) :
        print(self._copySquares)

      

        
        
        
      

    

Here's an example of how you would use the class:

game = TicTacToeBrain()
game.createBoard()
game.makeMove(4, "o")
game.makeMove(3, "x")
val, bestMove = game.minimax("o")
print('best move', bestMove) # --> 0 is a winning move.

      

        
        
        
      

    

See how it works for eval.in ... wait for it.

Some things you can still improve

I won't provide the code for this, but you could:

• Keep track of the move that is in self.player
  
  . This way, you don't need to pass the player as an argument to minimax, thus avoiding errors. It also makes the constructor argument useful - you are currently not doing anything with it.

• Add a method bestMove
  
  that will just call minimax
  
  , but only return the best result, not a value. It will be easier to manage.

• Use alpha-beta pruning to stop evaluating other moves when it becomes clear that you cannot improve on the value already reached in the recursion tree.