В комбинаторной теории игр , беспристрастная игра представляет собой игра , в которой допустимые шаги зависят только от положения , а не на какой из двух игроков в настоящее время двигается, и где выигрыши являются симметричными. Другими словами, единственная разница между игроком 1 и игроком 2 состоит в том, что игрок 1 ходит первым. Игра продолжается до тех пор, пока не будет достигнута конечная позиция. Конечная позиция - это позиция, из которой невозможно движение. Затем один из игроков объявляется победителем, а другой - проигравшим. Кроме того, в беспристрастные игры используются точная информация и отсутствие случайных ходов, что означает, что вся информация об игре и операциях обоих игроков видна обоим игрокам.
Объективные игры включают Nim , рассада , Kayles , Quarto , Крам , Chomp , вычитаем площадь , Notakto и посетом игры . Го и шахматы не беспристрастны, так как каждый игрок может ставить или перемещать фигуры только своего цвета. Такие игры, как покер , кости или домино , не являются беспристрастными играми, поскольку они полагаются на случай.
Беспристрастные игры можно анализировать с помощью теоремы Спрэга – Гранди , утверждающей, что каждая беспристрастная игра в соответствии с соглашением о нормальной игре эквивалентна нимберу . Представление этого ловка может меняться от игры к игре, но каждое возможное состояние любого варианта беспристрастной игровой доски должно иметь некоторую ценность ловкости. Например, несколько кучек нимов в игровом ниме могут быть рассчитаны, а затем суммированы с помощью сложения нимберов, чтобы получить значение ловкости для игры.
Игра, которая не является беспристрастной, называется партизанской игрой , хотя некоторые партизанские игры все же могут быть оценены с помощью ловушек, таких как Доминирование . [1] Доминирование не может быть классифицировано как беспристрастная игра, поскольку игроки используют разные фигуры, один игрок с вертикальными домино, другой с горизонтальными, тем самым нарушая правило, согласно которому каждый игрок должен иметь возможность действовать, используя одни и те же операции.
Требования
Все беспристрастные игры должны соответствовать следующим условиям:
- Два игрока должны чередовать ходы до достижения конечного состояния.
- Победитель определяется, когда один игрок больше не может менять позицию или выполнять какие-либо операции.
- Для обоих игроков должно быть конечное количество операций и позиций. Например, в Nim игроки должны забрать подмножество стека, которое в данный момент находится в игре. Поскольку в любой стопке есть конечное количество монет, игрок может удалить только конечное количество монет.
- Все операции должны выполняться обеими сторонами. Во всех беспристрастных играх игроки выполняют действия над некоторым игровым полем, будь то в виде стопок для нимов или строк и столбцов Cram. Оба игрока действуют на доске до тех пор, пока она не перестанет каким-либо образом измениться.
- Никакое действие в игре не может зависеть от случая. Любое включение случая означало бы, что нет точной информации об игре, кроме того, действия не могут быть минимизированы, исключая любую форму индуктивной стратегии. [2]
Рекомендации
- ^ Достижения в компьютерных играх: 14-я Международная конференция, ACG 2015, Лейден, Нидерланды, 1-3 июля 2015 г., Отредактированные избранные статьи . Херик, Яап ван ден, Плат, Аске, Костерс, Вальтер. Чам. 24 декабря 2015 года. ISBN 978-3319279923. OCLC 933627646 .CS1 maint: другие ( ссылка )
- ^ Фергюсон, Томас С. (осень 2000 г.). «Теория игр» (PDF) .
дальнейшее чтение
- Э. Берлекамп ; Дж. Х. Конвей ; Р. Гай (1982). Выигрышные способы для ваших математических пьес . 2 тт. Академическая пресса.; Berlekamp, Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (1982). т. 1 . ISBN 0-12-091101-9.; Берлекамп, Элвин Р. (1982). т. 2 . ISBN 0-12-091102-7.
- Э. Берлекамп; Дж. Х. Конвей; Р. Гай (2001–2004). Выигрышные способы для ваших математических пьес . 4 тт. (2-е изд.). AK Peters Ltd.; Berlekamp, Elwyn R .; Конвей, Джон Х .; Гай, Ричард К. (16 января 2001 г.). т. 1 . ISBN 1-56881-130-6.; т. 2 . ISBN 1-56881-142-X.; Berlekamp, Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (15 июня 2003 г.). т. 3 . ISBN 1-56881-143-8.; Berlekamp, Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (15 июня 2004 г.). т. 4 . ISBN 1-56881-144-6.