Max Home IndustryГо — важная игра для искусственного интеллекта, поскольку до недавнего времени люди играли в нее намного лучше, чем компьютеры. Это сложная и тонкая игра, которая только-только выявила один из самых фундаментальных параметров любой игры — сколько существует легальных позиций.
Только на прошлой неделе мы сообщили новость о том, что у 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. Что дальше?
Хотя ИИ обнаружил, что играть в Го сложнее, чем в шахматы, мы до сих пор не знаем количество возможных партий в шахматы — мы даже не знаем порядка их величины.