Chapter 1: Representing the Game¶
Welcome! In this tutorial series, we're going to build a complete checkers game engine with AI players and reinforcement learning agents. We'll start from the ground up, explaining every design decision along the way.
First: Representing the Game Elements and State¶
Before we can play checkers, move pieces, or train AI, we need a simple an efficient representation of the pieces, the player, the board, the position of pieces on the board, and the state of the game.
A checkers game has:
- An 8×8 board with 32 playable squares (the dark squares)
- Pieces: red pawns, white pawns, red kings, white kings
- Game state: whose turn it is, where pieces are located
We need a representation that is:
- Simple - easy to understand and debug
- Efficient - fast for AI to evaluate thousands of positions
- Immutable - prevents bugs from accidental state changes
- Hashable - allows us to detect repeated positions
Let's build this step by step.
Step 1: Piece Constants¶
First, let's define constants for piece types.
# Piece type constants
EMPTY = 0
RED_PAWN = 1
WHITE_PAWN = 2
RED_KING = 3
WHITE_KING = 4
# Player constants
RED = 1
WHITE = 2
Step 2: Coordinate Systems¶
Checkers has an interesting property: the board is 8×8, but only 32 squares (the dark ones) are playable.
We have two coordinate systems:
- 2D coordinates: (row, col) from 0-7, like a normal 2D array
- 1D coordinates: index from 0-31, representing only playable squares
The 1D system is more efficient (32 positions instead of 64), but we need to convert between them for moves and display.
Note on numbering: We are using 0-based numbering for programming convience. We'll convert the 2D or 1D coordinates to human readable 1-based numbering when rendering the positions.
Let's visualize the mapping:
# Let's see how squares are numbered in 1D
def visualize_1d_numbering():
"""Show how 1D indices map to 2D board positions."""
print("Checkers board with 1D indices (only dark squares):")
print("\n 0 1 2 3 4 5 6 7")
idx = 0
for row in range(8):
print(f"{row}", end=" ")
for col in range(8):
# Dark squares are where (row + col) is odd
if (row + col) % 2 == 1:
print(f"{idx:2d}", end=" ")
idx += 1
else:
print(" .", end=" ")
print()
visualize_1d_numbering()
Checkers board with 1D indices (only dark squares): 0 1 2 3 4 5 6 7 0 . 0 . 1 . 2 . 3 1 4 . 5 . 6 . 7 . 2 . 8 . 9 . 10 . 11 3 12 . 13 . 14 . 15 . 4 . 16 . 17 . 18 . 19 5 20 . 21 . 22 . 23 . 6 . 24 . 25 . 26 . 27 7 28 . 29 . 30 . 31 .
# The 1D representation of the initial board position
INITIAL_BOARD = [RED_PAWN] * 12 + [EMPTY] * 8 + [WHITE_PAWN] * 12
Now let's implement a couple of functions to convert between these two coordinate systems.
def map_1d_to_2d(i):
"""Maps the 0-based 1D index to a pair of row and col for the 2D representation."""
row = i // 4
col = 2 * (i % 4) + (1 - row % 2)
return row, col
def map_2d_to_1d(row, col):
"""Maps the 2D index to a 0-based 1D index for the 1D representation."""
return row * 4 + ((col - (1 - row % 2)) // 2)
# Test the conversion
print("Testing coordinate conversion:")
print(f"1D index 0 -> 2D: {map_1d_to_2d(0)}")
print(f"1D index 5 -> 2D: {map_1d_to_2d(5)}")
print(f"2D (0,1) -> 1D: {map_2d_to_1d(0, 1)}")
print(f"2D (1,2) -> 1D: {map_2d_to_1d(1, 2)}")
# Verify round-trip
for i in range(32):
row, col = map_1d_to_2d(i)
i_back = map_2d_to_1d(row, col)
assert i == i_back, f"Round-trip failed for {i}"
print("\n✓ All 32 squares convert correctly!")
Testing coordinate conversion: 1D index 0 -> 2D: (0, 1) 1D index 5 -> 2D: (1, 2) 2D (0,1) -> 1D: 0 2D (1,2) -> 1D: 5 ✓ All 32 squares convert correctly!
Step 3: GameState¶
Let's start with the simplest possible GameState class. We'll store the 1D representation of the board and the player who has the turn.
class GameStateV1:
"""Simple mutable game state."""
def __init__(self, board, turn=RED):
self.board = board # List of 32 piece values
self.turn = turn # Whose turn is it?
def at(self, row, col):
"""Get piece at 2D coordinates."""
idx = map_2d_to_1d(row, col)
return self.board[idx]
# Try it out
state_v1 = GameStateV1(INITIAL_BOARD, RED)
print(f"Board has {len(state_v1.board)} squares")
print(f"Turn: {'RED' if state_v1.turn == RED else 'WHITE'}")
print(f"Top-left playable square (0,1): {state_v1.at(0, 1)}")
print(f"Bottom-right playable square (7,6): {state_v1.at(7, 6)}")
Board has 32 squares Turn: RED Top-left playable square (0,1): 1 Bottom-right playable square (7,6): 2
We want to be able to store game states in data structures that will be used to check if the same state has been visited before. As a result allowing a game state to be modified can be dangerous.
# This is dangerous!
FRAGILE_INITIAL_BOARD = [RED_PAWN] * 12 + [EMPTY] * 8 + [WHITE_PAWN] * 12
fragile_state = GameStateV1(FRAGILE_INITIAL_BOARD, RED)
fragile_state.board[0] = EMPTY # Oops, we just removed a piece
print(f"After modification: {fragile_state.board[0]}")
print("\n⚠️ Mutable state can lead to bugs!")
After modification: 0 ⚠️ Mutable state can lead to bugs!
Step 4: GameState - Version 2 (Immutable)¶
The following hides the internal fields and only exposes read-only accessors.
class GameStateV2:
"""Immutable game state."""
def __init__(self, board, turn=RED):
self._board = tuple(board) # Store as tuple (immutable)
self._turn = turn
@property
def board(self):
return self._board
@property
def turn(self):
return self._turn
def at(self, row, col):
"""Get piece at 2D coordinates."""
idx = map_2d_to_1d(row, col)
return self._board[idx]
def __hash__(self):
"""Make it hashable so we can use in sets/dicts."""
return hash((self._board, self._turn))
def __eq__(self, other):
"""Check equality."""
if not isinstance(other, GameStateV2):
return False
return self._board == other._board and self._turn == other._turn
# Try it
state_v2 = GameStateV2(INITIAL_BOARD, RED)
print(f"State is hashable: {hash(state_v2)}")
# Try to modify (this will fail)
try:
state_v2.board[0] = EMPTY
except TypeError as e:
print(f"\n✓ Cannot modify tuple: {e}")
# We can use it in sets now!
seen_states = {state_v2}
print(f"\n✓ Can store in sets for detecting repeated positions")
State is hashable: 1750672304963306825 ✓ Cannot modify tuple: 'tuple' object does not support item assignment ✓ Can store in sets for detecting repeated positions
We will improve GameState further in the future. For now, the version we have here is sufficient for our purposes..
GameState = GameStateV2
Runnable Artifact: Display the Board¶
Let's create a simple function to visualize our game state:
def display_board(state: GameState):
"""Simple ASCII display of the board."""
piece_symbols = {
EMPTY: ' ',
RED_PAWN: 'r',
WHITE_PAWN: 'w',
RED_KING: 'R',
WHITE_KING: 'W'
}
print("\n 0 1 2 3 4 5 6 7")
for row in range(8):
print(f"{row}", end=" ")
for col in range(8):
if (row + col) % 2 == 0:
print(".", end=" ")
else:
piece = state.at(row, col)
symbol = piece_symbols[piece]
print(symbol, end=" ")
print()
turn_str = "RED" if state.turn == RED else "WHITE"
print(f"\nTurn: {turn_str}")
# Display the initial position
INITIAL_STATE = GameState(INITIAL_BOARD, RED)
display_board(INITIAL_STATE)
0 1 2 3 4 5 6 7 0 . r . r . r . r 1 r . r . r . r . 2 . r . r . r . r 3 . . . . 4 . . . . 5 w . w . w . w . 6 . w . w . w . w 7 w . w . w . w . Turn: RED
Summary¶
In this chapter, we built a representation of the game.
- Constants: Integer codes for pieces and players
- Coordinate mapping: Converting between 1D (0-31) and 2D (row, col) representations
- GameState: An immutable, hashable class representing the game state
What's next?
Now that we can represent game states, we need to represent moves. In Chapter 2, we'll implement:
- Move chains (single moves and multi-hop jumps)
- Legal move validation
- Move generation
Repo reference: The complete code is in core/representation.py
