Беспристрастная игра

В комбинаторной теории игр беспристрастная игра — это игра , в которой допустимые ходы зависят только от позиции, а не от того, кто из двух игроков в данный момент ходит, и где выигрыши симметричны. Другими словами, единственная разница между игроком 1 и игроком 2 заключается в том, что игрок 1 ходит первым. Игра ведется до тех пор, пока не будет достигнута конечная позиция. Терминальная позиция – это позиция, из которой ходы невозможны. Тогда один из игроков объявляется победителем, а другой – проигравшим. Кроме того, в беспристрастных играх используется точная информация и нет случайных ходов, а это означает, что вся информация об игре и операциях для обоих игроков видна обоим игрокам.

Беспристрастные игры включают Nim , Sprouts , Kayles , Quarto , Cram , Chomp , Subtract a Square , Notakto и игры с фиксированными наборами . Го и шахматы не беспристрастны, поскольку каждый игрок может размещать или перемещать фигуры только своего цвета. Такие игры, как покер , кости или домино, не являются беспристрастными играми, поскольку они полагаются на случайность.

Беспристрастные игры можно анализировать с помощью теоремы Спрэга-Грунди , утверждающей, что каждая беспристрастная игра в соответствии с соглашением о нормальной игре эквивалентна нимберу . Представление этого числа может меняться от игры к игре, но каждое возможное состояние любого варианта беспристрастного игрового поля должно иметь некоторое значение числа. Например, можно вычислить несколько куч нимов в игре nim, а затем суммировать их сложением, чтобы получить значение нимбера для игры.

Игра, которая не является беспристрастной, называется партийной игрой , хотя некоторые партийные игры все же можно оценить с помощью нимберов, таких как Доминирование . ^[1] Доминирование не может быть классифицировано как беспристрастная игра, поскольку игроки используют фигуры по-разному: один игрок - с вертикальными домино, другой - с горизонтальными, тем самым нарушая правило, согласно которому каждый игрок должен иметь возможность действовать, используя одни и те же операции.

Требования

Все беспристрастные игры должны соответствовать следующим условиям:

Два игрока должны чередовать ходы, пока не будет достигнуто окончательное состояние.
Победитель выбирается, когда один из игроков больше не может менять позицию или совершать какие-либо действия.
Для обоих игроков должно быть конечное число операций и позиций. Например, в Ниме игроки должны забрать часть стопки, которая в данный момент находится в игре. Поскольку в любой стопке ограниченное количество монет, игрок может удалить только ограниченное количество монет.
Все операции должны быть выполнены обеими сторонами. Во всех беспристрастных играх игроки совершают действия на каком-либо игровом поле, будь то стопки для Нима или строки и столбцы для Крама. Оба игрока действуют на доске до тех пор, пока доска не перестанет каким-либо образом меняться.
Ни одно действие в игре не может зависеть от случая. Любое включение случайности означало бы, что об игре нет полной информации, кроме того, действия не могут быть сведены к минимуму, исключая любую форму индуктивной стратегии. ^[2]

Ссылки

^ Достижения в компьютерных играх: 14-я Международная конференция ACG 2015, Лейден, Нидерланды, 1-3 июля 2015 г., Пересмотренные избранные статьи . Херик, Яап ван ден, Плаат, Аске, Костерс, Вальтер. Чам. 24 декабря 2015 г. ISBN. 978-3319279923 . OCLC 933627646 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )
^ Фергюсон, Томас С. (осень 2000 г.). «Теория игр» (PDF) .

Дальнейшее чтение

Э. Берлекамп ; Дж. Х. Конвей ; Р. Гай (1982). Пути выигрыша в математических играх . Том. 2 тома. Академическая пресса. ; Берлекамп, Элвин Р.; Конвей, Джон Хортон; Гай, Ричард К. (1982). том. 1 . Академическая пресса. ISBN 0-12-091101-9 . ; Берлекамп, Элвин Р. (1982). том. 2 . Академическая пресса. ISBN 0-12-091102-7 .
Э. Берлекамп; Дж. Х. Конвей; Р. Гай (2001–2004). Пути выигрыша в математических играх . Том. 4 тома. (2-е изд.). ООО «АК Петерс» ; Берлекамп, Элвин Р.; Конвей, Джон Х.; Гай, Ричард К. (16 января 2001 г.). том. 1 . ISBN 1-56881-130-6 . ; Том. 2 . ISBN 1-56881-142-Х . ; Берлекамп, Элвин Р.; Конвей, Джон Хортон; Гай, Ричард К. (15 июня 2003 г.). том. 3 . ISBN 1-56881-143-8 . ; Берлекамп, Элвин Р.; Конвей, Джон Хортон; Гай, Ричард К. (15 июня 2004 г.). том. 4 . ISBN 1-56881-144-6 .

[1] Достижения в компьютерных играх: 14-я Международная конференция ACG 2015, Лейден, Нидерланды, 1-3 июля 2015 г., Пересмотренные избранные статьи . Херик, Яап ван ден, Плаат, Аске, Костерс, Вальтер. Чам. 24 декабря 2015 г. ISBN. 978-3319279923 . OCLC 933627646 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )

[2] Фергюсон, Томас С. (осень 2000 г.). «Теория игр» (PDF) .

[1]

[2]