Просмотр кода страницы 3.3.5 Гекс - игра без ничьих

<span id="гекс-игра-без-ничьих"></span>

Забавно, что эту игру придумали независимо друг от друга сразу два человека — Пит Хейн в Дании в 1942 г. и Джон Нэш в США в 1948 г. Пит Хейн не менее знаменит среди датчан, чем Джон Нэш среди специалистов по теории игр. Будучи прямым потомком Пита Хейна — старшего, голландского моряка и народного героя XVII в., Пит Хейн — младший приобрёл известность благодаря созданию коротких стихотворных афоризмов, которые он называл «груками» (gruk). Груки были способом, позволявшим Хейну во время фашистской оккупации Дании обходить цензуру и доносить свои мысли до других датчан в иносказательной форме.

[[File:image99.jpeg|642x481px]]

Отец кибернетики Норберт Винер был большим почитателем литературного таланта Хейна и так отзывался о его творчестве: «''Пит Хейн — мастер эпиграммы. Его следует читать по меньшей мере на двух уровнях — внешнем и более глубоком. И в том и в другом случае они вызывают во мне восхищение. Какое богатство значительных мыслей заключено в них!''» Многие строки Хейна стали крылатыми словами и поговорками. Хейн был не только талантливым литератором, но и художником, инженером и изобретателем. Когда Пит Хейн работал в Институте теоретической физики Университета Копенгагена, то именно его Нильс Бор избрал в качестве партнёра по «интеллектуальному пинг-понгу»<ref>Hicks J. (1966). Close-up / Piet Hein bestrides art and science / LIFE, Oct. 14 // https://books.google.ru/books?id=lFYEAAAAMBAJ&amp;pg=PA64</ref><sup>,</sup> <ref>Варденга Г. Л. (1997). П. Хэйн. Груки / Вопросы истории естествознания и техники. № 3 // http://vivovoco.ibmh.msk.su/VV/PAPERS/BONMOTS/GROOKS/HEIN.HTM</ref>. Помимо других научных проблем, Хейн размышлял над знаменитой топологической проблемой четырёх красок (теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными красками так, чтобы любые две области с общим участком границы были раскрашены в разные цвета), и ему пришла в голову идея новой игры. Хейн рассказал о ней в одной из своих лекций, и через некоторое время её правила опубликовала газета ''Politiken''. Игра быстро стала весьма популярной в Дании — гекс тогда называли «многоугольники» и играли в него на бумаге. Со временем в продаже появились специальные блокноты для игры с напечатанными в них изображениями игровых полей. Задачи по гексу регулярно появлялись в газете ''Politiken'', которая назначала премии за лучшие решения. В 1950-е гг. доски для игры в гекс начала выпускать фирма Parker Brothers, тогда же игра и получила своё современное название — гекс.

Поле для игры в гекс состоит из шестиугольных ячеек. Оно может быть любого размера или формы, но обычно используют поле в форме ромба размером ''n'' × ''n'', обычно 11 × 11, 14 × 14 или 19 × 19. Нэш считал наилучшим размером 14 × 14.

Игра ведётся фишками двух цветов (обычно красными и синими). Игроки по очереди ставят фишки своего цвета в свободные ячейки поля. Первый ход делают синие.

Две противоположные стороны поля окрашены в красный и синий цвета и называются красной и синей сторонами соответственно. Ячейки в углах поля являются общими. Чтобы выиграть, игрок должен выстроить цепочку из своих фишек, соединив ею стороны своего цвета, то есть красные стремятся построить цепь из красных фишек между двумя красными сторонами доски, а синие — цепь из синих фишек, соединяющую синие стороны<ref>Toft H. (2019). Hex, Inside and Out: The Full Story. CRC Press // https://doi.org/10.1201/9780429031960</ref>.

[[File:image100.png|697x420px]]

Рис. 57. Пример игры в гекс

В отношении гекса авторы статьи в русской «Википедии» утверждают следующее: «''Нетрудно заметить, что игра никогда не кончается вничью''». Это утверждение напоминает мне анекдот про Лившица и Ландау, в котором первый заливает чаем сорок страниц доказательства, а второй советует заменить эти сорок страниц словами «очевидно, что…».

[[File:image101.jpeg|642x481px]]

Джон Нэш был первым, кто указал (примерно в 1949 г.), что гекс не может закончиться ничьей. Это утверждение в разговорной речи иногда называют теоремой гекса. В наши дни известно, что теорема гекса эквивалентна теореме Брауэра о неподвижной точке. Рассуждения Нэша, однако, не были опубликованы в научной прессе, они содержатся во внутреннем техническом отчёте RAND Corporation, подготовленном в 1952 г. Дословно Нэш пишет в нём следующее: «''Природа игры такова, что если всё игровое поле заполнено фишками, то либо белые совершили соединение, либо чёрные сделали это'' (Нэш использовал эти два цвета для фишек играющих сторон. — ''С. М.''). ''Соединение и блокирование противника являются эквивалентными действиями''»<ref>Nash J. (1952). Rand Corp. technical report D-1164: Some Games and Machines for Playing Them // https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf</ref>. Формальное доказательство было опубликовано Дэвидом Гейлом в 1979 г., то есть более чем через тридцать лет после изобретения игры. На самом деле оно совершенно нетривиальное и содержит десять шагов рассуждения:

# Возьмём любое поле игры в гекс, все ячейки которого полностью заполнены отметками X (ставит первый игрок) или 0 (ставит второй игрок).
# Возьмём точку соприкосновения сторон X и 0 в любом углу и от неё нарисуем путь вдоль рёбер, который будет проходить только между шестиугольниками с разными отметками X и 0. При этом края игрового поля мы считаем граничащими со сплошной стеной из шестиугольников с соответствующими стороне отметками (X или 0).
# Каждая вершина пути будет окружена тремя шестиугольниками, и поэтому путь не сможет содержать самопересечений или петель, поскольку пересекающаяся часть пути должна проходить между двумя шестиугольниками с одинаковыми отметками. Таким образом, путь должен иметь завершение.
# Путь не может завершаться в середине игрового поля, так как каждый конец пути заканчивается узлом, окружённым тремя шестиугольниками, два из которых должны содержать разные отметки в соответствии с условием построения пути. Поскольку третий шестиугольник не может содержать отметку, отличающуюся одновременно от этих отметок двух других, то путь будет продолжен по одной или другой стороне третьего шестиугольника.
# Аналогично путь не может заканчиваться и на краях поля, поскольку края игрового поля считаются граничащими со сплошной стеной из шестиугольников с соответствующими стороне отметками (X или 0).
# Таким образом, путь может закончиться только в другом углу.
# Согласно построению пути, с одной его стороны будет непрерывная цепочка из шестиугольников с отметкой X, а с другой — цепочка из шестиугольников с отметкой 0.
# Из предыдущего следует, что путь не может закончиться в углу, противоположном начальному, потому что в нём метки X и 0 находятся на иных сторонах пути, чем в исходном углу. Таким образом, путь может соединять только смежные углы (принадлежащие одной стороне).
# Поскольку путь соединяет смежные углы, сторона игрового поля между этими углами (скажем, сторона X) отрезана от остальной части игрового поля непрерывной цепью противоположных отметок (в данном случае 0). Эта неразрывная цепь обязательно соединяет две другие стороны, прилегающие к углам.
# Таким образом, на полностью заполненном поле для игры в гекс должен быть победитель.

[[File:image102.png|697x415px]]

Рис. 58. Иллюстрация к вышеизложенному доказательству

Итак, геометрия гекса не позволяет ни одному из игроков рассчитывать на ничью, следовательно, при идеальной игре сторон у гекса должен быть победитель<ref>Gale D. (1979). The Game of Hex and Brouwer Fixed-Point Theorem / The American Mathematical Monthly. Mathematical Association of America, Vol. 86, Iss. 10, pp. 818–827 //https://doi.org/10.2307/2320146</ref>. В своём отчёте 1952 г. Нэш приводит любопытное соображение: «''В гексе, —'' пишет он, ''— наличие лишней фишки на игровом поле никогда не может быть недостатком. Это в корне отличается от ситуации в шахматах или го, в которых наличие фигуры или камня на определённом участке доски может быть помехой''». Из этого Нэш делает вывод, что у игрока, ходящего вторым, не может быть выигрышной стратегии и что, следовательно, при идеальной игре обеих сторон игра является выигранной для первого игрока. Однако Нэш отмечает, что, по всей видимости, у первого игрока нет простой стратегии победы<ref>Nash J. (1952). Rand Corp. technical report D-1164: Some Games and Machines for Playing Them // https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf</ref>. И действительно, до сих пор придумать какое-либо простое правило для первого игрока, позволяющее ему выигрывать в гекс с гарантией, не удалось. В настоящее время найдено слабое решение для игры в гекс лишь на поле 9 × 9, хотя благодаря доказательству Нэша мы знаем, что игра является теоретически выигранной первым игроком для любого размера поля. Таким образом, для гекса с произвольным размером поля мы обладаем ультраслабым решением.

Иногда ультраслабым образом не может быть установлена точная теоретическая игровая оценка стартовой позиции, но может быть установлено её ограничение сверху или снизу. Например, в некоторых играх вторая сторона может повторять ходы противника, что гарантирует ей ничью. Для таких игр можно сказать, что их стартовая позиция точно не является выигрышной для первой стороны. Этот логический трюк называют обычно «воровством стратегии».
<references />
‎<comments />