Ant Colony Optimization + Genetic Algorithm — Hybrid Chess Engine
A Python chess engine combining classical alpha-beta search with bio-inspired optimisation (ACO/GA), spectral graph analysis via PyTorch, and game-theoretic root filtering. Features a PyQt5 GUI for interactive play.
flowchart TB
subgraph GUI["gui.py — PyQt5 Interface"]
UI[ChessWindow<br/>8x8 Board Grid]
AIW[AIWorker<br/>QThread]
end
subgraph GB["gameboard.py — State Engine"]
STATE[GameBoard<br/>8x8 board, Zobrist hash,<br/>king cache, EP tracking]
LEGAL[Legal Move Gen<br/>Pin-aware, ray-scan<br/>check detection]
SIM["Simulate / Unsimulate<br/>O(1) Zobrist, snapshot-based"]
end
subgraph SPEC["specturalchessboard.py — Spectral Features"]
GRAPH[SpectralChessGraph<br/>64x64 adjacency matrices<br/>attack + defense]
EIGEN[Eigendecomposition<br/>Fiedler, entropy,<br/>centrality, clustering]
INC[Incremental Update<br/>Rebuild affected rows only]
end
subgraph AI["acoga.py — Decision Layer"]
ROOT[Game-Theoretic<br/>Root Pipeline]
AB[Alpha-Beta + PVS<br/>+ NMP + LMR]
QS[Quiescence Search<br/>Captures + checks +<br/>check evasions]
EVAL[Evaluation Core<br/>Material, PST, mobility,<br/>king safety, king attack,<br/>pawn struct, spectral,<br/>entropy, NN]
ACO[Ant Colony<br/>Pheromone memory]
GA[Weight Evolver<br/>Genetic Algorithm]
end
subgraph PIECES["pieces.py — Piece Definitions"]
P[King Queen Rook<br/>Bishop Knight Pawn]
end
UI -->|user click| STATE
UI -->|start search| AIW
AIW -->|clone board| STATE
AIW -->|pick_best_move| ROOT
ROOT --> AB
AB --> QS
AB --> EVAL
QS --> EVAL
EVAL --> GRAPH
EVAL --> EIGEN
STATE --> SIM
SIM --> INC
ROOT -->|maximin / dominated| EVAL
ACO -->|pheromone priors| ROOT
GA -->|tuned weights| EVAL
LEGAL --> P
STATE --> LEGAL
flowchart TD
START([pick_best_move called]) --> CHECK{Only 1<br/>legal move?}
CHECK -->|Yes| RET1([Return that move])
CHECK -->|No| POOL[Candidate Pool<br/>Top 8 by move ordering]
POOL --> MAXIMIN[Maximin Root Filter<br/>For each candidate:<br/>simulate move, get top 4<br/>opponent replies, compute<br/>worst-case + mean score]
MAXIMIN --> SHALLOW[Shallow Eval + Safety<br/>1-ply leaf eval and<br/>spectral safety score<br/>per candidate]
SHALLOW --> DOM[Dominated-Move<br/>Elimination<br/>Remove moves dominated<br/>on all dimensions]
DOM --> SORT[Sort Survivors by<br/>maximin, shallow, safety]
SORT --> TOP4[Keep Top 4<br/>Survivors]
TOP4 --> ID[Iterative Deepening<br/>depth 1 .. N]
subgraph SEARCH["Alpha-Beta Search"]
ID --> ABR[Root Subset<br/>Alpha-Beta]
ABR --> PVS[PVS: first move full window<br/>later moves null-window scout<br/>re-search on fail-high]
PVS --> NMP{Null Move<br/>Pruning?}
NMP -->|Yes| NULLS[Reduced-depth search<br/>skip a move]
NMP -->|No| LMR{Late Move<br/>Reduction?}
NULLS --> LMR
LMR -->|Yes| REDS[Reduced-depth search<br/>re-search if beats alpha]
LMR -->|No| FULL[Full-depth search]
REDS --> LEAF{depth <= 0?}
FULL --> LEAF
LEAF -->|Yes| QUIES[Quiescence Search<br/>captures + checks +<br/>check evasions<br/>stand-pat pruning]
LEAF -->|No| ABR
end
QUIES --> EVALNODE[Evaluate Position]
EVALNODE --> TT[Store in<br/>Transposition Table]
TT --> BEST([Return best move])
ID --> PHER[Reinforce Pheromone<br/>along best line]
PHER --> BEST
flowchart LR
subgraph INPUT["Inputs"]
BOARD[Board State<br/>8x8 grid]
COLOR[AI Color]
DEPTH[Search Depth]
end
subgraph MOVEORD["Move Ordering Data"]
TT_TABLE[(Transposition<br/>Table<br/>262K entries)]
KILL[(Killer Moves<br/>2 per ply)]
HIST[(History<br/>Heuristic<br/>64x64)]
PHER_TABLE[(Pheromone<br/>Table<br/>from/to -> float)]
end
subgraph EVALDATA["Evaluation Features"]
MAT[Material<br/>Count]
PST_SCORE[Piece-Square<br/>Tables]
MOB[Mobility &<br/>Centre Control]
KS[King Safety<br/>Pawn shield +<br/>zone attacks]
PS[Pawn Structure<br/>Passed, isolated,<br/>doubled, connected]
SP[Spectral<br/>Advantage<br/>8 sub-features]
ENT[Phase-Aware<br/>Entropy]
NN[SpectralEvalNet<br/>ChebConv + RK4 ODE<br/>~5K params]
end
subgraph GRAPH_DATA["Spectral Graph"]
ADJ_ATK[Attack Matrix<br/>64x64 float32]
ADJ_DEF[Defense Matrix<br/>64x64 float32]
LAP[Laplacian<br/>Eigendecomposition]
FIED[Fiedler Vector<br/>Cohesion, Harmony,<br/>Bisection Tension]
end
subgraph ZOBRIST["Zobrist Hashing"]
ZH[Incremental Hash<br/>768 piece keys +<br/>side key + castle +<br/>EP file keys]
end
BOARD --> MAT & PST_SCORE & MOB & KS & PS
BOARD --> ADJ_ATK & ADJ_DEF
ADJ_ATK & ADJ_DEF --> LAP --> FIED --> SP
ADJ_ATK & ADJ_DEF --> ENT
BOARD --> ZH
ZH --> TT_TABLE
ZH --> EVALCACHE[(Eval Cache<br/>131K entries)]
subgraph KING_ATK["King Attack Features"]
KA_RESTRICT[Enemy King<br/>Restriction]
KA_ZONE[King-Zone<br/>Attack Count]
KA_PHASE[Phase-Weighted<br/>Attack Score]
end
BOARD --> KA_RESTRICT & KA_ZONE
KA_RESTRICT & KA_ZONE --> KA_PHASE
MAT & PST_SCORE & MOB & KS & PS & SP & ENT & KA_PHASE --> SCORE[Weighted<br/>Score Sum]
ADJ_ATK & ADJ_DEF --> NN --> SCORE
SCORE --> TT_TABLE
TT_TABLE & KILL & HIST & PHER_TABLE --> MOVEORD_OUT[Move<br/>Priority<br/>Sorting]
flowchart TD
ALL[All Legal Moves<br/>~30 avg] --> ORD[Move Ordering<br/>MVV-LVA, killers,<br/>history, pheromone,<br/>entropy gradient]
ORD --> POOL[Candidate Pool<br/>Top 8 moves]
POOL --> M1[Move 1: simulate]
POOL --> M2[Move 2: simulate]
POOL --> Mn[Move N: simulate]
M1 --> R1[Top 4 opponent<br/>replies for Move 1]
M2 --> R2[Top 4 opponent<br/>replies for Move 2]
Mn --> Rn[Top 4 opponent<br/>replies for Move N]
R1 --> S1["worst = min(vals)<br/>mean = avg(vals)"]
R2 --> S2["worst = min(vals)<br/>mean = avg(vals)"]
Rn --> Sn["worst = min(vals)<br/>mean = avg(vals)"]
S1 & S2 & Sn --> COMBINE[Combine with<br/>shallow eval + safety]
COMBINE --> DOMINATE[Eliminate<br/>Dominated Moves<br/>A dominates B iff<br/>A >= B on all metrics<br/>and A > B on at least one]
DOMINATE --> SURVIVORS[Sort by maximin<br/>then shallow, safety]
SURVIVORS --> TOP[Top 3-4<br/>Survivors]
TOP --> DEEP[Deep Alpha-Beta<br/>Search]
flowchart LR
BOARD[Board Position] --> BUILD[Build Adjacency<br/>per color]
BUILD --> ATK["Attack Graph<br/>A_atk[i,j] = 1.0<br/>if piece i can<br/>legally move to j"]
BUILD --> DEF["Defense Graph<br/>A_def[i,j] = 0.6<br/>if piece i protects<br/>friendly piece on j"]
ATK & DEF --> COMB["Combined Graph<br/>A = max(A_atk, A_def)"]
COMB --> SYM["Symmetrise<br/>A_sym = (A + A') / 2"]
SYM --> LAP["Laplacian<br/>L = D - A_sym"]
LAP --> EIGH["torch.linalg.eigh<br/>eigenvalues, eigenvectors"]
EIGH --> CONN[Connectivity<br/>lambda_2]
EIGH --> GAP[Spectral Gap<br/>lambda_2 / lambda_max]
EIGH --> CLUST[Cluster Count<br/>Union-Find]
EIGH --> ENTROPY[Spectral Entropy<br/>Shannon of eigenvalues]
EIGH --> FIEDLER[Fiedler Vector<br/>Cohesion, Harmony,<br/>Bisection Tension]
SYM --> POWER[Power Iteration<br/>15 iters]
POWER --> RADIUS[Spectral Radius]
POWER --> CENTRALITY[Eigenvector<br/>Centrality]
CONN & GAP & CLUST & ENTROPY & FIEDLER & RADIUS --> ADV[spectral_advantage<br/>weighted composite]
| File | Purpose | Key Classes / Functions |
|---|---|---|
acoga.py |
Decision layer: evaluation, search, ACO, GA, game-theoretic filtering | pick_best_move(), _alpha_beta(), _quiescence(), _root_maximin_scores(), _prune_dominated_root_moves(), _alpha_beta_root_subset(), SpectralEvalNet, AntColony, WeightEvolver |
gameboard.py |
State engine: board representation, move execution, Zobrist hashing | GameBoard, _simulate_move(), _unsimulate_move(), _pin_aware_legal_moves(), is_in_check() |
specturalchessboard.py |
Spectral graph features from board position | SpectralChessGraph, connectivity(), spectral_entropy(), fiedler_vector(), spectral_advantage() |
pieces.py |
Chess piece definitions with movement validation | King, Queen, Rook, Bishop, Knight, Pawn |
gui.py |
PyQt5 graphical interface with threaded AI | ChessWindow, AIWorker |
profile_ai.py |
Performance profiling harness | — |
test_comprehensive.py |
Full test suite (1256+ tests) | — |
| Feature | Description |
|---|---|
| Alpha-Beta | Minimax with alpha-beta pruning, depth-limited |
| PVS | Principal Variation Search — null-window scout with re-search |
| NMP | Null Move Pruning — skip a turn to test if position is already winning |
| LMR | Late Move Reductions — reduce depth for quiet late moves |
| Quiescence | Resolve captures, promotions, checking moves, and check evasions beyond horizon |
| Transposition Table | Zobrist-keyed, 262K entries, depth-preferred replacement |
| Killer Moves | 2 quiet beta-cutoff moves stored per ply |
| History Heuristic | 64x64 table of quiet cutoff frequency |
| Iterative Deepening | Search depth 1..N, reusing TT across iterations |
| Maximin Root Filter | Game-theoretic worst-case reply analysis |
| Dominated-Move Elimination | Remove root moves dominated on all eval dimensions |
| Component | Weight Key | Description |
|---|---|---|
| Material | material |
Piece value difference (P=100, N=320, B=330, R=500, Q=900). Danger-dependent scaling reduces weight when king attack is strong. |
| Piece-Square Tables | pst |
Positional value per piece type, phase-interpolated king table |
| King Safety | king_safety |
Pawn shield + zone attack penalty, phase-weighted |
| King Attack | king_attack |
Mate pressure: enemy king restriction, king-zone attack count, phase-weighted |
| Mobility | mobility |
Attacked square count difference (graph or ray-cast) |
| Centre Control | center |
Weighted central + extended centre squares |
| Pawn Structure | pawn_struct |
Passed, isolated, doubled, connected pawn bonuses/penalties |
| Spectral | spectral |
8-component graph feature advantage (connectivity, entropy, Fiedler, etc.) |
| Neural Network | nn |
SpectralEvalNet — Chebyshev graph convolution + RK4 ODE (~5K params, disabled by default) |
| Entropy | — | Phase-aware spectral entropy difference (automatic, no weight key) |
- Pheromone table persists across searches with 0.95 decay
- Root move selection via
torch.multinomialroulette-wheel - Multi-factor playout policy: checks (35), king-zone proximity (20/8), scaled captures, and noise — not just capture-seeking
- Elitist deposit on best ant path
- Entropy-modulated pheromone reward
- Tensor-vectorised population (8 individuals x 9 weight genes)
- Tournament selection, uniform crossover, Gaussian mutation
- 2-ply minimax fitness: evaluates root moves against top opponent replies, instant max fitness for checkmate lines
- Enabled by default (
use_ga=True) — explores weight space for each position
Python 3.10+
PyTorch 2.x (CPU)
PyQt5 5.15+
pip install torch --index-url https://download.pytorch.org/whl/cpu
pip install PyQt5python gui.pypython test_comprehensive.py| Operation | Complexity | Notes |
|---|---|---|
| Move generation | O(pieces x rays) | Pin-aware, avoids simulate for most moves |
| Check detection | O(25) | Targeted ray scan, not 64-square |
| Zobrist hash (simulate) | O(1) | Incremental XOR, no recompute |
| Spectral graph update | O(affected_pieces) | Incremental row rebuild (~5-15 pieces) |
| Eigendecomposition | O(64^3) | Cached, invalidated on graph update |
| EP clearing | O(1) | Single cached reference, no board scan |
| Root filtering | O(8 x 4) evals | 8 candidates x 4 replies = 32 leaf evals |
This project is for educational and research purposes.