Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Игры в теории игр
Games in game theory
В комбинаторной теории игр изучается несколько игр, связанных с раскраской карт. Общая идея заключается в том, что нам дана карта с нарисованными областями, но не все области раскрашены. Два игрока, Левый и Правый, по очереди раскрашивают одну нераскрашенную область за ход, соблюдая различные ограничения, как и в задаче о раскраске карты. Ограничения на ходы и условие победы являются характеристиками конкретной игры. Некоторым игрокам удобнее раскрашивать вершины двойственного графа, как в теореме о четырех красках. В этом способе игры области представляются небольшими кружками, а кружки для соседних областей соединяются линиями или кривыми. Преимущества этого способа в том, что за ход нужно отмечать небольшую площадь и что представление обычно занимает меньше места на бумаге или экране. Первое преимущество менее существенно при игре с компьютерным интерфейсом, а не карандашом и бумагой. Также можно играть с камнями го или шашками.
Several map coloring games are studied in combinatorial game theory. The general idea is that we are given a map with regions drawn in but with not all the regions colored. Two players, Left and Right, take turns coloring in one uncolored region per turn, subject to various constraints, as in the map coloring problem. The move constraints and the winning condition are features of the particular game. Some players find it easier to color vertices of the dual graph, as in the Four color theorem. In this method of play, the regions are represented by small circles, and the circles for neighboring regions are linked by line segments or curves. The advantages of this method are that only a small area need be marked on a turn, and that the representation usually takes up less space on the paper or screen. The first advantage is less important when playing with a computer interface instead of pencil and paper. It is also possible to play with Go stones or Checkers.
Ограничения перемещения
Неотъемлемым ограничением в каждой игре является набор цветов, доступных игрокам для окрашивания регионов. Если у игроков слева и справа одинаковый набор цветов, игра считается беспристрастной, иначе – партийной. Набор доступных цветов также может зависеть от состояния игры; например, может потребоваться, чтобы цвет, используемый на текущем ходу, отличался от цвета, использованного на предыдущем. Ограничения, основанные на карте, обычно определяются окрашиваемым регионом и его соседями, в то время как в задаче раскраски карты регионами считаются соседние, если они имеют общую границу длиннее одной точки. Классическая задача раскраски карты требует, чтобы никакие два соседних региона не были окрашены в один и тот же цвет. Классическое ограничение хода обеспечивает это, запрещая окрашивать регион в цвет, совпадающий с цветом одного из его соседей. Антиклассическое ограничение, напротив, запрещает окрашивать регион в цвет, отличный от цвета одного из его соседей. Другим видом ограничения является требование (entailment), согласно которому каждый ход после первого должен окрашивать соседа региона, окрашенного на предыдущем ходу. Антитребование (anti-entailment) – еще одно возможное ограничение. Возможны и другие типы ограничений, например, требование, чтобы регионы, являющиеся соседями соседей, использовали разные или одинаковые цвета. Эту концепцию можно рассматривать как применимую к регионам на графовом расстоянии два, и ее можно обобщить на большие расстояния.
An inherent constraint in each game is the set of colors available to the players in coloring regions. If Left and Right have the same colors available to them, the game is impartial; otherwise the game is partisan. The set of colors could also depend on the state of the game; for instance it could be required that the color used be different from the color used on the previous move. The map based constraints on a move are usually based on the region to be colored and its neighbors, whereas in the map coloring problem, regions are considered to be neighbors when they meet along a boundary longer than a single point. The classical map coloring problem requires that no two neighboring regions be given the same color. The classical move constraint enforces this by prohibiting coloring a region with the same color as one of its neighbor. The anticlassical constraint prohibits coloring a region with a color that differs from the color of one of its neighbors. Another kind of constraint is entailment, in which each move after the first must color a neighbor of the region colored on the previous move. Anti entailment is another possible constraint. Other sorts of constraints are possible, such as requiring regions that are neighbors of neighbors to use different or identical colors. This concept can be considered as applying to regions at graph distance two, and can be generalized to greater distances.
Условия выигрыша
Победителем обычно является последний игрок, сделавший ход. Это называется обычной конвенцией игры. В конвенции мизерной игры проигрывает последний игрок, сделавший ход. Существуют и другие возможные условия победы и поражения, например, подсчёт территории, как в игре Го.
The winner is usually the last player to move. This is called the normal play convention. The misère play convention considers the last player to move to lose the game. There are other possible winning and losing conditions possible, such as counting territory, as in Go.
Монохромные и варианты
Эти игры, впервые описанные в (Silverman, 1971), все используют классическое ограничение на ход. В беспристрастной игре "Монохром" доступен только один цвет, поэтому каждый ход удаляет окрашенную область и её соседей из игры. В игре "Бихром" оба игрока могут выбирать из двух цветов, соблюдая классическое условие. Поскольку оба игрока выбирают из одного и того же набора из двух цветов, игра остаётся беспристрастной. Игра "Трихром" расширяет это до трёх цветов для игроков. Условие можно обобщить на любое фиксированное количество цветов, что порождает новые игры. Как отмечает Сильверман, хотя теорема о четырёх цветах утверждает, что любую планарную карту можно раскрасить четырьмя цветами, она не применима к картам, в которых некоторые области уже окрашены, поэтому добавление более четырёх цветов может повлиять на ход игр.
These games, which appeared in (Silverman, 1971), all use the classical move constraint. In the impartial game "Monochrome" there is only one color available, so every move removes the colored region and its neighbors from play. In "Bichrome" both players have a choice of two colors, subject to the classical condition. Both players choose from the same two colors, so the game is impartial. "Trichrome" extends this to three colors to the players. The condition can be extended to any fixed number of colors, yielding further games. As Silverman mentions, although the Four color theorem shows that any planar map can be colored with four colors, it does not apply to maps in which some of the colors have been filled in, so adding more than four colors may have an effect on the games.
Кол и Снорт
В игре "Col" есть два цвета, подчиняющихся классическому ограничению, однако Левому разрешено окрашивать только области в "синий" цвет (B"l"ue), а Правому – только в "красный" цвет ("R"ed). Таким образом, это партийная игра, поскольку в процессе игры Левый и Правый получают доступ к разным возможным ходам. Игра "Snort" использует аналогичное партийное назначение двух цветов, но с антиклассическим ограничением: соседним областям нельзя присваивать разные цвета. Окрашивание областей объясняется как распределение полей между быками и коровами, при этом на соседних полях не могут находиться животные противоположного пола, чтобы не отвлекаться от выпаса. Эти игры были представлены и проанализированы в (Conway, 1976). Названия мнемонически отражают разницу в ограничениях (классическое раскрашивание карты и звуки животных), однако Конвей также приписывает их своим коллегам Колину Воуту и Саймону Нортону.
In "Col" there are two colors subject to the classical constraint, but Left is only allowed to color regions B"l"ue, while Right is only allowed to color them "R"ed. Thus this is a partisan game, because different moves become available to Left and Right in the course of play. "Snort" uses a similar partisan assignment of two colors, but with the anticlassical constraint: neighboring regions are not allowed to be given different colors. Coloring the regions is explained as assigning fields to bulls and cows, where neighboring fields may not contain cattle of the opposite sex, lest they be distracted from their grazing. These games were presented and analyzed in (Conway, 1976). The names are mnemonic for the difference in constraints (classical map coloring versus animal noises), but Conway also attributes them to his colleagues Colin Vout and Simon Norton.
Другие игры
В беспристрастной игре "Контакт" (Silverman, 1971) используется один цвет с условием следования: все ходы после первого должны быть сделаны на области, соседние с последней окрашенной областью. Сильверман также приводит пример игры "Контакт в проигрыш". Концепция игры раскраски карты может быть расширена и применена к играм, таким как "Ангелы и Дьяволы", где правила раскраски несколько иным образом определены.
The impartial game "Contact" (Silverman, 1971) uses a single color with the entailment constraint: all moves after the first color a neighbor of the most recently colored region. Silverman also provides an example of "Misère Contact". The concept of a map coloring game may be extended to cover games such as Angels and Devils, where the rules for coloring are somewhat different in flavor.