JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

Othello/Reversi. Minimax AI

Introduction

Reversi or Othello is a strategy board game for two players (Black and White). It is played on an 8×8 uncheckered board. Players take turns placing disks on the board with their assigned color facing up.

During a play, any disks of the opponent’s player that are in a straight line and bounded by the disk just placed and another disk of the current player’s color are turned over to the current player’s color. Besides, each player must place its disc (let’s say the white disk) on the board in such a way that there is at least one straight (horizontal, vertical, or diagonal) occupied line between the new disc and another white disc, with one or more contiguous opponent pieces (black) between them. The objective of the game is to have the majority of disks showing one’s color when the last playable empty square is filled. Otello

Otello

Initial imports and constants

import random
import sys, pygame, configparser, copy, math
from pygame.locals import *

This code is inspired on Making Games with Python & Pygame, Flippy by Al Sweigart, [email protected], http://inventwithpython.com/pygame, Creative Commons BY-NC-SA 3.0 US and it is released under the same license.

BOARDWIDTH = 8 # Othello is played on an 8x8 uncheckered board. 
BOARDHEIGHT = 8 
WHITE_TILE = 'WHITE_TILE' # The "human" player will use white discs.
BLACK_TILE = 'BLACK_TILE' 
EMPTY_SPACE = 'EMPTY_SPACE'  
#              R    G    B
WHITE = (255, 255, 255)
BLACK = (0,   0,   0)
GREEN = (0, 155,   0)
BRIGHTBLUE = (0,  50, 255)
BROWN = (174,  94,   0)
LIGHTGREY = (211, 211, 211)
DARKGREY = (105, 105, 105)
GRAY = (185, 185, 185)

GRIDLINECOLOR = BLACK
BGCOLOR = GREEN

The Board

The Board class encapsulates a two-dimensional (8 x 8) array or matrix that represents Othello’s board.

class Board:
    def __init__(self):
        """ It creates a new board. BOARDWIDTH = BOARDHEIGHT = 8."""
        self.board = []
        for i in range(BOARDWIDTH):
            self.board.append([EMPTY_SPACE] * BOARDHEIGHT)

        self.animation = False
        self.tilesToAnimate = [(None, None)]
        self.start = None, None
 
     def initBoard(self):
        """ It initializes and sets up our board. """

        for x in range(BOARDWIDTH):
            for y in range(BOARDHEIGHT):
                self.board[x][y] = EMPTY_SPACE

        # It adds four starting pieces (two white and two black pieces) on the board's center.
        self.board[3][3] = WHITE_TILE
        self.board[3][4] = BLACK_TILE
        self.board[4][3] = BLACK_TILE
        self.board[4][4] = WHITE_TILE

    def draw(self, game):
        """ It draws our board."""
        for x in range(BOARDWIDTH):
            for y in range(BOARDHEIGHT):
                # If the tile is not one to be animated, we just draw it using the auxiliary drawBox method.
                if (x, y) not in self.tilesToAnimate and (self.board[x][y] == WHITE_TILE or self.board[x][y] == BLACK_TILE):
                    if self.board[x][y] == WHITE_TILE:
                        tileColor = WHITE
                        tileBorder = DARKGREY

                    else:
                        tileColor = BLACK
                        tileBorder = LIGHTGREY

                    self.drawBox(x, y, tileColor, tileBorder, game)
                # If the tile is one to be animated (it is in the "current" play or move), we draw the tile with its opposite color before the animation starts so the user can see more clearly that this one has been flipped.
                elif (x, y) in self.tilesToAnimate and (self.board[x][y] == WHITE_TILE or self.board[x][y] == BLACK_TILE):
                    if self.board[x][y] == WHITE_TILE:
                        tileColor = BLACK
                        tileBorder = LIGHTGREY
                    else:
                        tileColor = WHITE
                        tileBorder = DARKGREY

                    self.drawBox(x, y, tileColor, tileBorder, game)

        if self.animation == True: # This flag indicates that the animation should take place. 
            self.drawAnimation(game) 
            self.animation = False
            self.tilesToAnimate = [(None, None)]

    def drawBox(self, x, y, tileColor, tileBorder, game, animation=False):
        centerx, centery = game.translateBoardToPixelCoord(x, y) # It translates from board (x, y) to pixel coordinates (centerx, centery).

        # If there is no animation going on, we just draw two circles, so the tile (black/white) is drawn with a border (light grey/dark grey).
        if not animation:
            pygame.draw.circle(game.screen, tileBorder, (centerx, centery), int(game.SQUARESIZE / 2) - 1)
            pygame.draw.circle(game.screen, tileColor, (centerx, centery), int(game.SQUARESIZE / 2) - 4)

        else: # It implements the flipping of the disk/tile (coin).
            coin = pygame.Surface( (int(game.SQUARESIZE), int(game.SQUARESIZE)), pygame.SRCALPHA)
            pygame.draw.circle(coin, tileBorder, (int(game.SQUARESIZE/2), int(game.SQUARESIZE/2)), int(game.SQUARESIZE / 2) - 1)
            pygame.draw.circle(coin, tileColor, (int(game.SQUARESIZE/2), int(game.SQUARESIZE/2)), int(game.SQUARESIZE / 2) - 4)
            coin_rect = coin.get_rect(center=(centerx, centery))
            angle = 0
            for angle in range(0, 360, 18):
                new_width = round( math.sin(angle) * coin_rect.width) # It takes values in the interval [-coin_rect.width, coin_rect.width]
                rot_coin = pygame.transform.flip(coin, True, False) # It flips the coin ...
                rot_coin = pygame.transform.scale(rot_coin, (abs(new_width), coin_rect.height)) # ... and it also resizes the coin (more specifically its width) to create the desired animation.
                game.screen.blit(rot_coin, rot_coin.get_rect(center=coin_rect.center))
                game.fpsClock.tick(game.fps*3)
                pygame.display.flip()
            # We finish the animation by drawing the tile's two circles.
            pygame.draw.circle(game.screen, tileBorder,
                               (centerx, centery), int(game.SQUARESIZE / 2) - 1)
            pygame.draw.circle(game.screen, tileColor,
                               (centerx, centery), int(game.SQUARESIZE / 2) - 4)
Programming Otello

Programming Otello

    def isValidMove(self, player, xstart, ystart):
    """ It returns all the tiles to be flipped if (xstart, ystart) is a valid move for "player". Otherwise, it returns False (it means that there are no tiles to flip)."""
        if xstart == None or ystart == None: 
            return False

        if self.board[xstart][ystart] != EMPTY_SPACE or not Board.isOnBoard(xstart, ystart):
        # The position should be empty and it should be a valid position on the board (0..7 x 0..7)
            return False

        if player == 'player':
            tile = WHITE_TILE
            otherTile = BLACK_TILE
        else:
            tile = BLACK_TILE
            otherTile = WHITE_TILE

        # It sets the tile temporarily on the board.
        self.board[xstart][ystart] = tile

        tilesToFlip = []
        # Let's check or iterate on each of the eight directions.
        for xdirection, ydirection in [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]:
            x, y = xstart, ystart
            x += xdirection
            y += ydirection
            if Board.isOnBoard(x, y) and self.board[x][y] == otherTile:
                # If the piece (x, y) belongs to the other player,
                x += xdirection # we continue searching in the same direction.
                y += ydirection
                if not Board.isOnBoard(x, y): # We break the loop because the position is not on the board. In other words, we could not find one of the player's tiles. 
                    continue

                while self.board[x][y] == otherTile: # As long as there are opposite player's pieces in this direction (xdirection, ydirection), it could be a valid move.
                    x += xdirection
                    y += ydirection
                    if not Board.isOnBoard(x, y): # It breaks out the while loop, we could not find one of the player's tiles, but a board's edge instead.
                        break 
                if not Board.isOnBoard(x, y): # There are two possible reasons why the while loop was broken. The first one is that we have reached an out-of-limits position.
                    continue
                if self.board[x][y] == tile: # The second possible explanation is that we have found one of the player's pieces. The algorithm goes in the reverse direction until we reach the original position (xstart, ystart) and saves all the tiles on tilesToFlip along the way.
                    while True:
                        x -= xdirection
                        y -= ydirection

                        if x == xstart and y == ystart:
                            break

                        tilesToFlip.append((x, y))

        self.board[xstart][ystart] = EMPTY_SPACE
        if len(tilesToFlip) == 0:  # If no tiles are to be flipped, this move is not valid.
            return False

        return tilesToFlip
Programming Otello

Programming Otello

    def getValidMoves(self, player):
        """ It returns a list of (x,y) tuples with all valid moves."""
        validMoves = []

        for x in range(BOARDWIDTH):
            for y in range(BOARDHEIGHT):
                if self.isValidMove(player, x, y) != False:
                    validMoves.append((x, y))

        return validMoves

    @staticmethod
    def isOnCorner(x, y):
        """ It returns True if the position (x, y) is in one of the four corners."""
        return (x == 0 and y == 0) or \
            (x == BOARDWIDTH-1 and y == 0) or \
            (x == 0 and y == BOARDHEIGHT-1) or \
            (x == BOARDWIDTH-1 and y == BOARDHEIGHT-1)

    @staticmethod
    def isOnBoard(x, y):
        """ It returns True if the position is on the board."""
        return x >= 0 and x < BOARDWIDTH and y >= 0 and y < BOARDHEIGHT

    def makeMove(self, player, xstart, ystart, animation=True):
        """ It implements the move. It places the tile on the board (xstart, ystart) and flips the corresponding opponent's tiles."""
        tilesToFlip = self.isValidMove(player, xstart, ystart)

        if tilesToFlip == False: # It returns False if this move is an invalid one (there are no tiles to flip).
            return False

        if player == 'player':
            tile = WHITE_TILE
        else:
            tile = BLACK_TILE

        if animation == True: # The user can select whether (s)he wants an animation or not. If (s)he wants an animation, we need to set the "self.animation" flag to True and add the current move (or tile) to the list with the opponent's captured tiles to be flipped.
            self.animation = True
            self.tilesToAnimate = tilesToFlip
            self.tilesToAnimate.append((xstart, ystart))

        # Finally, we make the move and update the board's state. 
        for x, y in self.tilesToAnimate:
            self.board[x][y] = tile

        return True

    def getComputerMove(self):
        # It determines where the computer should move."""

        possibleMoves = self.getValidMoves('computer')
        bestMove = None
        # It goes through all possible moves and saves the best scoring move.
        bestScore = -30

        for x, y in possibleMoves:
            copyBoard = copy.deepcopy(self)
            copyBoard.makeMove('computer', x, y)
            #_, computerScore = copyBoard.getScoreOfBoard() # This is one option. The computer selects the movement that maximizes the number of its pieces.  
            computerScore = copyBoard.getScoreOfBoard2('computer') # We use a heuristic function. It is based on [John Fish's Othello](https://github.com/johnafish/othello/blob/master/othello.py).

            if computerScore > bestScore:
                bestMove = [x, y]
                bestScore = computerScore

        return bestMove

    def getScoreOfBoard(self):
        # It calculates the game's score by counting the computer and the player's tiles.
        playerScore = 0
        computerScore = 0

        for x in range(BOARDWIDTH):
            for y in range(BOARDHEIGHT):
                if self.board[x][y] == WHITE_TILE:
                    playerScore += 1
                if self.board[x][y] == BLACK_TILE:
                    computerScore += 1

        return playerScore, computerScore

    def getScoreOfBoard2(self, player):
        # It helps to discern the player's best chance by using a heuristic function. It is based on [John Fish's Othello](https://github.com/johnafish/othello/blob/master/othello.py).
        cornerValue = 25
        adjacentValue = 5
        sideValue = 3
        score = 0

        if player == 'computer':
            colour = BLACK_TILE
            opponent = WHITE_TILE
        else:
            colour = WHITE_TILE
            opponent = BLACK_TILE

        for x in range(BOARDWIDTH):
            for y in range(BOARDHEIGHT):
                # Normal tiles are worth one point.
                add = 1
                # Adjacent to corners are worth -5 (if the corner does not belong to the player) or 3 points.
                if (x == 0 and y == 1) or (x == 1 and 0 <= y <= 1):
                    if self.board[0][0] == colour:
                        add = sideValue
                    else:
                        add = -adjacentValue
                elif (x == 0 and y == 6) or (x == 1 and 6 <= y <= 7):
                    if self.board[7][0] == colour:
                        add = sideValue
                    else:
                        add = -adjacentValue
                elif (x == 7 and y == 1) or (x == 6 and 0 <= y <= 1):
                    if self.board[0][7] == colour:
                        add = sideValue
                    else:
                        add = -adjacentValue
                elif (x == 7 and y == 6) or (x == 6 and 6 <= y <= 7):
                    if self.board[7][7] == colour:
                        add = sideValue
                    else:
                        add = -adjacentValue

                # Edge tiles are worth three points.
                elif (x == 0 and 1 < y < 6) or (x == 7 and 1 < y < 6) or (y == 0 and 1 < x < 6) or (y == 7 and 1 < x < 6):
                    add = sideValue

                # Corner tiles are worth 15 points.
                elif Board.isOnCorner(x, y):
                    add = cornerValue
                
                # Finally, it adds or subtracts the tile's value.
                if self.board[x][y] == colour:
                    score += add
                elif self.board[x][y] == opponent:
                    score -= add

        return score

The Game class

class Game:  # It represents the game itself
    def __init__(self):
        self.running = True # It indicates that the game is still running.
        pygame.init()  # It initializes all imported pygame modules.
        self.fpsClock = pygame.time.Clock() # A pygame.time.Clock object helps us to make sure our program runs at a certain FPS.

We will use the ConfigParser module to manage a user-editable configuration file for our application. It provides a structure similar to what’s found in Microsoft Windows INI files. Our config file othello.ini is quite simple:

[BASIC] # The file consists of sections, each of which contains keys with values. 
WINDOWWIDTH = 1280 
WINDOWHEIGHT = 800 
SQUARESIZE = 70 
FPS = 30
ANIMATION=True
        self.config = configparser.ConfigParser() # We create an instance of the main configuration parser.
        self.config.read("flippy.ini") # We read the configuration file.
        self.fps = int(self.config['BASIC']['FPS']) # This is our frame rate. It is expressed in frames per second or FPS. It is the frequency or rate at which consecutive images or frames are captured or displayed in the game.
        self.animation = self.config.getboolean('BASIC', 'ANIMATION') # The user can select whether (s)he wants an animation or not.
        self.font = pygame.font.Font("resources/CHERI.TTF", 30) # pygame.font.Font allows us to render fonts in the game.
        self.bigfont = pygame.font.Font("resources/CHERL.TTF", 50)
        self.WINDOWWIDTH = int(self.config['BASIC']['WINDOWWIDTH']) 
        self.SQUARESIZE = int(self.config['BASIC']['SQUARESIZE'])
        self.WINDOWHEIGHT = int(self.config['BASIC']['WINDOWHEIGHT'])
        # It sets the display mode and creates an instance of the pygame.Surface class.
        self.screen = pygame.display.set_mode((self.WINDOWWIDTH, self.WINDOWHEIGHT))
        pygame.display.set_caption('Othello') # It sets the current window tittle.

        self.XMARGIN = int( (self.WINDOWWIDTH - BOARDWIDTH * self.SQUARESIZE) / 2) # XMARGIN + BOARDWIDTH * SQUARESIZE + XMARGIN = WINDOWWIDTH. 
        self.YMARGIN = int( (self.WINDOWHEIGHT - (BOARDHEIGHT * self.SQUARESIZE)) / 2)

        self.board = Board() # It is an instance of our Board class.
        self.boardImage = pygame.image.load('boardImage.png') # It sets up an image for the game's board.
        self.boardImage = pygame.transform.smoothscale( self.boardImage, (BOARDWIDTH * self.SQUARESIZE, BOARDHEIGHT * self.SQUARESIZE)) # It uses pygame.transform.smoothscale() to stretch the board image to fit the entire board.
        boardImageRect = self.boardImage.get_rect() # It gets the rectangular area of the surface.
        boardImageRect.topleft = (self.XMARGIN, self.YMARGIN) # It places the board image in the right place. 
        
        self.backgroundImage = pygame.image.load('background.png') # It sets up an image for the game's background.
        self.backgroundImage = pygame.transform.smoothscale(self.backgroundImage, (self.WINDOWWIDTH, self.WINDOWHEIGHT)) # It uses pygame.transform.smoothscale() to stretch the background image to fit the entire window.
        self.backgroundImage.blit(self.boardImage, boardImageRect) # It draws the board image on top of the game's background.
        self.MOUSEBUTTONUP = self.KEYUP = False
        self.turn = 'player'

    def endGame(self):
    """ If the game is over (there are no valid moves left for the current player) returns True, otherwise it returns False.""" 
        return self.board.getValidMoves(self.turn) == []

This is just one implementation. In Reversi if one player cannot play a piece, the game finishes. In Othello, a player without a move simply passes, and the other player keeps playing pieces until the first player can make a move again.

The method game_loop controls the overall flow for the entire game program. There are three tasks: _1. Check all events. 2. Process these events and take action accordingly. 3. Draw the current state of the game so the player can see what is going on.

    def gameLoop(self):
        self.board.initBoard() # It initializes our board.
        while self.running: # It loops while the game is still running.
          self.check_events() # It checks all the events.

          if self.turn == 'player': # If it is the player's turn to move and he clicks the mouse button.
                if self.MOUSEBUTTONUP:
                  movex, movey = self.getSquareClicked(self.pos[0], self.pos[1]) # It returns _the mouse position in board coordinates_ (coordinates referring to the board) or (None, None).

                  # If the move is a valid one, it makes the move and gives the turn to the computer. 
                  if self.board.isValidMove(self.turn, movex, movey):
                      self.board.makeMove(self.turn, movex, movey, self.animation)
                      self.turn = 'computer'

                      if self.endGame(): # It checks if the game is over or not. 
                          self.running = False
                          self.showEndScreen()
                          sys.exit()

          else: # If it is the computer's turn, it decides where the computer should move (getComputerMove), makes the move, and gives the turn to the player.
              x, y = self.board.getComputerMove()
              self.board.makeMove(self.turn, x, y, self.animation)
              self.turn = 'player'

              if self.endGame(): # It checks if the game is over or not.
                  self.running = False
                  self.showEndScreen()
                  sys.exit()

          self.drawGame() # Finally, we draw the current state of the game.
          self.reset_keys()  # We reset the keys as we have already processed the key's associated event.

    def showEndScreen(self):
    """ It shows the end screen."""
        playerScore, computerScore = self.board.getScoreOfBoard()
        if playerScore < computerScore:
            self.showTextScreen("Computer wins!", "Player score: %s. Computer's score: %s" % (playerScore, computerScore))
        elif playerScore == computerScore:
            self.showTextScreen("It is a tie!", "Player's score: %s. Computer's score: %s" % (playerScore, computerScore))
        else:
            self.showTextScreen("Player wins!", "Player's score: %s. Computer's score: %s" % (playerScore, computerScore))

    def showTextScreen(self, text1, text2):
     """ It draws "text1" and "text2" with a big font, the "Press a key to play" text with a normal font, and it waits until the user presses a key."""
        self.screen.fill(BGCOLOR)
        self.drawText(text1, self.bigfont, int(self.WINDOWWIDTH / 7), int(self.WINDOWHEIGHT / 4))
        self.drawText(text2, self.bigfont, int(self.WINDOWWIDTH / 7), int(self.WINDOWHEIGHT / 4) + 100)
        self.drawText('Press a key to go.', self.font, int(self.WINDOWWIDTH / 7), int(self.WINDOWHEIGHT / 4) + 250)
        self.reset_keys()

        while not self.KEYUP:
            self.check_events()
            pygame.display.update()
            self.fpsClock.tick()

    def getSquareClicked(self, mousex, mousey):
    """ It returns the board coordinates where the mouse was clicked or (None, None)."""
        
        for x in range(BOARDWIDTH):
            for y in range(BOARDHEIGHT):
                if mousex > x * self.SQUARESIZE + self.XMARGIN and mousex < (x + 1) * self.SQUARESIZE + self.XMARGIN and mousey > y * self.SQUARESIZE + self.YMARGIN and mousey < (y + 1) * self.SQUARESIZE + self.YMARGIN:
                    return (x, y)

        return (None, None)

    def drawGame(self):
    """ It draws the current state of the game."""
        self.screen.blit(self.backgroundImage, self.backgroundImage.get_rect()) # It fills the screen with the background image so we can start from scratch.

        # It draws the grid lines of the board.
        for x in range(BOARDWIDTH + 1): # It draws the horizontal grid lines.
            startx = (x * self.SQUARESIZE) + self.XMARGIN
            starty = self.YMARGIN
            endx = (x * self.SQUARESIZE) + self.XMARGIN
            endy = self.YMARGIN + (BOARDHEIGHT * self.SQUARESIZE)
            pygame.draw.line(self.screen, GRIDLINECOLOR, (startx, starty), (endx, endy))

        for y in range(BOARDHEIGHT + 1): # It draws the vertical grid lines.
            startx = self.XMARGIN
            starty = (y * self.SQUARESIZE) + self.YMARGIN
            endx = self.XMARGIN + (BOARDWIDTH * self.SQUARESIZE)
            endy = (y * self.SQUARESIZE) + self.YMARGIN
            pygame.draw.line(self.screen, GRIDLINECOLOR, (startx, starty), (endx, endy))

        self.board.draw(self) # It draws the board.
        playerScore, computerScore = self.board.getScoreOfBoard() # It gets the game's score.
        self.drawText("Player's score: %s. Computer's score: %s" % (playerScore, computerScore), self.font, self.XMARGIN, 20) # It draws the game's score.

        pygame.display.update() # It updates the full display surface to the screen.

    def drawText(self, text, font, x, y):
    """ It draws "text" using the font passed as an argument with a shadow."""
        textSurf = font.render(text, True, GRAY)
        textRect = textSurf.get_rect()
        textRect.topleft = (x, y)
        self.screen.blit(textSurf, textRect)
        textSurf = font.render(text, True, WHITE)
        textRect = textSurf.get_rect()
        textRect.topleft = (x-3, y-3)
        self.screen.blit(textSurf, textRect)

    def check_events(self): # Pygame handles all its event messaging through an event queue. This method checks all these events.
        for event in pygame.event.get():  # It gets events from the queue.
            if event.type == pygame.QUIT:
                self.running = False
                sys.exit()
            if event.type == MOUSEBUTTONUP:
                self.MOUSEBUTTONUP = True
                self.pos = event.pos # event.pos is a tuple that stores the position that was clicked.
            if event.type == KEYUP:
                self.KEYUP = True

    def reset_keys(self):  # It reset all the keys.
        self.MOUSEBUTTONUP = False
        self.KEYUP = False

    def translateBoardToPixelCoord(self, x, y):
    """ It translates from board (x, y) to pixel coordinates."""
        return self.XMARGIN + x * self.SQUARESIZE + int(self.SQUARESIZE / 2), self.YMARGIN + y * self.SQUARESIZE + int(self.SQUARESIZE / 2)

if __name__ == '__main__':
    game = Game() # The main function is quite simple. We create an instance of our Game class.
    game.gameLoop()  # We call the game's game_loop function.

The minimax algorithm

A minimax algorithm is a recursive algorithm for choosing the next move in a game. At each step it assumes that the player (or AI) is trying to maximize his chances of winning, while on the next turn AI (or the player) is trying to minimize his opponent’s chances of winning. We use a rule that if the result of a move is an immediate win for AI, then it would be assigned positive infinity as a score and if it is an immediate win for the player, negative infinity. Our AI is called the maximizing player and the player, the minimizing player.

The minimax function returns a heuristic value for all the leaf nodes, i.e., terminal nodes and nodes at the maximum search depth.

    def is_terminal_node(self): # It returns True if the node is terminal.
        return self.winning_move(PLAYER_PIECE) or self.winning_move(AI_PIECE) or self.is_full()

function  minimax(node, depth, maximizingPlayer) # This is extracted from Wikipedia.
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth  1, FALSE))
            # If the node belongs to the AI player, we take its children's maximum value because he wants to make his final score as high as possible since the AI player always wants to win.
        return value
    else (* minimizing player *)
        value := +
        for each child of node do
            value := min(value, minimax(child, depth  1, TRUE))
        # If the internal node belongs to the human player, we take its children's minimum value because the player wants to make our AI's final score as low as possible.
        return value
Minimax algorithm

Minimax algorithm

The problem is that it takes a very long time to process the entire tree. Alpha-beta pruning seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It prunes away branches that cannot possibly influence the final decision.

We define two variables: alpha is the best already explored option along the path to the root for the maximizer (AI). Beta is the best already explored option along the path to the root for the minimizer.

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)
function alphabeta(node, depth, α, β, maximizingPlayer) # This is extracted from Wikipedia.
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then # If the maximizingPlayer (AI) finds a value that is higher than its current beta, it can discard the entire subtree because it is sure that his optimal path will not go through this. 
                break (* β cutoff *)
            α := max(α, value) # If the maximizingPlayer (AI) finds a value that is higher than alpha, it updates alpha.
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then # If the miximizingPlayer (player) finds a value that is lower than its current alpha, it can discard the entire subtree because it is sure that his optimal path will not go through this. 
                break (* α cutoff *)
            β := min(β, value)
        return value
Minimax Algorithm

Minimax Algorithm

Observe that as soon as the minimizer saw the 4 (node F; alpha=5, beta=4), he knew that the maximizer would never come this way because the maximizer was guaranteed a value of 5 or more (alpha=5), he can get a 5 on the left side (E).

def minimax(self, depth, alpha, beta, maximizingPlayer): # This is a method of the Board's class.
    possibleMoves = self.getValidMoves(maximizingPlayer) # It explores the nodes of a game tree. The branching factor of the tree is the number of children of each node (getValidMoves(maximizingPlayer)).
    bestMovex = bestMovey = None

    if depth == 0 or possibleMoves == []: # If depth is zero or it is a terminal node.
          if possibleMoves == []: # Game is over, no more valid moves.
              playerScore, computerScore = self.getScoreOfBoard()
              if computerScore > playerScore:
                  return (None, None, 1000000)
              elif computerScore < playerScore:
                  return (None, None, -1000000)
              else:
                  return (None, None, 0)
          else: # Depth is zero. We return the board's evaluation.
              return (None, None, self.getScoreOfBoard2('computer'))

    if maximizingPlayer == 'computer': # Maximizing player, our AI
          value = -1000000
          for x, y in possibleMoves:
              copyBoard = copy.deepcopy(self)
              copyBoard.makeMove('computer', x, y)
              _, _, new_score = copyBoard.minimax(depth-1, alpha, beta, 'player')
              alpha = max(alpha, new_score) # The maximizing player updates alpha.

              if new_score > value:
                  value = new_score
                  bestMovex = x
                  bestMovey = y

              if alpha >= beta:
                 break

Think about it, alpha and beta represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively.

Whenever the maximum score that the minimizing player (i.e. the “human” player, “beta”) is assured of becomes less than the minimum score that the maximizing player (i.e., the “computer”, “alpha”) is assured of (i.e. beta < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in the actual play.

          return bestMovex, bestMovey, value
      else:
          value = 1000000

          for x, y in possibleMoves:
              copyBoard = copy.deepcopy(self)
              copyBoard.makeMove('computer', x, y)
              _, _, new_score = copyBoard.minimax(depth-1, alpha, beta, 'player')
              
              beta = min(beta, value) # The minimizing player updates beta.
              if new_score < value:
                  value = new_score
                  bestMovex = x
                  bestMovey = y

              if alpha >= beta:
                  break

          return bestMovex, bestMovey, value

 def gameLoop(self):
[...]
        while self.running:
            self.check_events()     
            if self.turn == 'player':
            [...]
            else:
                x, y, _ = self.board.minimax(4, -math.inf, math.inf, 'computer')
                self.board.makeMove(self.turn, x, y, self.animation)
                self.turn = 'player'
                [...]
Bitcoin donation

JustToThePoint Copyright © 2011 - 2022 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.