В комбинаторной теории игр , то игра с нулевой является игрой , в которой ни один игрок не имеет какие - либо правовые варианты. Следовательно, согласно правилам обычной игры , первый игрок автоматически проигрывает, и это выигрывает второй игрок. В нулевой игре значение Спрэга – Гранди равно нулю. Комбинаторная запись нулевой игры: {| }. [1]
Нулевая игра должна контрастировать со звездной игрой {0 | 0}, которая является победой первого игрока, поскольку любой из игроков должен (если первый сделает ход в игре) перейти к нулевой игре и, следовательно, выиграть. [1]
Примеры [ править ]
Простые примеры нулевых игр включают Ним без стопок [2] или диаграмму Хакенбуша , на которой ничего не нарисовано. [3]
Значение Спраг-Гранди [ править ]
Теорема Спрэга – Гранди применяется к беспристрастным играм (в которых каждый ход может быть осуществлен любым игроком) и утверждает, что каждая такая игра имеет эквивалентное значение Спрага – Гранди, «ловушка», которое указывает количество фигур в эквивалентной позиции. в игре ним . [4] Все выигрышные игры второго игрока имеют нулевое значение Sprague – Grundy, хотя они могут и не быть нулевыми. [5]
Так , например, нормальный Nim с двумя одинаковыми сваями (любого размера) не игра с нулевым , но имеет значение 0, так как она является выигрышной ситуацией второго игрока всего первым игрок играет. Это не нечеткая игра, потому что у первого игрока нет возможности выиграть. [6]
Ссылки [ править ]
- ^ a b Конвей, JH (1976), О числах и играх , Academic Press, стр. 72.
- ^ Конвей (1976) , стр. 122.
- ^ Конвей (1976) , стр. 87.
- ^ Конвей (1976) , стр. 124.
- ^ Конвей (1976) , стр. 73.
- ^ Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (1983), Winning Ways для ваших математических пьес, Том 1: Игры в целом (исправленное издание), Academic Press, стр. 44 год.