Гаванна — абстрактная настольная игра для двух игроков, изобретённая . Относится к семейству игр, известных как игры на соединение, родственна таким играм, как Гекс и . Гаванна обладает «сложной и разнообразной стратегией» и лучше всего играется на шестиугольной доске с основанием 10, то есть по 10 гексагональных клеток с каждой стороны.
Некоторое время игра издавалась в Германии компанией Ravensburger с доской с основанием 8, подходящей для новичков. В настоящее время её производит только Hexboards.
Правила игры Один игрок играет белыми камнями, другой чёрными. Начинают белые, затем ходят поочерёдно. Правила следующие: Каждый игрок помещает камень своего цвета на доску во время хода. Камни не передвигаются, не захватываются, никаких изменений с камнями не происходит. Игрок выигрывает, когда он завершает одну из трёх отличающихся структур из путей, состоящих из примыкающих друг к другу камней своего цвета: кольцо — петля вокруг одного или более полей (не имеет значения, заняты ли внутренние поля кем-то из игроков, или пусты); мост, соединяющий любые два из шести угловых поля доски; вилка, соединяющая любые три ребра доски. Угловые поля не считаются частями рёбер.
Примеры трёх выигрышных комбинаций показаны на иллюстрации. Цепочка в центре доски — кольцо, цепочка слева — вилка, а цепочка справа — мост.
Поскольку игрок, играющий первым, имеет существенное преимущество, для достижения справедливой игры применяется . Это правило позволяет второму игроку выбирать, продолжать игру после хода первого игрока, или обменяться с ним ролями.
Игроки разного уровня могут играть интересную игру, если слабому игроку (играющему белыми камнями) даётся фора — разрешается положить первым ходом два и более камней.
Отличия от Гекс В игре Гекс, когда поле полностью заполнено, ровно один игрок будет иметь выигрышную цепочку. В игре Havannah же полностью заполненное поле обычно содержит несколько выигрышных структур, хотя игра заканчивается при обнаружении первой из них.
В отличие от игры Гекс, в игре Гаванна теоретически возможны ничьи, хотя на практике они встречаются крайне редко. Известен лишь один случай ничьей между игроками-людьми. Тактические приёмы освоить гораздо проще, чем стратегию, и разница в уровне мастерства игроков может быть весьма существенной.
Компьютерная Гаванна В 2002 году Фрилинг учредил приз в 1000 евро для создателей любой компьютерной программы, способной обыграть его хотя бы в одной игре из десяти. Долгое время компьютерные программы значительно уступали людям. Однако с 2010 года несколько программ, предназначенных для игры в Гаванну, стали использовать , что привело к заметному улучшению их игрового уровня. На «Соревновании по игре Гаванна», которое состоялось 15—19 октября 2012 года, Фрилинг сыграл десять партий против трёх сильнейших играющих в Гаванну доступных программ, проведя (как минимум) одну игру чёрными и одну белыми против каждого оппонента. Фрилинг проиграл вызов и выплатил обещанную сумму, когда ему пришлось сдаться в игре белыми против программы Lajkonik.
До 2019 года лучшие игроки-люди значительно превосходили компьютеры. Однако, программа MetaTotoro, основанная на Polygames (проект с открытым кодом, первоначально разрабатывавшийся Facebook Artificial Intelligence Research и несколькими университетами), четыре раза подряд одержала победу на доске размером 8 на 8 клеток против игрока-человека с наивысшим рейтингом Эло на сайте LittleGolem, который также был победителем различных турниров.
Этот результат был достигнут той же программой, что использовалась для победы над лучшими игроками-людьми в Гекс. Это алгоритм, основанный на обучении с нуля, как в AlphaZero, но с нововведениями — инвариантность к размеру доски благодаря полностью свёрточным нейронным сетям (как в U-Net) и глобальным пулингом. Это позволяет использовать растущие архитектуры, что означает, что программа может обучаться на маленькой доске, а затем экстраполировать опыт на большую.
Гаванна — это регулярно представленная игра на . В неё играют на доске с основанием 8, а иногда и на доске с основанием 10. Во время этого соревнования применяется правило пирога.
Вычислительная сложность Решение игры Гаванна авляется относительно размера входного графа. Доказательство ведётся сведением от игры в города и использует угрозы построения кольца для предоставления графа географии. В частности, поскольку Лихтенштейн и Сипсер доказали, что игра в города остаётся PSPACE-трудной, даже если граф является лишь двудольным графом со степенью вершин не более 3, остаётся лишь построить эквивалентную позицию в игре Гаванна из такого графа, что достигается путём создания различных конструкций в игре.
Примечания
Ссылки Official site MindSports.nl Havannah статья на сайте
Категория:Абстрактные стратегические игры Категория:Игры на соединение