Havannah - абстрактная настольная игра- стратегия для двух игроков , изобретенная Кристианом Фрилингом . Он принадлежит к семейству игр, обычно называемых играми с подключением ; его родственники включают Hex и TwixT . У Хаванны «сложная и разнообразная стратегия», и в нее лучше всего играть на гексагональной доске с основанием 10, по 10 гексагональных ячеек на сторону. [1]
Игра была издана в Германии компанией Ravensburger с небольшой доской base-8, подходящей для новичков. В настоящее время его производит только компания Hexboards. [2]
Правила игры [ править ]
Один игрок играет черными; другой играет белыми. Белые начинают, после чего ходы чередуются. Правила следующие:
- Каждый игрок кладет на доску по одному камню своего цвета за ход.
- Камни никогда не перемещаются, не захватываются или не изменяются иным образом.
- Игрок побеждает, когда он завершает одну из трех различных структур из непрерывных линий или дорожек соединенных камней, всех их цветов:
- Кольцо является петлей вокруг одного или нескольких ячеек (независимо от того , являются ли кружках клетки занимаемого любого игрока или пустым [3] );
- Мост , который соединяет любые два из шести угловых элементов платы;
- Вилка , которая соединяет любые три стороны доски; угловые точки не считаются частью кромки.
Пример всех трех выигрышных комбинаций показан выше. Структура в центре доски - кольцо; конструкция с левой стороны представляет собой развилку; конструкция с правой стороны представляет собой мост.
Поскольку первый игрок, который сделает ход в Гаванне, имеет явное преимущество, правило пирога обычно применяется для справедливости. Это правило позволяет второму игроку выбирать, менять ли его позицию с первым игроком после того, как первый игрок сделает первый ход. [4]
Игроки разной силы могут по-прежнему играть в интересную игру, когда более слабому игроку (как белому) разрешается поставить два или более камня на первом ходу.
Разница по сравнению с Hex [ править ]
В Hex, когда поле полностью заполнено, выигрышное соединение будет иметь ровно один игрок; в Гаванне на полностью заполненной доске обычно будет более одной выигрышной структуры (но игра заканчивается первой выигрышной структурой).
В отличие от Hex, в Havannah розыгрыши технически возможны, на практике они встречаются крайне редко. Была известна одна ничья между людьми-игроками. [5] Тактику освоить намного проще, чем стратегию, и различия в уровне игры значительны.
Компьютерная Хаванна [ править ]
В 2002 году Фрилинг предложил приз в размере 1000 евро, доступный до 2012 года, за любую компьютерную программу, которая могла бы обыграть его даже в одной игре из десяти матчей. На протяжении многих лет компьютерные программы сильно отставали от игроков. Однако с 2010 года в нескольких программах, играющих в «Гаванну», применялись методы поиска по дереву Монте-Карло , что привело к заметному повышению силы игры. «Вызов Хаванны 2012» проводился 15–19 октября 2012 года, во время которого Фрилинг сыграл десять игр против трех сильнейших доступных программ игры в Хаванна, сыграв (по крайней мере) одну игру черными и одну белыми против каждого соперника. [6] Фрилинг проиграл вызов, когда ему пришлось отказаться от игры белыми против программы Лайконика.
До 2019 года лучшие люди были намного сильнее компьютеров. Однако MetaTotoro , основанный на Polygames [7] (проект с открытым исходным кодом, первоначально разработанный Facebook Artificial Intelligence Research и несколькими университетами [8] ), победил человека с лучшим рейтингом ELO на LittleGolem , который также стал победителем. различных турниров.
Этот результат был достигнут с помощью той же программы, что и для победы над лучшими людьми в Hex . Это алгоритм, основанный на нулевом обучении, как в AlphaZero, но с нововведениями: инвариантность размера доски благодаря полностью сверточным нейронным сетям (как в U-Net) и глобальному пулингу. Это позволяет увеличивать архитектуру, то есть программа может учиться на маленькой плате, а затем экстраполировать ее на большую доску. [9]
Вычислительная сложность [ править ]
Решение Havannah является PSPACE-полным в отношении размера входного графа. [10] Доказательство представляет собой сокращение от обобщенной географии и основано на использовании кольцевых угроз для представления географического графа. В деталях, поскольку Лихтенштейн и Сипсер доказали, что обобщенная география остается сложной для PSPACE, даже если граф является только двудольным и имеет степень не выше 3 , остается только построить эквивалентную позицию Гаваны из такого графа, что достигается путем построения различных гаджеты в Гаванне.
Ссылки [ править ]
- ^ Хэндскомб, Керри, изд. (Зима 2002 г.). «Лицевая обложка». Абстрактные игры . Carpe Diem Publishing (12). ISSN 1492-0492 .
- ^ Хексборды
- ^ Как пояснил Фрилинг на http://www.mindsports.nl/index.php/arena/havannah/49-havannah-rules ; В книге Шмиттбергера ошибочно утверждается, что кольцо должно окружать хотя бы одну свободную ячейку.
- ^ Schmittberger, Р. Уэйн (1992), "Havannah" , новые правила для классических игр , John Wiley & Sons, Inc., стр. 116-17 , ISBN 978-0471536215 CS1 maint: обескураженный параметр ( ссылка )
- ^ "Маленький голем" .
- ^ «Человек против компьютера: 7-3 - Пресс-релиз» .
- ^ facebookincubator / Polygames , Facebook Incubator, 28 мая 2020 г. , получено 29 мая 2020 г.
- ^ «Открытый исходный код Polygames, новый фреймворк для обучения ботов AI через самостоятельную игру» . ai.facebook.com . Проверено 29 мая 2020 .
- ^ Cazenave, Тристан; Чен, Йен-Чи; Чен Гуань-Вэй; Чен, Ши-Ю; Чиу, Сиань-Донг; Дехос, Жюльен; Эльза, Мария; Гонг, Кученг; Ху, Хэнъюань; Халидов, Василь; Ли, Чэн-Лин (27.01.2020). «Полигры: Улучшенное нулевое обучение». arXiv : 2001.09832 [ cs.LG ].
- ^ Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (14 августа 2013 г.). Havannah и TwixT созданы для PSPACE . 8-й Междунар. Конф. по компьютерам и играм. Университет Кейо, Иокогама, Япония. arXiv : 1403,6518 . DOI : 10.1007 / 978-3-319-09165-5_15 .
Внешние ссылки [ править ]
- Официальный сайт MindSports.nl
- Havannah статья о библиотеке сенсея
- Хаванна в BoardGameGeek
