20 января 2016 года Джон Тромп сообщил об определении точного числа допустимых расстановок камней на стандартной доске 19×19. Результат содержит 171 десятичную цифру и составляет приблизительно 2,08168 × 10¹⁷⁰.
Под допустимой понимается расстановка, в которой каждая связная группа камней одного цвета имеет хотя бы один соседний свободный пункт. Это уже существенно меньше всех возможных раскрасок 361 пункта в три состояния: пустой, чёрный и белый. Приближённое значение было известно ранее; достижение 2016 года относится к полному точному числу.
Автор описал алгоритм через состояния границы последовательно рассматриваемой доски и разбиение вычисления на независимые части. Расчёт выполнялся на нескольких крупных вычислительных площадках; последняя задача завершилась 26 декабря 2015-го, после чего потребовалось получить журналы и собрать результат. Код и встроенные проверки опубликованы открыто.
Веха относится к математическому описанию пространства игры и воспроизводимой вычислительной работе. Она не означает решения го, доказательства победы первого или второго игрока и перечисления всех возможных партий. Число позиций, число последовательностей ходов и сложность выбора лучшего хода — разные характеристики; смешивать их было бы ошибкой.
Основание материала
Источники и проверка
- Официальный источник
John Tromp: Counting Legal Positions in Go
Введение / Computational Challenge / Chinese jobs / Verifiability
Проверен:
Раскрытие связи
Материал входит в общий проект сайтов о го.
История продолжается.
Другие события в хронике →