Blokus Duo: Deep Search & Reinforcement Learning for a Combinatorial Board Game

The board is a 14×14 list of integers. Each player tracks their available "possible squares," the corner positions where a new piece could legally be anchored, which are incrementally updated rather than recomputed from scratch each turn.

# Board is stored as a 14x14 grid of integers:
#   0 = empty  |  1 = Player 1  |  2 = Player 2
self.board = [[0 for _ in range(s)] for _ in range(s)]

# Each player's reachable corner positions:
# format: [x, y, [NE_open, SE_open, SW_open, NW_open]]
self.possible_squares = [
    [[4, 4, [True, True, True, True]]],    # P1 starts at (5,10)
    [[s-5, s-5, [True, True, True, True]]] # P2 starts at (10,5)
]

# Each player's remaining piece inventory (IDs 0-20)
self.inv = [
    list(range(21)),  # Player 1
    list(range(21))   # Player 2
]

self.score = [0, 0]   # tiles placed by each player

Move generation is the performance-critical path. Rather than scanning the whole board, it iterates only over pre-tracked "possible squares" (corner attachment points) and checks each piece/orientation combination against placement rules.

def calculateLegalMoves(self, only_fives_rounds=0):
    legal_placements = []
    # Iterate only over proven corner attachment points
    for x, y, [NE, SE, SW, NW] in self.possible_squares[self.turn - 1]:
        if self.board[y][x] != 0:
            continue   # already occupied
        if self.turn in self.getEdgesValues(x, y):
            continue   # would share an edge with own piece

        for piece_num in self.inv[self.turn - 1]:
            for orientation in piece_possible_orientations[piece_num]:
                piece_def = pieces[piece_num][orientation]
                # Try anchoring at each block of the piece
                for dir_idx in range(4):
                    for pieceBlock in piece_def[dir_idx + 1]:
                        center = [x - pieceBlock[0], y - pieceBlock[1]]
                        # validate all squares of the piece from this center
                        # ... (bounds + edge + corner checks)
                        legal_placements.append([center[0], center[1],
                                                 piece_num, orientation])
    return legal_placements

For RL training the board is flattened to a 1-D integer array and concatenated with the piece inventory. The observation is always returned from the current agent's perspective. Player 2's view is a board-flipped mirror of Player 1's, so a single policy network can handle both roles.

# Observation space definition (per agent)
self.observation_spaces = {
    i: spaces.Dict({
        # 196 board cells (0/1/2) + 42 piece-availability bits
        "observation": spaces.MultiDiscrete([3]*196 + [2]*42, dtype=np.int8),
        # One binary flag per possible (x, y, piece, orientation) combo
        "action_mask": spaces.MultiBinary(14 * 14 * 21 * 8),
    })
    for i in self.agents
}

def observe(self, agent):
    # Map agent IDs -> board encoding perspective (1 or -1)
    perspective = 1 if agent == 0 else -1
    # Piece availability matrix: shape [2, 21], agent-first ordering
    piecesMB = np.zeros([2, 21])
    for piece in range(21):
        if piece in self.board.inv[0]: piecesMB[0][piece] = 1
        if piece in self.board.inv[1]: piecesMB[1][piece] = 1
    if perspective == -1:
        piecesMB = piecesMB[::-1]   # swap so agent's own pieces come first

    return {
        # Flipped board (agent sees itself as "1") + inventory
        "observation": np.concatenate((
            np.array(self.board.get_flipped_board(perspective)).flatten(),
            piecesMB.flatten()
        )).astype(np.int8),
        "action_mask": self.genActionMask(),
    }

The full action space has 14 × 14 × 21 × 8 = 32,928 discrete indices. The discreteToAction / actionToDiscrete pair provides a fast bijection between integer indices and human-readable (x, y, piece, orientation) tuples.

# Total action space: 14 x-coords x 14 y-coords x 21 pieces x 8 orientations
ACTION_SPACE_SIZE = 14 * 14 * 21 * 8  # = 32,928

def discreteToAction(action: int) -> tuple:
    """Convert a flat integer index to (x, y, piece, orientation)."""
    x = action // (14 * 21 * 8)
    action %= (14 * 21 * 8)
    y = action // (21 * 8)
    action %= (21 * 8)
    piece = action // 8
    orientation = action % 8
    return (x, y, piece, orientation)

def actionToDiscrete(action: tuple) -> int:
    """Convert (x, y, piece, orientation) back to a flat index."""
    return (((action[0] * 14 + action[1]) * 21 + action[2]) * 8) + action[3]

Algorithm 4: PPO (MaskablePPO via Stable-Baselines 3)

The RL environment wraps Board inside a PettingZoo AECEnv, training both agents sequentially. Stable-Baselines3's MaskablePPO applies the action mask at every step so illegal moves are never sampled.

# Training entry point (PPO/aecTrain.py)
model = MaskablePPO(
    MaskableActorCriticPolicy,
    env,                         # SB3ActionMaskWrapper(BlokusEnv)
    verbose=1,
    device='cuda',
    learning_rate=0.001,         # Adam optimizer
    ent_coef=0.005,              # entropy bonus to encourage exploration
)

# Load checkpoint if continuing a training run
if i > 0:
    model = model.load(f"final_models/final_model_{i-1}.zip")
    model.set_env(env)

model.learn(total_timesteps=steps)   # ~100,000 steps ~= 4,000 games
model.save(f"final_models/final_model_{i}.zip")