Creating a bot for Checkers

In the previous post, we learnt about adversarial search. Before we relax more assumptions on search problems and move on to general games, let’s first see how we can create a bot for a zero-sum game, in particular, checkers.

Checkers State

Checkers or Draughts is a strategy board game for two players, played on an 8×8 chess board. There is a challenge on Hackerrank for creating a checkers bot. You can read the problem statement and the input/output format there. We’ll try to solve that challenge in this post.

There are 4 steps to creating a game bot:

  1. Creating a game state representation. This includes the logic for identifying terminal states and generating successor states for each game state.
  2. Creating an evaluation function for the game states.
  3. Implementing the search algorithm.
  4. Integration: Accepting the current state from the judge, converting it into our own state representation, running the search algorithm to find the next move to play and outputting it in the desired format.

We’ll look at each step one by one.

Creating a game state representation

There are many possible ways to represent a checkers state, from the simplest, storing an 8×8 matrix of characters, to the most complex, storing bitboard representation of the board for each type of piece (There are 4 types of pieces: black and white pawns and kings. We can use 4 64-bit integers to represent the game state. A bit for a piece is set if that piece is present at that bit location.). For the purpose of this post, let’s go with the simplest approach of storing the state as an 8×8 matrix of characters. We’ll find that move generation is still quite complex even with the simplest state representation.

from copy import deepcopy
from time import time
# Global Constants
MaxUtility = 1e9
IsPlayerBlack = True
MaxAllowedTimeInSeconds = 9.5
MaxDepth = 100
class CheckersState:
def __init__(self, grid, blackToMove, moves):
self.grid = grid
self.blackToMove = blackToMove
self.moves = moves # Hops taken by a disc to reach the current state
# This just checks for whether or not all pieces of a player have been eliminated.
# It does not check for whether a player has a move or not. In that case, there will
# be no successors for that player and alpha beta search will return Min/Max Utility.
def isTerminalState(self):
blackSeen, whiteSeen = False, False
for row in grid:
for cell in row:
if cell == 'b' or cell == 'B': blackSeen = True
elif cell == 'w' or cell == 'W': whiteSeen = True
if blackSeen and whiteSeen: return False
self.isLoserBlack = whiteSeen
return True
def getTerminalUtility(self):
return MaxUtility if IsPlayerBlack != self.isLoserBlack else -MaxUtility
def getSuccessors(self):
def getSteps(cell):
whiteSteps = [(-1, -1), (-1, 1)]
blackSteps = [(1, -1), (1, 1)]
steps = []
if cell != 'b': steps.extend(whiteSteps)
if cell != 'w': steps.extend(blackSteps)
return steps
def generateMoves(board, i, j, successors):
for step in getSteps(board[i][j]):
x, y = i + step[0], j + step[1]
if x >= 0 and x < 8 and y >= 0 and y < 8 and board[x][y] == '_':
boardCopy = deepcopy(board)
boardCopy[x][y], boardCopy[i][j] = boardCopy[i][j], '_'
# A pawn is promoted when it reaches the last row
if (x == 7 and self.blackToMove) or (x == 0 and not self.blackToMove):
boardCopy[x][y] = boardCopy[x][y].upper()
successors.append(CheckersState(boardCopy, not self.blackToMove, [(i, j), (x, y)]))
def generateJumps(board, i, j, moves, successors):
jumpEnd = True
for step in getSteps(board[i][j]):
x, y = i + step[0], j + step[1]
if x >= 0 and x < 8 and y >= 0 and y < 8 and board[x][y] != '_' and board[i][j].lower() != board[x][y].lower():
xp, yp = x + step[0], y + step[1]
if xp >= 0 and xp < 8 and yp >= 0 and yp < 8 and board[xp][yp] == '_':
board[xp][yp], save = board[i][j], board[x][y]
board[i][j] = board[x][y] = '_'
previous = board[xp][yp]
# A pawn is promoted when it reaches the last row
if (xp == 7 and self.blackToMove) or (xp == 0 and not self.blackToMove):
board[xp][yp] = board[xp][yp].upper()
moves.append((xp, yp))
generateJumps(board, xp, yp, moves, successors)
moves.pop()
board[i][j], board[x][y], board[xp][yp] = previous, save, '_'
jumpEnd = False
if jumpEnd and len(moves) > 1:
successors.append(CheckersState(deepcopy(board), not self.blackToMove, deepcopy(moves)))
player = 'b' if self.blackToMove else 'w'
successors = []
# generate jumps
for i in xrange(8):
for j in xrange(8):
if self.grid[i][j].lower() == player:
generateJumps(self.grid, i, j, [(i, j)], successors)
if len(successors) > 0: return successors
# generate moves
for i in xrange(8):
for j in xrange(8):
if self.grid[i][j].lower() == player:
generateMoves(self.grid, i, j, successors)
return successors

First, we’ve declared some global variables to store the maximum allowed time, depth, utility and the player for which the bot has been called. Then, we’ve created a class CheckersState, which provides methods isTerminalState(), getTerminalUtility() and getSuccessors(). The successor generation is complicated by the fact that a disc can take multiple jumps in a single move, may also get promoted while jumping, and additional jumps may become available because of promotion.

Creating an evaluation function for the game states

We can make the evaluation function as complex as we desire, looking at features like piece count, number of moves/jumps available, distance from opponent pieces etc. For now, let’s go with something simple: the difference in piece weight counts of us and our opponent, with a pawn having weight 1 and a king having weight 1.5.

def piecesCount(state):
# 1 for a normal piece, 1.5 for a king
black, white = 0, 0
for row in state.grid:
for cell in row:
if cell == 'b': black += 1.0
elif cell == 'B': black += 1.5
elif cell == 'w': white += 1.0
elif cell == 'W': white += 1.5
return black - white if IsPlayerBlack else white - black

Implementing the search algorithm

We’ll implement alpha beta search with iterative deepening and try to utilize most of the execution time provided by the judge (10s per move for python).

def iterativeDeepeningAlphaBeta(state, evaluationFunc):
startTime = time()
def alphaBetaSearch(state, alpha, beta, depth):
def maxValue(state, alpha, beta, depth):
val = -MaxUtility
for successor in state.getSuccessors():
val = max(val, alphaBetaSearch(successor, alpha, beta, depth))
if val >= beta: return val
alpha = max(alpha, val)
return val
def minValue(state, alpha, beta, depth):
val = MaxUtility
for successor in state.getSuccessors():
val = min(val, alphaBetaSearch(successor, alpha, beta, depth - 1))
if val <= alpha: return val
beta = min(beta, val)
return val
if state.isTerminalState(): return state.getTerminalUtility()
if depth <= 0 or time() - startTime > MaxAllowedTimeInSeconds: return evaluationFunc(state)
return maxValue(state, alpha, beta, depth) if state.blackToMove == IsPlayerBlack else minValue(state, alpha, beta, depth)
bestMove = None
for depth in xrange(1, MaxDepth):
if time() - startTime > MaxAllowedTimeInSeconds: break
val = -MaxUtility
for successor in state.getSuccessors():
score = alphaBetaSearch(successor, -MaxUtility, MaxUtility, depth)
if score > val:
val, bestMove = score, successor.moves
return bestMove

Since Alpha Beta Search does not guarantee that values of successors of the root are correct, we can’t directly use it for move selection. To solve this problem, we run the search for each successor of the root and choose the move which leads to the largest value.

Integration

Now, we just need to accept the state description from the judge, convert it to our representation, run the search algorithm to find the next move to play and output it in the correct format.

if __name__ == '__main__':
player = raw_input()
boardSize = int(raw_input())
grid = []
for i in xrange(boardSize):
grid.append(raw_input())
IsPlayerBlack = player[0] == 'b'
state = CheckersState([list(row.rstrip()) for row in grid], IsPlayerBlack, [])
move = iterativeDeepeningAlphaBeta(state, piecesCount)
print len(move) - 1
for step in move:
print step[0], step[1]

When we put these 4 codes together, we get a working solution to the Checkers challenge. It wins majority of the games and can be easily improved by using a better state representation (bitboards!) and a better evaluation function that looks at more features of the game state.

Here’s the complete code in python.

Advertisement
Privacy Settings

One thought on “Creating a bot for Checkers

  1. Pingback: Search in the presence of uncertainty | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s