Стратегические игры. Доступный учебник по теории игр - Авинаш Диксит

Когда стало ясно, что компьютеры способны выполнять сложные вычисления в науке и бизнесе, многие математики и программисты решили, что вскоре компьютерная шахматная программа победит именитых гроссмейстеров. Но это произошло не так быстро, хотя компьютерные технологии развивались стремительными темпами, тогда как человеческое мышление несколько поотстало. В конце концов в декабре 1992 года немецкая компьютерная программа под названием Fritz2 выиграла у чемпиона мира Гарри Каспарова несколько блицпартий. Согласно обычным правилам, каждому игроку предоставляется 2,5 часа на выполнение 40 ходов, и люди дольше удерживали превосходство. Команда специалистов, финансируемая компанией IBM, вложила немало усилий и ресурсов в разработку специализированного компьютера (получившего название Deep Blue) для игры в шахматы и соответствующего программного обеспечения. В феврале 1996 года Deep Blue выступил в роли противника Гарри Каспарова в матче из шести партий и произвел сенсацию, выиграв первую партию, но Каспаров быстро выявил его слабые места, улучшил контрстратегии и мастерски выиграл остальные партии. На протяжении следующих 15 месяцев команда IBM совершенствовала аппаратное и программное обеспечение компьютера, после чего в мае 1997 года модифицированный Deep Blue выиграл у Каспарова очередной матч из шести партий.

Таким образом, развитие компьютерных технологий характеризовалось сочетанием периодов медленного поэтапного улучшения и ряда стремительных рывков, в то время как люди, сохранив определенное превосходство, не смогли перестроиться настолько быстро, чтобы удержать передовые позиции. При ближайшем рассмотрении оказалось, что люди и компьютеры используют абсолютно разные подходы к анализу очень сложного дерева игры в шахматы.

При обдумывании хода в шахматах крайне трудно (для обоих: и людей, и компьютеров) заранее предвидеть исход игры. Но как насчет того, чтобы просчитать часть ходов, скажем 5−10, вперед и проанализировать игру в обратном порядке из этой позиции? Игра необязательно должна закончиться в рамках этого ограниченного периода; иными словами, узлы, которых вы достигнете через 5−10 ходов, не будут концевыми. Однако в соответствии с правилами игры выигрыши указываются только для концевых узлов. Следовательно, необходим некий косвенный способ присвоения правдоподобных выигрышей неконцевым узлам, поскольку вы не можете проанализировать все дерево игры методом обратных рассуждений с самого конца. Правило, согласно которому присваиваются промежуточные выигрыши, называется функцией промежуточной оценки.

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

Дальше всего оценка промежуточных позиций продвинулась в отношении дебютов, то есть первой дюжины ходов игры. Каждый отдельно взятый дебют может привести к любому из огромного множества дальнейших ходов и позиций, однако опыт позволяет игрокам делать вывод о том, какой дебют с определенной степенью вероятности более выгоден для того или иного игрока. Эта информация записана в объемных книгах о шахматных дебютах; все шахматисты высокого класса и компьютерные программы помнят и используют эти знания.

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

Именно на стадии миттельшпиля на первый план выходит искусство игры в шахматы. У лучших шахматистов развивается интуиция, которая позволяет им распознавать хорошие возможности и избегать скрытых ловушек на уровне, с которым компьютерным программам сложно конкурировать. Программисты обнаружили, что в большинстве случаев компьютеры трудно обучить тем навыкам распознавания образов, которые люди развивают и используют инстинктивно, – например, когда они узнают лица и связывают их с именами. Искусство ведения игры на стадии миттельшпиля в шахматах – это распознавание и оценка комбинаций столь же загадочным способом. Именно в этом состояло самое большое преимущество Каспарова перед Fritz2 или Deep Blue. Это также объясняет, почему компьютерные программы показывают более высокие результаты в игре с людьми в блицпартиях или партиях с ограниченным временем обдумывания ходов: человеку просто не хватает времени, чтобы применить свое искусство ведения игры на стадии миттельшпиля.

Иными словами, лучшие шахматисты обладают филигранным знанием шахмат, основанным на опыте или способности распознавать образы, что предоставляет в их распоряжение более эффективную функцию промежуточной оценки. Компьютеры доминируют в области вычислений методом грубой силы. Таким образом, хотя в настоящее время и люди, и компьютеры используют сочетание упреждающей и промежуточной оценки, они применяют их в разных пропорциях: шахматисты просчитывают наперед не так много ходов, но располагают более развитой функцией промежуточной оценки на основании знаний; компьютеры имеют менее развитые функции оценки, но могут просчитывать наперед гораздо больше ходов благодаря огромной вычислительной мощности.

В последнее время компьютеры начали накапливать больше знаний. В процессе модификации Deep Blue в 1996–1997 годах специалисты IBM заручились поддержкой экспертов по шахматам для улучшения функции промежуточной оценки в своих программах. Консультанты много раз играли в шахматы с компьютером, отмечали его слабые места и подсказывали, как изменить функцию оценки, чтобы устранить дефекты. Deep Blue явно пошел на пользу вклад экспертов и их тонкое мышление, ставшее результатом многолетнего опыта и знания сложных взаимосвязей между фигурами на шахматной доске.

Если люди, постепенно формулируя свои глубинные знания, передают их компьютерам, то на что рассчитывать шахматистам, не получающим от ПК аналогичной помощи? В момент первой встречи с Deep Blue в 1997 году Каспаров был поражен человеческим или даже сверхчеловеческим качеством игры компьютера. Он даже увидел в одном из его ходов «руку Бога». А ведь ситуация может усугубиться еще сильнее: способность компьютеров просчитывать ходы методом грубой силы стремительно повышается, причем одновременно, хотя и медленнее, они обретают тонкость мышления, свойственную человеку.

Абстрактная теория шахмат гласит, что это конечная игра, которая может быть решена методом обратных рассуждений. Шахматы зачастую требуют искусства ведения игры, опирающегося на опыт, интуицию и тонкие суждения. Плохо ли это с точки зрения использования метода обратных рассуждений в процессе анализа игр с последовательными ходами? Мы считаем, что нет. Теория действительно не позволяет найти полное решение игры в шахматы, но дает возможность достаточно далеко продвинуться в этом направлении. Упреждающий анализ нескольких ходов – важный аспект подхода, подразумевающий сочетание просчета ходов методом грубой силы и основанной на знаниях оценки промежуточных позиций. По мере увеличения вычислительной мощности компьютеров будет возрастать и роль просчитывания ходов методом грубой силы, а значит, и область применения теории обратных рассуждений.

Данные исследований игры в шашки, о чем мы расскажем ниже, говорят о том, что решение игры в шахматы все же может быть найдено.

Невероятное количество компьютерных и человеко-часов ушло на поиск решения игры в шахматы. С не меньшим упорством исследователи работали и над решением несколько более простой игры – в шашки, и в 2007 году объявили, что оно найдено[28].

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