Гавана (настольная игра)

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

Игра какое-то время издавалась в Германии компанией Ravensburger с доской меньшего размера, с основанием 8, подходящей для новичков. В настоящее время его производит только Hexboards. ^{[ 2 ]}

Правила игры

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

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

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

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

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

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

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

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

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

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

До 2019 года лучшие люди по-прежнему были намного сильнее компьютеров. Однако MetaTotoro , основанный на Polygames ^{[ 7 ]} (проект с открытым исходным кодом, первоначально разработанный Facebook Artificial Intelligence Research и несколькими университетами ^{[ 8 ]}), выиграл четыре раза подряд на доске размера 8 у игрока-человека с лучшим рейтингом ЭЛО на LittleGolem , который также был победителем различных турниров.

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

Гаванна — повторяющаяся игра на Компьютерной олимпиаде . В нее играют на доске с основанием 8, а иногда и на доске с основанием 10. Во время этого конкурса используется правило пирога.

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

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

Отзывы

Игры и стратегии №9 ^{[ 11 ]}

Ссылки

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

Внешние ссылки

[1] Хэндскомб, Керри, изд. (зима 2002 г.). «Передняя обложка». Абстрактные игры (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 Incubator, 28 мая 2020 г. , получено 29 мая 2020 г.

[8] «Polygames с открытым исходным кодом, новая платформа для обучения ботов с искусственным интеллектом посредством самостоятельной игры» . ai.facebook.com . Проверено 29 мая 2020 г.

[9] Казенав, Тристан; Чен, Йен-Чи; Чен, Гуан-Вэй; Чен, Ши-Ю; Чиу, Сянь-Донг; Деос, Жюльен; Эльза, Мария; Гун, Цюйчэн; Ху, Хэнъюань; Халидов, Василь; Ли, Ченг-Лин; Линь, Синь-И; Лин, Ю-Джин; Мартине, Ксавье; Мелла, Вегард; Рапин, Джереми; Розьер, Батист; Синнев, Габриэль; Тейто, Фабьен; Тейто, Оливье; Йе, Ши-Чэн; Йе, И-Джун; Йен, Ши-Джим; Загоруйко, Сергей (27 января 2020 г.). «Полиигры: улучшенное нулевое обучение». arXiv : 2001.09832 [ cs.LG ].

[10] Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (14 августа 2013 г.). Havannah и TwixT являются PSPACE-полными . 8-й международный Конф. по компьютерам и играм. Университет Кейо, Иокогама, Япония. arXiv : 1403.6518 . дои : 10.1007/978-3-319-09165-5_15 .

[11] «Игры и стратегии 09» . Июнь 1981 года.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]