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