Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья об абстрактной стратегической игре. Для использования в других целях, см Hex game (значения) .

Шестигранник
Доска-шестигранная-11x11- (2) .jpg
Игровое поле 11 × 11 Hex, показывающее выигрышную конфигурацию для синего
Активные годы1942 – настоящее время
Жанр (ы)Настольная игра
Абстрактная стратегическая игра
Соединительная игра
Игроки2
Время установкиНикто
Время игры30 минут - 2 часа (доска 11 × 11)
Случайный шансНикто
Требуются навыкиСтратегия , тактика

Hex - это абстрактная настольная игра для двух игроков , в которой игроки пытаются соединить противоположные стороны шестиугольной доски . Hex был изобретен математиком и поэтом Питом Хайном в 1942 году и независимо от него Джоном Нэшем в 1948 году.

В нее традиционно играют на доске ромбов 11 × 11 , хотя также популярны доски 13 × 13 и 19 × 19. Каждому игроку назначается пара противоположных сторон доски, которые они должны попытаться соединить, по очереди кладя камень своего цвета на любое пустое место. После размещения камни не могут быть перемещены или удалены. Игрок побеждает, когда он успешно соединяет свои стороны вместе цепочкой соседних камней. В Hex ничья невозможна из-за топологии игрового поля.

В игре есть глубокая стратегия, острая тактика и глубокая математическая основа, связанная с теоремой Брауэра о неподвижной точке . Игра впервые была продана как настольная игра в Дании под названием Con-tac-tix , а в 1952 году компания Parker Brothers выпустила ее версию под названием Hex ; они больше не производятся. В шестигранник также можно играть с бумагой и карандашом на миллиметровой бумаге с шестигранной линейкой.

Исследования, связанные с шестнадцатеричными данными, актуальны в областях топологии, теории графов и матроидов , комбинаторики, теории игр и искусственного интеллекта.

Тип игры [ править ]

Hex - это игра соединение , [1] и могут быть классифицированы как чайник-Breaker игры , [1] : 122 определенный тип позиционной игры . Игра никогда не может закончиться ничьей (ничьей) , [1] : 99 другими словами, Hex также является « решительной игрой ».

Hex - это игра с конечной идеальной информацией и абстрактная стратегическая игра, которая относится к общей категории игр со связями . Hex - это частный случай «узловой» версии игры с переключением Шеннона . [1] : 122

Как продукт, Hex - это настольная игра ; также можно поиграть с бумагой и карандашом .

История [ править ]

Изобретение [ править ]

Игра была изобретена датским математиком Питом Хайном , который представил ее в 1942 году в Институте Нильса Бора . Хотя позже Хайн переименовал его в Con-tac-tix, [2] [3] он стал известен в Дании под названием Polygon из-за статьи Хайна в датской газете Politiken от 26 декабря 1942 г. игра, в которой он использовал это имя. Игра была независимо заново изобретена в 1948 году математиком Джоном Нэшем из Принстонского университета . [4] [5] По словам Мартина Гарднера , который представил Хекса в своем июльском 1957 годуВ колонке «Математические игры » товарищи по игре Нэша назвали игру либо Нэшем, либо Джоном, причем последнее название относится к тому факту, что в игру можно играть на шестиугольной плитке для ванной. [4] Хайн написал Гарднеру в 1957 году, в котором выразил сомнение в том, что Нэш открыл Hex независимо, но Нэш настаивает на том, что он заново изобрел игру до того, как познакомился с работами Хайна. Гарднер не смог независимо проверить или опровергнуть утверждение Нэша. [6]

Опубликованные игры [ править ]

Издание игры Parker Brothers

В 1952 году компания Parker Brothers выпустила на рынок новую версию. Они назвали свою версию «Hex», и название прижилось. [4] Parker Brothers также продавали версию под названием «Con-tac-tix» в 1968 году. [2] Hex также была выпущена как одна из игр серии 3M Paper Games в 1974 году; игра содержала 5 1 / 2  матрицы с размерностью 8 1 / 2  - дюймовый (140 мм × 220 мм) 50 листов коврик из сетки правили Hex. Hex в настоящее время публикуется Nestorgames в размерах 11x11 и 14x14. [7]

Машина Шеннона Hex [ править ]

Примерно в 1950 году американский математик и инженер-электрик Клод Шеннон и Э. Ф. Мур сконструировали аналоговую шестигранную игровую машину, которая, по сути, представляла собой резистивную сеть с резисторами для ребер и лампочками для вершин. [8] Перемещение, которое необходимо сделать, соответствовало определенной указанной седловой точке в сети. Машина неплохо сыграла в Hex. Позже исследователи, пытающиеся решить эту игру и разработать компьютерные алгоритмы, играющие в Hex, эмулировали сеть Шеннона для создания сильных автоматов. [9]

Хронология исследования [ править ]

В 1952 году Джон Нэш изложил доказательство существования того, что на симметричных досках у первого игрока есть выигрышная стратегия.

В 1964 году математик Альфред Леман показал, что Hex не может быть представлен как двоичный матроид , поэтому определенная выигрышная стратегия, подобная той, что используется в игре с переключением Шеннона на регулярной прямоугольной сетке, была недоступна. Позже было показано, что игра завершена для PSPACE.

В 2002 году была описана первая явная выигрышная стратегия (стратегия редукционного типа) на доске 7 × 7.

В 2000-х годах с помощью компьютерных алгоритмов поиска методом перебора были полностью решены Hex-доски размером до 9 × 9 (по состоянию на 2016 год).

До 2019 года люди оставались лучше компьютеров, по крайней мере, на больших досках, таких как 19x19, но 30 октября 2019 года программа Mootwo победила человека с лучшим рейтингом ELO на LittleGolem, также победителя различных турниров (игра доступна здесь ). Эта программа была основана на Polygames [10] (проект с открытым исходным кодом, первоначально разработанный Facebook Artificial Intelligence Research и несколькими университетами [11] ) с использованием сочетания: [12]

  • нулевое обучение как в AlphaZero
  • инвариантность доски благодаря полностью сверточным нейронным сетям (как в U-Net ) и пулингу
  • и растущие архитектуры (программа может учиться на маленькой доске, а затем экстраполировать на большую доску, в отличие от обоснованных популярных заявлений [13] о более ранних методах искусственного интеллекта, таких как оригинальный AlphaGo).

Автоматы [ править ]

В начале 1980-х Dolphin Microware опубликовала Hexmaster , реализацию для 8-битных компьютеров Atari . [14]Различные парадигмы, возникшие в результате исследования игры, использовались для создания цифровых компьютерных игровых автоматов Hex, начиная примерно с 2000 года. Первые реализации использовали оценочные функции, которые имитировали модель электрических цепей Шеннона и Мура, встроенную в структуру альфа-бета-поиска с ручными знаниями. на основе шаблонов. Примерно с 2006 года методы поиска по дереву Монте-Карло, заимствованные из успешных компьютерных реализаций Go, были введены и вскоре стали доминировать в этой области. Позже созданные вручную выкройки были дополнены методами машинного обучения для обнаружения паттернов. Эти программы теперь конкурируют с опытными игроками-людьми. Рейтинги на основе Элобыли назначены различным программам и могут использоваться для измерения технического прогресса, а также для оценки игровой силы против людей с рейтингом Эло. Текущие исследования часто публикуются либо в ежеквартальном журнале ICGA, либо в ежегодной серии « Успехи в компьютерных играх » (van den Herik et al. Eds.).

Игра [ править ]

Черные против белых на доске Hex

Каждому игроку назначен цвет, обычно красный и синий или белый и черный. [4] Игроки по очереди кладут камень своего цвета в одну ячейку на общем игровом поле. После размещения камни не перемещаются, не захватываются и не удаляются с доски. Цель каждого игрока состоит в том, чтобы сформировать связанный путь из своих камней, соединяющий противоположные стороны доски, отмеченные их цветами, прежде чем их противник соединит свои стороны аналогичным образом. Игрок, первым завершивший соединение, побеждает в игре. Шестиугольники на каждом из четырех углов принадлежат обеим смежным сторонам.

Нет необходимости строить полную цепочку между сторонами или заполнять всю доску до того, как игра будет решена (но если это произойдет по построению, игрок, положивший последний камень, выиграет); обычно заполняется от 1/3 до 40% доски, прежде чем становится очевидным, что тот или иной игрок может добиться победы. Это в некоторой степени аналогично шахматным партиям, заканчивающимся задолго до мата - игра обычно заканчивается отставкой одного или другого игрока.

Поскольку первый игрок, который сделает ход в шестнадцатеричном формате, имеет явное преимущество, правило пирога обычно применяется для справедливости. Это правило позволяет второму игроку выбирать, менять ли его позицию с первым игроком после того, как первый игрок сделает первый ход.

Стратегия [ править ]

Из доказательства выигрышной стратегии для первого игрока известно, что доска Hex должна иметь сложный тип подключения, который никогда не был решен. Игра состоит из создания небольших паттернов, которые имеют более простой тип связи, называемого «безопасное соединение», и объединения их в последовательности, образующие «путь». В конце концов, одному из игроков удастся сформировать надежно соединенную дорожку из камней и промежутков между его сторонами доски и выиграть. Заключительный этап игры при необходимости заключается в заполнении пустых мест на пути. [15]

Схема 1: мост (A <--> C), схема безопасного соединения

«Надежно соединенный» узор состоит из камней цвета игрока и открытых пространств, которые можно соединить в цепочку, непрерывную последовательность смежных камней по краям, независимо от того, как играет противник. [16] Одним из простейших таких узоров является мост (см. Диаграмму 1), который состоит из двух камней одного цвета (A и C) и пары открытых пространств (B и D). [17] Если противник играет в одном пространстве, игрок играет в другом, создавая непрерывную цепочку. Есть также надежно соединенные узоры, соединяющие камни с краями. [18]Есть много более надежно связанных паттернов, некоторые из которых довольно сложные, построенные из более простых, подобных показанным. Шаблоны и пути могут быть нарушены противником до того, как они будут завершены, поэтому конфигурация доски во время реальной игры часто выглядит как лоскутное одеяло, а не что-то запланированное или разработанное. [15]

Существуют более слабые типы связи, чем «безопасное соединение», которые существуют между камнями или между надежно соединенными узорами, между которыми есть несколько промежутков. [19] Средняя часть игры состоит из создания сети из таких слабо связанных камней и узоров [19], которые, как мы надеемся, позволят игроку, заполнив слабые звенья, построить только один надежно соединенный путь между сторонами, как в игре. прогрессирует. [19]

Успех в Hex требует особой способности визуализировать синтез сложных шаблонов эвристическим способом и оценивать, насколько эти шаблоны «достаточно прочно» связаны, чтобы обеспечить возможную победу. [15] Навык чем-то похож на визуализацию паттернов, последовательность ходов и оценку позиций в шахматах. [20]

Математическая теория [ править ]

Решительность [ править ]

Джон Нэш был первым, кто доказал (около 1949 г.) [21], что Hex не может закончиться ничьей, - нетривиальный результат, в просторечии называемый «теоремой Hex», которая, как мы теперь знаем, эквивалентна теореме Брауэра о неподвижной точке. Судя по всему, доказательство он не опубликовал. Первое изложение этого появляется в внутреннем техническом отчете 1952 года [22], в котором он заявляет, что «соединение и блокирование противника являются эквивалентными действиями». Первое строгое доказательство было опубликовано Джоном Р. Пирсом в его книге « Символы, сигналы и шум» 1961 года . [23] В 1979 году Дэвид Гейл опубликовал доказательство, которое также показало, что его можно использовать для доказательства двумерной теоремы Брауэра о неподвижной точке., и что определенность многомерных вариантов доказывает теорему о неподвижной точке в целом. [24] Краткий набросок требования об отсутствии ничьей для Hex из этого документа представлен ниже:

  1. Начните с шестиугольной доски, полностью заполненной шестиугольниками, отмеченными X или O (указывающими, какой игрок играл на этом шестиугольнике).
  2. Начиная с вершины шестиугольника в углу доски, где встречаются стороны X и O, нарисуйте путь по краям между шестиугольниками с разными отметками X / O.
  3. Поскольку каждая вершина пути окружена тремя шестиугольниками, путь не может самопересекаться или зацикливаться, поскольку пересекающаяся часть пути должна приближаться между двумя шестиугольниками с одинаковой разметкой. Итак, путь должен закончиться.
  4. Путь не может заканчиваться в середине доски, так как каждое ребро пути заканчивается узлом, окруженным тремя шестиугольниками, два из которых должны быть размечены по-разному при построении. Третий шестиугольник должен быть размечен иначе, чем два, примыкающих к пути, чтобы путь мог продолжаться в одну или другую сторону третьего шестиугольника.
  5. Точно так же, если стороны доски рассматриваются как сплошная стена из шестиугольников X или O, в зависимости от того, какой игрок пытается соединиться с ними, тогда путь не может заканчиваться на сторонах.
  6. Таким образом, путь может заканчиваться только на другом углу.
  7. Шестиугольники по обе стороны от линии образуют непрерывную цепочку из X шестиугольников с одной стороны и O шестиугольников с другой.
  8. Путь не может заканчиваться на противоположном углу, потому что метки X и O в этом углу будут перевернуты, что нарушит правило построения пути.
  9. Поскольку путь соединяет соседние углы, сторона доски между двумя углами (скажем, сторона X) отрезана от остальной части доски непрерывной цепочкой противоположных отметок (в данном случае O). Эта непрерывная цепочка обязательно соединяет две другие стороны, примыкающие к углам.
  10. Таким образом, на полностью заполненной доске Hex должен быть победитель.

Есть доказательство существования reductio ad absurdum, приписываемое Джону Нэшу c. 1949 год: у первого игрока в Hex на доске любого размера есть выигрышная стратегия . Такое доказательство не указывает на правильную стратегию игры. Доказательство является общим для ряда игр, включая Hex, и получило название аргумента «кражи стратегии». Вот очень сжатое неформальное изложение доказательства: [4]

  1. Игра не может закончиться ничьей (см. Выше), поэтому либо первый, либо второй игрок должен выиграть.
  2. Поскольку Hex - идеальная информационная игра, должна быть выигрышная стратегия как для первого, так и для второго игрока.
  3. Предположим, что у второго игрока есть выигрышная стратегия.
  4. Теперь первый игрок может принять следующую защиту. Он делает произвольный ход. После этого он применяет предложенную выше выигрышную стратегию второго игрока. Если при игре по этой стратегии от него требуется играть на клетке, где был сделан произвольный ход, он делает еще один произвольный ход. Таким образом, он использует выигрышную стратегию с одной дополнительной фигурой на доске.
  5. Эта дополнительная фигура не может мешать имитации выигрышной стратегии первым игроком, поскольку лишняя фигура всегда является преимуществом, а не гандикапом. Следовательно, первый игрок может выиграть.
  6. Поскольку теперь мы опровергли наше предположение о наличии выигрышной стратегии для второго игрока, мы вынуждены отказаться от этого предположения.
  7. Следовательно, у первого игрока должна быть выигрышная стратегия.

Вычислительная сложность обобщений [ править ]

В 1976 году Шимон Эвен и Роберт Тарджан доказали, что определение того, является ли позиция в игре с обобщенным гексагоном, сыгранной на произвольных графах, выигрышной позицией, полностью соответствует PSPACE . [25] Усиление этого результата было доказано Райшем путем сведения количественной булевой формулы в конъюнктивной нормальной форме к шестнадцатеричной формуле, применяемой на произвольных плоских графах. [26] В теории сложности вычислений., широко распространено предположение, что PSPACE-полные проблемы не могут быть решены с помощью эффективных (полиномиальное время) алгоритмов. Этот результат ограничивает эффективность наилучших возможных алгоритмов при рассмотрении произвольных позиций на досках неограниченного размера, но не исключает возможности простой выигрышной стратегии для начальной позиции (на досках неограниченного размера) или простого выигрыша. стратегия для всех позиций на доске определенного размера.

Дерево игры 11 на 11 Hex [ править ]

В 11 × 11 Hex имеется приблизительно 2,4 × 10 56 возможных допустимых положений; [27] для сравнения: 4,6 × 10 46 допустимых позиций в шахматах. [28]

Грубую оценку количества узлов в дереве игры можно получить как экспоненциальную функцию от среднего коэффициента ветвления и среднего количества слоев в игре, таким образом: b d, где d - глубина слоя, а b - коэффициент ветвления. В Hex средний коэффициент ветвления зависит от глубины слоя. Было заявлено, что средний фактор ветвления составляет около 100; [ необходима цитата ]что подразумевает среднюю глубину слоя 43 (на доске будет 121 открытое пространство, когда первый игрок сделает свой первый ход, и 79, когда он должен сделать свой 22-й ход, 43-й слой - среднее количество открытых мест , т.е. коэффициент ветвления, во время игры равен (121 + 120 + ... + 79) / 43 = 100). Следовательно, размер игрового дерева имеет верхнюю границу примерно 100 43 = 10 86 . [29] Ограничение включает некоторое количество незаконных позиций из-за игры, когда существует полная цепочка для одного или другого игрока, а также исключает допустимые позиции для игр длиннее 43 слоев. Другой исследователь получил оценку пространства состояний 10 57 и размер дерева игры 10 98, используя верхний предел игры в 50 слоев.[ Требуется цитата ] Это сопоставимо с размером дерева игры в шахматы с 10 123 узлами. [ необходима цитата ]

Интересные сокращения игрового дерева доступны, если отметить, что доска имеет двойную двустороннюю симметрию, а также вращательную симметрию на 180 °: для каждой позиции топологически идентичная позиция получается путем переворачивания доски влево-вправо, вверх-вниз или поворота на 180 °. .

Вычисленные стратегии для небольших плат [ править ]

В 2002 году Цзин Ян, Саймон Ляо и Мирек Павляк нашли явную выигрышную стратегию для первого игрока на шестнадцатеричных досках размером 7 × 7, используя метод декомпозиции с набором многоразовых локальных шаблонов. [30] Они расширили этот метод для слабого решения центральной пары топологически конгруэнтных отверстий на досках 8 × 8 в 2002 году и центрального отверстия на досках 9 × 9 в 2003 году. [31] В 2009 году Филип Хендерсон, Бродерик Арнесон и Райан Б. Хейворд завершил анализ доски 8 × 8 компьютерным поиском, решив все возможные отверстия. [32] В 2013 году Якуб Павлевич и Райан Б. Хейворд решили все дебюты для досок 9 × 9 и один (самый центральный) дебют на доске 10 × 10. [33]Для каждого N≤10 выигрышный первый ход в N × N Hex является самым центральным, что наводит на мысль о том, что это верно для любого N≥1.

Варианты [ править ]

Другие игры со связями с аналогичными целями, но с другой структурой включают игру с переключением Шеннона и TwixT . Оба они в некоторой степени похожи на древнюю азиатскую игру го .

Прямоугольные сетки, бумага и карандаш [ править ]

В игру можно играть на прямоугольной сетке, такой как шахматы, шашки или доска го, учитывая, что места (пересечения в случае го) соединены в одном диагональном направлении, но не в другом. В игру можно играть с бумагой и карандашом на прямоугольном массиве точек или миллиметровой бумаге таким же образом, используя два разных цветных карандаша.

Размеры доски [ править ]

Популярные размеры, отличные от стандартных 11x11, - 13x13 и 19x19, что связано с отношением игры к более старой игре го . Согласно книге A Beautiful Mind , Джон Нэш (один из изобретателей игры) рекомендовал 14 × 14 как оптимальный размер.

Рекс (обратный шестигранник) [ править ]

Нищета вариант Hex. Каждый игрок пытается заставить своего противника составить цепочку. Rex медленнее, чем Hex, поскольку на любой пустой доске с одинаковыми размерами проигрышная игра может отложить проигрыш до тех пор, пока не заполнится вся доска. [34] На досках с неравными размерами игрок, чьи стороны находятся дальше друг от друга, может выиграть независимо от того, кто играет первым. [35] На досках одинаковых размеров первый игрок может выиграть на доске с четным числом клеток на каждой стороне, а второй игрок может выиграть на доске с нечетным числом. [36] [37] На досках с четным номером один из выигрышных ходов первого игрока всегда заключается в том, чтобы положить камень в аккуратный угол. [34]

Блокбастеры [ править ]

У Хекса было воплощение как доска вопросов из телеигры Blockbusters . Чтобы разыграть «ход», участники должны были правильно ответить на вопрос. На доске было 5 чередующихся столбцов по 4 шестиугольника; одиночный игрок может соединяться сверху вниз за 4 хода, а команда из двух человек может соединяться слева направо за 5 ходов.

Д [ редактировать ]

В игре Y is Hex используется треугольная сетка из шестиугольников; цель состоит в том, чтобы любой игрок соединил все три стороны треугольника. Y - это обобщение Hex в том смысле, что любая позиция на Hex-доске может быть представлена ​​как эквивалентная позиция на более крупной Y-доске.

Хаванна [ править ]

Havannah - игра, основанная на Hex. [38] Он отличается от Hex тем, что в нем используется гексагональная сетка из шестиугольников, и выигрыш достигается путем формирования одного из трех шаблонов.

Projex [ править ]

Projex является вариацией Hex играл на вещественной проективной плоскости , в которой игроки имеют цель создания нон стягиваемую цикла. [39] Как и в Hex, здесь нет ничьей и нет позиции, в которой у обоих игроков есть выигрышная связь.

Конкурс [ править ]

По состоянию на 2016 год сообщалось о турнирах за бортом из Бразилии, Чехии, Дании, Франции, Германии, Италии, Нидерландов, Норвегии, Польши, Португалии, Испании, Великобритании и США.

Один из крупнейших турниров Hex организован Международным комитетом математических игр в Париже, Франция, и проводится ежегодно с 2013 года.

Hex также является частью компьютерной олимпиады .

См. Также [ править ]

  • Китайские шашки , играемые на шестиугольной доске
  • Связь игры
  • Математические игры
  • Проект GIPF, набор из 6 игр на шестивалентных сетках
  • Так
  • Игра Y

Ссылки [ править ]

  1. ^ а б в г Хейворд; Тофт (2019). Hex, Inside and Out: Полная история . CRC Press.
  2. ^ a b Руководство Con-tac-tix (PDF) . Братья Паркер. 1968 г.
  3. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 156. ISBN. 978-0367144258.
  4. ^ a b c d e Гарднер М. (1959). Книга "Математические головоломки и решения" от Scientific American . Нью-Йорк, Нью-Йорк: Саймон и Шустер. С.  73–83 . ISBN 0-226-28254-6.
  5. ^ Назар, Sylvia (13 ноября 1994). «Потерянные годы нобелевского лауреата» . Нью-Йорк Таймс . Проверено 23 августа 2017 года .
  6. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. С. 127–138. ISBN 978-0367144258.
  7. ^ "nestorgames - развлечься" . www.nestorgames.com . Дата обращения 3 сентября 2020 .
  8. Перейти ↑ Shannon, C. (1953). «Компьютеры и автоматы». Труды Института Радиоинженеров . 41 (10): 1234–41. DOI : 10,1109 / jrproc.1953.274273 . S2CID 51666906 . 
  9. ^ Аншелевич, В. (2002). Иерархический подход к компьютерному шестиугольнику.
  10. ^ facebookincubator / Polygames , Facebook Incubator, 28 мая 2020 г. , получено 29 мая 2020 г.
  11. ^ «Открытый исходный код Polygames, новый фреймворк для обучения ботов AI через самостоятельную игру» . ai.facebook.com . Проверено 29 мая 2020 .
  12. ^ Cazenave, Тристан; Чен, Йен-Чи; Чен Гуань-Вэй; Чен, Ши-Ю; Чиу, Сиань-Донг; Дехос, Жюльен; Эльза, Мария; Гонг, Кученг; Ху, Хэнъюань; Халидов, Василь; Ли, Чэн-Лин (27 января 2020 г.). «Полигры: Улучшенное нулевое обучение». arXiv : 2001.09832 [ cs.LG ].
  13. ↑ Маркус, Гэри (17 января 2018 г.). «Врожденность, AlphaZero и искусственный интеллект». arXiv : 1801.05667 [ cs.AI ].
  14. ^ Kucherawy, Мюррей (январь 1984). «Хексмастер» . Античный . п. 112 . Проверено 18 января 2019 .
  15. ^ a b c Браун с.
  16. ^ Браун, стр.28
  17. Перейти ↑ Browne, pp. 29–30
  18. ^ Browne, стр. 71-77
  19. ^ a b c Браун, стр.
  20. ^ Ласкер, стр.
  21. ^ Хейворд, Райан Б .; Рейсвейк, ван, Джек (6 октября 2006 г.). «Шестиугольник и комбинаторика» . Дискретная математика . 306 (19–20): 2515–2528. DOI : 10.1016 / j.disc.2006.01.029 . Проверено 21 октября 2020 года .
  22. ↑ Нэш, Джон (февраль 1952 г.). Технический отчет Rand Corp. D-1164: Некоторые игры и машины для игры в них. https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf
  23. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 99. ISBN 978-0367144258.
  24. ^ Дэвид Гейл (1979). "Игра шестиугольника и теорема Брауэра о неподвижной точке". Американский математический ежемесячник . Математическая ассоциация Америки. 86 (10): 818–827. DOI : 10.2307 / 2320146 . JSTOR 2320146 . 
  25. ^ Даже, S .; Tarjan, RE (1976). «Комбинаторная задача, полная в полиномиальном пространстве». Журнал ACM . 23 (4): 710–719. DOI : 10.1145 / 321978.321989 . S2CID 8845949 . 
  26. ^ Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex ist PSPACE-complete)». Acta Informatica (15): 167–191. DOI : 10.1007 / bf00288964 . S2CID 9125259 . 
  27. Перейти ↑ Browne, C (2000). Hex-стратегия . Натик, Массачусетс: AK Peters, Ltd., стр. 5–6. ISBN 1-56881-117-9.
  28. ^ Тромп, Дж. "Количество шахматных диаграмм и позиций" . Шахматная площадка Джона . Архивировано 29 июня 2011 года.CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
  29. ^ Фактическое количество узлов 121 * 120 * ... * 79 = 121! / 78! = 7,4 * 10 85 .
  30. ↑ О методе разложения для поиска выигрышной стратегии в игре Hex. Архивировано 2 апреля 2012 г. в Wayback Machine , Цзин Ян, Саймон Ляо и Мирек Павляк, 2002 г.
  31. ^ Неопубликованные официальные документы, ранее @ www.ee.umanitoba.com/~jingyang/
  32. ^ Решение 8x8 Hex , П. Хендерсон, Б. Арнесон и Р. Хейворд, Proc. IJCAI-09 505-510 (2009 г.)
  33. ^ Павлевич, Якуб; Хейворд, Райан (2013). «Масштабируемый параллельный поиск DFPN» (PDF) . Proc. Компьютеры и игры . Проверено 21 мая 2014 .
  34. ^ a b Хейворд, Райан Б.; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 175. ISBN 978-0367144258.
  35. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 154. ISBN 978-0367144258.
  36. ^ Gardner (1959) стр.78
  37. ^ Browne (2000) P.310
  38. ^ Свободный, Кристиан. «Как я придумывал игры и почему нет» . MindSports . Проверено 19 октября 2020 года .
  39. ^ "Projex" . BoardGameGeek . Проверено 28 февраля 2018 .

Дальнейшее чтение [ править ]

  • Hex Strategy: Making the Right Connections , Browne C. (2000), AK Peters Ltd. Натик, Массачусетс. ISBN 1-56881-117-9 (торговая книга в мягкой обложке, 363 стр.) 
  • HEX: Полная история , Хейворд Р. и Тофт Б. (2019), CRC Press, Бока-Ратон, Флорида. ISBN 978-0-367-14422-7 (мягкая обложка) 

Внешние ссылки [ править ]

  • Hex: A Strategy Guide, бесплатная Интернет-книга Мэтью Сеймура
  • Диссертация по истории, классификации и сложности Hex
  • HexWiki , вики, посвященная Hex
  • Computer Hex Research Group Университета Альберты
  • Страница Theory, на которой собраны теоретические работы по Hex (перемещены - страницы верхнего уровня в Hex-архиве ; загружаемые материалы больше не доступны)
  • Hex в BoardGameGeek
  • Game of Hex в MathWorld со ссылками на соответствующие математические статьи
  • Печатные шестигранные доски на бумаге формата A4 или A3 для использования со стандартными камнями го