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