Хаванна: Стратегическая игра и вызов искусственному интеллекту
Havannah (board game)
Хаванна: абстрактная стратегия для двоих игроков. Настольная игра, похожая на Hex и TwixT, с глубокой стратегией на гексагональном поле. Купить Хаванна!
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Хаванна – настольная игра для двух игроков, изобретённая Кристианом Фрилингом. Она относится к семейству игр, обычно называемых играми на соединение; к её «родственникам» относятся Hex и TwixT. Хаванна обладает «сложной и разнообразной стратегией» и лучше всего играется на гексагональной доске с основанием 10, то есть с 10 гексагональными ячейками на каждой стороне. В своё время игра издавалась в Германии компанией Ravensburger, с уменьшенной доской с основанием 8, подходящей для начинающих. В настоящее время её производит только Hexboards.
the board game
Havannah is a two player abstract strategy board game invented by Christian Freeling. It belongs to the family of games commonly called connection games; its relatives include Hex and TwixT. Havannah has "a sophisticated and varied strategy" and is best played on a base 10 hexagonal board, 10 hex cells to a side. The game was published for a period in Germany by Ravensburger, with a smaller, base 8 board suitable for beginners. It is nowadays only produced by Hexboards.
Разница по сравнению с Hex
В игре "Шестигранник", когда доска полностью заполнена, выигрышную связь имеет ровно один игрок; в "Гаванне" на полностью заполненной доске обычно бывает больше одной выигрышной структуры (но игра заканчивается, как только появляется первая выигрышная структура). В отличие от "Шестигранника", в "Гаванне" ничьи технически возможны, но на практике они чрезвычайно редки. Известна всего одна ничья между игроками-людьми. Тактику освоить гораздо проще, чем стратегию, и разница в уровне игры между игроками может быть очень большой.
In Hex, when the board is completely filled, exactly one player will have a winning connection; in Havannah a completely filled board will have usually more than one winning structures (but the game ends with first winning structure). Unlike in Hex, in Havannah draws are technically possible, in practice they are extremely rare. There has been one known draw between human players. Tactics are much easier to master than strategy, and differences in playing level are considerable.
Компьютерная Гавана
В 2002 году Фрилинг предложил приз в размере 1000 евро, доступный до 2012 года, любой компьютерной программе, способной выиграть хотя бы одну партию из десяти. На протяжении многих лет компьютерные программы значительно отставали от игроков-людей. Однако, начиная с 2010 года, несколько программ для игры в Хаванну стали использовать методы поиска по деревьям Монте-Карло, что привело к заметному улучшению их игровой силы. "Havannah Challenge 2012" прошел с 15 по 19 октября 2012 года, в ходе которого Фрилинг сыграл десять партий против трех сильнейших программ для игры в Хаванну, сыграв как минимум одну партию черными и одну белыми против каждого соперника. Фрилинг проиграл, когда был вынужден сдаться в партии белыми против программы Lajkonik. До 2019 года лучшие игроки-люди все еще значительно превосходили компьютеры. Однако MetaTotoro, основанный на Polygames (проекте с открытым исходным кодом, первоначально разработанным Facebook Artificial Intelligence Research и несколькими университетами), четыре раза подряд выиграл на доске размером 8x8 у игрока с самым высоким рейтингом ELO на LittleGolem, который также был победителем различных турниров. Этот результат был достигнут той же программой, которая победила лучших игроков в Hex. Это алгоритм, основанный на обучении с нуля, как в AlphaZero, но с новыми особенностями: инвариантность к размеру доски благодаря полностью сверточным нейронным сетям (как в U-Net) и глобальному объединению. Это позволяет создавать масштабируемые архитектуры, то есть программа может обучаться на маленькой доске, а затем применять полученные знания к большой доске.
In 2002 Freeling offered a prize of 1000 euros, available through 2012, for any computer program that could beat him in even one game of a ten game match. For many years, computer programs lagged far behind human players. However, since 2010 several Havannah playing programs have applied Monte Carlo tree search techniques resulting in some notable improvement in playing strength. The "Havannah Challenge 2012" was held October 15–19, 2012 during which Freeling played ten games against three of the strongest Havannah playing programs available, playing (at least) one game as black and one as white against each opponent. Freeling lost the challenge when he had to resign a game with white against the Lajkonik program. Until 2019, the best humans were still by far stronger than computers. However, MetaTotoro, based on Polygames (an open source project, initially developed by Facebook Artificial Intelligence Research and several universities), won four times in a row on the board of size 8 against the human player with the best ELO rank on LittleGolem, who was also the winner of various tournaments. This result was achieved by the same program as the one used for beating best humans at Hex. It is a zero learning based algorithm, as in AlphaZero, but with novelties: boardsize invariance thanks to fully convolutional neural networks (as in U Net) and global pooling. This allows growing architectures, meaning the program can learn on a small board, and then extrapolate on a large board.
Комплексность вычислений
Решение задачи Гаванна является PSPACE-полным по отношению к размеру входного графа. Доказательство основано на сведении из обобщённой географии и использует кольцевые угрозы для представления графа географии. Поскольку Лихтенштейн и Сипсер доказали, что обобщённая география остаётся PSPACE-трудной даже для двудольных графов со степенью не более 3, остаётся лишь построить эквивалентную позицию в Гаванне на основе такого графа, что достигается путём создания различных конструкций (гаджетов) в Гаванне.
Solving Havannah is PSPACE complete with respect to the size of the input graph. The proof is by a reduction from generalized geography and is based on using ring threats to represent the geography graph. In detail, since Lichtenstein and Sipser have proved that generalized geography remained PSPACE hard even if the graph is only bipartite and of degree at most 3, it only remains to construct an equivalent Havannah position from such a graph, which is accomplished by constructing various gadgets in Havannah.