Editing Impartial game

{{Short description|Concept in game theory}}
In [[combinatorial game theory]], an '''impartial game''' is a [[Mathematical game|game]] in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.

Impartial games include [[Nim]], [[Sprouts (game)|Sprouts]], [[Kayles]], [[Quarto (board game)|Quarto]], [[Cram (game)|Cram]], [[Chomp]], [[Subtract a square]], [[Notakto]], and [[poset game]]s. [[Go (game)|Go]] and [[chess]] are not impartial, as each player can only place or move pieces of their own color. Games such as [[poker]], [[dice]] or [[Dominoes|dominos]] are not impartial games as they rely on chance.

Impartial games can be analyzed using the [[Sprague–Grundy theorem]], stating that every impartial game under the [[normal play convention]] is equivalent to a [[nimber]]. The representation of this nimber can change from game to game, but every possible state of any variation of an impartial game board should be able to have some nimber value. For example, several nim heaps in the game nim can be calculated, then summed using nimber addition, to give a nimber value for the game.

A game that is not impartial is called a [[partisan game]], though some partisan games can still be evaluated using nimbers such as [[Domineering]].<ref>{{Cite book|title=Advances in computer games : 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers|others=Herik, Jaap van den,, Plaat, Aske,, Kosters, Walter|date = 24 December 2015|isbn=978-3319279923|location=Cham|oclc=933627646}}</ref> Domineering would not be classified as an impartial game as players use differently acting pieces, one player with vertical dominoes, one with horizontal ones, thereby breaking the rule that each player must be able to act using the same operations.

== Requirements ==
All impartial games must meet the following conditions:
* Two players must alternate turns until a final state is reached.
* A winner is chosen when one player may no longer change position or make any operation.
* There must be a finite number of operations and positions for both players. For example, in Nim, players must take away a subset of a stack that is currently in play. As there is a finite number of coins in any stack, a player may only remove a finite number of coins.
* All operations must be able to be done by both sides. In all Impartial games, the players are making actions to some game board whether in the form of stacks for Nim or rows and columns Cram. Both players are acting on the board till the board can no longer change in some way.
* No action in the game may be reliant on chance. Any inclusion of chance would mean there is not perfect information about the game, furthermore actions could not be [[minimax algorithm|minmaxed]] ruling out any form inductive strategy.<ref>{{Cite web|url=https://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf|title=Game Theory|last=Ferguson|first=Thomas S.|authorlink= Thomas S. Ferguson |date=Fall 2000}}</ref>

==Heap game==
'''Heap games''' are a [[Subclass_(set_theory)|subclass]] of impartial games that involve the [[disjunctive sum]] of various single-heap games. ''Single-heap positions'', or ''Γ-heaps''  are games represented naturally by the [[Ordinal_number|ordinal]] amount of a heap of tokens, where players play according to a specific [[Game rule|ruleset]] on that single heap.<ref>{{cite book |last1=Siegel |first1=Aaron |title=Combinatorial Game Theory |date=20 November 2023 |publisher=American Mathematical Society |isbn=978-1-4704-7568-0}}</ref>

Every option of a heap game must be representable as <math>H^{'}_{n} = H_{a_{1}} + H_{a_{2}} + H_{a_{3}} + ...</math>, where each <math>H^{a_{n}}</math> is another heap game.

The [[nim]]-value of a game is represented as the nim-addition of each heap in a heap game.

Examples include:
* [[Octal games]]
* [[Nim]]
* [[Kayles]]

== References ==
{{reflist}}

==Further reading==
*{{cite book |author1=[[E. Berlekamp]] |author2=J. H. Conway |author2link = John Conway|author3=R. Guy | title=Winning Ways for your Mathematical Plays |title-link=Winning Ways for your Mathematical Plays | publisher=Academic Press | year=1982 | volume=2 vols.}}; {{cite book|title=vol. 1|isbn=0-12-091101-9|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|year=1982|publisher=Academic Press }}; {{cite book|title=vol. 2|isbn=0-12-091102-7|last1=Berlekamp|first1=Elwyn R.|year=1982|publisher=Academic Press }}
*{{cite book |author1=E. Berlekamp |author2=J. H. Conway |author3=R. Guy | title=Winning Ways for your Mathematical Plays | edition=2nd | publisher=A K Peters Ltd | year=2001–2004 | volume=4 vols.}}; {{cite book|title=vol. 1|isbn=1-56881-130-6|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John H.|last3=Guy|first3=Richard K.|date=16 January 2001}}; {{cite book|title=vol. 2|isbn=1-56881-142-X}}; {{cite book|title=vol. 3|isbn=1-56881-143-8|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=15 June 2003}}; {{cite book|title=vol. 4|isbn=1-56881-144-6|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=15 June 2004}}

[[Category:Combinatorial game theory]]