Category:Combinatorial Game Theory

The typical example of a problem in this category is, given a game, assuming both players play optimally, to determine the final outcome.

The most basic tool here is Win-Loss(-Draw) Analysis. This notion is generalized by

• minimax search and
• Sprague-Grundy analysis --- this only works when the game is impartial (roughly meaning that both players have the same set of moves from any position) but gives a useful xor-sum rule for decomposition.

If the game involves imperfect knowledge, different tools are needed in general. "Chance" moves also may require a more general model, but can sometimes be dealt with in a minimax search if you want to maximize your expected payoff.

See also the page at Wikipedia.