Дизъюнктивная сумма - Disjunctive sum
В математике комбинаторные игры, то сумма или же дизъюнктивная сумма из двух игр - это игра, в которой две игры проводятся параллельно, причем каждому игроку разрешается делать ход только в одной из игр за ход. Игра с суммой завершается, когда в любой из двух параллельных игр не остается ходов, после чего (в нормальная игра ) проигрывает последний сделавший ход игрок. Эта операция может быть расширена до дизъюнктивных сумм любого количества игр, опять же, играя в игры параллельно и переходя ровно в одну из игр за ход. Это основная операция, которая используется в Теорема Спрага – Гранди за беспристрастные игры и что привело к области комбинаторная теория игр за партизанские игры.
Приложение к обычным играм
Дизъюнктивные суммы возникают в играх, которые естественным образом распадаются на компоненты или области, которые не взаимодействуют друг с другом, за исключением того, что каждый игрок, в свою очередь, должен выбрать только один компонент для игры. Примеры таких игр: Идти, Ним, Ростки, Властный, то Игра амазонок, а раскраски карты.
В таких играх каждый компонент может быть проанализирован отдельно на предмет упрощений, которые не влияют на его результат или результат его дизъюнктивной суммы с другими играми. После того, как этот анализ будет выполнен, компоненты можно объединить, взяв дизъюнктивную сумму двух игр за раз, объединив их в одну игру с тем же результатом, что и исходная игра.
Математика
Операция суммы была формализована Конвей (1976). Это коммутативный и ассоциативная операция: если две игры объединены, результат будет одинаковым независимо от того, в каком порядке они объединены, а если объединено более двух игр, результат будет одинаковым независимо от того, как они сгруппированы.
Отрицание -грамм игры грамм (игра, сформированная обменом ролями двух игроков) формирует Противоположное число по дизъюнктивным суммам: игра грамм + −грамм представляет собой нулевую игру (выигрывает тот, кто ходит вторым) с использованием простой стратегии повторения, в которой второй игрок многократно копирует ход первого игрока в другой игре. Для любых двух игр грамм и ЧАС, игра ЧАС + грамм + −грамм имеет тот же результат, что и ЧАС сам (хотя может иметь больший набор доступных ходов).
Исходя из этих свойств, класс комбинаторных игр можно рассматривать как имеющий структуру абелева группа, хотя с правильный класс элементов, а не (как более стандартно для групп) набор элементов. Для важного подкласса игр, называемого сюрреалистические числа, существует оператор умножения, расширяющий эту группу до поле.
За беспристрастную Misère играть в игры, можно разработать аналогичную теорию сумм, но с меньшим количеством этих свойств: эти игры образуют коммутативный моноид с одним нетривиальным обратимым элементом, называемым звезда (* ) второго порядка.
Рекомендации
- Джон Хортон Конвей (1976), О числах и играх, Academic Press.