✖


Jump to content

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

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

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

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

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

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

Тип игры

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

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

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

Правила

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

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

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

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

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

История

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

Изобретение

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

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

Претензия Нэша

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

Игра была заново открыта в 1948 или 1949 году математиком Джоном Нэшем из Принстонского университета . [2] [5] По словам Мартина Гарднера , который представил Хекс в своей колонке «Математические игры» в июле 1957 года , коллеги Нэша называли игру либо «Нэш», либо «Джон», причем последнее название имело в виду тот факт, что в игру можно было играть на шестиугольной плитке для ванной комнаты. [2] Нэш настаивал на том, что он открыл игру независимо от Хайна, но в этом есть некоторые сомнения, поскольку известно, что были датчане, в том числе Оге Бор , которые играли в Хекс в Принстоне в 1940-х годах, так что Нэш, возможно, подсознательно подхватил игру. идея. Хейн написал Гарднеру в 1957 году, выразив сомнение в том, что Нэш открыл Хекс самостоятельно. Гарднер не смог независимо подтвердить или опровергнуть утверждение Нэша. [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 1974 года; игра содержала Блокнот размером 5 + 1 ⁄ 2 на 8 + 1 ⁄ 2 дюйма (140 × 220 мм) на 50 листов с разлинованной шестигранной сеткой. Hex в настоящее время публикуется Nestorgames в размерах 11×11 и 14×14. [7]

Шестнадцатеричная машина Шеннон

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

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

График исследования

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

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

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

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

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

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

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

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

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

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

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

Стратегия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В 2002 году Цзин Ян, Саймон Ляо и Мирек Павляк нашли явную стратегию выигрыша для первого игрока на шестигранных досках размером 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 and Bridg-It) и TwixT . Обе игры имеют некоторую степень сходства с древней китайской игрой Го .

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

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

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

Размеры платы

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

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

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

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

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

Блокбастеры

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

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

И

[ редактировать ]
Основная статья: Y (игра)

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

Гаванна

[ редактировать ]
Основная статья: Гаванна (настольная игра)

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

Проект

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

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

Темное проклятие

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

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


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

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

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

Отзывы

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

См. также

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

Примечания

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

Ссылки

[ редактировать ]
  1. ^ Jump up to: а б с д и ж г час я дж к л м Хейворд, Райан Б.; Тофт, Бьярн (2019). Шестигранник, внутри и снаружи: полная история . ЦРК Пресс.
  2. ^ Jump up to: а б с д и Гарднер, М. (1959). Научно-американская книга математических головоломок и развлечений . Нью-Йорк, Нью-Йорк: Саймон и Шустер. стр. 73–83 . ISBN  0-226-28254-6 .
  3. ^ Jump up to: а б Руководство Con-tac-tix (PDF) . Братья Паркер. 1968. Архивировано (PDF) из оригинала 9 октября 2022 года.
  4. ^ Хейворд, Райан Б.; Тофт, Бьярн (2019). Шестигранник внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 156. ИСБН  978-0367144258 .
  5. ^ Насар, Сильвия (13 ноября 1994 г.). «Потерянные годы нобелевского лауреата» . Нью-Йорк Таймс . Проверено 23 августа 2017 г.
  6. ^ Хейворд, Райан Б.; Тофт, Бьярн (2019). Шестигранник внутри и снаружи: полная история . Бока-Ратон, Флорида: 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. ^ Леман, Альфред (1964). «Решение игры с переключением Шеннона». ИСИАМ . 12 (4). Общество промышленной и прикладной математики: 687–725.
  11. ^ Райш, Стефан (1981). «Hex является PSPACE-полным». Акта Информатика . 15 (2): 167–191. дои : 10.1007/BF00288964 . S2CID   9125259 .
  12. ^ Кучерави, Мюррей (январь 1984 г.). «Хексмастер» . Антик . п. 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. ^ Jump up to: а б с Браун р.
  18. ^ Браун, стр.28
  19. ^ Браун, стр. 29–30.
  20. ^ Браун, стр. 71–77.
  21. ^ Jump up to: а б с Браун, с.
  22. ^ Ласкер, с.
  23. ^ Хейворд, Райан Б.; Рейсвейк, ван, Джек (6 октября 2006 г.). «Гекс и комбинаторика». Дискретная математика . 306 (19–20): 2515–2528. дои : 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). Шестигранник внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 99. ИСБН  978-0367144258 .
  26. ^ Дэвид Гейл (1979). «Игра в шестнадцатеричные числа и теорема Брауэра о фиксированной точке». Американский математический ежемесячник . 86 (10). Математическая ассоциация Америки: 818–827. дои : 10.2307/2320146 . JSTOR   2320146 .
  27. ^ Эвен, С.; Тарьян, Р.Э. (1976). «Комбинаторная задача, полная в полиномиальном пространстве» . Журнал АКМ . 23 (4): 710–719. дои : 10.1145/321978.321989 . S2CID   8845949 .
  28. ^ Стефан Райш (1981). «Hex является PSPACE-полным». Акта Информатика . 15 (2): 167–191. дои : 10.1007/bf00288964 . S2CID   9125259 .
  29. ^ Санджив Арора, Боаз Барак, «Вычислительная сложность: современный подход». Издательство Кембриджского университета, 2009. Раздел 4.3.
  30. ^ Браун, К. (2000). Шестнадцатеричная стратегия . Натик, Массачусетс: AK Peters, Ltd., стр. 5–6. ISBN  1-56881-117-9 .
  31. ^ Тромп, Дж. «Количество шахматных диаграмм и позиций» . Шахматная площадка Джона . Архивировано из оригинала 29 июня 2011 года. {{cite web}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
  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. ^ Решение Hex 8x8 , Архивировано 16 июля 2011 г. в Wayback Machine , П. Хендерсон, Б. Арнесон и Р. Хейворд, Proc. IJCAI-09 505-510 (2009 г.)
  37. ^ Павлевич, Якуб; Хейворд, Райан (2013). «Масштабируемый параллельный поиск DFPN» (PDF) . Учеб. Компьютеры и игры . Архивировано (PDF) из оригинала 9 октября 2022 года . Проверено 21 мая 2014 г.
  38. ^ Гарднер, Мартин, Scientific American, июль 1957 г., стр. 145-151.
  39. ^ Jump up to: а б Хейворд, Райан Б.; Тофт, Бьярн (2019). Шестигранник внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 175. ИСБН  978-0367144258 .
  40. ^ Хейворд, Райан Б.; Тофт, Бьярн (2019). Шестигранник внутри и снаружи: полная история . Бока-Ратон, Флорида: CRC Press. п. 154. ИСБН  978-0367144258 .
  41. ^ Гарднер (1959) стр.78
  42. ^ Браун (2000) стр.310
  43. ^ Фрилинг, Кристиан. «Как я придумал игры и почему бы и нет» . MindSports . Проверено 19 октября 2020 г.
  44. ^ «Прожекс» . Настольные игрыGeek . Проверено 28 февраля 2018 г.
  45. ^ Тапкан, М.Бедир. «Dark Hex: Крупномасштабная несовершенная информационная игра» .
  46. ^ «Игры и головоломки 1973-08: Выпуск 16» . Публикации AHC. Август 1973 года.
  47. ^ «Игры и стратегии 06» . Декабрь 1980 года.

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

[ редактировать ]
  • Шестнадцатеричная стратегия: создание правильных связей , Браун К. (2000), AK Peters Ltd., Натик, Массачусетс. ISBN   1-56881-117-9 (торговая мягкая обложка, 363 страницы)
  • HEX: The Full Story , Хейворд Р. и Тофт Б. (2019), CRC Press Бока-Ратон, Флорида. ISBN   978-0-367-14422-7 (мягкая обложка)
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hex_(board_game)&oldid=1234031185"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 538434802b60c9666e371c87932ae612__1720755540
URL1:https://arc.ask3.ru/arc/aa/53/12/538434802b60c9666e371c87932ae612.html
Заголовок, (Title) документа по адресу, URL1:
Hex (board game) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)