Текст книги "Стратегические игры. Доступный учебник по теории игр"
Автор книги: Авинаш Диксит
Жанр: Зарубежная образовательная литература, Наука и Образование
Возрастные ограничения: +12
сообщить о неприемлемом содержимом
Текущая страница: 7 (всего у книги 72 страниц) [доступный отрывок для чтения: 20 страниц]
Действие методов, представленных в разделе 2 в самой простой ситуации с двумя игроками и двумя ходами, можно легко расширить, при этом деревья становятся более сложными, в них увеличивается количество ветвей, узлов и уровней, но основные концепции и метод обратных рассуждений не меняются. В данном разделе мы рассмотрим игру с тремя участниками, у каждого из которых есть два варианта выбора. С небольшими вариациями эта игра будет появляться во многих следующих главах.
Три игрока, Эмили, Нина и Талия, живут на одной маленькой улице. Каждую девушку попросили внести свой вклад в создание декоративного сада на месте пересечения улицы с автомагистралью. Окончательная площадь и пышность сада зависят от того, сколько участницы игры готовы в него вложить. Кроме того, хотя все три участницы были бы счастливы иметь такой сад (а его размер еще больше усилил бы это ощущение), ни одна из них не спешит с инвестициями из-за их размера.
Предположим, что если две или три участницы игры внесут свой вклад в создание сада, то этих ресурсов хватит для его закладки и последующего ухода за растениями, а сам сад будет весьма привлекательным и милым. Тем не менее, если всего одна из девушек или никто из них этого не сделают, сад будет скудным и неухоженным и не принесет радости людям. Таким образом, с точки зрения каждой участницы, существуют четыре разных исхода.
• Одна участница игры не инвестирует в сад, в отличие от двух остальных (что приводит к созданию привлекательного сада и позволяет ей сэкономить на вкладе).
• Одна участница игры инвестирует в сад, и остальные, одна или обе, – тоже (что приводит к созданию привлекательного сада, но не позволяет ей сэкономить на вкладе).
• Одна участница игры не инвестирует в сад, и только одна из двух оставшихся участниц вносит свой вклад (что приводит к созданию скудного сада, но позволяет ей сэкономить на вкладе).
• Одна участница игры инвестирует в сад, в отличие от двух остальных (что приводит к созданию скудного сада и не позволяет ей сэкономить на вкладе).
Очевидно, что первый из исходов – лучший, тогда как последний – худший. Мы хотим, чтобы более высокие показатели выигрышей соответствовали более благоприятным исходам, поэтому присваиваем первому исходу в списке выигрыш 4, а последнему – выигрыш 1. (Иногда выигрыши соответствуют порядковому номеру исхода в списке исходов. Следовательно, при наличии четырех исходов первый был бы лучшим, а четвертый – худшим, а меньшие числа обозначали бы более предпочтительные исходы. Читая книгу по теории игр, обратите особое внимание на то, какую систему обозначений выбрал автор; если вы пишете о теории игр, вам следует точно указать используемую систему обозначений.)
В двух средних исходах присутствует некоторая неоднозначность. Предположим, каждый игрок ценит привлекательный сад более высоко, чем собственный вклад в его создание. В таком случае исход, указанный в списке вторым, обеспечит выигрыш 3, а исход под номером три – выигрыш 2.
Допустим, участницы игры ходят поочередно. Эмили получает право первого хода и решает, инвестировать ли ей в сад. В свою очередь Нина, глядя на выбор Эмили, решает, стоит ли и ей так поступить. И наконец, Талия, оценив выбор Эмили и Нины, делает аналогичный выбор[22]22
В следующих главах мы внесем изменения в правила этой игры (в частности, в порядок ходов и выигрышей) и проанализируем, как они скажутся на ее исходе.
[Закрыть].
На рис. 3.6 изображено дерево этой игры. Чтобы облегчить ее описание, мы обозначили узлы действия специальными символами. Эмили делает ход в начальном узле a, а ветви, соответствующие двум имеющимся у нее вариантам выбора («внести вклад» и «не вносить вклад»), ведут к узлам b и c. В каждом из них должна сделать ход Нина и выбрать один из представленных вариантов. Ее выбор приводит к узлам d, e, f и g, в каждом из которых наступает очередь Талии ходить. Имеющиеся у Талии варианты выбора приводят к восьми концевым узлам, где мы показываем выигрыш в таком порядке: (Эмили, Нина, Талия)[23]23
Как было сказано в разделе 1, в играх с последовательными ходами обычно принято перечислять выигрыши в том порядке, в котором игроки делают ходы, однако при наличии неоднозначности или просто для ясности лучше задавать порядок перечисления выигрышей в явной форме.
[Закрыть]. Например, если Эмили решает инвестировать в создание сада, Нина нет, а Талия да, то красивый декоративный сад будет разбит и две участницы, внесшие вклад в его создание, получат выигрыш 3 каждая, а участница, которая решила сэкономить, – свой максимальный выигрыш 4. В данном случае список выигрышей выглядит так: (3, 4, 3).
.
Рис. 3.6. Игра «уличный сад»
Для того чтобы применить к этой игре метод обратных рассуждений, начнем с узлов действия, расположенных непосредственно перед концевыми узлами, а именно с узлов d, e, f и g. Талия делает ход в каждом из этих узлов. В узле d она сталкивается с ситуацией, когда и Эмили, и Нина вносят вклад в создание сада, то есть сад уже наверняка будет красивым, поэтому, выбрав вариант «не вносить вклад», Талия получает свой максимальный выигрыш 4, тогда как в противном случае – следующий по размеру выигрыш 3. Стало быть, предпочтительный для Талии вариант выбора в данном узле – «не вносить вклад». Мы отображаем это путем выделения соответствующей ветви жирной линией и добавления к ней стрелки; любого из этих способов было бы достаточно для иллюстрации выбора Талии. В узле e Эмили выбрала вариант «внести вклад», а Нина – «не вносить», поэтому вклад Талии крайне важен для создания красивого сада. Талия получит выигрыш 3, если выберет «внести вклад», и 2 в результате отказа. Ее предпочтительный вариант выбора в узле e – «внести вклад». Аналогичным образом можно проверить выбор Талии в двух оставшихся узлах.
Теперь давайте вернемся немного назад и проанализируем предыдущий этап – а именно узлы b и c, в которых наступает очередь Нины выбирать. В узле b Эмили решила инвестировать в создание сада, поэтому Нина рассуждает так: «Если я выберу вариант “внести вклад”, это приведет игру в узел d, а там, насколько мне известно, Талия выберет “не вносить вклад”, и мой выигрыш составит 3. (Сад будет красивым, но я понесу убытки.) Если я выберу “не вносить вклад”, игра переместится в узел e, где, как мне известно, Талия выберет “внести вклад”, а мой выигрыш будет 4. (Сад будет красивым, а я сэкономлю на расходах.) Следовательно, я выбираю “не вносить вклад”». Аналогичные рассуждения показывают, что в узле c Нина предпочтет вариант «внести вклад».
И наконец, рассмотрим выбор Эмили в начальном узле a. Она может предвидеть последующий выбор как Нины, так и Талии и знает, что если выберет вариант «внести вклад», то Нина выберет «не вносить вклад», а Талия – «внести вклад». Если две участницы игры инвестируют в создание сада, он будет красивым, но Эмили понесет издержки, а значит, ее выигрыш составит 3. Если Эмили предпочтет «не вносить вклад», то в двух следующих друг за другом узлах будет выбран вариант «внести вклад», и при наличии красивого сада и отсутствии издержек ее выигрыш составит 4. Таким образом, оптимальный выбор Эмили в узле a – «не вносить вклад».
Теперь подвести итоги анализа игры «уличный сад» методом обратных рассуждений не составит труда. Эмили выберет вариант «не вносить вклад», затем Нина – «внести вклад» и наконец Талия – тоже «внести вклад». Такая последовательность выбора образует конкретный путь игры на данном дереве, который проходит по нижней ветви, исходящей из начального узла, а затем по верхним ветвям в каждом из двух идущих друг за другом следующих узлов, с и f. На рис. 3.6 этот путь игры легко отследить как непрерывную последовательность стрелок, пролегающую от начального до пятого концевого узла, если вести отсчет от верхней части дерева. Выигрыши, которые получат участницы игры, показаны в концевом узле.
Анализ методом обратных рассуждений прост и привлекателен. Мы бы хотели подчеркнуть его некоторые особенности. Во-первых, обратите внимание, что на равновесном пути игры с последовательными ходами отсутствует большинство ветвей и узлов. Однако вычисление лучших действий, которые следовало бы предпринять, если бы игра все же их достигла, – важная часть процесса поиска окончательного равновесия. Выбор на ранних этапах игры ее участницы делают под влиянием своих ожиданий в отношении того, что произойдет, если они выберут действие, отличающееся от оптимального, а также что бы произошло, если бы любая из оставшихся участниц игры предпочла нечто иное, чем то, что является для нее лучшим. Эти ожидания, основанные на прогнозируемых вариантах выбора в узлах, расположенных вне равновесного пути игры (то есть в узлах, которые соответствуют ветвям, отсеченным в процессе анализа методом обратных рассуждений), позволяют участницам игры совершать оптимальные действия в каждом узле. Например, предпочтительный выбор Эмили «не вносить вклад», сделанный в первом узле, обусловлен пониманием того, что если она выберет вариант «внести вклад», то Нина выберет «не вносить вклад», после чего Талия решит «внести вклад»; эта последовательность обеспечит Эмили выигрыш 3 вместо выигрыша 4, который она могла бы получить, указав вариант «не вносить вклад» на первом ходе.
Равновесие обратных рассуждений обеспечивает полное описание всего процесса анализа посредством формулировки оптимальной стратегии для каждого игрока. Мы уже отмечали, что стратегия – это исчерпывающий план действий. Эмили делает первый ход, имея два варианта выбора, а значит, ее стратегия достаточно проста и фактически сводится к одному ходу. Но Нина, которая ходит второй, действует уже в каком-то из двух узлов: в одном – если Эмили выбрала вариант «внести вклад», и в другом – если Эмили предпочла «не вносить вклад». В исчерпывающем плане Нины должны быть указаны действия в каждом из этих случаев. Один такой план, или стратегия, может быть следующим: «Выбрать “внести вклад”, если Эмили выбрала “внести вклад”, и “не вносить вклад”, если Эмили его не вносит». Благодаря анализу методом обратных рассуждений мы знаем, что Нина не выберет эту стратегию, но на данном этапе нам необходимо описать все доступные стратегии, из которых Нина сможет выбирать согласно правилам игры. Мы можем сократить их описание, используя обозначение «В» вместо «внести вклад» и «Н» вместо «не вносить вклад». В результате вышеупомянутую стратегию можно представить так: «В, если Эмили выберет В, а значит, игра перейдет в узел b; Н, если Эмили выберет Н и игра перейдет в узел с», или еще проще: «В в b, Н в c», или даже «ВН», если обстоятельства, при которых выбирается каждое из указанных действий, очевидны или разъяснены ранее. Теперь легко увидеть, что поскольку у Нины по два варианта выбора в каждом из двух узлов, в которых она может действовать, в ее распоряжении находятся четыре плана действий, или стратегии: «В в b, В в c»; «В в b, Н в c»; «Н в b, В в c» и «Н в b, Н в c», или «ВВ», «ВН», «НВ» и «НН». Анализ методом обратных рассуждений, а также стрелки в узлах b и c на рис. 3.6 показывают, что оптимальная стратегия Нины – «НВ».
В случае Талии ситуация усложняется. Когда наступит ее черед, история игры может представлять собой любой из четырех возможных вариантов. Очередь действовать переходит к Талии в одном из четырех узлов дерева: один после выбора Эмили В и Нины В (узел d); второй после В Эмили и Н Нины (узел e); третий после Н Эмили и В Нины (узел f) и четвертый после Н и Эмили, и Нины (узел g). Каждая из стратегий (или исчерпывающих планов действий) Талии должна определять одно из двух действий по каждому из этих четырех сценариев или одно из двух действий в каждом из возможных узлов действия. При наличии четырех узлов, в которых необходимо указать действие, и двух действий, из которых следует выбрать одно в каждом узле, существует 2 × 2 × 2 × 2, или 16, вероятных комбинаций действий. Следовательно, в распоряжении Талии 16 доступных стратегий. Одну из них можно было бы записать так:
«В в d, Н в e, Н в f, В в g», или для краткости «ВННВ»
Здесь мы зафиксировали последовательность четырех сценариев (историй ходов Эмили и Нины) в порядке расположения узлов d, e, f и g. Далее с помощью такой же сокращенной формы записи можно составить полный список всех 16 находящихся в распоряжении Талии стратегий:
ВВВВ, ВВВН, ВВНВ, ВВНН, ВНВВ, ВНВН, ВННВ, ВННН, НВВВ, НВВН, НВНВ, НВНН, ННВВ, ННВН, НННВ, НННН.
Анализ методом обратных рассуждений дерева игры на рис. 3.6, а также стрелки в узлах d, e, f и g показывают, что оптимальная стратегия Талии – НВВН.
Теперь выводы нашего анализа методом обратных рассуждений можно представить в виде описания стратегического выбора, сделанного каждой участницей игры: Эмили выберет Н из двух имеющихся у нее стратегий, Нина – НВ из четырех доступных стратегий, а Талия – НВВН из шестнадцати стратегий. Когда каждая из участниц анализирует следующие ветви и узлы дерева игры, чтобы составить прогноз конечных результатов текущих действий, она вычисляет оптимальные стратегии других участниц игры. Эта конфигурация стратегий (Н в случае Эмили, НВ – Нины и НВВН – Талии) представляет собой равновесие в данной игре, полученное методом обратных рассуждений.
Мы можем объединить оптимальные стратегии участниц игры, чтобы найти фактический путь игры, который приведет к равновесию обратных рассуждений. Эмили начнет с выбора Н. Нина, придерживаясь своей стратегии НВ, выберет в ответ на действие Эмили Н действие В. (Помните: стратегия НВ Нины означает «выбрать Н, если Эмили выбрала В, и В, если Эмили предпочла Н».) Согласно принятой нами договоренности, фактическое действие Талии после Н Эмили и В Нины (из узла f) обозначается третьей буквой в нашем четырехбуквенном описании ее стратегий. Поскольку оптимальная стратегия Талии – НВВН, ее действие по пути игры – В. Таким образом, фактический путь игры состоит из действия Н, выбранного Эмили, и действия В, сделанного Ниной и Талией.
В итоге мы имеем три разные концепции:
1. Список доступных стратегий для каждого игрока, который, особенно для игроков, вступающих в игру на более поздних этапах, может быть очень длинным, поскольку необходимо перечислить их действия в ситуациях, соответствующих всем возможным предыдущим ходам других игроков.
2. Оптимальная стратегия, или исчерпывающий план действий, для каждого игрока. Эта стратегия должна описывать лучший выбор игрока в каждом узле, в котором, согласно правилам игры, игрок делает ход, даже если многие из этих узлов так и не будут достигнуты на фактическом пути игры. По сути, такое описание – это прогноз игроков, сделавших предыдущие ходы, относительно того, что бы произошло, если бы они предприняли другие действия, а значит, оно представляет собой важную часть определения их наилучших действий в предыдущих узлах. Совокупность оптимальных стратегий всех игроков образует равновесие обратных рассуждений.
3. Фактический путь игры в равновесии обратных рассуждений, найденный посредством объединения оптимальных стратегий всех игроков.
4. Преимущества порядкаВ равновесии обратных рассуждений в игре «уличный сад» Эмили получает наилучший исход (выигрыш 4) благодаря возможности сделать первый ход. Решив не вносить вклад в создание сада, Эмили перекладывает бремя ответственности на двух других участниц игры, каждая из которых может получить следующий лучший исход только при условии, что обе выберут вариант «внести вклад». Большинство людей, не имеющих опыта ведения стратегических игр, придерживаются мнения, будто преимущество первого хода должно присутствовать во всех играх. Однако это не так. Во многих играх второй ход более выигрышный. Представьте себе стратегическое взаимодействие между двумя компаниями, продающими аналогичные товары по каталогам, скажем, Land’s End и L.L. Bean. Если бы одна из них выпустила каталог первой, вторая еще до выпуска своего каталога обрела бы шанс узнать, какие цены установила первая компания, и смогла бы предложить на свои товары более низкие цены, получив в результате огромное конкурентное преимущество.
Преимущество первого хода зависит от способности игрока взять на себя обязательство в связи с выгодной позицией и вынудить других игроков приспосабливаться к нему; преимущество второго хода обусловлено гибкостью адаптации игрока, делающего ход вторым, к выбору других игроков. Что важнее в той или иной игре, обязательство или гибкость, определяется ее конкретной конфигурацией стратегий и выигрышей; общего правила здесь нет. На протяжении всей книги мы будем встречать примеры преимуществ обоих типов. Основная мысль (противоречащая общепринятому мнению) состоит в том, что преимущество не всегда получает игрок, который ходит первым. И она настолько важна, что мы сочли необходимым подчеркнуть ее с самого начала.
Когда в игре есть преимущество первого или второго хода, каждый игрок может попытаться манипулировать порядком игры, чтобы обеспечить себе выгодную позицию. Тактические приемы такой манипуляции – это стратегические ходы, которые мы рассмотрим в главе 9.
5. Увеличение количества ходовВ разделе 3 мы говорили о том, что увеличение количества игроков усложняет анализ игр с последовательными ходами. В данном разделе мы рассмотрим еще один тип сложности, возникающий в результате добавления в игру дополнительных ходов. Самый простой способ сделать это в игре с двумя участниками – разрешить им чередовать ходы более одного раза. В итоге дерево игры разрастается таким же образом, как и дерево игры со многими участниками, но последующие ходы делают те же игроки, что и на более ранних этапах игры.
Многие широко распространенные игры, такие как крестики-нолики, шашки и шахматы, и есть стратегические игры с двумя участниками и чередующимися последовательными ходами. Использование дерева игры и анализа методом обратных рассуждений теоретически позволяет их «решить», то есть определить равновесный исход игры методом обратных рассуждений, а также равновесные стратегии, обеспечивающие такой исход. К сожалению, по мере того как игра усложняется, а стратегии становятся все запутаннее, поиск оптимальной стратегии тоже затрудняется. В таких случаях на помощь приходят стандартные компьютерные программы вроде упомянутой в главе 2 Gambit.
А. Крестики-нолики
Начнем с игры в крестики-нолики, самой простой из вышеупомянутых, и рассмотрим ее более легкий вариант, в котором каждый из двух игроков (Х и 0) пытается первым заполнить двумя своими символами любой столбец, ряд или диагональ в игре на поле два на два. У первого игрока четыре возможных действия или позиции, в которых он может поставить крестик. Второй игрок имеет три возможных действия в каждом из четырех узлов принятия решений. Когда первый игрок получает право сделать второй ход, у него есть два варианта действия в каждом из 12 (4 × 3) узлов принятия решений. Как показано на рис. 3.7, даже у этой мини-игры в крестики-нолики очень сложное дерево игры. Хотя на самом деле оно не такое уж сложное, поскольку игра гарантированно закончится, после того как первый игрок сделает второй ход. Тем не менее на этом дереве 24 концевых узла, и их необходимо проанализировать.
.
Рис. 3.7. Сложное дерево простой игры в крестики-нолики на поле два на два
Это дерево служит здесь иллюстрацией того, насколько сложным может быть дерево даже в случае простых (или упрощенных) игр. Как оказалось, применение метода обратных рассуждений к анализу мини-игры в крестики-нолики позволяет быстро найти равновесие. Из такого анализа следует, что любой выбор первого игрока на втором ходе приводит к одному и тому же исходу игры. Здесь нет оптимального действия; любой ход так же хорош, как и остальные. Стало быть, когда второй игрок делает первый ход, он тоже видит, что любой возможный ход даст тот же результат, поэтому может с одинаковым успехом выбрать любой из трех вариантов в каждом из четырех узлов принятия решений. И наконец, то же самое верно и для первого игрока, делающего первый ход: любой вариант выбора равноценен остальным вариантам, а значит, он гарантированно победит в игре.
Хотя у этой версии игры в крестики-нолики весьма занимательное дерево, ее решение не представляет особого интереса. Первый игрок всегда выигрывает, поэтому выбор, сделанный обоими игроками, никак не влияет на конечный результат. Многим из нас больше знакома версия «три на три» игры в крестики-нолики. Для того чтобы проиллюстрировать ее деревом игры, нам пришлось бы показать, что первый игрок имеет девять возможных действий в начальном узле, у второго игрока восемь вариантов действий в каждом из девяти узлов принятия решения. На втором ходе у первого игрока семь возможных действий в каждом из 8 × 9 = 72 узлов, тогда как у второго игрока на втором ходе – шесть возможных действий в каждом из 7 × 8 × 9 = 504 узлов. Эта закономерность продолжается до тех пор, пока дерево не прекратит стремительно разрастаться, поскольку определенные комбинации ходов приводят к победе первого игрока, после чего игра заканчивается. Однако минимум до пятого хода победа невозможна. Для того чтобы нарисовать полное дерево этой игры, понадобится огромный лист бумаги или очень мелкий почерк.
Однако большинство из вас знают, как в худшем случае добиться хотя бы ничьей в игре в крестики-нолики на поле три на три. Так что есть простое решение этой игры, которое можно найти посредством обратных рассуждений, и истинный стратег способен существенно снизить сложность игры в ходе его поисков. Оказывается, как и в версии игры «два на два», многие возможные пути на дереве игры со стратегической точки зрения идентичны. В частности, девять начальных ходов могут быть только трех типов: вы ставите крестик на угловую позицию (четыре возможных варианта), на боковую позицию (также четыре возможных варианта) и на центральную позицию (один вариант). Использование этого метода для упрощения дерева игры поможет снизить уровень сложности задачи и приведет вас к описанию оптимальной равновесной стратегии, полученной методом обратных рассуждений. К примеру, мы могли бы показать, что игрок, который ходит вторым, может гарантированно добиться как минимум ничьей, сделав надлежащий первый ход и постоянно блокируя в дальнейшем попытки первого игрока выставить три символа в ряд[24]24
Если первый игрок ставит первый символ на центральную позицию, второй игрок должен поставить первый символ на угловую позицию. Далее второй игрок может обеспечить ничью, заняв третью позицию в любом ряду, столбце или диагонали, которую пытается заполнить первый игрок. Если первый игрок сначала ставит символ на угловую или боковую позицию, то второй игрок может гарантировать ничью, сперва поставив свой символ в центр, а затем придерживаясь того же метода блокирования. Обратите внимание, что если первый игрок выбирает угловую позицию, второй игрок – центральную позицию, а затем первый игрок выбирает угол, противоположный первоначальному ходу, то второй игрок не должен выбирать оставшиеся углы, чтобы обеспечить хотя бы ничью. Подробное описание такой исчерпывающей условной стратегии в игре крестики-нолики можно найти в онлайн-комиксе на странице http://xkcd.com/832/.
[Закрыть].
Б. Шахматы
Хотя сравнительно простые игры, такие как крестики-нолики, решаемы методом обратных рассуждений, выше мы показали, насколько быстро повышается сложность дерева игры даже в играх с двумя участниками. Поэтому при анализе более сложных игр вроде шахмат находить полное решение становится гораздо труднее.
В шахматах в распоряжении игроков (условно называемых «белые» и «черные») имеются наборы из 16 фигур разной формы, которые передвигаются по шахматной доске восемь на восемь клеток (рис. 3.8) в соответствии с заданными правилами[25]25
Описание правил игры в шахматы и много другой информации о шахматах можно найти в «Википедии».
[Закрыть]. Белые ходят первыми, черные – вторыми, и так далее по очереди. Все ходы видны другому игроку, и ничего не оставлено на волю случая, как в карточных играх, где карты перетасовываются и сдаются. Кроме того, шахматная партия должна заканчиваться за конечное число ходов. Согласно правилам, при троекратном повторении одной и той же позиции в течение игры объявляется ничья. Ввиду наличия конечного количества способов разместить 32 фигуры (или меньше, если некоторые фигуры побиты) на 64 клетках шахматной доски, партия не может продолжаться бесконечно долго без возникновения подобной ситуации. Поэтому в принципе шахматы поддаются полному анализу методом обратных рассуждений.
Рис. 3.8. Шахматная доска
Однако этот анализ так и не проведен. Шахматы не «решены» так, как в свое время крестики-нолики, а причина в том, что, несмотря на простоту правил, шахматы – чрезвычайно сложная игра. Из начальной позиции набора фигур, показанных на рис. 3.8, белые могут сделать любой из 20 ходов[26]26
Белые могут сделать ход любой из восьми пешек либо на одну, либо на две клетки вперед или одним из двух коней (на клетки a3, c3, f3 или h3).
[Закрыть], а черные – ответить любым из 20 ходов. Следовательно, из первого узла исходят 20 ветвей, каждая ведет ко второму узлу, из которого исходят еще 20 ветвей. Всего после двух ходов образуется 400 ветвей, и каждая ведет к узлу, из которого исходят очередные ветви. Общее же количество возможных ходов в шахматах составляет, по примерным оценкам, 10120, то есть единицу со 120 нулями. Суперкомпьютеру, в тысячу раз превышающему ваш ПК по быстродействию и выполняющему один триллион операций в секунду, понадобилось бы более 10100 лет, чтобы проверить все ходы[27]27
Это можно было бы сделать только один раз, поскольку как только игра была бы решена, любой желающий мог бы воспользоваться этим решением и никому не было бы необходимости играть на самом деле. В таком случае все знали бы, выиграют ли белые или смогут ли черные добиться ничьей. Игроки бросили бы монету, чтобы решить, кто играет белыми, а кто черными. После этого игрокам был бы известен исход игры, поэтому они пожали бы друг другу руки и разошлись по домам.
[Закрыть]. Астрономы отводят нам менее 1010 лет до того момента, когда Солнце превратится в красный гигант и поглотит Землю.
Получается, что хотя для игры в шахматы теоретически можно найти всеобъемлющее решение методом обратных рассуждений, ее полное дерево может оказаться слишком сложным для того, чтобы реализовать такое решение на практике. Что делать игроку в данной ситуации? Знакомство с историей попыток запрограммировать компьютер на игру в шахматы поможет нам многое об этом узнать.
Когда стало ясно, что компьютеры способны выполнять сложные вычисления в науке и бизнесе, многие математики и программисты решили, что вскоре компьютерная шахматная программа победит именитых гроссмейстеров. Но это произошло не так быстро, хотя компьютерные технологии развивались стремительными темпами, тогда как человеческое мышление несколько поотстало. В конце концов в декабре 1992 года немецкая компьютерная программа под названием Fritz2 выиграла у чемпиона мира Гарри Каспарова несколько блицпартий. Согласно обычным правилам, каждому игроку предоставляется 2,5 часа на выполнение 40 ходов, и люди дольше удерживали превосходство. Команда специалистов, финансируемая компанией IBM, вложила немало усилий и ресурсов в разработку специализированного компьютера (получившего название Deep Blue) для игры в шахматы и соответствующего программного обеспечения. В феврале 1996 года Deep Blue выступил в роли противника Гарри Каспарова в матче из шести партий и произвел сенсацию, выиграв первую партию, но Каспаров быстро выявил его слабые места, улучшил контрстратегии и мастерски выиграл остальные партии. На протяжении следующих 15 месяцев команда IBM совершенствовала аппаратное и программное обеспечение компьютера, после чего в мае 1997 года модифицированный Deep Blue выиграл у Каспарова очередной матч из шести партий.
Таким образом, развитие компьютерных технологий характеризовалось сочетанием периодов медленного поэтапного улучшения и ряда стремительных рывков, в то время как люди, сохранив определенное превосходство, не смогли перестроиться настолько быстро, чтобы удержать передовые позиции. При ближайшем рассмотрении оказалось, что люди и компьютеры используют абсолютно разные подходы к анализу очень сложного дерева игры в шахматы.
При обдумывании хода в шахматах крайне трудно (для обоих: и людей, и компьютеров) заранее предвидеть исход игры. Но как насчет того, чтобы просчитать часть ходов, скажем 5−10, вперед и проанализировать игру в обратном порядке из этой позиции? Игра необязательно должна закончиться в рамках этого ограниченного периода; иными словами, узлы, которых вы достигнете через 5−10 ходов, не будут концевыми. Однако в соответствии с правилами игры выигрыши указываются только для концевых узлов. Следовательно, необходим некий косвенный способ присвоения правдоподобных выигрышей неконцевым узлам, поскольку вы не можете проанализировать все дерево игры методом обратных рассуждений с самого конца. Правило, согласно которому присваиваются промежуточные выигрыши, называется функцией промежуточной оценки.
В шахматах и люди, и компьютерные программы используют такой частичный упреждающий анализ в сочетании с функцией промежуточной оценки. Классический метод присваивает определенные значения каждой фигуре, а также позиционным и комбинационным преимуществам, которые могут возникнуть в процессе игры. Количественная оценка значений для различных позиций производится на основе опыта игры, накопленного всем шахматным сообществом в ходе прошлых партий, начинавшихся с соответствующих позиций или комбинаций; этот опыт называется знанием. Сумма всех числовых значений, закрепленных за шахматными фигурами и их комбинациями на той или иной позиции, и есть ее промежуточная оценка. Целесообразность хода определяется по оценке позиции, на которую предположительно выйдет игра после точного упреждающего вычисления конкретного количества (например, пяти или шести) ходов.
Дальше всего оценка промежуточных позиций продвинулась в отношении дебютов, то есть первой дюжины ходов игры. Каждый отдельно взятый дебют может привести к любому из огромного множества дальнейших ходов и позиций, однако опыт позволяет игрокам делать вывод о том, какой дебют с определенной степенью вероятности более выгоден для того или иного игрока. Эта информация записана в объемных книгах о шахматных дебютах; все шахматисты высокого класса и компьютерные программы помнят и используют эти знания.
На последних стадиях игры, когда на доске остается всего несколько фигур, сам процесс обратных рассуждений зачастую достаточно прост, чтобы быть выполнимым, и достаточно полон, чтобы дать исчерпывающий ответ. Труднее всего проанализировать миттельшпиль (середину игры), когда позиции развились до того уровня сложности, который не упростится за несколько ходов. Для поиска удачного хода из такой позиции хорошо проработанная функция промежуточной оценки может быть более значимой, чем способность рассчитать игру еще на несколько ходов вперед.
Именно на стадии миттельшпиля на первый план выходит искусство игры в шахматы. У лучших шахматистов развивается интуиция, которая позволяет им распознавать хорошие возможности и избегать скрытых ловушек на уровне, с которым компьютерным программам сложно конкурировать. Программисты обнаружили, что в большинстве случаев компьютеры трудно обучить тем навыкам распознавания образов, которые люди развивают и используют инстинктивно, – например, когда они узнают лица и связывают их с именами. Искусство ведения игры на стадии миттельшпиля в шахматах – это распознавание и оценка комбинаций столь же загадочным способом. Именно в этом состояло самое большое преимущество Каспарова перед Fritz2 или Deep Blue. Это также объясняет, почему компьютерные программы показывают более высокие результаты в игре с людьми в блицпартиях или партиях с ограниченным временем обдумывания ходов: человеку просто не хватает времени, чтобы применить свое искусство ведения игры на стадии миттельшпиля.
Иными словами, лучшие шахматисты обладают филигранным знанием шахмат, основанным на опыте или способности распознавать образы, что предоставляет в их распоряжение более эффективную функцию промежуточной оценки. Компьютеры доминируют в области вычислений методом грубой силы. Таким образом, хотя в настоящее время и люди, и компьютеры используют сочетание упреждающей и промежуточной оценки, они применяют их в разных пропорциях: шахматисты просчитывают наперед не так много ходов, но располагают более развитой функцией промежуточной оценки на основании знаний; компьютеры имеют менее развитые функции оценки, но могут просчитывать наперед гораздо больше ходов благодаря огромной вычислительной мощности.
Правообладателям!
Данное произведение размещено по согласованию с ООО "ЛитРес" (20% исходного текста). Если размещение книги нарушает чьи-либо права, то сообщите об этом.Читателям!
Оплатили, но не знаете что делать дальше?
