Chapter 2: Modeling Moves¶

📚 Previous: Chapter 1: Representing the Game¶

Now that we have built a representation for game states, we need to represent moves and implement the rules of checkers, which determine what legal moves are and how they change the state of the game.

Moves in Checkers¶

Checkers has two types of moves:

• Regular moves: A piece moves diagonally to an adjacent empty square
• Jump moves: A piece jumps over an opponent's piece to capture it

A interesting aspect of checkers is that a move can consists of a chaing of back-to-back jumps by the same piece.

In this chapter we will

1. Represent complete moves (including multi-hop jump chains)
2. Determine which moves are legal in a given state
3. Generate all legal moves
4. Apply moves to create new states

Setup: Import from Chapter 1¶

# Import everything from Chapter 1
from typing import Optional

# Piece type constants
EMPTY = 0
RED_PAWN = 1
WHITE_PAWN = 2
RED_KING = 3
WHITE_KING = 4

# Player constants
RED = 1
WHITE = 2

def map_1d_to_2d(i):
    row = i // 4
    col = 2 * (i % 4) + (1 - row % 2)
    return row, col

def map_2d_to_1d(row, col):
    return row * 4 + ((col - (1 - row % 2)) // 2)

class GameState:
    def __init__(self, board, turn=RED):
        self._board = tuple(board)
        self._turn = turn
    
    @property
    def board(self):
        return self._board
    
    @property
    def turn(self):
        return self._turn
    
    def at(self, row, col):
        idx = map_2d_to_1d(row, col)
        return self._board[idx]
    
    def __hash__(self):
        return hash((self._board, self._turn))
    
    def __eq__(self, other):
        if not isinstance(other, GameState):
            return False
        return self._board == other._board and self._turn == other._turn

print("✓ Setup complete")

✓ Setup complete

Step 1: Move Representation¶

There are many ways to represent a move. Here we choose one that is relatively compact and yet easy to process programmatically.

We represent a move as a sequence of positions that a piece goes through. The starting position is where the moving piece resides in the current state. Subsequent positions are where that piece will move to.

For a regular move, the sequence would contain exactly two positions: the staring position and the (diagonally) negighboring position. For a multi-hop jump, it's all the positions in the chain.

# Type alias for moves
MoveChain = list[int]

# Examples
regular_move = [8, 13]  # Move from position 8 to position 13
double_jump = [13, 22, 29]  # Jump chain: 13 -> 22 -> 29 (captures two pieces)

print(f"Regular move: {regular_move}")
print(f"Double jump: {double_jump}")

Regular move: [8, 13]
Double jump: [13, 22, 29]

Step 2: Rules for Legal Moves¶

Let's review the rules of checkers that determine what moves are legal:

1. Basic move structure: The list must have at least two numbers and all numbers must be in the range 0-31. All positions except the first must correspond to empty squares.
2. Taking turns: The first square must contain a piece (pawn or king) belonging to the player whose turn it is.
3. Move direction:
   • Pawns can only move and jump forward (in the direction of their color)
   • Kings can move and jump in all four diagonal directions
4. Regular move: If the move is a single diagonal step to an adjacent square, it's only legal if no jumps are available from ANY piece.
5. Jump (capture) move:
   • Jumps require the adjacent square to contain an opponent piece and the square beyond to be empty
   • All hops in the chain must be valid jumps (diagonal moves of 2 squares)
6. Mandatory jump chain: If further jumps are available after landing, the move must continue jumping.

In this step we will implement the boolean function is_lega(state, move) that returns true if the given move is legal in the specified state.

Rule 1 ensures that a move has a reasonable structural form, and that it contains meaningful numbers, that is, numbers that could be a position index.

if len(move) < 2:
      return False # False means the move is illegal
   for idx, pos in enumerate(move):
      if not (0 <= pos <= 31):
         return False
      if idx > 0 and state.board[pos] != EMPTY:
         return False

Rule 2 states that the only the player who has the move can make a move with one of their pieces. To implement this we use an auxiliary map that tells us which player the piece at the starting positions belongs.

PIECE_COLOR = {
    RED_PAWN: RED,
    WHITE_PAWN: WHITE,
    RED_KING: RED,
    WHITE_KING: WHITE
}

# The rule is implemented as:
   piece = state.board[move[0]]
   if PIECE_COLOR.get(piece) != state.turn:
      return False

Rule 3 specifies the direction each piece can move. To implement this rule we use an auxiliary map that tells us the direction that each piece can move.

According to rules of checkers, pieces may move only in the following directions:

• Red pawns move down the board (row increases)
• White pawns move up the board (row decreases)
• Kings move in all four diagonal directions

NOTE: It is easier to implement this rule and rule 4 by converting the 1D positions to 2D coordinates. Therefore, we make user of map_1d_to_2d. We could also do this, probably more efficiently, by representing the direction and adjacency relationships for 1D positions in precomputed data strutures, but that would make the code slightly more complicated and harder to understand. For our purposes, we ignore this or similar optimizations here.

# Movement directions for each piece type (row_delta, col_delta)
DIRECTIONS = {
   RED_PAWN: [(1, 1), (1, -1)],        # Down-right, down-left
   WHITE_PAWN: [(-1, 1), (-1, -1)],    # Up-right, up-left
   RED_KING: [(1, 1), (1, -1), (-1, 1), (-1, -1)],    # All four diagonals
   WHITE_KING: [(1, 1), (1, -1), (-1, 1), (-1, -1)],  # All four diagonals
}

# Get 2D coordinates for direction checks
first_r, first_c = map_1d_to_2d(move[0])
second_r, second_c = map_1d_to_2d(move[1])

# The rule is implemented as, Note that kings can move in any direction.
   if piece == RED_PAWN and second_r <= first_r:
      return False
   if piece == WHITE_PAWN and second_r >= first_r:
      return False

Rule 4 states when a regular move can be made. Since jumpas are manadatory in checkers, a regular move is illegal if a jump is available in the current state of the game. Note that the rule is not about each piece individually: if any jump (capture) is available to the player who has the turn, the player must take it.

To implement this and the following rules we need a helper function _get_one_hop_jumps(state, pos). This functions returns the jumps available from the given pos.

def _get_one_hop_jumps(state, pos): 
   """Helper: Get all possible single jump destinations from a position."""
   # See the code cell below for impl.

...

   ## First: identify regular moves: that is, when the piece moves diagonally by one square. 
   ## Note: we have already verified the direction of the move when enforcing rule 3. 
   if abs(second_r - first_r) == 1 and abs(second_c - first_c) == 1:
      if len(move) > 2: # A regular move ends immediately: no chaining allowed.
         return False
      # Regular moves are  permitted if no jumps available from ANY piece
      for i in range(32):
         if PIECE_COLOR.get(state.board[i]) == state.turn:
            if len(_get_one_hop_jumps(state, i)) > 0:
               return False
      return True # We are done with validating a regular move.

Rule 5 States that a jump can move only two squares in the allowed direction and it must be a jump over an opponent's piece. Sine jump moves can be chained together, we enforce this requirement for all the hops in the move chain.

for i in range(len(move) - 1):
      r1, c1 = map_1d_to_2d(move[i])
      r2, c2 = map_1d_to_2d(move[i + 1])
        
      # Must be diagonal move of 2 squares
      if abs(r2 - r1) != 2 or abs(c2 - c1) != 2:
         return False
        
      # Jumped square must contain opponent piece
      jr, jc = (r1 + r2) // 2, (c1 + c2) // 2
      jumped_piece = state.board[map_2d_to_1d(jr, jc)]
      if jumped_piece == EMPTY or PIECE_COLOR.get(jumped_piece) == state.turn:
         return False

Rule 6 is the requirement that subsequent jumps must be taken if available. The implementation of this rule is rather simple: we only need to ensure that at the end of the jump chain, no further jumps are available:

# 6. Mandatory jump chain
    if len(_get_one_hop_jumps(state, move[-1])) > 0:
      return False

The following code cell puts all of these together.

# Map pieces to players. 
PIECE_COLOR = {
    RED_PAWN: RED,
    WHITE_PAWN: WHITE,
    RED_KING: RED,
    WHITE_KING: WHITE
}

# Movement directions for each piece type (row_delta, col_delta)
DIRECTIONS = {
    RED_PAWN: [(1, 1), (1, -1)],        # Down-right, down-left
    WHITE_PAWN: [(-1, 1), (-1, -1)],    # Up-right, up-left
    RED_KING: [(1, 1), (1, -1), (-1, 1), (-1, -1)],    # All four diagonals
    WHITE_KING: [(1, 1), (1, -1), (-1, 1), (-1, -1)],  # All four diagonals
}


def _get_one_hop_jumps(state, pos):
    """Helper: Get all possible single jump destinations from a position."""
    jumps = []
    piece = state.board[pos]
    
    if piece == EMPTY or PIECE_COLOR.get(piece) != state.turn:
        return jumps
    
    opponent = WHITE if state.turn == RED else RED
    row, col = map_1d_to_2d(pos)
    
    for dr, dc in DIRECTIONS.get(piece, []):
        jump_row, jump_col = row + 2*dr, col + 2*dc
        if 0 <= jump_row < 8 and 0 <= jump_col < 8:
            adj_row, adj_col = row + dr, col + dc
            adj_pos = map_2d_to_1d(adj_row, adj_col)
            jump_pos = map_2d_to_1d(jump_row, jump_col)
            
            if (PIECE_COLOR.get(state.board[adj_pos]) == opponent and 
                state.board[jump_pos] == EMPTY):
                jumps.append(jump_pos)
    return jumps


def is_legal(state, move):
    """Check if a move is legal in the given state."""
    # 1. Basic move structure
    if len(move) < 2:
        return False
    for idx, pos in enumerate(move):
        if not (0 <= pos <= 31):
            return False
        if idx > 0 and state.board[pos] != EMPTY:
            return False
    
    # 2. Taking turns
    piece = state.board[move[0]]
    if PIECE_COLOR.get(piece) != state.turn:
        return False
    
    # Get 2D coordinates for direction checks
    first_r, first_c = map_1d_to_2d(move[0])
    second_r, second_c = map_1d_to_2d(move[1])
    
    # 3. Move direction
    if piece == RED_PAWN and second_r <= first_r:
        return False
    if piece == WHITE_PAWN and second_r >= first_r:
        return False
    
    # 4. Regular move (single diagonal step)
    if abs(second_r - first_r) == 1 and abs(second_c - first_c) == 1:
        if len(move) > 2:
            return False
        # Regular moves are  permitted if no jumps available from ANY piece
        for i in range(32):
            if PIECE_COLOR.get(state.board[i]) == state.turn:
                if len(_get_one_hop_jumps(state, i)) > 0:
                    return False
        return True
    
    # 5. Jump move validation
    for i in range(len(move) - 1):
        r1, c1 = map_1d_to_2d(move[i])
        r2, c2 = map_1d_to_2d(move[i + 1])
        
        # Must be diagonal move of 2 squares
        if abs(r2 - r1) != 2 or abs(c2 - c1) != 2:
            return False
        
        # Jumped square must contain opponent piece
        jr, jc = (r1 + r2) // 2, (c1 + c2) // 2
        jumped_piece = state.board[map_2d_to_1d(jr, jc)]
        if jumped_piece == EMPTY or PIECE_COLOR.get(jumped_piece) == state.turn:
            return False
    
    # 6. Mandatory jump chain
    if len(_get_one_hop_jumps(state, move[-1])) > 0:
        return False
    
    return True


# Test is_legal with various scenarios
board = [EMPTY] * 32
board[9] = RED_PAWN
state = GameState(board, RED)

print("Testing move validation:")
print(f"  [9, 13] (regular move): {is_legal(state, [9, 13])}")
print(f"  [9, 14] (regular move): {is_legal(state, [9, 14])}")
print(f"  [9, 5] (backward - invalid for pawn): {is_legal(state, [9, 5])}")

# Test with jump scenario
board[13] = WHITE_PAWN
state = GameState(board, RED)
print(f"\nWith white pawn at 13:")
print(f"  [9, 13] (regular move blocked by jump): {is_legal(state, [9, 13])}")
print(f"  [9, 18] (jump over white pawn): {is_legal(state, [9, 18])}")

Testing move validation:
  [9, 13] (regular move): True
  [9, 14] (regular move): True
  [9, 5] (backward - invalid for pawn): False

With white pawn at 13:
  [9, 13] (regular move blocked by jump): False
  [9, 18] (jump over white pawn): False

Step 4: Available moves: Regular moves¶

In this step and Step 5, we implement the function that returns all available legal move in a given game state. Obviously, these are moves that can be played by the player who has the turn.

In this step, we focus on collecting only the regular moves. Remember that this function may only be called and used if no jumps are available in the current game state. We only present it first because it's simpler.

def get_regular_moves(state, pos):
    """Get all regular (non-jump) moves from a position."""
    piece = state.board[pos]   
    if PIECE_COLOR.get(piece) != state.turn:
        return [] # Nothing to return if the player doesn't have a piece at pos.
    
    # We check along all allowed directions, if the landing square is 
    # withing the bounds of the board and is empty.
    moves = []
    row, col = map_1d_to_2d(pos)
    for dr, dc in DIRECTIONS.get(piece, []): 
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < 8 and 0 <= new_col < 8:
            new_pos = map_2d_to_1d(new_row, new_col)
            if state.board[new_pos] == EMPTY:
                moves.append([pos, new_pos])
    return moves

# Test with a simple position
board = [EMPTY] * 32
board[13] = RED_PAWN  # Place a red pawn at position 13
state = GameState(board, RED)

moves = get_regular_moves(state, 13)
print(f"Regular moves from position 13: {moves}")

Regular moves from position 13: [[13, 17], [13, 16]]

Step 5: Available Moves: Multi-Hop Jump Chains¶

The key rule: if a jump is possible after landing, you must continue jumping.

def get_full_jump_chains(state, pos):
    """Get all complete jump chains from a given position (with mandatory continuation)."""    
    piece = state.board[pos]    
    if PIECE_COLOR.get(piece) != state.turn:
        return [] # Nothing to return if the player doesn't have a piece at pos.
    
    # Use BFS to explore all possible jump paths
    all_chains = []
    to_explore = [(state, [pos])]
    while to_explore:
        current_state, path = to_explore.pop(0)
        last_pos = path[-1]
        next_jumps = _get_one_hop_jumps(current_state, last_pos)
        
        if not next_jumps:
            # No more jumps possible - this is a complete chain
            if len(path) > 1:  # Must have at least one jump
                all_chains.append(path)
            continue
        
        # Explore each possible next jump
        for jump_pos in next_jumps:
            # Create new board state with the jump applied
            new_board = list(current_state.board)
            new_board[jump_pos] = new_board[last_pos]  # Move piece
            new_board[last_pos] = EMPTY
            
            # Remove the jumped piece
            r1, c1 = map_1d_to_2d(last_pos)
            r2, c2 = map_1d_to_2d(jump_pos)
            jumped_row, jumped_col = (r1 + r2) // 2, (c1 + c2) // 2
            jumped_pos = map_2d_to_1d(jumped_row, jumped_col)
            new_board[jumped_pos] = EMPTY
            
            new_state = GameState(new_board, current_state.turn)
            to_explore.append((new_state, path + [jump_pos]))
    
    return all_chains

# Test with a double jump scenario
board = [EMPTY] * 32
board[9] = RED_PAWN     # Red pawn
board[13] = WHITE_PAWN  # First white pawn to jump
board[22] = WHITE_PAWN  # Second white pawn to jump
state = GameState(board, RED)

chains = get_full_jump_chains(state, 9)
print(f"All complete jump chains from position 9: {chains}")

All complete jump chains from position 9: [[9, 16]]

Step 6: Legal Move Generation¶

We put together the last two functions to implement get_legal_moves(state). Here we implement the rule that regular move may be taken only if no jump rules are available to the player who has the turn.

def get_legal_moves(state):
    """Get all legal moves in the current state."""
    # First, check if any jumps are available from any position.
    all_jumps = []
    for i in range(32):
        chains = get_full_jump_chains(state, i)
        all_jumps.extend(chains)
    
    # If jumps exist, only return jumps (mandatory)
    if all_jumps:
        return all_jumps
    
    # Otherwise, return regular moves
    all_regular = []
    for i in range(32):
        moves = get_regular_moves(state, i)
        all_regular.extend(moves)
    return all_regular

# Test with initial position (should have regular moves)
board = [RED_PAWN] * 12 + [EMPTY] * 8 + [WHITE_PAWN] * 12
state = GameState(board, RED)

moves = get_legal_moves(state)
print(f"Number of legal moves from starting position: {len(moves)}")
print(f"First 3 moves: {moves[:3]}")

Number of legal moves from starting position: 7
First 3 moves: [[8, 13], [8, 12], [9, 14]]

Step 7: Applying Moves¶

So far we have implemented both a function that says when a move is legal and a function that returns all legal moves in a given game state. These are enough for a playing agent to decide what move to make. Now we need to implement the function that determines the next state after a move is made in the current game state.

Apply a move consists of making all the following changes to the current game state. Here we assume the move is a legal move.

1. Move the piece from start to end of the chain
2. Remove all jumped pieces
3. Promote to king if reaching the far row
4. Switch turns

def apply_move(state, move):
    """Apply a 'legal' move to a state and return the new state."""
    new_board = list(state.board)
    
    # 1. Move the piece from start to end
    start_pos = move[0]
    end_pos = move[-1]
    new_board[end_pos] = new_board[start_pos]
    new_board[start_pos] = EMPTY
    
    # 2. Remove jumped pieces (for each hop in the move)
    for i in range(len(move) - 1):
        r1, c1 = map_1d_to_2d(move[i])
        r2, c2 = map_1d_to_2d(move[i + 1])
        
        # Check if this is a jump (distance > 1)
        if abs(r2 - r1) > 1:
            jumped_row = (r1 + r2) // 2
            jumped_col = (c1 + c2) // 2
            jumped_pos = map_2d_to_1d(jumped_row, jumped_col)
            new_board[jumped_pos] = EMPTY
    
    # 3. King promotion
    if new_board[end_pos] == RED_PAWN and end_pos in range(28, 32):
        new_board[end_pos] = RED_KING
    elif new_board[end_pos] == WHITE_PAWN and end_pos in range(0, 4):
        new_board[end_pos] = WHITE_KING
    
    # 4. Switch turns
    next_turn = WHITE if state.turn == RED else RED
    
    return GameState(new_board, next_turn)

# Test: make a move from the initial position
board = [RED_PAWN] * 12 + [EMPTY] * 8 + [WHITE_PAWN] * 12
state = GameState(board, RED)

print("Before move:")
print(f"  Position 9: piece={state.board[9]}")
print(f"  Position 13: piece={state.board[13]}")
print(f"  Turn: {'RED' if state.turn == RED else 'WHITE'}")

new_state = apply_move(state, [9, 13])

print("\nAfter move [9, 13]:")
print(f"  Position 9: piece={new_state.board[9]}")
print(f"  Position 13: piece={new_state.board[13]}")
print(f"  Turn: {'RED' if new_state.turn == RED else 'WHITE'}")

Before move:
  Position 9: piece=1
  Position 13: piece=0
  Turn: RED

After move [9, 13]:
  Position 9: piece=0
  Position 13: piece=1
  Turn: WHITE

Runnable Artifact: Play a Few Moves¶

Let's put it all together and play through a sequence of moves.

def display_board(state):
    """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}")

# Start a game and make a few moves
board = [RED_PAWN] * 12 + [EMPTY] * 8 + [WHITE_PAWN] * 12
state = GameState(board, RED)

print("Initial position:")
display_board(state)

# Make a few moves
moves_sequence = [
    [9, 13],   # Red moves
    [22, 18],  # White moves
    [10, 14],  # Red moves
]

for move in moves_sequence:
    print(f"\nMove: {move}")
    state = apply_move(state, move)
    display_board(state)

print(f"\n✓ Successfully played {len(moves_sequence)} moves!")

Initial position:

  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

Move: [9, 13]

  0 1 2 3 4 5 6 7
0 . r . r . r . r 
1 r . r . r . r . 
2 . r .   . r . r 
3   . r .   .   . 
4 .   .   .   .   
5 w . w . w . w . 
6 . w . w . w . w 
7 w . w . w . w . 

Turn: WHITE

Move: [22, 18]

  0 1 2 3 4 5 6 7
0 . r . r . r . r 
1 r . r . r . r . 
2 . r .   . r . r 
3   . r .   .   . 
4 .   .   . w .   
5 w . w .   . w . 
6 . w . w . w . w 
7 w . w . w . w . 

Turn: RED

Move: [10, 14]

  0 1 2 3 4 5 6 7
0 . r . r . r . r 
1 r . r . r . r . 
2 . r .   .   . r 
3   . r . r .   . 
4 .   .   . w .   
5 w . w .   . w . 
6 . w . w . w . w 
7 w . w . w . w . 

Turn: WHITE

✓ Successfully played 3 moves!

Summary¶

In this chapter, we implemented move representation and game logic:

1. Move representation: List of positions (MoveChain) for both regular moves and jump chains
2. Rules of legal moves: Which moves are legal checkers moves
3. Regular move generation: Single diagonal steps to empty squares
4. Multi-hop jump chain generation: BFS exploration with mandatory jump continuation
5. Legal move generation: Jumps are mandatory when available
6. Applying moves: Creating new states with piece movement, captures, and king promotion

What's next?

In Chapter 3, we'll implement game ending conditions and the complete game loop.

Repo reference: The complete code is in core/logic.py [Repo to be published soon.]

📖 Next: Chapter 3