In combinatorial game theory, the zero game is the game where neither player has any legal options. Therefore, under the normal play convention, the first player automatically loses, and it is a second-player win. The zero game has a Sprague–Grundy value of zero. The combinatorial notation of the zero game is: { | }.[1]

A zero game should be contrasted with the star game {0|0}, which is a first-player win since either player must (if first to move in the game) move to a zero game, and therefore win.[1]

Examples

Simple examples of zero games include Nim with no piles[2] or a Hackenbush diagram with nothing drawn on it.[3]

Sprague-Grundy value

The Sprague–Grundy theorem applies to impartial games (in which each move may be played by either player) and asserts that every such game has an equivalent Sprague–Grundy value, a "nimber", which indicates the number of pieces in an equivalent position in the game of nim.[4] All second-player win games have a Sprague–Grundy value of zero, though they may not be the zero game.[5]

For example, normal Nim with two identical piles (of any size) is not the zero game, but has value 0, since it is a second-player winning situation whatever the first player plays. It is not a fuzzy game because first player has no winning option.[6]

References

  1. 1 2 Conway, J. H. (1976), On numbers and games, Academic Press, p. 72.
  2. ↑ Conway (1976), p. 122.
  3. ↑ Conway (1976), p. 87.
  4. ↑ Conway (1976), p. 124.
  5. ↑ Conway (1976), p. 73.
  6. ↑ Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1983), Winning Ways for your mathematical plays, Volume 1: Games in general (corrected ed.), Academic Press, p. 44.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.