Эта странная математика. На краю бесконечности и за ним - Дэвид Дарлинг

Игра в го.

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

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

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

Зато мы точно знаем, что игры типа шахмат и го, а также более простые, вроде крестиков-ноликов или точек и квадратов, – это “игры с совершенной информацией”: обдумывая ход, участник располагает всей информацией, необходимой, чтобы определить, какие ходы хорошие, а какие плохие. Никакой неопределенности, все на виду. А это значит, что в принципе, при наличии неограниченных ресурсов памяти и времени, такие игры можно просчитать. Но есть и другие игры, такие как покер, где не вся информация участникам доступна. Обдумывая свой ход, игрок в покер не знает, какие карты на руках у соперников – а ведь это решающий фактор, определяющий исход партии. Новичку, противостоящему в турнире профессионалу, конечно, может повезти – соберет роял-флеш да и выиграет партию. Но при длительной игре с большим количеством партий более опытный участник, знающий, когда делать ставку, а когда пасовать, в среднем выигрывает чаще и более крупные суммы, чем новичок.

Прежде чем говорить о просчитывании игр, подобных покеру, необходимо определиться, что же означает “просчитать”, когда речь идет об играх без “совершенной информации”. Ни один компьютер не может гарантировать стопроцентного выигрыша в покере (если не будет жульничать) – всегда ведь есть вероятность, что человеку придет роял-флеш. Поэтому “просчитыванием” в случае с покером будет выработка компьютером такой стратегии, при которой он в среднем окажется в выигрыше максимальное количество раз.

В покере еще больше усложняет задачу просчитывания возможность блефа и то, что обычно в турнирах игроков за столом значительно больше двух. Когда вместе состязаются компьютер и несколько человек, люди вполне могут объединиться против машины (причем, скорее всего, так и сделают), стремясь поставить ее в невыгодное положение. И пусть в подобной ситуации выигрыш каждого из живых участников будет менее ощутимым, чем если бы он действовал только сам за себя, – зато команда выиграет больше.

И все же для одной из разновидностей покера – техасского холдема для двух участников с лимитом – ученые уже разработали программу, которую невозможно победить в длинной серии игр. Ее появление в 2014 году стало важной вехой: впервые был найден алгоритм, способный просчитать сложную игру, в которой часть информации участникам недоступна. Эта скрытая информация и случайность розыгрыша карт не дают компьютеру выигрывать каждый раз. Но в серии из множества партий у человека практически нет шансов (так же как шахматисту, например, практически невозможно превзойти программу Stockfish) – так что эту версию игры мы вправе объявить просчитанной. Программа может не только помочь участникам усовершенствовать навыки игры; предполагается, что используемый в ней подход найдет применение в здравоохранении и системах безопасности.