# Game theory

A winning move is defined against optimal opponent responses, rather than against one friendly execution.

## Definitions

- **Normal play**: The player with no legal move loses.
- **Winning position**: A state with at least one move to a losing position for the opponent.
- **Strategy**: A legal choice for every winning state in the declared game domain.

## Acceptance procedure

1. Set the empty heap to losing.
2. Process heap sizes in increasing order.
3. Mark a heap winning if an allowed subtraction reaches a losing heap.
4. Validate every submitted winning move and every losing-state marker.

## Complexity

N heap sizes with m allowed moves require O(Nm) dynamic-programming checks.

## Common failure

A single successful play does not establish a strategy against all opponent choices.

## Extensions

Add alternating-player reachability graphs and strategy certificates.

## Instances

- KL-FCS-049: Take one or two stones — Winning heap sizes: [1, 2, 4, 5, 7, 8, 10, 11]
- KL-FCS-050: Odd-sized subtraction choices — Winning heap sizes: [1, 3, 5, 7, 9, 11, 13, 15]
- KL-FCS-051: A game with a nontrivial move set — Winning heap sizes: [2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 16, 17, 18, 19, 20]

## References

- https://isa-afp.org/entries/Parity_Game.html