Эта странная математика

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

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

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

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