Hex (настольная игра) - Hex (board game)

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

Hex
Доска-шестигранная-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 году под названием Hex; они больше не производятся. В шестигранник также можно играть бумагой и карандашом на миллиметровой бумаге с шестигранной линейкой.

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

Тип игры

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

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

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

История

Изобретение

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

Опубликованные игры

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

В 1952 г. Братья Паркер продал версию. Они назвали свою версию «Hex», и название прижилось.[4] Братья Паркер также продавала версию под названием "Con-tac-tix" в 1968 году.[2] Hex также был выпущен как одна из игр серии 3M Paper Games в 1974 году; игра содержала блокнот размером 5½ × 8½ дюймов на 50 листов с шестигранной сеткой в ​​линейку. Hex в настоящее время публикуется Nestorgames в размерах 11x11 и 14x14.[7]

Машина Шеннона Hex

Около 1950 г., американский математик и инженер-электрик. Клод Шеннон и Э. Ф. Мур сконструировал аналоговый игровой автомат Hex, который по сути представлял собой сеть сопротивлений с резисторами для ребер и лампочками для вершин.[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 и несколько университетов[11]) используя смесь:[12]

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

Автоматы

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

Игра

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

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

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

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

Стратегия

Из доказательства выигрышной стратегии для первого игрока известно, что доска 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 должен быть победитель.

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

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

Вычислительная сложность обобщений

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

Игровое дерево 11 на 11 Hex

В 11 × 11 Hex примерно 2,4 × 1056 возможные правовые позиции;[27] это по сравнению с 4,6 × 1046 правовые позиции в шахматах.[28]

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

Интересные сокращения игрового дерева доступны, если отметить, что доска имеет двойную двустороннюю симметрию, а также вращательную симметрию на 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, что связано с отношением игры к более старой игре. Идти. По книге Прекрасный ум, Джон Нэш (один из изобретателей игры) рекомендовал 14 × 14 как оптимальный размер.

Рекс (обратный шестигранник)

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

Блокбастеры

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

Y

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

Гаванна

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

Projex

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

Конкуренция

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c d Хейворд; Тофт (2019). Hex, Inside and Out: Полная история. CRC Press.
  2. ^ а б Con-tac-tix инструкция (PDF). Братья Паркер. 1968 г.
  3. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история. Бока-Ратон, Флорида: CRC Press. п. 156. ISBN  978-0367144258.
  4. ^ а б c d е Гарднер, М. (1959). Книга "Математические головоломки и решения" Scientific American. Нью-Йорк, Нью-Йорк: Саймон и Шустер. стр.73–83. ISBN  0-226-28254-6.
  5. ^ Насар, Сильвия (13 ноября 1994 г.). «Потерянные годы нобелевского лауреата». Нью-Йорк Таймс. Получено 23 августа 2017.
  6. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история. Бока-Ратон, Флорида: CRC Press. п. 127-138. ISBN  978-0367144258.
  7. ^ "nestorgames - развлечение на вынос". www.nestorgames.com. Получено 3 сентября 2020.
  8. ^ Шеннон, К. (1953). «Компьютеры и автоматы». Труды Института Радиоинженеров.. 41 (10): 1234–41. Дои:10.1109 / jrproc.1953.274273. S2CID  51666906.
  9. ^ Аншелевич, В. (2002). Иерархический подход к компьютерному шестиугольнику.
  10. ^ facebookincubator / Polygames, Инкубатор Facebook, 28 мая 2020 г., получено 29 мая 2020
  11. ^ «Открытый исходный код Polygames, новый фреймворк для обучения ботов с ИИ через самостоятельную игру». ai.facebook.com. Получено 29 мая 2020.
  12. ^ Казенаве, Тристан; Чен, Йен-Чи; Чен Гуань-Вэй; Чен, Ши-Ю; Чиу, Сиань-Донг; Дехос, Жюльен; Эльза, Мария; Гонг, Кученг; Ху, Хэнъюань; Халидов, Василь; Ли, Чэн-Лин (27 января 2020 г.). «Polygames: Улучшенное нулевое обучение». arXiv:2001.09832 [cs.LG ].
  13. ^ Маркус, Гэри (17 января 2018 г.). «Врожденность, AlphaZero и искусственный интеллект». arXiv:1801.05667 [cs.AI ].
  14. ^ Кучерави, Мюррей (январь 1984). "Хексмастер". Античный. п. 112. Получено 18 января 2019.
  15. ^ а б c Браун П.
  16. ^ Браун, стр.28
  17. ^ Браун, стр. 29–30.
  18. ^ Браун, стр. 71–77.
  19. ^ а б c Браун, стр.
  20. ^ Ласкер, стр.
  21. ^ Хейворд, Райан Б .; Рейсвейк, ван, Джек (6 октября 2006 г.). «Шестнадцатеричная система и комбинаторика». Дискретная математика. 306 (19–20): 2515–2528. Дои: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. Дои:10.2307/2320146. JSTOR  2320146.
  25. ^ Даже, S .; Тарьян, Р. Э. (1976). «Комбинаторная задача, полная в полиномиальном пространстве». Журнал ACM. 23 (4): 710–719. Дои:10.1145/321978.321989. S2CID  8845949.
  26. ^ Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex ist PSPACE-complete)». Acta Informatica (15): 167–191. Дои:10.1007 / bf00288964. S2CID  9125259.
  27. ^ Браун, С. (2000). Hex стратегия. Натик, Массачусетс: А.К. Peters, Ltd. стр. 5–6. ISBN  1-56881-117-9.
  28. ^ Тромп, Дж. «Количество шахматных диаграмм и позиций». Шахматная площадка Джона. Архивировано 29 июня 2011 года.CS1 maint: BOT: статус исходного URL-адреса неизвестен (связь)
  29. ^ Фактическое количество узлов 121 * 120 * ... * 79 = 121! / 78! = 7,4 * 1085.
  30. ^ О методе декомпозиции для поиска выигрышной стратегии в игре Hex В архиве 2 апреля 2012 г. Wayback Machine, Цзин Ян, Саймон Ляо и Мирек Павлак, 2002 г.
  31. ^ Неопубликованные официальные документы, ранее @ www.ee.umanitoba.com/~jingyang/
  32. ^ Решение 8x8 Hex, P. Henderson, B. Arneson, R. Hayward, Proc. IJCAI-09 505-510 (2009 г.)
  33. ^ Павлевич, Якуб; Хейворд, Райан (2013). "Масштабируемый параллельный поиск DFPN" (PDF). Proc. Компьютеры и игры. Получено 21 мая 2014.
  34. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история. Бока-Ратон, Флорида: CRC Press. п. 175. ISBN  978-0367144258.
  35. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история. Бока-Ратон, Флорида: CRC Press. п. 154. ISBN  978-0367144258.
  36. ^ Гарднер (1959) с.78
  37. ^ Браун (2000) стр.310
  38. ^ Хейворд, Райан Б .; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история. Бока-Ратон, Флорида: CRC Press. п. 175. ISBN  978-0367144258.
  39. ^ Фрилинг, Кристиан. «Как я придумывал игры и почему нет». MindSports. Получено 19 октября 2020.
  40. ^ «Проект». НастольнаяИграГик. Получено 28 февраля 2018.

дальнейшее чтение

  • Hex-стратегия: установление правильных связей , Браун К. (2000), А.К. Peters Ltd. Натик, Массачусетс. ISBN  1-56881-117-9 (торговая мягкая обложка, 363 стр.)
  • HEX: полная история, Хейворд Р. и Тофт Б. (2019), CRC Press Boca Raton, FL. ISBN  978-0-367-14422-7 (мягкая обложка)

внешняя ссылка