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.