King + Rook vs King Endgame Solver

Final project for ECE 270 (Game Theory) taught by Joao P. Hespanha, following the modeling style from his textbook Noncooperative Game Theory: An Introduction for Engineers and Computer Scientists. The KRK endgame is treated as a finite, sequential, zero-sum game with adversarial best response at every move.

Game-Theoretic Framing

The endgame is formulated as a sequential zero-sum game:
  • White (minimizer): force checkmate while avoiding stalemate.
  • Black (maximizer): avoid mate, delay loss, or capture the rook.
Decision-making follows the same principle emphasized in class: assume the opponent plays a best response to your policy at every stage.
State is encoded as a 65-element vector: 64 board entries + 1 move counter (even/odd parity for side-to-move), enabling explicit dynamic-state recursion.

Legal-Move Constraints

Illegal king-touching move example Illegal rook-hop move example Illegal capture of protected rook example

From Game Theory Principles to Code

Core strategy computation
  • depth-limited minimax
  • alpha-beta pruning
  • best-response assumption at each ply
Dynamic-programming flavor
  • memoized recursive evaluation
  • persistent transposition-style cache reuse
  • terminal-state early exits

Payoff / Cost Design

The payoff design follows course principles by combining terminal rewards/penalties with positional shaping terms.
  • strong terminal preference for checkmate
  • strong penalties for stalemate and rook loss
  • positional shaping using black-king mobility ("oxygen") and king geometry
Illegal move where black remains in check