Chomp Game and Strategy Stealing Existence Argument

Scenario

Two players play the combinatorial game of Chomp on an $m \times n$ grid of chocolate squares. The bottom-left square $(0, 0)$ is poisoned. A legal move consists of choosing any remaining chocolate square $(r, c)$ and removing all squares $(x, y)$ such that $x \ge r$ and $y \ge c$ (the chosen square and all squares above/right of it). The player forced to eat the poisoned square $(0, 0)$ loses.

Your Task

1. Classify Chomp as a finite, impartial game of perfect information with no draws.
2. State Zermelo's Theorem on the existence of a winning strategy in two-player games.
3. Use a strategy-stealing argument to prove that Player 1 (first mover) must possess a winning strategy for any grid size larger than $1 \times 1$.
4. Implement a minimax retrograde game-tree solver to verify that Player 1 wins on a $2 \times 3$ grid.

Constraints

• Grid dimensions $m \ge 2$ or $n \ge 2$.
• Normal play / misère play convention.

Examples For a $2 \times 2$ grid, Player 1 eats $(1, 1)$, leaving an L-tromino, and can always mirror Player 2's moves to win.