Category:Combinatorial Game Theory

From Algorithmist
Jump to: navigation, search

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.

Pages in category "Combinatorial Game Theory"

The following 3 pages are in this category, out of 3 total.