Welcome back to the PyMinMaximus series! In Part 1, we built move generation, in Part 2 we added minimax search, in Part 3 we created a sophisticated evaluation function, and in Part 4 we added the ability to search an opening book for a position. We can start a game strong and think deeply in the middle of the game, but now we need to address the other end of the game: endgames. In this post, we will create an endgame tablebase.
The Endgame Problem
Currently, PyMinMaximus struggles in simple endgames:
- King + Queen vs King: Takes 30-50 moves to mate (should be 10)
- King + Rook vs King: Often fails to mate within 50 moves
- KPK positions: Misses wins, doesn’t know theoretical draws
This is frustrating because these positions are solved – we know the perfect play! To address this, we can use an endgame tablebase.
What Are Endgame Tablebases?
An endgame tablebase is a pre-computed database that contains perfect play information for specific endgame positions. For every legal position with a given material configuration, the tablebase knows:
- The outcome (Win, Loss, or Draw)
- The distance to mate (DTM) – how many moves until mate with perfect play
Unlike game tree search (minimax), which computes positions on-demand, tablebases compute ALL positions once and store the results.
Syzygy Tablebases
Syzygy is the modern standard, created by Ronald de Man. Benefits:
- Compact size (compared to older Nalimov bases)
- Fast probing
- 6-piece tablebases fit in ~150GB
- Two types: WDL (outcome) and DTZ (distance)
However, Syzygy tablebases are very complex (primarily due to compression).
Simple Endgame Tablebase
We are interested in understanding how different parts of the chess engine work. Therefore, we are going to implement a simple tablebase. This is an educational implementation. This will not beat Stockfish, but it is useful for learning (and hopefully better than our engine without it). We will start with a 3 piece board (king + rook vs. king).
King + Rook vs King (we will refer to this as KRK) is perfect for learning tablebases because:
- ~447,888 legal positions – Small enough to compute quickly (~5 seconds)
- Simple material – Only 3 pieces to track
- Clear outcomes – Almost all positions are wins for White
- Known mate patterns – Easy to verify correctness
- Educational value – Teaches retrograde analysis fundamentals
How Tablebases Work
The key insight is retrograde analysis. Traditional game tree search works forward from a position, exploring possible moves. Retrograde analysis works backward from known outcomes.
The basic process is:
- Mark terminal positions: Checkmate = win, stalemate = draw
- Work backwards: If a position can reach a win in one move, it’s “win in 1”
- Iterate: Keep going until all positions are classified
Terminal Positions (Depth 0): checkmate or draw
↓
Positions leading to terminals (Depth 1)
↓
Positions leading to Depth 1 (Depth 2)
↓
... continue until all positions classified
In pseudocode:
Phase 1: Classify Terminal Positions
-------------------------------------
- Checkmate positions → Win in 0 moves
- Stalemate positions → Draw
Phase 2: Iterative Backward Propagation
----------------------------------------
For depth = 1, 2, 3, ... until convergence:
For each unsolved position:
Generate all legal moves
Check outcomes of resulting positions
If side to move is winning side:
If ANY move leads to a win → Position is a win
If ALL moves explored and none win → Draw
If side to move is losing side:
If ANY move leads to a draw → Position is a draw
If ALL moves lead to losses → Position is a lossImplementation Details
Position Encoding
Each position is encoded as a tuple:
(white_king_square, white_rook_square, black_king_square, white_to_move)Symmetry Reduction: We use horizontal mirroring to halve the storage:
- If White king is on the right half of the board (files e-h), mirror everything to the left
This reduces ~524,288 theoretical positions to ~447,888 legal positions.
Illegal Position Filtering
Positions are illegal if:
- Two pieces occupy the same square
- The two kings are adjacent (within 1 square)
Move Generation
The implementation includes:
- King moves: All 8 directions
- Rook moves: Sliding along ranks and files until blocked
- Attack detection: Check if a square is under attack
Outcome Classification
Terminal Positions (Depth 0):
- Checkmate: Black king in check with no legal moves
- Stalemate: Black king not in check but with no legal moves
Non-terminal Positions:
- White to move: Win if ANY move leads to a won position
- Black to move: Draw if ANY move leads to a drawn position
Interesting Findings
- Maximum mate in 6: The longest forced mate is only 6 moves! This happens when:
- Black king is in a corner (e.g., a1)
- White pieces are on the opposite side
- White must methodically drive the king to the edge
- 184 stalemate positions: Very rare in KRK, mostly corner positions where:
- Black king is trapped (a1, a8, h1, or h8)
- Rook blocks escape but doesn’t give check
- White king controls remaining squares
Generate the Tablebase
Now that we know the theory, how do we implement? We will create a class called KRKTablebase. We start with a few constants (draw, white_win, black_win). We also create a dictionary to hold the table and a counter for the number of positions solved.
#krk_tablebase.py
from constants import *
class KRKTablebase:
# Outcome constants
UNKNOWN = 0
DRAW = 1
WHITE_WIN = 2
BLACK_WIN = 3 # Shouldn't occur in KRK, but included for completeness
def __init__(self):
"""Initialize the tablebase."""
# Dictionary mapping position keys to (outcome, depth)
# outcome: DRAW or WHITE_WIN
# depth: moves to mate (DTM - Distance To Mate)
self.table = {}
self.positions_solved = 0Next, we create two methods that allow us to convert a board position into an index (0-63) and back to a board position.
# .. continued from class KRKTablebase
def square_to_coords(self, square):
"""Convert square index (0-63) to (row, col)."""
return (square // 8, square % 8)
def coords_to_square(self, row, col):
"""Convert (row, col) to square index (0-63)."""
if not (0 <= row < 8 and 0 <= col < 8):
return None
return row * 8 + colWe then create a method to encode a given position into the tuple referenced above.
def encode_position(self, wk_sq, wr_sq, bk_sq, white_to_move):
"""
Encode position as a unique key.
We use horizontal mirroring symmetry to reduce storage.
"""
# Apply horizontal mirroring if king is on right half
wk_row, wk_col = self.square_to_coords(wk_sq)
wr_row, wr_col = self.square_to_coords(wr_sq)
bk_row, bk_col = self.square_to_coords(bk_sq)
if wk_col > 3: # Mirror if on right half
wk_col = 7 - wk_col
wr_col = 7 - wr_col
bk_col = 7 - bk_col
wk_sq = self.coords_to_square(wk_row, wk_col)
wr_sq = self.coords_to_square(wr_row, wr_col)
bk_sq = self.coords_to_square(bk_row, bk_col)
return (wk_sq, wr_sq, bk_sq, white_to_move)We check whether a position is a legal position. When considering KRK, this is incredibly simplified from the main engine. None of the pieces can be on the same square and kings can’t be beside each other.
def is_legal_position(self, wk_sq, wr_sq, bk_sq):
"""Check if position is legal (no overlapping pieces)."""
if wk_sq == wr_sq or wk_sq == bk_sq or wr_sq == bk_sq:
return False
# Kings can't be adjacent
wk_row, wk_col = self.square_to_coords(wk_sq)
bk_row, bk_col = self.square_to_coords(bk_sq)
row_diff = abs(wk_row - bk_row)
col_diff = abs(wk_col - bk_col)
if row_diff <= 1 and col_diff <= 1:
return False
return TrueNext, we add two methods to check whether a square is attacked by a rook or a king.
def is_attacked_by_rook(self, rook_sq, target_sq, blocking_sq=None):
"""Check if rook attacks a square (with optional blocking piece)."""
r_row, r_col = self.square_to_coords(rook_sq)
t_row, t_col = self.square_to_coords(target_sq)
# Rook must be on same rank or file
if r_row != t_row and r_col != t_col:
return False
# Check for blocking piece
if blocking_sq is not None:
b_row, b_col = self.square_to_coords(blocking_sq)
# If moving horizontally
if r_row == t_row:
min_col = min(r_col, t_col)
max_col = max(r_col, t_col)
# Blocker must be on same row and between rook and target
if b_row == r_row and min_col < b_col < max_col:
return False
# If moving vertically
else:
min_row = min(r_row, t_row)
max_row = max(r_row, t_row)
if b_col == r_col and min_row < b_row < max_row:
return False
return True
def is_attacked_by_king(self, king_sq, target_sq):
"""Check if king attacks a square."""
k_row, k_col = self.square_to_coords(king_sq)
t_row, t_col = self.square_to_coords(target_sq)
return abs(k_row - t_row) <= 1 and abs(k_col - t_col) <= 1We add two methods to generate the positions for kings and rooks.
def generate_king_moves(self, king_sq, occupied_squares):
"""Generate all legal king moves from a square."""
moves = []
k_row, k_col = self.square_to_coords(king_sq)
for drow in [-1, 0, 1]:
for dcol in [-1, 0, 1]:
if drow == 0 and dcol == 0:
continue
new_row = k_row + drow
new_col = k_col + dcol
new_sq = self.coords_to_square(new_row, new_col)
if new_sq is not None and new_sq not in occupied_squares:
moves.append(new_sq)
return moves
def generate_rook_moves(self, rook_sq, occupied_squares):
"""Generate all legal rook moves from a square."""
moves = []
r_row, r_col = self.square_to_coords(rook_sq)
# Horizontal moves
for dcol in [-1, 1]:
col = r_col + dcol
while 0 <= col < 8:
sq = self.coords_to_square(r_row, col)
if sq in occupied_squares:
break
moves.append(sq)
col += dcol
# Vertical moves
for drow in [-1, 1]:
row = r_row + drow
while 0 <= row < 8:
sq = self.coords_to_square(row, r_col)
if sq in occupied_squares:
break
moves.append(sq)
row += drow
return movesWe check for terminal positions.
def is_checkmate(self, wk_sq, wr_sq, bk_sq):
"""
Check if black king is checkmated.
Black is in check and has no legal moves.
"""
# Black king must be in check from rook
if not self.is_attacked_by_rook(wr_sq, bk_sq, wk_sq):
return False
# Check if black king has any legal moves
occupied = {wk_sq, wr_sq}
black_king_moves = self.generate_king_moves(bk_sq, occupied)
for bk_new_sq in black_king_moves:
# Can't move into check from white king
if self.is_attacked_by_king(wk_sq, bk_new_sq):
continue
# Can't move into check from rook
if self.is_attacked_by_rook(wr_sq, bk_new_sq, wk_sq):
continue
# Found a legal move - not checkmate
return False
# No legal moves - checkmate!
return True
def is_stalemate(self, wk_sq, wr_sq, bk_sq):
"""
Check if black king is stalemated.
Black is NOT in check but has no legal moves.
"""
# Black king must NOT be in check from rook
if self.is_attacked_by_rook(wr_sq, bk_sq, wk_sq):
return False
# Black king must NOT be in check from white king (shouldn't happen but check anyway)
if self.is_attacked_by_king(wk_sq, bk_sq):
return False
# Check if black king has any legal moves
occupied = {wk_sq, wr_sq}
black_king_moves = self.generate_king_moves(bk_sq, occupied)
# If no squares to move to at all, it's stalemate
if len(black_king_moves) == 0:
return True
for bk_new_sq in black_king_moves:
# Can't move into check from white king
if self.is_attacked_by_king(wk_sq, bk_new_sq):
continue
# Can't move into check from rook
if self.is_attacked_by_rook(wr_sq, bk_new_sq, wk_sq):
continue
# Found a legal move - not stalemate
return False
# No legal moves but not in check - stalemate!
return TrueThe next method generates all legal positions. This simply loops over all three pieces and all positions on the board. Before adding the position to the list, we check whether it is legal.
def generate_all_positions(self):
"""Generate all legal KRK positions."""
positions = []
for wk_sq in range(64):
for wr_sq in range(64):
for bk_sq in range(64):
if not self.is_legal_position(wk_sq, wr_sq, bk_sq):
continue
# Both sides to move
positions.append((wk_sq, wr_sq, bk_sq, True)) # White to move
positions.append((wk_sq, wr_sq, bk_sq, False)) # Black to move
return positionsOnce we have generated all of the positions, next we find which of these positions are terminal (checkmate or stalemate). If yes, then we add to the solved table dictionary (the key is the encoded position).
def classify_terminal_positions(self, positions):
"""
Phase 1: Classify all terminal positions (checkmate, stalemate).
Returns number of positions classified.
"""
count = 0
for wk_sq, wr_sq, bk_sq, white_to_move in positions:
key = self.encode_position(wk_sq, wr_sq, bk_sq, white_to_move)
if key in self.table:
continue
# Check for checkmate (black is mated)
if self.is_checkmate(wk_sq, wr_sq, bk_sq):
self.table[key] = (self.WHITE_WIN, 0)
count += 1
continue
# Check for stalemate (only when black to move)
if not white_to_move and self.is_stalemate(wk_sq, wr_sq, bk_sq):
self.table[key] = (self.DRAW, 0)
count += 1
continue
return countNow, we are to the heart of the tablebase generation process. We now need to conduct the retrograde analysis. For each unsolved position (i.e., the encoded position is not in the solved table):
- Generate the legal moves
- If any of those legal moves lead to a solved position then we record this position in the table with the current depth
def retrograde_iteration(self, positions, current_depth):
"""
Single iteration of retrograde analysis.
For each unsolved position:
- Generate all legal moves
- Check outcomes of resulting positions
- If we can force a mate, mark this position with current_depth
Returns number of new positions solved.
"""
newly_solved = 0
for wk_sq, wr_sq, bk_sq, white_to_move in positions:
key = self.encode_position(wk_sq, wr_sq, bk_sq, white_to_move)
# Skip if already solved
if key in self.table:
continue
if white_to_move:
# White to move - looking for winning moves
can_win = False
all_moves_solved = True
occupied = {bk_sq}
# Try white king moves
wk_moves = self.generate_king_moves(wk_sq, occupied)
for wk_new_sq in wk_moves:
# Can't move into check from rook's original position
if self.is_attacked_by_rook(wr_sq, wk_new_sq, bk_sq):
continue
if not self.is_legal_position(wk_new_sq, wr_sq, bk_sq):
continue
next_key = self.encode_position(wk_new_sq, wr_sq, bk_sq, False)
if next_key not in self.table:
all_moves_solved = False
elif self.table[next_key][0] == self.WHITE_WIN:
can_win = True
break
if can_win:
self.table[key] = (self.WHITE_WIN, current_depth)
newly_solved += 1
continue
# Try white rook moves
if not can_win:
occupied_with_king = {wk_sq, bk_sq}
wr_moves = self.generate_rook_moves(wr_sq, occupied_with_king)
for wr_new_sq in wr_moves:
if not self.is_legal_position(wk_sq, wr_new_sq, bk_sq):
continue
# Check if this move gives check
gives_check = self.is_attacked_by_rook(wr_new_sq, bk_sq, wk_sq)
# If black is in check, verify it's legal (white king not in check)
if gives_check:
if self.is_attacked_by_king(bk_sq, wk_sq):
continue # Illegal - white king in check
next_key = self.encode_position(wk_sq, wr_new_sq, bk_sq, False)
if next_key not in self.table:
all_moves_solved = False
elif self.table[next_key][0] == self.WHITE_WIN:
can_win = True
break
if can_win:
self.table[key] = (self.WHITE_WIN, current_depth)
newly_solved += 1
elif all_moves_solved:
# All moves explored, none win - this is a draw
self.table[key] = (self.DRAW, 0)
newly_solved += 1
else:
# Black to move - can black force a draw or does white win?
can_draw = False
all_moves_lose = True
occupied = {wk_sq, wr_sq}
bk_moves = self.generate_king_moves(bk_sq, occupied)
for bk_new_sq in bk_moves:
# Can't move into check from white king
if self.is_attacked_by_king(wk_sq, bk_new_sq):
continue
# Can't move into check from rook
if self.is_attacked_by_rook(wr_sq, bk_new_sq, wk_sq):
continue
next_key = self.encode_position(wk_sq, wr_sq, bk_new_sq, True)
if next_key not in self.table:
all_moves_lose = False
elif self.table[next_key][0] == self.DRAW:
can_draw = True
break
if can_draw:
self.table[key] = (self.DRAW, 0)
newly_solved += 1
elif all_moves_lose:
# All moves lead to white win - this is a white win
self.table[key] = (self.WHITE_WIN, current_depth)
newly_solved += 1
return newly_solvedFor code this complicated, I need a flow chart:
The next code generates the tablebase. First, we generate all terminal positions. Then for each terminal position, we conduct the retrograde analysis at increasing depths. Once the retrograde analysis returns 0 (no new positions found at that depth), we are done.
def generate(self):
"""
Generate the complete KRK tablebase using retrograde analysis.
"""
print("Generating KRK Tablebase...")
print("=" * 60)
# Generate all legal positions
print("Generating all legal positions...")
positions = self.generate_all_positions()
print(f"Total legal positions: {len(positions):,}")
# Phase 1: Classify terminal positions
print("\nPhase 1: Classifying terminal positions...")
terminal_count = self.classify_terminal_positions(positions)
print(f"Terminal positions found: {terminal_count:,}")
print(f" - Checkmates and stalemates")
# Phase 2: Retrograde analysis
print("\nPhase 2: Retrograde analysis...")
depth = 1
max_depth = 100 # Safety limit
while depth <= max_depth:
newly_solved = self.retrograde_iteration(positions, depth)
if newly_solved == 0:
print(f"\nConverged at depth {depth}")
break
total_solved = len(self.table)
percentage = (total_solved / len(positions)) * 100
print(f"Depth {depth:2d}: +{newly_solved:5,} new positions "
f"(Total: {total_solved:6,} / {len(positions):,} = {percentage:5.1f}%)")
depth += 1
# Summary
print("\n" + "=" * 60)
print("Tablebase Generation Complete!")
print("=" * 60)
print(f"Total positions: {len(positions):,}")
print(f"Positions solved: {len(self.table):,}")
print(f"Maximum depth: {depth - 1}")
# Statistics
wins = sum(1 for outcome, _ in self.table.values() if outcome == self.WHITE_WIN)
draws = sum(1 for outcome, _ in self.table.values() if outcome == self.DRAW)
print(f"\nOutcome distribution:")
print(f" White wins: {wins:,} ({wins/len(self.table)*100:.1f}%)")
print(f" Draws: {draws:,} ({draws/len(self.table)*100:.1f}%)")
# Find longest mate
max_dtm = max((depth for outcome, depth in self.table.values()
if outcome == self.WHITE_WIN), default=0)
print(f"\nLongest forced mate: {max_dtm} moves")Next, we add two methods to probe the database from a given board position.
def probe(self, wk_sq, wr_sq, bk_sq, white_to_move):
"""
Look up a position in the tablebase.
Returns: (outcome, depth) or None if position is illegal/not in tablebase
"""
if not self.is_legal_position(wk_sq, wr_sq, bk_sq):
return None
key = self.encode_position(wk_sq, wr_sq, bk_sq, white_to_move)
return self.table.get(key)
def probe_from_board(self, board):
"""
Probe the tablebase from a Board object.
Only works if the position is a KRK endgame.
"""
# Count pieces
white_king = None
white_rook = None
black_king = None
piece_count = 0
for row in range(8):
for col in range(8):
piece = board.board[row][col]
if piece == EMPTY:
continue
piece_count += 1
piece_type = piece & 7
color = piece & 24
if piece == (WHITE | KING):
white_king = self.coords_to_square(row, col)
elif piece == (WHITE | ROOK):
white_rook = self.coords_to_square(row, col)
elif piece == (BLACK | KING):
black_king = self.coords_to_square(row, col)
# Must be exactly 3 pieces: WK, WR, BK
if piece_count != 3 or white_king is None or white_rook is None or black_king is None:
return None
white_to_move = (board.to_move == WHITE)
return self.probe(white_king, white_rook, black_king, white_to_move)Finally, we add methods to save and load the tablebase. We don’t need to run the table generation every time. We just need to run it once and save it. When we use the engine, we will simply load the tablebase.
def save(self, filename):
"""Save tablebase to file."""
import pickle
with open(filename, 'wb') as f:
pickle.dump(self.table, f)
print(f"\nTablebase saved to {filename}")
print(f"File size: {len(pickle.dumps(self.table)) / 1024 / 1024:.2f} MB")
def load(self, filename):
"""Load tablebase from file."""
import pickle
with open(filename, 'rb') as f:
self.table = pickle.load(f)
print(f"Tablebase loaded from {filename}")
print(f"Positions in tablebase: {len(self.table):,}")Now that we have the code, generating the database is easy:
from krk_tablebase import KRKTablebase
tb = KRKTablebase()
tb.generate()
tb.save("krktablebase.pkl")Integrating with Search
Next, we need to integrate into our SearchEngine class. For simplicity, I am not including all existing code in search.
Step 1: Load the Tablebase
In the SearchEngine constructor, we include code to load the tablebase. We create a wrapper method within SearchEngine that tries to load an existing tablebase. If the file doesn’t exist, then we generate it.
# search.py
from krk_tablebase import KRKTablebase
class SearchEngine:
def __init__(self, board, evaluator=None):
self.board = board
self.evaluator = evaluator if evaluator else Evaluator()
self.nodes_searched = 0
self.tt = TranspositionTable()
# Opening book
self.book = OpeningBook('books/kasparov.bin')
# Add tablebase
self.krk_tablebase = None
self.load_tablebases()
def load_tablebases(self):
"""Load endgame tablebases"""
try:
self.krk_tablebase = KRKTablebase()
self.krk_tablebase.load("tablebase/krk_tablebase.pkl")
print("KRK tablebase loaded successfully")
except:
# Generate if not found
print("Generating KRK tablebase...")
self.krk_tablebase = KRKTablebase()
self.krk_tablebase.generate()
self.krk_tablebase.save("tablebase/krk_tablebase.pkl")Step 2: Detect Tablebase Positions
We add a method to check if current position is in tablebase:
def is_tablebase_position(self, board):
"""Check if position is in a tablebase"""
# Count pieces and material
piece_count = 0
white_pieces = []
black_pieces = []
for row in range(8):
for col in range(8):
piece = board.board[row][col]
if piece != EMPTY:
piece_count += 1
if (piece & 24) == WHITE:
white_pieces.append(piece & 7)
else:
black_pieces.append(piece & 7)
# Check for KRK
if piece_count == 3:
white_pieces.sort()
black_pieces.sort()
# White has K+R, Black has K
if white_pieces == [KING, ROOK] and black_pieces == [KING]:
return 'KRK_white'
# Black has K+R, White has K (flip the board mentally)
if white_pieces == [KING] and black_pieces == [KING, ROOK]:
return 'KRK_black'
return NoneStep 3: Probe the Tablebase and Get the Best Move
Add a method to query the tablebase and if the position is in the tablebase, get the best move.
def probe_tablebase(self, board):
"""
Probe endgame tablebases.
Returns (score, best_move) or None if not in tablebase.
"""
tb_type = self.is_tablebase_position(board)
if tb_type is None:
return None
if tb_type == 'KRK_white':
# Query KRK tablebase
result = self.krk_tablebase.probe_from_board(board)
if result is None:
return None
outcome, dtm = result
if outcome == self.krk_tablebase.WHITE_WIN:
# Convert DTM to score
# Use high score that decreases with distance
score = 19000 - dtm
else: # DRAW
score = 0
# Find the best move that maintains this outcome
best_move = self.find_tablebase_best_move(board, outcome, dtm)
return (score, best_move)
elif tb_type == 'KRK_black':
# Flip perspective for black
result = self.krk_tablebase.probe_from_board(board)
if result is None:
return None
outcome, dtm = result
if outcome == self.krk_tablebase.WHITE_WIN:
# Black is losing
score = -(19000 - dtm)
else:
score = 0
best_move = self.find_tablebase_best_move(board, outcome, dtm)
return (score, best_move)
return None
def find_tablebase_best_move(self, board, target_outcome, current_dtm):
"""
Find the best move according to the tablebase.
Looks for moves that maintain winning path or quickest mate.
"""
moves = board.generate_legal_moves()
best_move = None
best_dtm = float('inf')
for move in moves:
undo_info = board.make_move(move)
# Query position after move
result = self.krk_tablebase.probe_from_board(board)
board.unmake_move(move, undo_info)
if result is None:
continue
outcome, dtm = result
# If we're winning, look for quickest mate
if outcome == target_outcome:
if outcome == self.krk_tablebase.WHITE_WIN:
# Want smallest DTM (quickest mate)
if dtm < best_dtm:
best_dtm = dtm
best_move = move
else: # DRAW
best_move = move
break # Any drawing move is fine
return best_moveStep 4: Integrate with Search
Modify your alpha-beta search to check tablebase first:
def alphabeta(self, depth, alpha, beta, maximizing_player):
"""
Alpha-beta with transposition table.
"""
# Check tablebase FIRST (before any search)
piece_count = sum(1 for row in self.board.board for p in row if p != EMPTY)
if piece_count <= 5:
tb_result = self.probe_tablebase(self.board)
if tb_result is not None:
score, _ = tb_result
# Return from current player's perspective
if not maximizing_player:
score = -score
return scoreWe also need to modify the root search.
def find_best_move_alphabeta(self, depth):
"""
Find the best move using alpha-beta pruning.
"""
# Check opening book
if self.book.is_in_book(self.board):
moves = self.board.generate_legal_moves()
book_move = self.book.get_book_move(self.board,len(self.board.move_stack))
for move in moves:
if str(move) == book_move:
return move, 1000
# Check tablebase
piece_count = sum(1 for row in self.board.board for p in row if p != EMPTY)
if piece_count <= 5:
tb_result = self.probe_tablebase(self.board)
if tb_result is not None:
score, best_move = tb_result
if best_move is not None:
print(f"Tablebase: {best_move} (score: {score})")
return best_move, scoreUsage Example
Here is a quick example:
from board import Board
from search import SearchEngine
# Create board and search engine
board = Board()
engine = SearchEngine(board)
# Set up a KRK position
board.from_fen("4k3/8/8/8/8/8/4K3/4R3 w - - 0 1")
# Search will automatically use tablebase
best_move, score = engine.find_best_move_alphabeta(5)
print(f"Best move: {best_move}")
print(f"Evaluation: {score}")Performance Considerations
Our simplistic implementation of one tablebase is very efficient.
- KRK tablebase: ~3.4 MB (pickled)
- Keep in memory for fast access
If we wanted to create more tablebases, we would need more sophisticated compression. Below are tables that show the size of different tablebases and how much memory to store various numbers of remaining pieces.
3-Piece Tablebases
| Tablebase | Positions | Our Size (Pickle) | Syzygy Size | Ratio |
| KRK | 223,944 | 3.4 MB | ~0.1 MB | 5x larger |
| KQK | 223,944 | 3.4 MB | ~0.1 MB | 5x larger |
| KBK | 111,972 | 1.7 MB | ~0.05 MB | 6x larger |
| KNK | 111,972 | 1.7 MB | ~0.05 MB | 6x larger |
For KRK, we only need 3.4 MB, which is manageable. However, it is already 5 times larger than Syzygy. If we look at storage needs up to 6 pieces, we really see the difference.
Summary Chart: Total Storage Needs
| Pieces | Total Positions | Pickle (Ours) | Syzygy | Feasibility |
| 3-piece | ~1M | 10 MB | 0.3 MB | ✅ Easy |
| 4-piece | ~240M | 7.5 GB | 200 MB | ✅ Manageable |
| 5-piece | ~28B | 461 GB | 7.1 GB | ⚠️ Challenging |
| 6-piece | ~150B | 2.4 TB | 150 GB | ❌ Syzygy only |
| 7-piece | ~500B | 8+ TB | 140 GB | ❌ Syzygy only |
Key Takeaways
- Tablebases use different algorithm than search
- Retrograde analysis vs forward minimax
- Pre-computation vs on-demand
- They provide perfect play
- No search errors
- Optimal moves guaranteed
- Exact mate distances
- Scalability is the challenge
- 3 pieces: trivial
- 5 pieces: manageable
- 7 pieces: challenging
- 8+ pieces: impractical
- Implementation teaches fundamentals
- Position encoding
- Symmetry reduction
- Retrograde algorithms
- Storage optimization
Resources for Further Learning
Papers
- Thompson (1986): “Retrograde Analysis of Certain Endgames”
- Heinz (2000): “Endgame Databases and Efficient Index Schemes”
Code
- Syzygy: https://github.com/syzygy1/tb
- python-chess tablebase support
Databases
- Lichess tablebase: https://syzygy-tables.info
- ChessBase endgame database
What We’ve Accomplished
In this part, we’ve transformed PyMinMaximus into a complete chess player:
✅ Endgame tablebases – Perfect endgame play
✅ Smart integration – Book → Tablebase → Search hierarchy
✅ Enhanced interface – Information-rich game display
✅ Performance gains – Measurable strength improvement
Complete Code Structure
Your final project structure:
pyminmaximus/
├── constants.py # Piece and color constants
├── move.py # Move class
├── board.py # Board representation
├── evaluation.py # Position evaluation
├── search.py # Search with book/tablebase integration
├── zobrist.py # Zobrist hashing
├── opening_book.py # Polyglot book reader
├── book_creator.py # Custom book creation
├── krk_tablebase.py # Generate, Save, and Load a king + rook and king tablebase
Next Steps
In Part 6 (our finale), we’ll:
- Implement the UCI protocol
- Test PyMinMaximus with CuteChess CLI
- Get accurate strength measurements
- Compare against other engines
- Calculate final ELO rating
We’ve built the knowledge base—next we’ll integrate it into the engine!
Questions about tablebases? Built your own tablebase? Share in the comments!
Visited 12 times, 1 visit(s) today
