Теория комбинаторных игр: совершенная информация и последовательные ходы.

Введение

Отрасль теории игр, посвященная последовательным играм для двух игроков с полной информацией – теория комбинаторных игр.

Комбинаторная теория игр – это раздел математики и теоретической информатики, который обычно изучает последовательные игры с полной информацией. Исследования в значительной степени ограничивались играми для двух игроков, в которых игроки поочередно изменяют позицию определенным образом или совершают ходы для достижения определенного выигрышного условия. Комбинаторная теория игр традиционно не изучала игры, основанные на случайности, или игры с неполной или несовершенной информацией, предпочитая игры с полной информацией, в которых состояние игры и набор доступных ходов всегда известны обоим игрокам. Однако, по мере развития математических методов, расширяется круг игр, которые можно математически анализировать, таким образом, границы этой области постоянно меняются. Исследователи обычно определяют, что они подразумевают под «игрой» в начале работы, и эти определения часто различаются, поскольку они специфичны для анализируемой игры и не претендуют на охват всей области. Комбинаторные игры включают в себя хорошо известные игры, такие как шахматы, шашки и го, которые считаются нетривиальными, и крестики-нолики, которые считаются тривиальными в том смысле, что их «легко решить». Некоторые комбинаторные игры могут также иметь неограниченную игровую область, например, бесконечные шахматы. В комбинаторной теории игр ходы в этих и других играх представляются в виде дерева игры. Комбинаторные игры также включают в себя однопользовательские комбинаторные головоломки, такие как судоку, и автоматы без игроков, такие как «Игра жизни» Конвея (хотя в строгом определении «игра» предполагает участие более одного игрока, поэтому используются термины «головоломка» и «автомат»). Теория игр в целом включает в себя игры, основанные на случайности, игры с неполной информацией и игры, в которых игроки могут ходить одновременно, и они, как правило, моделируют реальные ситуации принятия решений. Комбинаторная теория игр имеет иной акцент, чем «традиционная» или «экономическая» теория игр, которая изначально разрабатывалась для изучения игр с простой комбинаторной структурой, но с элементами случайности (хотя она также рассматривает последовательные ходы, см. игру в развернутой форме). По сути, комбинаторная теория игр внесла новые методы анализа деревьев игр, например, с использованием сюрреальных чисел, которые являются подклассом всех двухсторонних игр с полной информацией. Другие игры из реального мира в основном слишком сложны для полного анализа на сегодняшний день, хотя теория добилась некоторых недавних успехов в анализе эндшпилей в го. Применение комбинаторной теории игр к позиции пытается определить оптимальную последовательность ходов для обоих игроков до конца игры, и таким образом найти оптимальный ход в любой позиции. На практике этот процесс чрезвычайно сложен, если игра не очень проста. Может быть полезно различать комбинаторные «математические игры», представляющие интерес в первую очередь для математиков и ученых, чтобы размышлять и решать, и комбинаторные «игры», представляющие интерес для широкой публики как форма развлечения и соревнования. Однако некоторые игры попадают в обе категории. Например, ним – это игра, которая сыграла важную роль в создании комбинаторной теории игр и одна из первых компьютерных игр. Крестики-нолики до сих пор используются для обучения студентов компьютерных наук основам разработки игрового ИИ.

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field. Combinatorial games include well known games such as chess, checkers, and Go, which are regarded as non trivial, and tic tac toe, which is considered trivial, in the sense of being "easy to solve". Some combinatorial games may also have an unbounded playing area, such as infinite chess. In combinatorial game theory, the moves in these and other games are represented as a game tree. Combinatorial games also include one player combinatorial puzzles such as Sudoku, and no player automata, such as Conway's Game of Life, (although in the strictest definition, "games" can be said to require more than one participant, thus the designations of "puzzle" and "automata".) Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real life decision making situations. Combinatorial game theory has a different emphasis than "traditional" or "economic" game theory, which was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive form game). Essentially, combinatorial game theory has contributed new methods for analyzing game trees, for example using surreal numbers, which are a subclass of all two player perfect information games. Other real world games are mostly too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames. Applying combinatorial game theory to a position attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is torturously difficult unless the game is very simple. It can be helpful to distinguish between combinatorial "mathgames" of interest primarily to mathematicians and scientists to ponder and solve, and combinatorial "playgames" of interest to the general population as a form of entertainment and competition. However, a number of games fall into both categories. Nim, for instance, is a playgame instrumental in the foundation of combinatorial game theory, and one of the first computerized games. Tic tac toe is still used to teach basic principles of game AI design to computer science students.

История

Комбинаторная теория игр возникла в связи с теорией беспристрастных игр, в которых любой ход, доступный одному игроку, должен быть доступен и другому. Одной из таких игр является Nim, которую можно полностью решить. Nim — это беспристрастная игра для двух игроков, и в соответствии с нормальными правилами игры, что означает, что проигрывает игрок, который не может сделать ход. В 1930-х годах теорема Спрага — Гранди показала, что все беспристрастные игры эквивалентны кучкам в Nim, тем самым демонстрируя возможность существенных унификаций в играх, рассматриваемых на комбинаторном уровне, где важны детальные стратегии, а не только выигрыши. В 1960-х годах Элвин Р. Берлекамп, Джон Х. Конвей и Ричард К. Гай совместно представили теорию партийных игр, в которой требование, чтобы ход, доступный одному игроку, был доступен обоим, было ослаблено. Их результаты были опубликованы в книге «Winning Ways for your Mathematical Plays» в 1982 году. Однако первой опубликованной работой по этой теме была книга Конвея 1976 года «О числах и играх», также известная как ONAG, в которой было введено понятие сюрреалистических чисел и обобщение для игр. «О числах и играх» также была результатом сотрудничества Берлекампа, Конвея и Гая. Комбинаторные игры обычно, по соглашению, приводятся к форме, в которой один игрок выигрывает, когда у другого не осталось ходов. Легко преобразовать любую конечную игру с только двумя возможными исходами в эквивалентную, где применяется это соглашение. Одним из важнейших понятий в теории комбинаторных игр является сумма двух игр, которая представляет собой игру, в которой каждый игрок может выбирать, делать ход либо в одной игре, либо в другой в любой момент игры, и игрок выигрывает, когда у его противника нет хода ни в одной из игр. Этот способ объединения игр приводит к богатой и мощной математической структуре. Конвей отметил в книге «О числах и играх», что вдохновение для теории партийных игр было основано на его наблюдениях за игрой в эндшпилях го, которые часто можно разложить на суммы более простых эндшпилей, изолированных друг от друга в разных частях доски.

Combinatorial game theory arose in relation to the theory of impartial games, in which any play available to one player must be available to the other as well. One such game is Nim, which can be solved completely. Nim is an impartial game for two players, and subject to the normal play condition, which means that a player who cannot move loses. In the 1930s, the Sprague–Grundy theorem showed that all impartial games are equivalent to heaps in Nim, thus showing that major unifications are possible in games considered at a combinatorial level, in which detailed strategies matter, not just pay offs. In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book Winning Ways for your Mathematical Plays in 1982. However, the first work published on the subject was Conway's 1976 book On Numbers and Games, also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games was also a fruit of the collaboration between Berlekamp, Conway, and Guy. Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure. Conway stated in On Numbers and Games that the inspiration for the theory of partisan games was based on his observation of the play in Go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

Обзор

В простейшем виде игра – это список возможных «ходов», которые могут сделать два игрока, называемые левым и правым. Позиция в игре, полученная в результате любого хода, может рассматриваться как другая игра. Эта идея рассмотрения игр с точки зрения их возможных переходов в другие игры приводит к рекурсивному математическому определению игр, которое является стандартным в комбинаторной теории игр. В этом определении каждая игра имеет обозначение {L|R}, где L – множество позиций, в которые может перейти левый игрок, а R – множество позиций, в которые может перейти правый игрок; каждая позиция в L и R определяется как игра, использующая ту же нотацию. Используя Доминеринг в качестве примера, обозначим каждое из шестнадцати полей доски 4x4 как A1 для верхнего левого квадрата, C2 для третьего поля слева во втором ряду сверху и так далее. Мы используем, например, (D3, D4) для обозначения игровой позиции, в которой вертикальное домино размещено в правом нижнем углу. Тогда начальная позиция может быть описана в нотации комбинаторной теории игр как

В стандартной игре Cross Cram игроки ходят по очереди, но эта очередность обрабатывается неявно в определениях комбинаторной теории игр, а не кодируется в состояниях игры. Описанная выше игра представляет собой сценарий, в котором у каждого игрока остался только один ход, и если любой игрок сделает этот ход, он выиграет. (Незначительный пустой квадрат в C3 был опущен из диаграммы.) {|} в списке ходов каждого игрока (соответствующий единственному оставшемуся квадрату после хода) называется нулевой игрой и может быть сокращенно обозначено как 0. В нулевой игре ни у одного игрока нет допустимых ходов; таким образом, игрок, чей ход наступает, когда возникает нулевая игра, автоматически проигрывает. Тип игры на диаграмме выше также имеет простое название; он называется звездной игрой и может быть сокращенно обозначен как ∗. В звездной игре единственный допустимый ход ведет к нулевой игре, что означает, что тот, чей ход наступает во время звездной игры, автоматически выигрывает. Дополнительный тип игры, не встречающийся в Доминеринге, – это циклическая игра, в которой допустимый ход левого или правого игрока – это игра, которая затем может вернуться к исходной игре. Например, шашки становятся циклическими, когда одна из фигур становится дамой, поскольку тогда она может бесконечно перемещаться между двумя или более полями. Игра, которая не обладает такими ходами, называется ациклической.

Звезда

Звезда, записываемая как ∗ или {0|0}, является выигрышной позицией для первого игрока, поскольку любой игрок, ходящий первым, должен перейти в нулевую позицию и, следовательно, выиграть. ∗ + ∗ = 0, потому что первый игрок должен превратить одну копию ∗ в 0, а затем второй игрок должен превратить другую копию ∗ в 0; в этот момент первый игрок проиграет, так как 0 + 0 не допускает ходов. Игра ∗ не является ни положительной, ни отрицательной; она и все другие игры, в которых первый игрок выигрывает (независимо от стороны игрока), считаются нечеткими или отождествляются с 0; символически мы пишем ∗ || 0.

"Жаркие" игры

Рассмотрим игру {1|−1}. Оба хода в этой игре дают преимущество игроку, который их делает; поэтому игра называется "горячей". Она больше любого числа, меньшего −1, меньше любого числа, большего 1, и не определена с любым числом между ними. Она записывается как ±1. Её можно складывать с числами или умножать на положительные числа обычным образом; например, 4 ± 1 = {5|3}.

Нимберы

Непристрастная игра — это игра, в которой на каждой позиции доступны одинаковые ходы для обоих игроков. Например, Ним является непристрастной игрой, поскольку любой набор объектов, который может быть удалён одним игроком, может быть удалён и другим. Однако доминирование не является непристрастным, так как один игрок выкладывает горизонтальные домино, а другой — вертикальные. Аналогично, шашки не являются непристрастной игрой, поскольку игроки владеют фигурами разных цветов. Для любого порядкового числа можно определить непристрастную игру, обобщающую Ним, в которой при каждом ходе любой игрок может заменить число на любое меньшее порядковое число; игры, определённые таким образом, называются нимберами. Теорема Спрага — Гранди утверждает, что любая непристрастная игра эквивалентна нимберу. "Наименьшие" нимберы — самые простые и наименьшие в обычном порядке порядковых чисел — это 0 и ∗.