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.
