Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

Игра в го.

Но вот наступил 2016 год, и разработанная Google программа AlphaGo победила одного из лучших в мире игроков в го Ли Седоля со счетом 4:1. AlphaGo полагается не столько на просчитывание ходов и перебор возможных ситуаций, сколько на другие методы, больше свойственные человеку, чем машине. В ее основе – нейронная сеть, моделирующая работу органического мозга при решении проблемы. Изучив заложенную в нее огромную базу данных сыгранных мастерами партий, программа стала нескончаемо состязаться сама с собой, чтобы научиться узнавать выигрышные позиции и комбинации. Сочетание интеллектуального, эвристического подхода, свойственного человеку, с высокой скоростью, обеспечиваемой кремниевой начинкой, позволяет AlphaGo достичь того, что еще до недавнего времени считалось очень дальней перспективой, – уровня суперзвезды го мирового класса. В 2017 году AlphaGo улучшила собственный результат, одержав победу во всех трех партиях с лучшим игроком мира Кэ Цзе.

Мало кто сегодня сомневается, что уже скоро компьютерные мастера игры в го станут такими же непобедимыми соперниками для своих органических создателей, как и их шахматные собратья. Но мы так и не ответили на вопрос: разрешимы ли такие игры, как шахматы и го? В шахматах, поскольку белые ходят первыми, черные могут только реагировать на создаваемые ими угрозы. Поэтому, если когда-нибудь решение будет найдено – то есть будет вычислена оптимальная последовательность ходов белых в ответ на любые действия черных, – почти наверняка единственными возможными исходами игры будут победа белых или ничья. В го ситуация несколько сложнее, потому что по правилам в качестве компенсации за право черных ходить первыми белые получают определенное количество очков (6,5 по японским правилам, 7,5 по китайским). Возможно, этого достаточно для победы белых, но не исключено, что преимущество первого хода настолько перевешивает компенсацию, что выигрыш черным все равно обеспечен. Точно никто не знает – а может, никогда и не узнает.

Верным способом вычислить решение шахматной игры было бы нарисовать дерево со всеми возможными позициями-ветвями, затем, начиная с любой из них, дать оценку каждому из ответвлений, посмотрев, чем они кончаются, и выбрать то, которое ведет к оптимальному исходу. В теории все просто. Но поскольку общее количество возможных вариантов игр составляет приблизительно триллион триллионов триллионов триллионов триллионов триллионов триллионов триллионов триллионов триллионов, получившееся дерево будет иметь колоссальный размер. Создать компьютер, способный вместить такое количество данных, будет несколько проблематично, учитывая, что атомов во всей видимой Вселенной, вероятно, всего-то около 10 80, то есть в 10 40раз меньше. На практике большую часть ветвей можно отсечь уже на начальном этапе, потому что многие из возможных позиций совершенно нелепы и в реальной партии никогда не возникнут, даже если играют новички. Но и после такой обрезки оставшееся дерево возможных реалистичных ходов будет чудовищно большим. А в случае с го его крона будет еще ветвистее. Из-за невероятной сложности подобных игр многие считают, что, хотя теоретически их и можно рассчитать, на практике это совершенно нереально. Если во всей Вселенной не хватит элементарных частиц, чтобы сохранить даже сильно обрезанное дерево ходов игры, как же ее просчитать? Возможно, на помощь придет более совершенный искусственный интеллект, который сумеет отсечь в дереве поиска еще больше ветвей и довести его крону до приемлемых размеров. Еще один вариант – квантовые компьютеры, способные вести поиск одновременно в огромном количестве ветвей. Впрочем, в отличие от случая с алгоритмом Шора для разложения на множители больших чисел, на сегодняшний день у нас не только нет алгоритма для решения задач такого типа, но мы даже не знаем, существует ли он вообще. Некоторую надежду вселяет тот факт, что для шашек решение все же было найдено. Это произошло в 2007 году и потребовало почти двадцати лет работы сотен компьютеров, которые все эти годы перебирали возможные комбинации ходов в игре. Как выяснилось, в шашках, если оба соперника играют без ошибок, партия всегда закончится ничьей. Удастся ли благодаря прогрессу технологий и программирования найти аналогичное решение для шахмат, а может быть, и для го? Время покажет.