Дизъюнктивная сумма

В математике комбинаторных игр сумма двух или дизъюнктивная сумма игр — это игра, в которой две игры проводятся параллельно, причем каждому игроку разрешено делать ход только в одной из игр за ход. Игра с суммой заканчивается, когда ни в одной из двух параллельных игр не остается ходов, и в этот момент (в обычной игре ) побеждает игрок, сделавший ход последним.Эту операцию можно распространить на дизъюнктивную сумму любого количества игр, опять же, играя в игры параллельно и проходя ровно одну из игр за ход. Это фундаментальная операция, которая используется в теореме Спрэга-Грунди для беспристрастных игр и которая привела к созданию области комбинаторной теории игр для партизанских игр .

Применение к обычным играм

Дизъюнктивные суммы возникают в играх, которые естественным образом распадаются на компоненты или области, которые не взаимодействуют, за исключением того, что каждый игрок, в свою очередь, должен выбрать только один компонент для игры. Примерами таких игр являются Го , Ним , Ростки , Доминирование , Игра Амазонки и игры-раскраски карт .

В таких играх каждый компонент может анализироваться отдельно на предмет упрощений, не влияющих на его результат или результат его дизъюнктивной суммы с другими играми. После проведения этого анализа компоненты можно объединить, взяв дизъюнктивную сумму двух игр одновременно и объединив их в одну игру с тем же результатом, что и исходная игра.

Математика

Операция суммирования была формализована Конвеем (1976) . Это коммутативная и ассоциативная операция : если объединить две игры, результат будет одинаковым независимо от порядка их объединения, а если объединить более двух игр, результат будет одинаковым независимо от того, как они сгруппированы.

Отрицание − G игры G (игра, образованная путем обмена ролями двух игроков) образует аддитивную инверсию относительно дизъюнктивных сумм: игра G + − G представляет собой нулевую игру (выигрывает тот, кто идет вторым) с использованием простого повторения стратегия, в которой второй игрок неоднократно копирует ход первого игрока в другой игре. Для любых двух игр G и H игра H + G + − G имеет тот же результат, что и сама H (хотя у нее может быть больший набор доступных ходов).

На основании этих свойств класс комбинаторных игр можно рассматривать как имеющий структуру абелевой группы , хотя и с собственным классом элементов, а не (как более стандартно для групп) набором элементов. Для важного подкласса игр, называемого сюрреалистическими числами , существует оператор умножения, который расширяет эту группу до поля .

Для беспристрастных «мизер» игр типа можно разработать аналогичную теорию сумм, но с меньшим количеством этих свойств: эти игры образуют коммутативный моноид только с одним нетривиальным обратимым элементом, называемым звездой ( * ), второго порядка.

Ссылки

• Конвей, Джон Хортон (1976), О числах и играх , Academic Press .