Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В математике комбинаторных игр сумма или дизъюнктивная сумма двух игр — это игра, в которой обе игры играются параллельно, и каждый игрок в свой ход имеет право сделать ход только в одной из них. Сумма игр завершается, когда в обеих параллельных играх не остаётся доступных ходов, при этом (в нормальной игре) побеждает игрок, сделавший последний ход. Эта операция может быть расширена на дизъюнктивные суммы любого числа игр, также играя в игры параллельно и делая ход ровно в одной из них за ход. Это фундаментальная операция, используемая в теореме Спрага — Гранди для беспристрастных игр и положившая начало развитию комбинаторной теории игр для позиционных игр.
In the mathematics of combinatorial games, the sum or disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. The sum game finishes when there are no moves left in either of the two parallel games, at which point (in normal play) the last player to move wins. This operation may be extended to disjunctive sums of any number of games, again by playing the games in parallel and moving in exactly one of the games per turn. It is the fundamental operation that is used in the Sprague–Grundy theorem for impartial games and which led to the field of combinatorial game theory for partisan games.
Применение к обычным играм
Дисъюнктивные суммы возникают в играх, которые естественно распадаются на компоненты или области, не взаимодействующие друг с другом, за исключением того, что каждый игрок по очереди должен выбрать только один компонент для игры. Примерами таких игр являются Го, Ним, Спрауты, Доминирование, Игра Амазонок и игры раскраски карт. В таких играх каждый компонент можно анализировать отдельно, упрощая его без изменения его исхода или исхода его дизъюнктивной суммы с другими играми. После проведения такого анализа компоненты можно объединить, последовательно вычисляя дизъюнктивную сумму двух игр, объединяя их в одну игру с тем же исходом, что и исходная игра.
Disjunctive sums arise in games that naturally break up into components or regions that do not interact except in that each player in turn must choose just one component to play in. Examples of such games are Go, Nim, Sprouts, Domineering, the Game of the Amazons, and the map coloring games. In such games, each component may be analyzed separately for simplifications that do not affect its outcome or the outcome of its disjunctive sum with other games. Once this analysis has been performed, the components can be combined by taking the disjunctive sum of two games at a time, combining them into a single game with the same outcome as the original game.
Математика
Операция суммирования была формализована. Это коммутативная и ассоциативная операция: если две игры комбинируются, результат не зависит от порядка их комбинирования, а если комбинируется более двух игр, результат не зависит от способа их группировки. Отрицание −G игры G (игра, полученная обменом ролями игроков) является аддитивно обратным элементом при дизъюнктивном суммировании: игра G + −G является нулевой игрой (выигрывает игрок, ходящий вторым), используя простую стратегию «эхо», в которой второй игрок повторяет ход первого игрока в другой игре. Для любых двух игр G и H игра H + G + −G имеет тот же результат, что и сама игра H (хотя набор доступных ходов может быть больше). Благодаря этим свойствам класс комбинаторных игр можно рассматривать как имеющий структуру абелевой группы, хотя и с собственным классом элементов, а не (как обычно для групп) множеством элементов. Для важного подкласса игр, называемого сюрреальными числами, существует оператор умножения, который расширяет эту группу до поля. Для беспристрастных игр с мизерным правилом можно разработать аналогичную теорию сумм, но с меньшим количеством этих свойств: такие игры образуют коммутативный моноид, содержащий единственный нетривиальный обратимый элемент, называемый звездой (*), порядка два.
The sum operation was formalized by It is a commutative and associative operation: if two games are combined, the outcome is the same regardless of what order they are combined, and if more than two games are combined, the outcome is the same regardless of how they are grouped. The negation −G of a game G (the game formed by trading the roles of the two players) forms an additive inverse under disjunctive sums: the game G + −G is a zero game (won by whoever goes second) using a simple echoing strategy in which the second player repeatedly copies the first player's move in the other game. For any two games G and H, the game H + G + −G has the same outcome as H itself (although it may have a larger set of available moves). Based on these properties, the class of combinatorial games may be thought of as having the structure of an abelian group, although with a proper class of elements rather than (as is more standard for groups) a set of elements. For an important subclass of the games called the surreal numbers, there exists a multiplication operator that extends this group to a field. For impartial misère play games, an analogous theory of sums can be developed, but with fewer of these properties: these games form a commutative monoid with only one nontrivial invertible element, called star (*), of order two.