Minimax algorithm for Tic Tac Toe Python

Question

I kind of understand how the minimax algorithm works for Tic Tac Toe python but I have no idea how to actually code it in Python... this is what I have so far:

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) :
            self._squares[i] = None
        print(self._squares)

    def showBoard(self) :
        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) :
            if self._squares[i] == None :
                self._availableMoves.append(i)
        return self._availableMoves

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

    def complete(self) :
        if None 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
        if None not in self._squares.values() :
            return "tie"
        return None

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

    def minimax(self, node, player, depth = 0, first = True) :
        if first :
            best = 0
            self._copySquares = deepcopy(self._squares)

        if node.complete() :
            if node.getWinner() == "x" :
                self._squares = self._copySquares
                return -1 - depth
            elif node.getWinner() == "tie" :
                self._squares = self._copySquares
                return 0
            elif node.getWinner() == "o" :
                self._squares = self._copySquares
                return 1 + depth
            best = None
        for move in node.getAvailableMoves() :
            depth += 1
            node.makeMove(move, player)
            print()
            val = self.minimax(node, node.getEnemyPlayer(player), depth, first = False)
            print(val)
            if player == "o" :
                if val > best :
                    best = val
            else :
                if val < best :
                    best = val
            return best
            print()
            print()

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

However, it never prints out all the scenarios....someone please help !!! This is due for a project on Monday..

Answer 1

Some issues:

• Execution breaks out of the for loop with a return at the first iteration: this is premature, as you never get to test any of the other available moves. That return should happen after the loop.

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

• The move done before the recursive call, must be taken back right after it, otherwise the next iteration of the for loop will not start from the same position.

• The value for best needs to be initialised at every call of the minimax method, not only 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. So you need to initialise it to an extreme bad value.

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

Some non-critical issues:

• As you want to delay an inevitable loss, or speed-up a forced win, the formula for calculating the value when a player wins should get closer to 0 the further away it is, not the closer it is. So a change is needed in that formula.

• Since you should restore the board by taking back moves, there is no need to work with a duplicated board, and duplicated squares. If all is coded well, after the top call of the minimax method has completed, the board should be in exactly the same state as it was before that call.

• The board prints better when you don't use None for empty squares, but a single character, like a ".". So everywhere where you refer to empty square values, put that character.

• You have print() here and there in order to separate the output. Put one in the method showBoard, and the rest of your code can do without them.

• Given some of the above points, you don't need the node nor the first parameter to the minimax method.

Here is a commented, corrected version. I left your original lines in place, but commented them out where needed.

# *** 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 is an example on 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 it run on eval.in... wait for it.

Some things you could still improve

I will not provide the code for this, but you could:

• Keep track whose turn it is in self.player. That way you don't have to pass the player as argument to minimax, which will avoid mistakes. Also it makes the constructor argument useful -- currently you don't do anything with it.

• Add a method bestMove that will simply call minimax, but will only return the best move, not the value. That will be easier to manage.

• Use alpha-beta pruning, so that you stop evaluating other moves, when it is clear you cannot improve the value already achieved up in the recursion tree.