stringtranslate.com

Гекс (настольная игра)

Hex (также называется Nash ) — это абстрактная стратегическая настольная игра для двух игроков , в которой игроки пытаются соединить противоположные стороны доски в форме ромба, состоящей из шестиугольных ячеек . Hex был изобретен математиком и поэтом Питом Хайном в 1942 году и позже заново открыт и популяризирован Джоном Нэшем .

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

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

Тип игры

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

Hex — это особый случай «узловой» версии игры Шеннона с переключением . [1] : В  Hex можно играть как в настольную игру или как в игру с карандашом и бумагой .

Правила

Конец игры в Гекс на стандартной доске 11×11. Здесь белые выигрывают игру.

В игре Hex используется ромбическая сетка из шестиугольников, обычно размером 11×11, хотя возможны и другие размеры. Каждому игроку назначен цвет, обычно красный и синий, или черный и белый. [2] Каждому игроку также назначены два противоположных края доски. Шестиугольники на каждом из четырех углов принадлежат обоим смежным краям доски.

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

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

Когда обоим игрокам становится ясно, кто победит в игре, то обычно, но не обязательно, проигравший игрок сдается. На практике большинство игр в Hex заканчиваются тем, что один из игроков сдается.

История

Изобретение

Игра была изобретена датским математиком Питом Хейном , который представил ее в 1942 году в Институте Нильса Бора . Хотя Хейн позже переименовал ее в Con-tac-tix, [3] [4] она стала известна в Дании под названием Polygon из-за статьи Хейна в датской газете Politiken от 26 декабря 1942 года , первого опубликованного описания игры, в которой он использовал это название.

Заявление Нэша

Игра была заново открыта в 1948 или 1949 году математиком Джоном Нэшем из Принстонского университета . [2] [5] По словам Мартина Гарднера , который представил Hex в своей колонке Mathematical Games в июле 1957 года , товарищи Нэша по игре называли игру либо Nash, либо John, причем последнее название отсылало к тому факту, что в игру можно было играть на шестиугольной плитке в ванной. [2] Нэш настаивал на том, что он открыл игру независимо от Хейна, но в этом есть некоторые сомнения, поскольку известно, что были датчане, включая Оге Бора , которые играли в Hex в Принстоне в 1940-х годах, так что Нэш мог подсознательно подхватить эту идею. Хейн написал Гарднеру в 1957 году, выразив сомнение в том, что Нэш открыл Hex независимо. Гарднер не смог независимо проверить или опровергнуть заявление Нэша. [6] Гарднер в частном порядке написал Хайну: «Я обсудил это с редактором, и мы решили, что было бы милосердно дать Нэшу шанс на успех. ... Тот факт, что вы придумали игру раньше всех остальных, неоспорим. Любое количество людей может прийти позже и сказать, что они думали о том же самом в какой-то момент, но это мало что значит, и никого это на самом деле не волнует». [1] : 134  В более позднем письме Хайну Гарднер также написал: «Только между нами и неофициально, я думаю, что вы попали в точку, когда упомянули «вспышку предложения», которая пришла к мистеру Нэшу из датского источника и о которой он позже забыл. Это кажется наиболее вероятным объяснением». [1] : 136 

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

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

Первоначально в 1942 году Хайн распространял игру, которая тогда называлась Polygon, в виде 50-листовых игровых планшетов. Каждый лист содержал пустую доску 11×11, на которой можно было играть карандашами или ручками. [1] В 1952 году Parker Brothers выпустили на рынок версию игры под названием «Hex», и это название прижилось. [2] Parker Brothers также продавали версию под названием «Con-tac-tix» в 1968 году. [3] Hex также была выпущена как одна из игр в серии 3M Paper Games Series 1974 года; игра содержала 5+1 ⁄ 2 -на- 8+1 ⁄ 2 дюйма (140 мм × 220 мм) 50-листовая тетрадь с разлинованными сетками Hex. В настоящее время Hex издается Nestorgames в размерах 11×11, 14×14 и 19×19. [7]

Hex-машина Шеннона

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

Хронология исследования

В 1942 году Хайну было известно, что игра Hex не может закончиться вничью; фактически, одним из его критериев разработки игры было то, что «только один из двух игроков может соединить свои две стороны». [1] : 29 

Хайну также было известно, что у первого игрока есть теоретическая выигрышная стратегия. [1] : 42 

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

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

В 1981 году Стефан Райш показал, что Hex является PSPACE-полным. [11]

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

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

Начиная примерно с 2006 года, область компьютерного Hex стала доминировать в методах поиска по дереву Монте-Карло, заимствованных из успешных компьютерных реализаций Go. Они заменили более ранние реализации, которые объединяли эвристику Шеннона, играющую в Hex, с альфа-бета-поиском . Что касается раннего компьютерного Hex, то среди известных ранних реализаций можно назвать Hexmaster от Dolphin Microware , опубликованный в начале 1980-х годов для 8-битных компьютеров Atari. [12]

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

Стратегия

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

«Мост» (A ↔ C) — простой пример надежно связанного узора. Он состоит из двух камней одного цвета (A и C) и пары открытых пространств (B и D).

«Безопасно связанный» узор состоит из камней цвета игрока и открытых пространств, которые могут быть соединены в цепочку, непрерывную последовательность смежных по ребру камней, независимо от того, как играет противник. [18] Одним из самых простых таких узоров является мост, который состоит из ромба из двух камней одного цвета и двух пустых пространств, где два камня не соприкасаются. [19] Если противник играет в одном из пространств, игрок играет в другом, создавая смежную цепочку. Существуют также безопасно связанные узоры, которые соединяют камни с краями. [20] Существует еще много безопасно связанных узоров, некоторые довольно сложные, построенные из более простых, таких как показанные. Узоры и пути могут быть нарушены противником до того, как они будут завершены, поэтому конфигурация доски во время реальной игры часто выглядит как лоскутное одеяло, а не что-то запланированное или спроектированное. [17]

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

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

Математическая теория

Определенность

Нетрудно убедиться с помощью изложения, что гексагон не может закончиться вничью, что называется «теоремой гексагона». То есть, независимо от того, как заполнена доска камнями, всегда найдется один и только один игрок, который соединил их края. Этот факт был известен Питу Хейну в 1942 году, который упомянул его как один из своих критериев проектирования гексагона в оригинальной статье Politiken. [1] : 29  Хейн также сформулировал этот факт как «барьер для вашего противника — это соединение для вас». [1] : 35  Джон Нэш написал доказательство этого факта около 1949 года, [23] но, по-видимому, не опубликовал доказательство. Его первое изложение появляется во внутреннем техническом отчете в 1952 году, [24] в котором Нэш утверждает, что «соединение и блокирование противника являются эквивалентными действиями». Более строгое доказательство было опубликовано Джоном Р. Пирсом в его книге 1961 года «Символы, сигналы и шум » . [25] В 1979 году Дэвид Гейл опубликовал доказательство того, что детерминированность Hex эквивалентна двумерной теореме Брауэра о неподвижной точке , и что детерминированность многомерных вариантов n -игроков доказывает теорему о неподвижной точке в целом. [26]

Неформальное доказательство свойства невытягивания Hex можно набросать следующим образом: рассмотрим связный компонент одного из красных ребер. Этот компонент либо включает противоположное красное ребро, в этом случае у Red есть соединение, либо нет, в этом случае синие камни вдоль границы связного компонента образуют выигрышный путь для Blue. Концепция связного компонента четко определена, поскольку в шестиугольной сетке две ячейки могут встретиться только на ребре или не встретиться вообще; ячейки не могут перекрываться в одной точке.

Победа первого игрока, неофициальное доказательство существования

В Hex без правила обмена на любой доске размера n x n первый игрок имеет теоретическую выигрышную стратегию. Этот факт был упомянут Хайном в его заметках к лекции, которую он прочитал в 1943 году: «в отличие от большинства других игр, можно доказать, что первый игрок в теории всегда может выиграть, то есть, если он сможет увидеть конец всех возможных линий игры». [1] : 42 

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

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

Сложность вычислений

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

В 11×11 Hex сложность пространства состояний составляет приблизительно 2,4×10 56 ; [30] против 4,6×10 46 для шахмат. [31] Сложность дерева игры составляет приблизительно 10 98 [32] против 10 123 для шахмат. [33]

Вычисленные стратегии для меньших досок

В 2002 году Цзин Ян, Саймон Ляо и Мирек Павляк нашли явную выигрышную стратегию для первого игрока на досках Hex размером 7×7, используя метод разложения с набором повторно используемых локальных шаблонов. [34] Они расширили метод, чтобы слабо решить центральную пару топологически конгруэнтных дебютов на досках 8×8 в 2002 году и центральный дебют на досках 9×9 в 2003 году. [35] В 2009 году Филип Хендерсон, Бродерик Арнесон и Райан Б. Хейворд завершили анализ доски 8×8 с помощью компьютерного поиска, решив все возможные дебюты. [36] В 2013 году Якуб Павлевич и Райан Б. Хейворд решили все дебюты для досок 9×9 и один (самый центральный) дебютный ход на доске 10×10. [37] С тех пор как Гарднер впервые предположил в своей колонке в Scientific American в 1957 году, хотя и ложно, что любой первый ход по короткой диагонали является выигрышным ходом, [38] для всех решенных игровых досок до n=9 это действительно так. Кроме того, для всех досок, кроме n=2 и n=4, было множество дополнительных выигрышных первых ходов; количество выигрышных первых ходов обычно ≥ n²/2.

Варианты

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

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

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

Размеры доски

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

Рекс (Обратный Гекс)

Вариант игры «Missère» в Hex называется «Rex», в котором каждый игрок пытается заставить своего противника сделать цепочку. Игра «Rex» медленнее, чем «Hex», поскольку на любой пустой доске с равными размерами проигравший игрок может отложить проигрыш до тех пор, пока вся доска не будет заполнена. [39] На досках с неравными размерами игрок, чьи стороны находятся дальше друг от друга, может выиграть независимо от того, кто ходит первым. [40] На досках с равными размерами первый игрок может выиграть на доске с четным числом клеток на стороне, а второй игрок может выиграть на доске с нечетным числом. [41] [42] На досках с четным числом клеток одним из выигрышных ходов первого игрока всегда является размещение камня в остром углу. [39]

Блокбастеры

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

И

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

Гаванна

Havannah — игра, основанная на Hex. [43] В ней также есть игровое поле, состоящее из шестиугольных плиток, однако само поле имеет форму большого шестиугольника, а победа достигается путем формирования одного из трех узоров.

Проект

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

Темный Гекс

Dark Hex (также известный как Phantom Hex) — это несовершенная информационная версия Hex. [45] Игроки не подвергаются воздействию камней друг друга в любой момент игры, если только они не обнаружат их первыми. Игра проходит в присутствии судьи, где каждый игрок сначала проверяет ход, является ли он столкновением или нет. В зависимости от продолжения этого момента игра имеет разные версии.


Соревнование

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

Обзоры

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

Примечания

  1. ^ Если доска полностью заполнена, то один игрок, должно быть, уже выиграл, и это должен быть первый игрок, поскольку он применял выигрышную стратегию.

Ссылки

  1. ^ abcdefghijklm Хейворд, Райан Б.; Тофт, Бьярне (2019). Hex, Inside and Out: The Full Story . CRC Press.
  2. ^ abcde Гарднер, М. (1959). The Scientific American Book of Mathematical Puzzles & Diversions . NY, NY: Simon and Schuster. стр. 73–83. ISBN 0-226-28254-6.
  3. ^ ab Con-tac-tix manual (PDF) . Parker Brothers. 1968. Архивировано (PDF) из оригинала 9 октября 2022 г.
  4. ^ Хейворд, Райан Б.; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. стр. 156. ISBN 978-0367144258.
  5. ^ Насар, Сильвия (13 ноября 1994 г.). «Потерянные годы лауреата Нобелевской премии». The New York Times . Получено 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. doi :10.1109/jrproc.1953.274273. S2CID  51666906.
  9. ^ Аншелевич, В. (2002). Иерархический подход к компьютерному шестнадцатеричному коду.
  10. ^ Леман, Альфред (1964). «Решение игры Шеннона с переключением». JSIAM . 12 (4). Общество промышленной и прикладной математики: 687–725.
  11. ^ Райш, Стефан (1981). «Hex ist PSPACE-vollständig». Акта Информатика . 15 (2): 167–191. дои : 10.1007/BF00288964. S2CID  9125259.
  12. ^ Кучерави, Мюррей (январь 1984). "Hexmaster". Antic . стр. 112. Получено 18 января 2019 .
  13. ^ facebookincubator/Polygames, Facebook Incubator, 28 мая 2020 г. , получено 29 мая 2020 г.
  14. ^ "Открытый исходный код Polygames, новая структура для обучения ботов ИИ через самостоятельную игру". ai.facebook.com . Получено 29 мая 2020 г. .
  15. ^ Казенав, Тристан; Чен, Йен-Чи; Чен, Гуан-Вэй; Чен, Ши-Ю; Чиу, Сянь-Донг; Деос, Жюльен; Эльза, Мария; Гун, Цюйчэн; Ху, Хэнъюань; Халидов, Василь; Ли, Ченг-Лин; Линь, Синь-И; Лин, Ю-Джин; Мартине, Ксавье; Мелла, Вегард; Рапин, Джереми; Розьер, Батист; Синнев, Габриэль; Тейто, Фабьен; Тейто, Оливье; Йе, Ши-Чэн; Йе, И-Джун; Йен, Ши-Джим; Загоруйко, Сергей (27 января 2020 г.). «Полиигры: улучшенное нулевое обучение». arXiv : 2001.09832 [cs.LG].
  16. ^ Маркус, Гэри (17 января 2018 г.). «Врожденность, AlphaZero и искусственный интеллект». arXiv : 1801.05667 [cs.AI].
  17. ^ abc Browne стр.
  18. ^ Браун, стр.28
  19. ↑ Браун, стр. 29–30.
  20. ↑ Браун, стр. 71–77.
  21. ^ abc Browne, стр.
  22. ^ Ласкер, стр.
  23. ^ Хейворд, Райан Б.; Рейсвейк, ван, Джек (6 октября 2006 г.). «Hex и комбинаторика». Дискретная математика . 306 (19–20): 2515–2528. doi :10.1016/j.disc.2006.01.029.
  24. ↑ Нэш, Джон (февраль 1952 г.). Технический отчет Rand Corp. D-1164: Некоторые игры и машины для игры в них. https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf Архивировано 21 января 2017 г. на Wayback Machine
  25. ^ Хейворд, Райан Б.; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. стр. 99. ISBN 978-0367144258.
  26. ^ Дэвид Гейл (1979). «Игра в гексагон и теорема Брауэра о неподвижной точке». The American Mathematical Monthly . 86 (10). Математическая ассоциация Америки: 818–827. doi :10.2307/2320146. JSTOR  2320146.
  27. ^ Even, S.; Tarjan, RE (1976). «Комбинаторная задача, полная в полиномиальном пространстве». Журнал ACM . 23 (4): 710–719. doi : 10.1145/321978.321989 . S2CID  8845949.
  28. ^ Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex является PSPACE-полным)». Акта Информатика . 15 (2): 167–191. дои : 10.1007/bf00288964. S2CID  9125259.
  29. ^ Санджив Арора, Боаз Барак, «Вычислительная сложность: современный подход». Cambridge University Press, 2009. Раздел 4.3
  30. ^ Браун, С. (2000). Hex Strategy . Natick, MA: AK Peters, Ltd. стр. 5–6. ISBN 1-56881-117-9.
  31. ^ Тромп, Дж. "Число шахматных диаграмм и позиций". John's Chess Playground . Архивировано из оригинала 29 июня 2011 г.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  32. ^ HJ ван ден Херик; JWHM Уитервейк; Дж. ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект. 134 (1–2): 277–311.
  33. ^ Виктор Эллис (1994). Поиск решений в играх и искусственном интеллекте . Кандидатская диссертация, Университет Лимбурга, pdf, 6.3.9 Шахматы, стр. 171
  34. ^ О методе декомпозиции для поиска выигрышной стратегии в игре Hex Архивировано 2 апреля 2012 г. на Wayback Machine , Цзин Ян, Саймон Ляо и Мирек Павляк, 2002 г.
  35. ^ Неопубликованные официальные документы, ранее @ www.ee.umanitoba.com/~jingyang/
  36. ↑ Решение 8x8 Hex, Архивировано 16 июля 2011 г. на Wayback Machine , P. Henderson, B. Arneson и R. Hayward, Proc. IJCAI-09 505-510 (2009)
  37. ^ Pawlewicz, Jakub; Hayward, Ryan (2013). "Scalable Parallel DFPN Search" (PDF) . Proc. Computers and Games . Архивировано (PDF) из оригинала 9 октября 2022 г. . Получено 21 мая 2014 г. .
  38. ↑ Гарднер, Мартин, Scientific American, июль 1957 г., стр. 145-151.
  39. ^ ab Hayward, Ryan B.; Toft, Bjarne (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. стр. 175. ISBN 978-0367144258.
  40. ^ Хейворд, Райан Б.; Тофт, Бьярн (2019). Hex, внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. стр. 154. ISBN 978-0367144258.
  41. ^ Гарднер (1959) стр.78
  42. ^ Браун (2000) стр.310
  43. ^ Фрилинг, Кристиан. «Как я придумал игры и почему нет». MindSports . Получено 19 октября 2020 г.
  44. ^ "Projex". BoardGameGeek . Получено 28 февраля 2018 г. .
  45. ^ Тапкан, М. Бедир. «Темный гексагон: крупномасштабная игра с несовершенной информацией».
  46. ^ «ICGA – Компьютерная олимпиада».
  47. ^ "Games and Puzzles 1973-08: Iss 16". AHC Publications. Август 1973.
  48. ^ "Игры и стратегия 06" . Декабрь 1980 года.

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

Внешние ссылки