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

Checkers in Python with Pygame. Minimax algorithm.

Introduction

Checkers is a classic board game for two players. One player has the dark pieces; the other has the light pieces. Players alternate turns. A move consists of moving a piece diagonally to an adjacent unoccupied square. If the adjacent square contains an opponent’s piece, and the square immediately beyond it is vacant, the piece may be captured and removed from the game by jumping over it.

There is a basic rule in Checkers that if you can jump or capture an opponent piece then you must.

The game’s main objective is to capture every opponent’s piece. When a piece reaches the king’s row (the farthest row forward), it becomes a king and is marked or crowned by placing an additional piece on top. From now on, it can move backward and forward any distance along unblocked diagonals, but only in a diagonal direction, and may capture an opposing piece any distance away by jumping to any of the unoccupied squares immediately beyond it. Checkers is a classic board game for two players

Checkers is a classic board game for two players

The Piece class

import random # Initial imports and constants
import sys
import pygame
import configparser
import math
from pygame.locals import *
from rich import print
from copy import deepcopy

BOARDWIDTH = 8 # Checkers is played on an 8x8 uncheckered board.
BOARDHEIGHT = 8  
EMPTY_SPACE = 'EMPTY_SPACE' 
SQUARESIZE = 100
#              R    G    B
WHITE = (255, 255, 255)
BLACK = (0,   0,   0)
LIGHTBROWN = (200, 157, 124)
DARKBROWN = (78, 53, 36)
DARKGREY = (105, 105, 105)
GRAY = (185, 185, 185)
RED = (255,  0,   0)
BGCOLOR = GRAY
CROWN = pygame.transform.scale(
    pygame.image.load('resources/crown.png'), (44, 25))

class Piece: # It is the class that represents the game's pieces.
    def __init__(self,  col, row, color):
        self.row = row # The piece's board coordinates (row, col)
        self.col = col
        self.color = color # The piece's color (Player is WHITE, Computer is BLACK).
        self.selected = False # It indicates if the piece has been selected or not.
        self.king = False # There are two kinds of pieces in Checkers: men and kings.
        self.pixelRow = 0 # The piece's pixel coordinates (pixelRow, pixelCol)
        self.pixelCol = 0
        self.value = 0 # The piece's value.
        self.update()

    def update(self): 
    """ It updates the Piece's state."""
        self.translateBoardToPixelCoord() # It updates the piece's pixel coordinates.

        if self.king: # It updates the piece's value. 
            self.value = 7
        else:
            self.value = 1

        if self.color == WHITE: # White pieces have negative values.
            self.value = -self.value

    def makeKing(self):
    """ If the piece is crowned king, it needs to update its state."""
        self.king = True
        self.update()

    def draw(self, screen):
    """ It draws the piece in the screen surface."""
        if self.selected: # If the piece is selected, we draw an outer red circle around it.
            pygame.draw.circle(
                screen, RED, (self.pixelCol, self.pixelRow), SQUARESIZE//2-12)
        elif self.color == BLACK: # Every piece is drawn using two circles. The outer circle forms the border.
            pygame.draw.circle(
                screen, GRAY, (self.pixelCol, self.pixelRow), SQUARESIZE//2-12)
        elif self.color == WHITE:
            pygame.draw.circle(
                screen, BLACK, (self.pixelCol, self.pixelRow), SQUARESIZE//2-12)
        pygame.draw.circle(
            screen, self.color, (self.pixelCol, self.pixelRow), SQUARESIZE//2-15)
        if self.king: # If it is a king, we draw a picture of a crown on top of it.
            screen.blit(CROWN, (self.pixelCol - CROWN.get_width() //
                        2, self.pixelRow-CROWN.get_height()//2))

    def drawAnimation(self, game):
    """ It draws an animation on the piece's tile. It is based on our [Othello's drawBox method](https://www.justtothepoint.com/code/otello/)."""
        tile = pygame.Surface((int(SQUARESIZE), int(SQUARESIZE)), pygame.SRCALPHA)
        if self.color == BLACK:
            pygame.draw.circle(tile, GRAY, (int(SQUARESIZE/2), int(SQUARESIZE/2)), SQUARESIZE//2-12)
        elif self.color == WHITE:
            pygame.draw.circle(tile, BLACK, (int(SQUARESIZE/2), int(SQUARESIZE/2)), SQUARESIZE//2-12)
        pygame.draw.circle(tile, self.color, (int(SQUARESIZE/2), int(SQUARESIZE/2)), SQUARESIZE//2-15)
        tile_rect = tile.get_rect(center=(self.pixelCol, self.pixelRow))
        angle = 0
        for angle in range(0, 360, 18):
            new_width = round(math.sin(angle) * tile_rect.width) # It takes values in the interval [-tile_rect.width, tile_rect.width].

            rot_tile = pygame.transform.flip(tile, True, False) # It flips the tile and...
            rot_tile = pygame.transform.scale(rot_tile, (abs(new_width), tile_rect.height)) # it also resizes the tile (more specifically its width) to create the desired animation.  
            game.screen.blit(rot_tile, rot_tile.get_rect(center=tile_rect.center))
            game.fpsClock.tick(game.fps*3)
            pygame.display.flip()

    def translateBoardToPixelCoord(self):
    """ It translates from board to pixel coordinates."""
        self.pixelCol = self.col * SQUARESIZE + SQUARESIZE // 2
        self.pixelRow = self.row * SQUARESIZE + SQUARESIZE // 2

    def select(self, selected=True):
        self.selected = selected

    def move(self, movex, movey):
    """ It moves the Piece and as a consequence its state needs to be updated."""
        self.col = movex
        self.row = movey
        self.selected = False
        self.update()

    def __str__(self):
    """ It is used as a debugging tool when print() is invoked on the object and returns a string."""
        stringRepresentation = "(" + str(self.col) + \
            " , " + str(self.row) + "). Value: " + str(self.value)
        if self.selected:
            stringRepresentation += " and it is Selected."
        else:
            stringRepresentation += " and it is not Selected."
        if self.color == WHITE:
            stringRepresentation += " It is WHITE"
        else:
            stringRepresentation += " It is BLACK."

        return stringRepresentation

The Board class

The Board class encapsulates a two-dimensional (8 x 8) array or matrix that represents our Checkers’ 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.createBoard()
        self.isPieceSelected = False # It is a flag that indicates whether a piece is selected on the board or not.
        self.pieceSelected = None
        self.black_pieces = self.white_pieces = 12 # These are attributes that contain the numbers of black and white pieces on the board.
        self.value = 0 # This is the board's value. It is calculated using a heuristic evaluation function.
        self.animation = False # This flag indicates whether an animation should take place or not. 
        self.tilesToAnimate = []
        self.updateGame()

    def createBoard(self):
    """ It initializes and sets up our board. """
        for row in range(BOARDHEIGHT):
            for col in range(BOARDWIDTH):
                if col % 2 == ((row + 1) % 2):
                    if row < 3:
                        self.board[row][col] = Piece(col, row, BLACK)
                    elif row > 4:
                        self.board[row][col] = Piece(col, row, WHITE)

    def endGame(self, game):
    """ If the game is over (there are no valid moves left for the current player or no more pieces) returns True, otherwise it returns False.""" 
        endGame = False
        if game.turn == 'player':
            endGame = self.white_pieces == 0 or self.black_pieces == 0 or self.getValidMoves(WHITE) == []
        else:
            endGame = self.white_pieces == 0 or self.black_pieces == 0 or self.getValidMoves(BLACK) == []
        if endGame:
            game.running = False
            game.showEndScreen()
            sys.exit()
        return endGame

    def updateGame(self): 
    """ It updates the board's state: the board's value and the number of white and black pieces remaining on the board."""
        self.white_pieces = self.black_pieces = 0
        self.value = 0
        for row in range(BOARDHEIGHT):
            for col in range(BOARDWIDTH):
                piece = self.board[row][col]
                if piece != EMPTY_SPACE:
                    self.value += piece.value
                    if piece.color == WHITE:
                        self.white_pieces += 1
                    else:
                        self.black_pieces += 1

    def draw(self, game, animation, tilesToAnimate, player):
    """ It draws the current state of the game."""
        self.drawSquares(game.screen) # It draws the empty board.
        # It draws all the board's pieces by invoking the piece's draw() method.
        for row in range(BOARDHEIGHT): 
            for col in range(BOARDWIDTH):
                piece = self.board[row][col]
                if piece != EMPTY_SPACE:
                    piece.draw(game.screen)

        if animation and tilesToAnimate is not None:
        # If an animation should take place...  
            tilesToAnimate.reverse()
            for (col, row) in tilesToAnimate:
            # ... it iterates over the list with the tiles to be animated and invokes the Piece's drawAnimation() method.
                if player == 'player':
                    piece = Piece(col, row, BLACK)
                else:
                    piece = Piece(col, row, WHITE)
                piece.drawAnimation(game)

    def drawSquares(self, screen):
    """ It draws the empty board with no pieces on it yet."""
        screen.fill(DARKBROWN)
        for row in range(BOARDHEIGHT):
            for col in range(row % 2, BOARDWIDTH, 2):
                pygame.draw.rect(game.screen, LIGHTBROWN, (row*SQUARESIZE, col * SQUARESIZE, SQUARESIZE, SQUARESIZE))

    def select(self, col, row, player):
    """ It implements the logic for the user to select and move a piece."""
        if player == 'player':
            myColor = WHITE
        else:
            myColor = BLACK

        if row == None or col == None:
            return False, False, None
        piece = self.board[row][col]
        if not self.isPieceSelected and piece != EMPTY_SPACE and piece.color == myColor:
        # If there is no piece selected yet and _the board contains one of the current player's pieces on the position_ (col, row) given as an argument, we select the piece. 
            piece.select()
            self.isPieceSelected = True
            self.pieceSelected = piece
            self.showValidMoves() # This is just for debugging purposes.
            return False, False, None # It returns a tuple that contains three elements: False (the piece has only been selected), False (No animation should take place), None (there are no tiles to animate).
        isValid, adversaries = self.isValidMove(col, row)

The Board’s method isValidMove() returns a tuple. The first value indicates that the position (col, row) is a valid Checkers move and the second is a list containing all the opponent player’s pieces to be captured or tiles to be animated.

        if self.isPieceSelected and isValid:
        # If there is a piece already selected and the position (col, row) is a valid Checkers' move, it moves the selected piece, removes all the opponent's captured pieces from the board, and unselects the piece.
            self.move(col, row)
            self.remove(adversaries)
            self.isPieceSelected = False
            self.pieceSelected.select(False)
            return True, True, adversaries # It returns a tuple that contains three elements: True (the piece has been moved), True (an animation should take place), and adversaries (a list with the opponent player's pieces to be captured or tiles to be animated).
        elif self.isPieceSelected and not isValid and piece != EMPTY_SPACE and piece.color == myColor:
        # If there is a piece already selected and the board contains one of the current player's pieces on the position (col, row), we select it.
            self.pieceSelected.select(False)
            piece.select()
            self.pieceSelected = piece
            self.showValidMoves() # This is just for debugging purposes.
        return False, False, None

    def remove(self, adversaries):
    """ It removes all the opponent's captured pieces from the board."""
        if adversaries == None:
            return

        for col, row in adversaries:
            self.board[row][col] = EMPTY_SPACE

        self.updateGame()

    @ staticmethod
    def isValidPosition(col, row):
    """ It returns True if (col, row) represents a valid board position."""
        if row == None or col == None:
            return False
        if row >= 0 and row < BOARDHEIGHT and col >= 0 and col < BOARDWIDTH:
            return True
        else:
            return False

    def validMoves(self):
    """ If the currently selected piece is not a king, it returns all its valid moves."""
        if self.pieceSelected == None:
            return

        left = self.pieceSelected.col - 1
        right = self.pieceSelected.col + 1
        row = self.pieceSelected.row
        opponentColor = None
        directionRow = None
        if self.pieceSelected.color == WHITE:
            directionRow = -1
            opponentColor = BLACK
        else:
            directionRow = +1
            opponentColor = WHITE

        row += directionRow
        return self.traverse(left, row, opponentColor, directionRow, -1, []) + self.traverse(right, row, opponentColor, directionRow, +1, [])

    def traverse(self, col, row, opponentColor, directionRow, directionLeft, adversaries, jumping=False, lastEmpty=False):
    """ This is an auxiliary method for validMoves."""
        if not Board.isValidPosition(col, row):
            return []

        piece = self.board[row][col]
        if piece == EMPTY_SPACE and not jumping and not lastEmpty:
        # If we have reached an empty square and the "jumping" and "lastEmpty" flags were not set to True, we have found a valid move.
            return [(col, row, adversaries)]
Checkers in Python

Checkers in Python

If the player has previously jumped over an opponent’s piece (the “jumping” flag was set to True) and we have just reached an empty square, then we have found a valid move. The “jumping” flag is set to False and the “lastEmpty” flag is set to True to indicate that after jumping we have already reached an empty square (the next empty squares are not valid moves).

        elif piece == EMPTY_SPACE and jumping and not lastEmpty:
            return [(col, row, adversaries)] + self.traverse(col-1, row+directionRow, opponentColor, directionRow, -1, adversaries, False, True) + self.traverse(col+1, row+directionRow, opponentColor, directionRow, +1, adversaries, False, True) # We can continue searching for valid moves in the same and opposite directions.
Checkers in Python

Checkers in Python

        elif piece != EMPTY_SPACE and piece.color == opponentColor and not jumping:
        # If we have reached an opponent piece, we set the "jumping" flag to True and add (col, row) as a captured opponent's piece.
            return self.traverse(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries + [(col, row)], True)
        return []

We need the flag “jumping” having being set to False because we cannot jump over two opponent’s pieces without empty squares between them.

    def validMovesKing(self):
    """ If the currently selected piece is a king, it returns all its valid moves."""
        left = self.pieceSelected.col - 1
        right = self.pieceSelected.col + 1
        row = self.pieceSelected.row
        opponentColor = None
        directionRow = None
        downRow = self.pieceSelected.row
        if self.pieceSelected.color == WHITE:
            directionRow = -1
            opponentColor = BLACK
        else:
            directionRow = +1
            opponentColor = WHITE

        downRow -= directionRow
        row += directionRow
        return self.traverseKing(left, row, opponentColor, directionRow, -1, []) + self.traverseKing(right, row, opponentColor, directionRow, +1, []) + self.traverseKing(left, downRow, opponentColor, -directionRow, -1, []) + self.traverseKing(right, downRow, opponentColor, -directionRow, +1, [])

    def traverseKing(self, col, row, opponentColor, directionRow, directionLeft, adversaries, jumping=False, findingEmptySpace=False, findingOpponent=False):
    """ This is an auxiliary method for validMoves."""
        if not Board.isValidPosition(col, row):
            return []

        piece = self.board[row][col]

The player has previously jumped over an opponent’s piece (the “findingEmptySpace” and “jumping” flags were set to True) and we have just reached an empty square, so we have found a valid move. _We set the flag “findingEmptySpace” to True because we have already found an empty space.

        if piece == EMPTY_SPACE and findingEmptySpace:
                    return [(col, row, adversaries)] + self.traverseKing(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries, jumping, False, findingOpponent) \ # Every empty space in the same direction is a valid move. However, we should also search for valid moves in the opposite direction (col-directionLeft, row+directionRow) and backwards (col+directionLeft, row-directionRow), but we need to make sure that we reach an opponent's piece followed by a free square (findingOpponent=True, jumping=True)
                + self.traverseKing(col-directionLeft, row+directionRow, opponentColor, directionRow, -directionLeft, adversaries, True, False, True) \
                + self.traverseKing(col+directionLeft, row-directionRow, opponentColor, -directionRow, +directionLeft, adversaries, True, False, True)
Checkers in Python

Checkers in Python

        elif piece == EMPTY_SPACE and jumping and not findingOpponent:
            return [(col, row, adversaries)] + self.traverseKing(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries, jumping, False, findingOpponent) \
                + self.traverseKing(col-directionLeft, row+directionRow, opponentColor, directionRow, -directionLeft, adversaries, True, False, True) \
                + self.traverseKing(col+directionLeft, row-directionRow, opponentColor, -directionRow, +directionLeft, adversaries, True, False, True)
Checkers in Python

Checkers in Python

        elif piece == EMPTY_SPACE and jumping and findingOpponent:
        # If we are still searching for an opponent's piece, we move on in the same direction. The current square is not a valid move.
            return self.traverseKing(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries, jumping, False, findingOpponent)
        elif piece == EMPTY_SPACE and not jumping:
        # If the user has never jumped over an opponent's piece, all the empty squares in this direction are valid moves.
            return [(col, row, adversaries)] + self.traverseKing(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries, False, False, findingOpponent)

If we were searching for an opponent’s piece and we have just found it, we set the “findingOpponent” flag to False, the “findingEmptySpace” and “jumping” flags to True (we need to find an empty space and the following piece cannot be an opponent piece either), and add (col, row) as a captured opponent’s piece.

        elif piece != EMPTY_SPACE and piece.color == opponentColor and findingOpponent:
            return self.traverseKing(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries + [(col, row)], True, True, False)

Checkers

Checkers

Checkers

Checkers

If we were not searching for an empty space (we cannot jump over two opponent’s pieces) and we have just found an opponent’s piece, we set the “findingOpponent” flag to False, the “findingEmptySpace” and “jumping” flags to True, and add (col, row) as a captured opponent’s piece.

        elif piece != EMPTY_SPACE and piece.color == opponentColor and not findingEmptySpace:
            return self.traverseKing(col+directionLeft, row+directionRow, opponentColor, directionRow, directionLeft, adversaries + [(col, row)], True, True, False)
        return []

    def showValidMoves(self):
    """ This method is just for debugging purposes. It prints the board and the selected piece's valid moves in the terminal."""
        copy = deepcopy(self)
        if self.pieceSelected.king == True:
            for (c, r, list) in self.validMovesKing():
                copy.board[r][c] = Piece(c, r,  RED)
        else:
            for (c, r, list) in self.validMoves():
                copy.board[r][c] = Piece(c, r,  RED)

        print("‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐-")
        for row in range(BOARDHEIGHT):
            for col in range(BOARDWIDTH):
                piece = copy.board[row][col]
                if piece == EMPTY_SPACE:
                    print(" * ", end=' ')
                elif piece.color == BLACK:
                    print("[italic black on white] B [/]", end=' ')
                elif piece.color == RED:
                    print("[italic red] R [/italic red]", end=' ')
                else:
                    print("[italic white on yellow] W [/]",  end=' ')
                if col == BOARDWIDTH-1:
                    print("\n‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐-")

    def isValidMove(self, col, row):
        """ If the position (col, row) is a valid move for the selected piece, it returns True and all the opponent's pieces to be captured. Otherwise, it returns False and None (there are no pieces to be captured)."""
        if not Board.isValidPosition(col, row):
            return False, None
        piece = self.board[row][col]
        if piece == None or piece != EMPTY_SPACE or self.pieceSelected == EMPTY_SPACE:
            return False, None

        possibleMoves = self.getValidMoves(self.pieceSelected.color)
        # getValidMoves returns a list of tuples with all the available (valid) moves for the player given as a parameter
        for (colSelected, rowSelected, c, r, adversaries) in possibleMoves:
            # We loop through all the valid moves and check if the current selected piece and the given position (col, row) are on one of the tuples.
            if colSelected == self.pieceSelected.col and rowSelected == self.pieceSelected.row and c == col and r == row:
                return True, adversaries

        return False, None

    def move(self, col, row):
        """ It implements the move. It updates the board and the selected piece. Besides, if the selected piece reaches the furthest row from the player, then it is crowned king.""" 
        self.board[row][col], self.board[self.pieceSelected.row][self.pieceSelected.col] = self.board[self.pieceSelected.row][self.pieceSelected.col], self.board[row][col]
        self.pieceSelected.move(movex=col, movey=row)
        if row == BOARDHEIGHT-1 or row == 0:
            self.pieceSelected.makeKing()

    def playComputer(self, selectedx, selectedy, movex, movey, adversaries):
        """ It implements the computer's turn. It selects the piece located on the board position (selectedx, selectedy), moves it to (movex, movey), and finally removes all the opponent's captured pieces.""" 
        self.isPieceSelected = True
        self.pieceSelected = self.board[selectedy][selectedx]
        self.pieceSelected.select()
        self.showValidMoves() # It is used for debugging purposes.
        self.move(movex, movey)
        self.remove(adversaries)

    def selectComputer(self):
        """ It implements the Checkers' AI logic by selecting from all the valid moves, the one with the highest board's value (according to the heuristic function).""" 
        possibleMoves = self.getValidMoves(BLACK)
        bestValue = -2000
        bestPosition = (None, None, None, None, None)

        for (col, row, c, r, adversaries) in possibleMoves:
        # We loop through all the computer's valid moves, create a deep copy of the board object, make the move in the "cloned" board, and check its value. If this value is higher than the previous saved one, we update the best score (or value) and position to move. 
            copyBoard = deepcopy(self)
            copyBoard.pieceSelected = copyBoard.board[row][col]
            copyBoard.isPieceSelected = True
            copyBoard.pieceSelected.select()
            copyBoard.move(c, r)
            copyBoard.remove(adversaries)
            if copyBoard.value > bestValue:
                bestValue = copyBoard.value
                bestPosition = (col, row, c, r, adversaries)
        return bestPosition

    def getValidMoves(self, player):
    """ It returns a list of tuples with all the valid moves for the player given as a parameter."""
        possibleMoves = [] # It is a list with all the tuples (moves) that do not involve capturing some opponent's pieces.
        possibleMovesCapture = [] # It is a list with all the tuples (moves) that involve capturing some opponent's pieces.
        capture = False # If a single or multiple captures are available, the player can decide which one to take, but nevertheless a capture must be taken.
        for row in range(BOARDHEIGHT):
            for col in range(BOARDWIDTH):
                copy = deepcopy(self)
                copy.pieceSelected = copy.board[row][col]
                copy.isPieceSelected = True
                if copy.pieceSelected != EMPTY_SPACE and copy.pieceSelected.color == player:
                    copy.pieceSelected.select()
                    if copy.pieceSelected.king == True:
                        for (c, r, adversaries) in copy.validMovesKing():
                            if adversaries != []:
                                capture = True
                                possibleMovesCapture = possibleMovesCapture + [(col, row, c, r, adversaries)]
                            else:
                                possibleMoves = possibleMoves + [(col, row, c, r, adversaries)]
                    else:
                        for (c, r, adversaries) in copy.validMoves():
                            if adversaries != []:
                                capture = True
                                possibleMovesCapture = possibleMovesCapture + [(col, row, c, r, adversaries)]
                            else:
                                possibleMoves = possibleMoves + [(col, row, c, r, adversaries)]

        if capture:
            return possibleMovesCapture
        else:
            return possibleMoves

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 leaf nodes, i.e., terminal nodes and nodes at the maximum search depth.

  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

Minimax

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
Minimax2

Minimax2

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. 
        bestSelectcol = bestSelectrow = None
        bestMovecol = bestMoverow = None
        bestAdversaries = None

        if depth == 0 or possibleMoves == []: # If depth is zero or it is a terminal node.
            self.updateGame()
            if possibleMoves == []: # The game is over because there are no more valid moves.
                if self.value > 0:
                    return (None, None, None, None, None, 1000000)
                elif self.value < 0:
                    return (None, None, None, None, None, -1000000)
                else:
                    return (None, None, None, None, None, 0)
            else: # Depth is zero. We return the board's evaluation.
                return (None, None, None, None, None, self.value)

        if maximizingPlayer == BLACK: # Maximizing player, our AI.
            value = -1000000
            for (col, row, c, r, adversaries) in possibleMoves:
                copyBoard = deepcopy(self)
                copyBoard.pieceSelected = copyBoard.board[row][col]
                copyBoard.isPieceSelected = True
                copyBoard.pieceSelected.select()
                copyBoard.move(c, r)
                copyBoard.remove(adversaries)

                _, _, _, _, _, new_score = copyBoard.minimax(
                    depth-1, alpha, beta, WHITE)

                alpha = max(alpha, new_score) # The maximizing player updates alpha.
                if new_score > value:
                    value = new_score
                    bestSelectcol = col
                    bestSelectrow = row
                    bestMovecol = c
                    bestMoverow = r
                    bestAdversaries = adversaries
                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 bestSelectcol, bestSelectrow, bestMovecol, bestMoverow, bestAdversaries, value
        else:
            value = 1000000
            for (col, row, c, r, adversaries) in possibleMoves:
                copyBoard = deepcopy(self)
                copyBoard.pieceSelected = copyBoard.board[row][col]
                copyBoard.isPieceSelected = True
                copyBoard.pieceSelected.select()
                copyBoard.move(c, r)
                copyBoard.remove(adversaries)

                _, _, _, _, _, new_score = copyBoard.minimax(
                    depth-1, alpha, beta, BLACK)

                beta = min(beta, value)

                if new_score < value:
                    value = new_score
                    bestSelectcol = col
                    bestSelectrow = row
                    bestMovecol = c
                    bestMoverow = r
                    bestAdversaries = adversaries
                if alpha >= beta:
                    break

            return bestSelectcol, bestSelectrow, bestMovecol, bestMoverow, bestAdversaries, value

The Game class

class Game:  # It represents the game itself
    def __init__(self):
        pygame.init()  # It initializes all imported pygame modules.

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 checkers.ini is quite simple:

[BASIC] # The file consists of sections, each of which contains keys with values. 
WINDOWWIDTH = 1280 
WINDOWHEIGHT = 800 
FPS = 30 
SQUARESIZE = 70 
MODE = 2 
DEBUG = True
        self.config = configparser.ConfigParser() # We create an instance of the main configuration parser.
        self.config.read("checkers.ini")  # We read the configuration file.
        self.font = pygame.font.Font("resources/CHERI.TTF", 20) # pygame.font.Font allows us to render fonts in the game.
        self.bigfont = pygame.font.Font("resources/CHERL.TTF", 30)
        self.fpsClock = pygame.time.Clock() # A pygame.time.Clock object helps us to make sure our program runs at a certain FPS.
        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.
        # It sets the display mode and creates an instance of the pygame.Surface class.
        self.screen = pygame.display.set_mode(
            (SQUARESIZE*BOARDWIDTH, SQUARESIZE*BOARDHEIGHT))
        pygame.display.set_caption('Checkers')
        self.MODE = int(self.config['BASIC']['MODE'])
        self.board = Board() # It is an instance of our Board class.
        self.running = True # It indicates that the game is still running.
        self.MOUSEBUTTONUP = False
        self.KEYUP = False
        self.turn = 'player'
        self.animation = False
        self.tilesToAnimate = [(None, None)]
        sys.setrecursionlimit(1500)
        self.board.updateGame()

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):
        while self.running and not self.board.endGame(self): # It loops while the game is still running (the user has not pressed the "x" button) and it is not the end of the game.
            self.check_events()  # It checks all the events.
            if self.turn == 'player':
                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).
                    move, animation, tilesToAnimate = self.board.select(movex, movey, 'player') # The select method returns a tuple that contains three elements: move (True, the previously selected piece has been moved; False, a piece has just been selected), animation (An animation should take place or not), tilesToAnimate (a list with the opponent's captured pieces or tiles to animate).
                    self.animation = animation
                    self.tilesToAnimate = tilesToAnimate
                    if move: # If a move has taken place, we give the turn to the computer.
                        self.turn = 'computer'
            else:
                if self.MODE == 0: # A human player plays against another one.
                    if self.MOUSEBUTTONUP:
                        movex, movey = self.getSquareClicked(self.pos[0], self.pos[1])
                        move, animation, tilesToAnimate = self.board.select(movex, movey, 'computer')
                        self.animation = animation
                        self.tilesToAnimate = tilesToAnimate
                        if move:
                            self.turn = 'player'
                elif self.MODE == 1: # A human player plays against the computer.
                    selectedx, selectedy, movex, movey, adversaries = self.board.selectComputer() # It selects from all the valid moves, the one with the highest board's value (according to the heuristic function).
                    self.animation = True
                    self.tilesToAnimate = adversaries
                    self.board.playComputer(selectedx, selectedy, movex, movey, adversaries) # It implements the computer player's turn by selecting the piece located on (selectedx, selectedy), moving it to (movex, movey), and finally removing all opponent's captured pieces (adversaries).
                    self.turn = 'player'
                elif self.MODE == 2:
                    selectedx, selectedy, movex, movey, adversaries, _ = self.board.minimax(4, -math.inf, math.inf, BLACK) # It selects from all the valid moves, the best one given by the minimax algorithm.
                    self.animation = True
                    self.tilesToAnimate = adversaries
                    if not (selectedx == None or selectedy == None or movex == None or movey == None):
                        self.board.playComputer(selectedx, selectedy, movex, movey, adversaries) # It implements the computer player's turn by selecting the piece located on (selectedx, selectedy), moving it to (movex, movey), and finally removing all opponent's captured pieces (adversaries).
                        self.turn = 'player'
                    else:
                        self.showEndScreen(
                            "All my moves end up in failure. You win!")

            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, text=None):
    """ It shows the end screen."""
        if text is not None:
            self.showTextScreen("Player wins", text)
        else:
            self.board.updateGame()

            if self.board.black_pieces > self.board.white_pieces:
                self.showTextScreen("Computer wins!", "Player score: %s. Computer score: %s" % (self.board.white_pieces, self.board.black_pieces))
            elif self.board.black_pieces < self.board.white_pieces:
                self.showTextScreen("Player wins!", "Player's score: %s. Computer's score: %s" % (self.board.white_pieces, self.board.black_pieces))
            else:
                self.showTextScreen("It is a tie!", "Player's score: %s. Computer's score: %s" % (self.board.white_pieces, self.board.black_pieces))

    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(
            SQUARESIZE*BOARDWIDTH / 7), int(SQUARESIZE*BOARDHEIGHT / 4))
        self.drawText(text2, self.bigfont, int(
            SQUARESIZE*BOARDWIDTH / 7), int(SQUARESIZE*BOARDHEIGHT / 4) + 100)
        self.drawText('Press a key to go.', self.font, int(
            SQUARESIZE*BOARDWIDTH / 7), int(SQUARESIZE*BOARDHEIGHT / 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 * SQUARESIZE and mousex < (x + 1) * SQUARESIZE and mousey > y * SQUARESIZE and mousey < (y + 1) * SQUARESIZE:
                    return (x, y)
        return (None, None)

    def drawGame(self):
    """ It draws the current state of the game."""
        self.board.draw(self, self.animation, self.tilesToAnimate, self.turn)
        if self.animation == True:
            self.animation = False
            self.tilesToAnimate = [(None, None)]

        pygame.display.update()

    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:
                # Handle mouse click events
                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 resets all the keys."""
        self.MOUSEBUTTONUP = False
        self.KEYUP = False

if __name__ == '__main__':
    # The main function is quite simple. We create an instance of our Game class.
    game = Game()
    game.gameLoop() # We call the game's game_loop function.
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.