Tic Tac Toe with AI (MinMax and alpha-beta pruning)

Tic Tac Toe game

This is a simple tic-tac-toe application with AI using minmax algorithm along with alpha-beta pruning. The game is made in python using pygame. The first step to create the game is to make a basic framework to allow two human players to play against each other. The initial game can be found here. In this version, only two human players can compete with each other.

Next step is to add minmax algorithm to the computer player. The source code can be found here. The ComputerPlayer class with minmax algorithm is

class ComputerPlayer(Player):
    '''Computer player class. '''
    
    def __init__(self,sign,name):
        super().__init__(computer,sign,name)#computer player
        self.lastmove=-1

    def GetMove(self):
        '''Returns the next move. Computer player uses minmax algorithm
        to determine the next move'''
        self.loop = 0
        val,move = self.MaxValue()
        print(self.loop," moves")
        return move
    def GetScore(self):
        '''Utility function for determining the numerical value of terminal condition.
        Called in game over condition'''
        if self.board.Draw():
            return 0
        elif self.board.GetWinner() == self.sign:
            return 1
        return -1 #the other player won
    
    def MaxValue(self):
        '''maxvalue returns the maximized score and position for the player's move'''
        maxpos = None
        maxval = -9

        for move in self.board.getFreePositions():
            self.loop+=1
            self.board.Move(move,self.sign)

            if self.board.GameOver():
                newval = self.GetScore()
            else:
                newval,movepos = self.MinValue()

            self.board.UndoMove()

            if newval > maxval:
                maxval = newval
                maxpos = move

        return maxval,maxpos
    
    def MinValue(self):
        '''minvalue returns the minimized score and position for the opponent's move'''
        minpos = None
        minval = 9

        for move in self.board.getFreePositions():
            self.loop+=1
            self.board.Move(move,self.OppositeSign(self.sign))

            if self.board.GameOver():
                newval = self.GetScore()
            else:
                newval,movepos = self.MaxValue()

            self.board.UndoMove()

            if newval < minval:
                minval = newval
                minpos = move

        return minval,minpos

With only minmax algorithm, the computer takes about 3 seconds to make it’s first move (in my computer). The total number of moves analyzed by the computer is recorded in a variable. If the computer starts the game, it analyzes 549945 positions in the first move.

It can be improved by using alpha-beta pruning. The ComputerPlayer code that implements alpha beta pruning is as below.

class ComputerPlayer(Player):
    '''Computer player class. '''
    
    def __init__(self,sign,name):
        super().__init__(computer,sign,name)#computer player
        self.lastmove=-1

    def GetMove(self):
        '''Returns the next move. Computer player uses minmax algorithm
        to determine the next move'''
        self.loop = 0
        val,move = self.MaxValue(-9,9)
        print(self.loop," moves")
        return move

    def GetScore(self):
        '''Utility function for determining the numerical value of terminal condition.
        Called in game over condition'''
        if self.board.Draw():
            return 0
        elif self.board.GetWinner() == self.sign:
            return 1
        return -1 #the other player won
    
    def MaxValue(self,alpha,beta):
        '''maxvalue returns the maximized score and position for the player's move'''
        maxpos = None
        maxval = -9

        for move in self.board.getFreePositions():
            self.loop+=1
            self.board.Move(move,self.sign)

            if self.board.GameOver():
                newval = self.GetScore()
            else:
                newval,movepos = self.MinValue(alpha,beta)

            self.board.UndoMove()

            if newval > beta:
                return newval,move
            if newval > alpha:
                alpha = newval

            if newval > maxval:
                maxval = newval
                maxpos = move

        return maxval,maxpos
    
    def MinValue(self,alpha,beta):
        '''minvalue returns the minimized score and position for the opponent's move'''
        minpos = None
        minval = 9

        for move in self.board.getFreePositions():
            self.loop+=1
            self.board.Move(move,self.OppositeSign(self.sign))

            if self.board.GameOver():
                newval = self.GetScore()
            else:
                newval,movepos = self.MaxValue(alpha,beta)

            self.board.UndoMove()

            if newval < alpha:
                return newval,move
            if newval < beta:
                beta = newval

            if newval < minval:
                minval = newval
                minpos = move

        return minval,minpos

With alpha beta pruning, the total number of moves analyzed in the first step reduces to 146119 from previous 549945 moves.

One quick optimization that we can implement is to hard code the first move so that the computer always places it’s first move in a predefined position. Also, we can implement another optimization : We can stop searching for better moves once a win state is reached. i.e Once we get 1 in MaxVal function or -1 in MinVal function, we can stop searching for better or worse conditions. The second optimization again reduces the total number of moves analyzed in the first step from the previous 146119 moves to 94977 moves. The implementation of the above optimizations are :

class ComputerPlayer(Player):
    '''Computer player class. '''
    
    def __init__(self,sign,name):
        super().__init__(computer,sign,name)#computer player
        self.lastmove=-1

    def GetMove(self):
        '''Returns the next move. Computer player uses minmax algorithm
        to determine the next move'''
        possiblemoves = [mv for mv in self.board.possiblecells if not mv in self.board.moves]
        #just a minor optimization : if it is the first move, always place in the center
        if len(possiblemoves) == 9:
            return (1,1)
        self.maxdepth = 100
        self.loop = 0
        val,move = self.MaxValue(-9,9)
        print(self.loop," moves")
        return move

    def GetScore(self):
        '''Utility function for determining the numerical value of terminal condition.
        Called in game over condition'''
        if self.board.Draw():
            return 0
        elif self.board.GetWinner() == self.sign:
            return 1
        return -1 #the other player won
    
    def MaxValue(self,alpha,beta):
        '''maxvalue returns the maximized score and position for the player's move'''
        maxpos = None
        maxval = -9

        for move in self.board.getFreePositions():
            self.loop+=1
            self.board.Move(move,self.sign)

            if self.board.GameOver():
                newval = self.GetScore()
            else:
                newval,movepos = self.MinValue(alpha,beta)

            self.board.UndoMove()

            if newval > beta:
                return newval,move
            if newval > alpha:
                alpha = newval

            if newval > maxval:
                maxval = newval
                maxpos = move
            if newval == 1:
                break;

        return maxval,maxpos
    
    def MinValue(self,alpha,beta):
        '''minvalue returns the minimized score and position for the opponent's move'''
        minpos = None
        minval = 9

        for move in self.board.getFreePositions():
            self.loop+=1
            self.board.Move(move,self.OppositeSign(self.sign))

            if self.board.GameOver():
                newval = self.GetScore()
            else:
                newval,movepos = self.MaxValue(alpha,beta)

            self.board.UndoMove()

            if newval < alpha:
                return newval,move
            if newval < beta:
                beta = newval

            if newval < minval:
                minval = newval
                minpos = move
            if newval == -1:
                break;

        return minval,minpos

The final game can be found here.

Leave a Reply

avatar
  Subscribe  
Notify of