|
 |
 |
|
 |
|
|
|
|
|
|
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
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 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)]
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.
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)
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)
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
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
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
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
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
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.
JustToThePoint Copyright © 2011 - 2023 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.
