Количество окончательно проработанных позиций Legal Go


Го – важная игра для искусственного интеллекта, поскольку до недавнего времени люди играли в нее намного лучше, чем компьютеры. Это сложная и тонкая игра, которая только-только выявила один из самых фундаментальных параметров любой игры – сколько существует легальных позиций.

Только на прошлой неделе мы сообщили новость о том, что у Google DeepMind есть программа, которая работает очень хорошо, достаточно хорошо, чтобы победить профессионального игрока. В то же время у нас есть еще один прорыв – ответ на вопрос, сколько ходов в го?

Изображение предоставлено: Goban1

Доска Го имеет размер 19×19, и вы можете разместить черный или белый камень в любом месте, таким образом, каждое место может находиться в одном из трех состояний – пустом, черном или белом. Это означает, что если бы все комбинации были допустимыми позициями, в игре было бы 3361 возможное состояние. Камни могут быть размещены в любом месте на доске, но для того, чтобы каждая группа камней одного цвета была разрешена, она должна иметь по крайней мере одну пустую позицию рядом с одним из камней. Если это условие не выполняется, группа захватывается другим игроком, и камни удаляются с доски. Следовательно, единственные позиции, которые могут встречаться в Go, – это именно юридические позиции.

Итак, сколько существует юридических позиций?

Примерное значение этого числа, получившее название L19, известно с 2006 года.

L19 составляет приблизительно 2,081681994 * 10170

Спустя еще десять лет работы Джона Тромпа у нас наконец-то есть:

2081681993819799846

9947863334486277028

6522453884530548425

6394568209274196127

3801537852564845169

8519643907259916015

6281285460898883144

2712971531931755773

6620397247064840935

Как это было сделано?

Оказывается, проблема сводится к задаче возведения разреженной матрицы с 363 миллиардами строк и столбцов в 361 степень. Да, это была квадратная матрица с 363 миллиардами строк.

Эта формулировка была известна в начале 2000-х, но вычислительные мощности были доступны только сейчас. После того, как Тромп определил количество разрешенных ходов для 18-позиционной доски, вы могли подумать, что он получит много предложений о помощи, но только HP с ее Helion Cloud предложила предоставить вычислительные ресурсы. Вычисления начались 6 марта 2015 г. и продолжались до 26 декабря 2015 г., а после некоторой постобработки число было объявлено 20 января 2016 г. Было сгенерировано около 30 петабайт дискового ввода-вывода.

Если вам нравится идея проверки вычислений путем повторного запуска программы, вам понадобится что-то вроде сервера с 15 ТБ быстрого рабочего дискового пространства, от 8 до 16 ядер и 192 ГБ ОЗУ, и вам придется подождать несколько месяцев.

Теперь у нас есть количество разрешенных ходов на доске всех размеров от 1 до 19. Что дальше?

Хотя ИИ обнаружил, что играть в Го сложнее, чем в шахматы, мы до сих пор не знаем количество возможных партий в шахматы – мы даже не знаем порядка их величины.


Добавить комментарий