Войти
 Игровая доска 11 × 11 Hex, показывающая выигрышную конфигурацию для Blue | |
| Годы активности | 1942 – настоящее время |
|---|---|
| Жанры | Настольная игра. Абстрактная стратегическая игра. Соединительная игра |
| Игроки | 2 |
| Время подготовки | Нет |
| Время игры | 30 минут - 2 часа (доска 11 × 11) |
| Случайный шанс | Нет |
| Требуются навыки | Стратегия, тактика |
Hex - это абстрактная стратегия для двух игроков настольная игра, в которой игроки пытаются соединить противоположные стороны шестиугольной доски. Hex был изобретен математиком и поэтом Питом Хейном в 1942 году и независимо от него Джоном Нэшем в 1948 году.
Традиционно игра играется на ромбе 11 × 11 , хотя также популярны доски 13 × 13 и 19 × 19. Каждому игроку назначается пара противоположных сторон доски, которые они должны попытаться соединить, по очереди кладя камень своего цвета на любое пустое место. После размещения камни не могут быть перемещены или удалены. Игрок побеждает, когда он успешно соединяет свои стороны вместе цепочкой соседних камней. Ничья невозможны в Hex из-за топологии игрового поля.
В игре есть глубокая стратегия, острая тактика и глубокая математическая основа, связанная с теоремой Брауэра о фиксированной точке. Впервые игра была продана как настольная игра в Дании под названием Con-tac-tix, и Parker Brothers выпустили ее версию в 1952 году под названием Шестнадцатеричный ; они больше не производятся. В шестигранник также можно играть с бумагой и карандашом на миллиметровой бумаге с шестигранной линейкой.
Исследования, связанные с Hex, актуальны в областях топологии, графов и теории матроидов, комбинаторики, теории игр и искусственного интеллекта.
Hex - это игра с подключением, и ее можно классифицировать как игра Maker-Breaker, особый тип позиционной игры. Игра никогда не может закончиться ничьей (ничьей), другими словами, Hex также является «определенной игрой ».
Hex - это конечная игра с точной информацией и абстрактная стратегическая игра, которая принадлежит к общей категории игр с подключением. Hex - это частный случай «узловой» версии игры с переключением Шеннона.
Как продукт, Hex - это настольная игра ; в нее также можно играть бумагой и карандашом.
Игра была изобретена датским математиком Питом Хайном, который представил его в 1942 году в Институте Нильса Бора. Хотя позже Хайн переименовал ее в Con-tac-tix, она стала известна в Дании под названием Polygon из-за статьи Хайна в датской газете Politiken от 26 декабря 1942 года, первого опубликованного описания игры, в котором он использовал это имя. Игра была независимо заново изобретена в 1948 году математиком Джоном Нэшем из Принстонского университета. Согласно Мартину Гарднеру, который представил Хекса в своей колонке Математические игры в июле 1957 года, товарищи Нэша назвали игру либо Нэшем, либо Джоном, причем последнее название относится к тому факту, что можно играть на шестиугольной плитке для ванной. Хайн написал Гарднеру в 1957 году, выражая сомнение в том, что Нэш открыл Hex независимо, но Нэш настаивает на том, что он заново изобрел игру, прежде чем познакомиться с работами Хайна. Гарднер не смог независимо подтвердить или опровергнуть утверждение Нэша.
Издание игры Parker Brothers В 1952 году Parker Brothers выпустила версию. Они назвали свою версию «Hex», и это название прижилось. Parker Brothers также продавали версию под названием «Con-tac-tix» в 1968 году. Hex также был выпущен как одна из игр в 3M 1974 года. Серия бумажных игр; игра содержала блокнот размером 5 ½ × 8 ½ дюймов на 50 листов с линейчатыми шестигранными решетками. Hex в настоящее время издается Nestorgames в размерах 11x11 и 14x14.
Примерно в 1950 году, американский математик и инженер-электрик Клод Шеннон и Э. Ф. Мур сконструировал аналоговую шестигранную игровую машину, которая по сути представляла собой резистивную сеть с резисторами для ребер и лампочками для вершин. Перемещение, которое необходимо сделать, соответствовало определенной указанной седловой точке в сети. Машина неплохо сыграла в Hex. Позже исследователи, пытающиеся решить эту игру и разработать компьютерные алгоритмы игры в гексагон, эмулировали сеть Шеннона для создания сильных автоматов.
В 1952 году Джон Нэш представил доказательство существования того, что на симметричных досках, у первого игрока есть выигрышная стратегия.
В 1964 году математик показал, что Hex не может быть представлен как двоичный матроид, поэтому определенная выигрышная стратегия, подобная той, что использовалась для игры с переключением Шеннона на регулярной прямоугольной сетке, была недоступна. Позже было показано, что игра завершена для PSPACE.
В 2002 году была описана первая явная выигрышная стратегия (стратегия редукционного типа) на доске 7 × 7.
В 2000-х, с использованием компьютерных алгоритмов поиска грубой силой, были полностью решены Hex-доски размером до 9 × 9 (по состоянию на 2016 год).
До 2019 года люди оставались лучше компьютеров, по крайней мере, на больших досках, таких как 19x19, но 30 октября 2019 года программа Mootwo победила человека с лучшим рейтингом ELO на LittleGolem, также победителя различных турниров. (игра доступна здесь ). Эта программа была основана на Polygames (проект с открытым исходным кодом, первоначально разработанный Facebook Artificial Intelligence Research и несколькими университетами) с использованием комбинации:
В начале 1980-х Dolphin Microware опубликовала Hexmaster, реализацию для 8-битной версии Atari компьютеры. Различные парадигмы, возникшие в результате исследования игры, использовались для создания цифровых компьютерных игровых автоматов Hex, начиная примерно с 2000 года. Первые реализации использовали оценочные функции, которые имитировали модель электрических цепей Шеннона и Мура, встроенную в структуру альфа-бета-поиска с ручными знаниями на основе шаблонов. Примерно с 2006 года методы поиска по дереву Монте-Карло, заимствованные из успешных компьютерных реализаций Go, были введены и вскоре стали доминировать в этой области. Позже созданные вручную выкройки были дополнены методами машинного обучения для обнаружения паттернов. Эти программы теперь конкурируют с опытными игроками-людьми. Рейтинги на основе Эло были присвоены различным программам и могут использоваться для измерения технического прогресса, а также для оценки игровой силы против людей с рейтингом Эло. Текущие исследования часто публикуются либо в ежеквартальном журнале ICGA, либо в ежегодной серии «Успехи в компьютерных играх» (van den Herik et al. Eds.).
Черный против белого на шестигранной доске Каждому игроку назначен цвет, обычно красный и синий или белый и черный. Игроки по очереди кладут камень своего цвета в одну ячейку на общем игровом поле. После размещения камни не перемещаются, не захватываются и не удаляются с доски. Цель каждого игрока состоит в том, чтобы сформировать связанный путь из своих камней, соединяющий противоположные стороны доски, отмеченные их цветами, прежде чем их противник соединит свои стороны аналогичным образом. Игрок, первым завершивший соединение, побеждает в игре. Каждый из четырех угловых шестиугольников принадлежит обеим смежным сторонам.
Нет необходимости строить полную цепочку между сторонами или заполнять всю доску до того, как игра будет решена (но если это произойдет по построению, игрок, положивший последний камень, выиграет); обычно заполняется от 1/3 до 40% доски, прежде чем становится очевидным, что тот или иной игрок может добиться победы. Это в некоторой степени аналогично шахматным партиям, заканчивающимся задолго до мата - игра обычно заканчивается тем, что один или другой игрок сдается.
Поскольку игрок, первым сделавший ход в шестнадцатеричном формате, имеет явное преимущество, правило круговой диаграммы обычно применяется для справедливости. Это правило позволяет второму игроку выбирать, менять ли его позиции с первым игроком после того, как первый игрок сделает первый ход.
Из доказательства выигрышной стратегии для первого игрока известно, что шестигранная доска должна иметь сложный тип связи, который никогда не решался. Игра состоит из создания небольших паттернов, которые имеют более простой тип связи, называемого «безопасное соединение», и объединения их в последовательности, образующие «путь». В конце концов, одному из игроков удастся сформировать надежно соединенную дорожку из камней и промежутков между его сторонами доски и выиграть. Заключительный этап игры, если необходимо, состоит в заполнении пустых мест на пути.
Схема 1: мост (A <-->C), шаблон безопасного соединения Шаблон "безопасно соединенный" состоит из камней цвета игрока и открытых пространств, которые можно соединить в цепочку, непрерывную последовательность смежных камней по краям, независимо от того, как играет противник. Одним из самых простых таких узоров является мост (см. Диаграмму 1), который состоит из двух камней одного цвета (A и C) и пары открытых пространств (B и D). Если противник играет в одном из полей, игрок играет в другом, создавая непрерывную цепочку. Также существуют надежно соединенные узоры, соединяющие камни с краями. Есть еще много надежно связанных паттернов, некоторые из которых довольно сложные, построенные из более простых, как показано. Шаблоны и пути могут быть нарушены противником до того, как они будут завершены, поэтому конфигурация доски во время реальной игры часто выглядит как лоскутное одеяло, а не что-то запланированное или разработанное.
Есть более слабые типы связи, чем " безопасно соединенные ", которые существуют между камнями или между надежно соединенными узорами, между которыми есть несколько промежутков. Средняя часть игры состоит из создания сети из таких слабо связанных камней и узоров, которые, мы надеемся, позволят игроку, заполнив слабые звенья, построить только один надежно соединенный путь между сторонами по ходу игры.
Успех в гексагоне требует особой способности визуализировать синтез сложных шаблонов эвристическим способом и оценивать, являются ли такие шаблоны «достаточно прочными», чтобы обеспечить возможную победу. Навык чем-то похож на визуализацию шаблонов, последовательность ходов и оценку позиций в шахматах.
Джон Нэш был первым, кто доказал (c. 1949), что Hex не может закончиться ничьей, нетривиальный результат, в просторечии называемый «теоремой Hex», который, как мы теперь знаем, эквивалентен теореме Брауэра о неподвижной точке. Судя по всему, доказательство он не опубликовал. Первое изложение этого появляется в внутреннем техническом отчете в 1952 году, в котором он заявляет, что «соединение и блокирование противника являются эквивалентными действиями». Первое строгое доказательство было опубликовано Джоном Р. Пирсом в его книге «Символы, сигналы и шум» 1961 года. В 1979 году Дэвид Гейл опубликовал доказательство, которое также показало, что его можно использовать для доказательства двумерной теоремы Брауэра о неподвижной точке и что детерминированность многомерных вариантов доказывает теорема о неподвижной точке в общем. Краткий набросок требования о запрещении розыгрыша шестиугольника из этого документа представлен ниже:
Имеется reductio ad absurdum доказательство существования приписывается Джону Нэшу ок. 1949 г., первый игрок в гексагоне на доске любого размера имеет выигрышную стратегию. Такое доказательство не указывает на правильную стратегию игры. Доказательство является общим для ряда игр, включая Hex, и получило название аргумента "кражи стратегии". Вот краткое неофициальное заявление доказательства:
В 1976 году Шимон Эвен и Роберт Тарджан доказали, что определение того, является ли позиция в игра обобщенного Hex, играемая на произвольных графах, является выигрышной позицией PSPACE-complete. Усиление этого результата было доказано Райшем путем сведения квантифицированной булевой формулы в конъюнктивной нормальной форме к шестнадцатеричной системе с произвольными планарными графами. В теории вычислительной сложности широко распространено предположение о том, что PSPACE-полные задачи не могут быть решены с помощью эффективных (полиномиальное время) алгоритмов. Этот результат ограничивает эффективность наилучших возможных алгоритмов при рассмотрении произвольных позиций на досках неограниченного размера, но не исключает возможности простой выигрышной стратегии для начальной позиции (на досках неограниченного размера) или простого выигрыша. стратегия для всех позиций на доске определенного размера.
В шестнадцатеричном формате 11 × 11 существует приблизительно 2,4 × 10 возможных допустимых положений; это можно сравнить с 4,6 × 10 разрешенных позиций в шахматах.
Грубую оценку количества узлов в дереве игры можно получить как экспоненциальную функцию от среднего коэффициента ветвления и среднего количества слоев в игре таким образом: b, где d - глубина слоя, а b - коэффициент ветвления. В Hex средний коэффициент ветвления зависит от глубины слоя. Было заявлено, что средний фактор ветвления составляет около 100; что подразумевает среднюю глубину слоя 43 (на доске будет 121 открытое пространство, когда первый игрок сделает свой первый ход, и 79, когда он должен сделать свой 22-й ход, 43-й слой - среднее количество открытых мест, т.е. коэффициент ветвления, во время игры равен (121 + 120 +... + 79) / 43 = 100). Следовательно, размер дерева игры имеет верхнюю границу примерно 100 = 10. Эта граница включает некоторое количество недопустимых позиций из-за игры, когда существует полная цепочка для одного или другого игрока, а также исключает допустимые позиции для более длительных игр. чем 43 слоя. Другой исследователь получил оценку пространства состояний 10 и размер дерева игры 10, используя верхний предел игры в 50 слоев. Это можно сравнить с размером дерева игры в шахматы с 10 узлами.
Доступны интересные сокращения игрового дерева, если отметить, что доска имеет двойную двустороннюю симметрию, а также симметрию вращения 180 °: для каждой позиции получается топологически идентичная позиция перевернув доску влево-вправо, вверх-вниз или повернув ее на 180 °.
В 2002 году Цзин Ян, Саймон Ляо и Мирек Павляк нашли явную выигрышную стратегию для первого игрока на шестнадцатеричных досках размера 7 × 7, используя метод разложения с набор многоразовых локальных шаблонов. Они расширили этот метод, чтобы слабо решить центральную пару топологически конгруэнтных отверстий на досках 8 × 8 в 2002 году и центральное отверстие на досках 9 × 9 в 2003 году. В 2009 году Филип Хендерсон, Бродерик Арнесон и Райан Б. Хейворд завершили анализ доска 8х8 с компьютерным поиском, разгадывая все возможные проемы. В 2013 году Якуб Павлевич и Райан Б. Хейворд решили все дебюты для досок 9 × 9 и один (самый центральный) дебют на доске 10 × 10. Для каждого N≤10 выигрышный первый ход в гексагоне N × N является наиболее центральным, что наводит на мысль о том, что это верно для любого N≥1.
Другие игры со связями с аналогичными целями, но с другой структурой включают игру с переключением Шеннона и TwixT. Оба они имеют некоторую степень сходства с древней азиатской игрой в Go.
В эту игру можно играть на прямоугольной сетке, например в шахматы, шашку или гоу, если учесть, что пространства (пересечения в случае go) связаны в одном диагональном направлении, но не в другом. В игру можно играть с бумагой и карандашом на прямоугольном массиве точек или миллиметровой бумаге таким же образом, используя два разных цветных карандаша.
Популярными размерами, отличными от стандартного 11x11, являются 13x13 и 19x19 в результате связи игры с более старой игрой Go. Согласно книге A Beautiful Mind, Джон Нэш (один из изобретателей игры) рекомендовал 14 × 14 как оптимальный размер.
misère вариант шестнадцатеричного. Каждый игрок пытается заставить своего противника составить цепочку. Rex медленнее, чем Hex, поскольку на любой пустой доске с одинаковыми размерами проигрышная игра может отложить проигрыш до тех пор, пока не заполнится вся доска. На досках с неравными размерами игрок, чьи стороны находятся дальше друг от друга, может выиграть независимо от того, кто играет первым. На досках одинаковых размеров первый игрок может выиграть на доске с четным числом ячеек на каждой стороне, а второй игрок может выиграть на доске с нечетным числом. На досках с четным номером один из выигрышных ходов первого игрока всегда заключается в том, чтобы положить камень в острый угол.
Хекс воплощался как доска вопросов из телевизионной игры. покажите Blockbusters. Чтобы разыграть «ход», участники должны были правильно ответить на вопрос. Доска имела 5 чередующихся столбцов по 4 шестиугольника; одиночный игрок может соединяться сверху вниз за 4 хода, а команда из двух человек может соединяться слева направо за 5 ходов.
игра Y - это шестигранник, играемый на треугольной сетке шестиугольников; цель состоит в том, чтобы любой игрок соединил все три стороны треугольника. Y - это обобщение Hex в том смысле, что любая позиция на Hex-доске может быть представлена как эквивалентная позиция на большей Y-доске.
Havannah - это игра, основанная на Hex. Он отличается от Hex тем, что в нем используется гексагональная сетка из шестиугольников, а выигрыш достигается путем формирования одного из трех шаблонов.
Projex - это вариант Hex, играемый на реальной проективной плоскости, где игроки имеют цель создать не стягиваемый цикл.. Как и в Hex, здесь нет ничьей и нет позиции, в которой у обоих игроков есть выигрышная связь.
По состоянию на 2016 год было зарегистрировано турниров за доской из Бразилии, Чехии, Дании, Франции, Германии, Италия, Нидерланды, Норвегия, Польша, Португалия, Испания, Великобритания и США.
Один из крупнейших турниров Hex организован Международным комитетом математических игр в Париже, Франция, который проводится ежегодно с 2013 года.
Hex также является частью компьютерной олимпиады.
