Zero game

Not to be confused with Zero-sum game.
This article is about combinatorial game theory. For the novel entitled "The Zero Game", see Brad Meltzer.

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 - version of the Friday, January 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.