В математике комбинаторных игр , то сумма или дизъюнктивной сумма двух игр является игра , в которой две игры играют параллельно, причем каждый игрок будет разрешено двигаться только в одном из игр в свою очередь. Игра с суммой заканчивается, когда в любой из двух параллельных игр не остается ходов, и в этот момент (при нормальной игре ) побеждает последний сделавший ход игрок. Эту операцию можно расширить до дизъюнктивных сумм любого количества игр, опять же, играя в игры параллельно и переходя точно в одну из игр за ход. Это фундаментальная операция, которая используется в теореме Спрага – Гранди для беспристрастных игр и привела к области комбинаторной теории игр.для партизанских игр .
Применение к обычным играм [ править ]
Дизъюнктивные суммы возникают в играх, которые естественным образом распадаются на компоненты или области, которые не взаимодействуют друг с другом, за исключением того, что каждый игрок по очереди должен выбрать только один компонент для игры. Примеры таких игр: Go , Nim , Sprouts , Domineering , Game of the Амазонки и игры с раскраской карт .
В таких играх каждый компонент может анализироваться отдельно на предмет упрощений, которые не влияют на его результат или результат его дизъюнктивной суммы с другими играми. После выполнения этого анализа компоненты можно объединить, взяв дизъюнктивную сумму двух игр за раз, объединив их в одну игру с тем же результатом, что и исходная игра.
Математика [ править ]
Операция суммирования была формализована Конвеем (1976) . Это коммутативная и ассоциативная операция : если две игры объединены, результат будет одинаковым независимо от того, в каком порядке они объединены, а если объединено более двух игр, результат будет одинаковым независимо от того, как они сгруппированы.
Отрицание - G игры G (игра, образованная обменом ролями двух игроков) образует аддитивную инверсию по дизъюнктивным суммам: игра G + - G - игра с нулем (выигранная тем, кто идет вторым), с использованием простого повторения. стратегия, в которой второй игрок многократно копирует ход первого игрока в другой игре. Для любых двух игр G и H игра H + G + - G имеет тот же результат, что и сама H (хотя в ней может быть больший набор доступных ходов).
Основываясь на этих свойствах, класс комбинаторных игр можно рассматривать как имеющий структуру абелевой группы , хотя и с надлежащим классом элементов, а не (как более стандартно для групп) набором элементов. Для важного подкласса игр, называемого сюрреалистическими числами , существует оператор умножения, расширяющий эту группу до поля .
Для беспристрастных игр типа misère play может быть разработана аналогичная теория сумм, но с меньшим количеством этих свойств: эти игры образуют коммутативный моноид только с одним нетривиальным обратимым элементом, называемым звездой ( * ), второго порядка.
Ссылки [ править ]
- Джон Хортон Конвей (1976), О числах и играх , Academic Press.
