AI DEVELOPMENT / DEDICATED BUILD
Game AI
Choose actions inside formal game rules using search, heuristics, planning, learned policies, or combinations of these methods.
What it is
Choose actions inside formal game rules using search, heuristics, planning, learned policies, or combinations of these methods.
This page separates the concept, implementation path, interactive experiment, evaluation criteria, failure modes, and sources so the topic can be studied without relying on a summary tile.
Core concepts
- A game state and legal-action generator define what moves are possible.
- Search explores future action sequences.
- Evaluation functions estimate states when exhaustive search is impossible.
- Minimax models adversarial turn-taking; pruning avoids branches that cannot change the result.
- Monte Carlo tree search estimates promising actions through repeated simulated play.
Architecture / workflow
- Implement legal state transitions before adding intelligence.
- Create a deterministic baseline such as random or heuristic play.
- Add search with a fixed depth or simulation budget.
- Benchmark against the baseline across many games.
- Inspect illegal moves, repeated states, timing, and edge cases.
Technical foundations
- Minimax alternates MAX and MIN layers to propagate utility values.
- Alpha-beta pruning preserves the minimax result while skipping provably irrelevant branches.
- MCTS balances exploration and exploitation while building a partial search tree.
- Learned policies/value functions can replace or guide hand-written heuristics.
Evaluation checklist
- Win/draw/loss rate against fixed opponents.
- Illegal-move rate must be zero.
- Nodes searched, time per move, and memory.
- Performance by opening/state family rather than only aggregate win rate.
- Determinism and reproducibility under fixed seeds.
Failure modes and limits
- A strong evaluation function can still violate rules if state transitions are wrong.
- Benchmark opponents may be too weak or too similar.
- Search time can explode with branching factor.
- Learning systems can exploit simulator bugs instead of learning intended strategy.
Practical build path
- Implement minimax on a tiny deterministic game tree.
- Add alpha-beta pruning and count visited nodes.
- Integrate a legal-move engine for a real game.
- Benchmark a heuristic or learned evaluator against fixed search baselines.
Primary / authoritative references
AUTHORED STUDY COMPANION / 3.5
Solve a small game exactly before learning it
Prerequisites. Turn-based games, terminal states and dynamic programming.
In this normal-play subtraction game, a player removes one or two stones and the player taking the last stone wins. Position zero is losing for the player to move. A positive position is winning if any legal move leads to a losing position for the opponent. The companion builds this table from small positions upward.
For five stones, taking two leaves three, a losing position. This is exact dynamic programming for a fully known game, not an RL agent and not a change to either protected portfolio game. It provides a clean baseline for a later learned policy: compare decisions against the solved state table, including losing states where no winning move exists.
| Element | Model | Interpretation |
|---|---|---|
| Terminal | Zero stones | Losing for the next player |
| Recurrence | Any move to a losing state? | Winning-state test |
| Policy | Select such a move | Exact model-based baseline |
Predict, run, compare
States 0,3,6,… are losing. At five stones the winning move takes two; at three stones the function reports no forced-winning move.
Download executable notebooks and source Inspect source ↗
Open game.ipynb in the package. Run cells in order, compare with the reference, then change the stated input. Restart the kernel to reset.
Computed reference result — local CPU fixture
{
"winning": true,
"optimal_take": 2,
"winning_states": [
false,
true,
true,
false,
true,
true
],
"scope": "perfect-information normal-play subtraction game, take 1 or 2; exact dynamic programming"
}This is the recorded result of the included code under the package environment. It is not a live service or device measurement.
Extend the experiment
Train a small policy against the solved opponent and report agreement by state. Do not score an arbitrary move in a losing state as a missed guaranteed win.
Check your reasoning: A losing state means:
- No legal move exists in every case — Three stones has legal moves but is losing.
- No forced win against optimal play under the rules — Correct. Every legal move gives the opponent a winning position.
- The program crashed — It is a valid game-theoretic result.
This is an explained self-check, not a certification of mastery.
Claim-specific sources
Reviewed 2026-10-02: this worked example and its explicit assumptions. Source links and notebook results do not establish production or hardware validation.