Гаванна - Havannah

Эта статья про настольную игру. Для английской деревни см. Гаванна, Чешир. Для использования в других целях см. Гавана (значения).
Примеры трех выигрышных структур в Havannah на доске base-8. Слева направо они вилка, то звенеть и мост.

Гаванна это двое игроков абстрактная стратегия настольная игра изобретен Кристиан Фрилинг. Он принадлежит к семейству игр, обычно называемых соединительные игры; его родственники включают Шестигранник и TwixT. У Гаванны «сложная и разнообразная стратегия», и в нее лучше всего играть на гексагональной доске с основанием 10, по 10 гексагональных ячеек на сторону.[1]

Игра издавалась некоторое время в Германии компанией Равенсбургер, с меньшей доской base-8, подходящей для начинающих. В настоящее время его производит только компания Hexboards.[2]

Правила игры

Один игрок играет черными; другой играет белыми. Белые начинают, после чего ходы чередуются. Правила следующие:

  • Каждый игрок кладет на доску по одному камню своего цвета за ход.
  • Камни никогда не перемещаются, не захватываются или не изменяются иным образом.
  • Игрок побеждает, когда он завершает одну из трех различных структур из непрерывных линий или путей соединенных камней, всех их цветов:
    • А звенеть представляет собой петлю вокруг одной или нескольких ячеек (независимо от того, заняты ли обведенные ячейки любым игроком или пустые[3]);
    • А мост, который соединяет любые две из шести угловых ячеек доски;
    • А вилка, который соединяет любые три края доски; угловые точки не считаются частью кромки.

Пример всех трех выигрышных комбинаций показан выше. Структура в центре доски - кольцо; конструкция слева представляет собой вилку; конструкция с правой стороны представляет собой мост.

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

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

Разница по сравнению с Hex

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

В отличие от Hex, в Havannah розыгрыши технически возможны, на практике они встречаются крайне редко. Была известна одна ничья между людьми-игроками.[5]Тактику освоить намного проще, чем стратегию, и различия в уровне игры значительны.

Компьютер Хаванна

В 2002 году Фрилинг предложил приз в размере 1000 евро, доступный до 2012 года, за любую компьютерную программу, которая могла бы победить его даже в одной игре из десяти матчей. На протяжении многих лет компьютерные программы сильно отставали от игроков. Однако с 2010 года несколько программ, играющих в Гаванну, подали заявки Поиск в дереве Монте-Карло техники, приводящие к заметному увеличению силы игры. «Вызов Хаванны 2012» проводился 15–19 октября 2012 года, в ходе которого Фрилинг сыграл десять партий против трех сильнейших доступных программ игры в Хаванна, сыграв (по крайней мере) одну игру черными и одну белыми против каждого противника.[6] Фрилинг проиграл вызов, когда ему пришлось отказаться от игры белыми против программы Лайконика.

До 2019 года лучшие люди были намного сильнее компьютеров. Тем не мение, МетаТоторо, на основе Polygames[7] (проект с открытым исходным кодом, первоначально разработанный Исследование искусственного интеллекта Facebook и несколько университетов[8]), выиграл у игрока-человека с лучшим рейтингом ELO на LittleGolem, который также был победителем различных турниров.

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

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

Решение Havannah - это PSPACE-полный относительно размера входного графа.[10] Доказательство проводится редукцией от обобщенная география и основан на использовании кольцевых угроз для представления графа географии. Подробно, поскольку Лихтенштейн и Сипсер доказали, что обобщенная география остается сложной для PSPACE, даже если граф только двудольные и степени не выше 3, остается только построить эквивалентную позицию Гаванны из такого графа, что достигается путем создания различных устройств в Гаване.

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

  1. ^ Хэндскомб, Керри, изд. (Зима 2002 г.). «Передняя обложка». Абстрактные игры. Издательство Carpe Diem (12). ISSN  1492-0492.
  2. ^ Хексборды
  3. ^ Как пояснил Фрилинг в http://www.mindsports.nl/index.php/arena/havannah/49-havannah-rules; В книге Шмиттбергера ошибочно утверждается, что кольцо должно окружать хотя бы одну свободную ячейку.
  4. ^ Шмиттбергер, Р. Уэйн (1992), "Хаванна", Новые правила классических игр, John Wiley & Sons, Inc., стр.116–17, ISBN  978-0471536215
  5. ^ "Маленький голем".
  6. ^ «Человек против компьютера: 7-3 - Пресс-релиз».
  7. ^ facebookincubator / Polygames, Инкубатор Facebook, 2020-05-28, получено 2020-05-29
  8. ^ «Открытый исходный код Polygames, новый фреймворк для обучения ботов с ИИ через самостоятельную игру». ai.facebook.com. Получено 2020-05-29.
  9. ^ Казенаве, Тристан; Чен, Йен-Чи; Чен Гуань-Вэй; Чен, Ши-Ю; Чиу, Сиань-Донг; Дехос, Жюльен; Эльза, Мария; Гонг, Кученг; Ху, Хэнъюань; Халидов, Василь; Ли, Чэн-Лин (27.01.2020). «Polygames: Улучшенное нулевое обучение». arXiv:2001.09832 [cs.LG ].
  10. ^ Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (14 августа 2013 г.). Havannah и TwixT созданы для PSPACE. 8-й международный. Конф. по компьютерам и играм. Университет Кейо, Иокогама, Япония. arXiv:1403.6518. Дои:10.1007/978-3-319-09165-5_15.

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