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 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:
- Creating a game state representation. This includes the logic for identifying terminal states and generating successor states for each game state.
- Creating an evaluation function for the game states.
- Implementing the search algorithm.
- 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.
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.
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).
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.
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.
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.