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.

Intelligent Snake

This is the final version of the snake game. I have implemented a* algorithm in the intelligent snake (it is much clever than the previous ones). There are three kinds of snakes. You can choose the color and start position of any snake yourself. The different types of snake are :

Human Snake

This is a human-controlled snake. It can be created by pressing ‘h’ during gameplay. You have to control the human snake from your keyboard .

Computer Snake

It is slightly intelligent snake. It is the remain of the previous version of the game. It can still play quite well. But, the algorithm is quite weak compared to the “intelligent snake”. You can create a computer snake by pressing “c” during gameplay.

Intelligent Snake

It is the most advanced snake of all. It uses a* algorithm to find it’s path to the food. If there is no path (like when the body of snake is forming a loop around the food and preventing itself from going towards food) then it will use the algorithm of “computer snake” to find it’s path until a clear route to the food is found.

 

Snake game version 3.0 screenshot
Snake game version 3.0 screenshot

All of the snakes can warp around the platform. The computer snake is aware of this, the human snake can be aware of this . But unfortunately, the intelligent snake is not aware of this. Anyway, it can survive about 20-40 foods in a 40×40 board. I will try to make the snake play a perfect game in later days. If you encountered any errors in the program, please contact me. I created the game using python 3.3 and pygame 1.9.2

You can view the sources file in it’s repository.

The Monty Hall Problem

The monty hall problem is a popular math probability puzzle. The game consist of three closed doors, two of which contain goat inside them and one contains a car (or anything precious). You are given a chance to select one of the three doors. After you make your selection, the host opens one of the doors from the two remaining doors and shows you a goat in that door. After this, should you change your selection?

It can seem a useless act to switch the door because it looks like 50/50 change of having car in any of the two doors. But actually, if you switch the door, your chance of winning the car increases to 66% while if you don’t switch the door, it will remain 33%. It can be clear from the image below.

The player has an equal chance of initially selecting the car, Goat A, or Goat B. Switching results in a win 2/3 of the time.
The player has an equal chance of initially selecting the car, Goat A, or Goat B. Switching results in a win 2/3 of the time.

This small python program simulates the monty hall problem. The greater number of times you play, the closer your success percentage will reach to 66.66%.

#!/usr/bin/python
from random import randrange

print "Monty Hall Simulator"
simnum = int(input("How many simulations to run?"))

changepoint = 0
nochangepoint = 0

for j in range(0, simnum):
    # generate a random number (1 to 3)
    a = randrange(1, 4)
    # choose a door
    choice = randrange(1, 4)
    # choose a door to show
    showdoor = randrange(1, 4)
    # the door we show must not be the door the player selected
    # or the door that contains the prize
    while showdoor == choice or showdoor == a:
        showdoor = randrange(1, 4)

    # second choice represent that the player chose another door
    secondchoice = 1
    while secondchoice == choice or secondchoice == showdoor:
        secondchoice = randrange(1, 4)
    # if the first choice was the winning door, add to nochangepoint. Else,
    # add to changepoint
    if a == choice:
        nochangepoint += 1
    else:
        changepoint += 1
print "In total ", simnum, " games, the player will win ", changepoint, " rounds if he switches the door. Else, he wins ", nochangepoint, " rounds"
print "In percentage, win rate is ", ((changepoint / (simnum*1.0)) * 100), " % for switching and ", ((nochangepoint / (simnum*1.0))*100), " % for not switching"

Snake game in python-2

Snake game version 2.0 screenshot
Snake game version 2.0 screenshot

I have updated the last snake game and made it multiplayer. You can choose any number of players – either human or computer. The computer just chooses the direction that will yield the shortest path for now. It doesnot detect loops or one way inlets….It just tries to reduce its path. I will soon implement A* algorithm for the snake. But for now, here is the code for the game.