27.05.2005

Битва железных шашистов

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

Генеральной репетицией успеха шахматного суперкомпьютера Deep Blue стала победа шашечной программы Chinook над лучшим среди людей шашистом. Эта история заслуживает упоминания хотя бы потому, что, несмотря на победу программы, лучший шашист планеты так и остался неповерженным.

Лучший матч за 40 лет

Одной из первых и наиболее удачных шашечных программ была Samuel. В то время пресса писала, что она играет в шашки на уровне мастера спорта и фактически "просчитала" шашки. Оба заявления, разумеется, ложны, однако интерес к шашкам со стороны кибернетики несколько поостыл и переключился на шахматы, как на более сложную задачу.

В 1989 году команда канадских ученых из Университета Альберты под руководством доктора Джонатана Шеффера занялась исследованиями в рамках теории игр. Одной из поставленных канадцами целей было, ни много, ни мало, создание шашечной программы, способной нанести поражение чемпиону мира по шашкам, которым на тот момент являлся непревзойденный Марион Тинсли.

Свежеиспеченная программа Chinook победила всех своих соперников на чемпионате по шашкам для компьютерных программ. После подачи петиции в Американскую шашечную федерацию создатели Chinook получили возможность выставить свое детище на чемпионат Америки по шашкам 1990 года. Его победитель получал право участвовать в матче за титул чемпиона мира.

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

Программе предстояло иметь дело с Марионом Тинсли. Его звезда на шашечной арене взошла еще в сороковых годах ХХ столетия. В 1955 году он стал чемпионом мира по шахматам и с тех пор ни разу никому не отдавал свой титул. Звучит невероятно, но за сорок лет Марион Тинсли проиграл всего пять партий.

События, предшествовавшие матчу между Chinook и Тинсли, развивались, тем временем, весьма интересно. В декабре 1990 года Тинсли приезжает на показательный матч против Chinook и выигрывает турнир, одержав одну победу и заключив 13 ничьих. При этом Chinook показала наилучший результат в игре против Тинсли, чем кто-либо еще за все минувшие 40 лет.

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

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

"Битва титанов" состоялась в августе 1992 года в Лондоне. В первых играх Тинсли потерпел два поражения, что, однако, не помешало ему выиграть всю серию, одержав в ней четыре победы при 33 ничьих. Победы, одержанные Chinook, были шестым и седьмым поражениями Тинсли за 42 года. Казалось бы, для Тинсли прозвучал тревожный звоночек, однако это не помешало ему с удовольствием согласиться на проведение матча-реванша, который был назначен на август 1994 года.

Как компьютер играет в шашки

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

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

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

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

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

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

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

Подготовка к матчу-реваншу

Через несколько недель после поражения создатели Chinook начали подготовку к предстоящему реваншу. Во-первых, была модернизирована аппаратная составляющая: к 1994 году Chinook "переехал" на рабочую станцию Silicon Graphics Challenge, оснащенную 16 процессорами частотой 150 МГц и 1 Гб оперативной памяти. Такая модернизация уже сама по себе гарантировала углубление анализа, как минимум, на два полухода.

Был модернизирован алгоритм альфа-бета-поиска. Ранее считалось, что глубина дерева поиска, которое строит программа, прямо пропорциональна игровой эффективности программы, то есть, если играют две программы, первая из которых просматривает игру на четыре полухода вперед, а вторая - на три, то прогнозируемый счет в матче из 20 партий будет 16,5 : 3,5. Такой же счет ожидается в матче, в котором встретятся программы, строящие дерево поиска на глубину в восемь и семь полуходов. Однако оказалось, что подобное соотношение справедливо лишь до тех пор, пока глубина поиска не достигает 17-19 полуходов. Дальнейшее наращивание глубины поиска уже не дает решающего преимущества. Иными словами, программы, просчитывающие все варианты на 21 и 20 полуходов вперед, будут играть почти одинаково.

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

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

База эндшпилей

За два года была значительно расширена база окончаний, которая представляет собой набор позиций с малым числом шашек и информацией о том, кто в какой позиции выигрывает (или о том, что позиция ничейная). Если в процессе игры программе удастся свести игру к одной из таких известных ей выигрышных позиций, это даст ей преимущество. В 1992 году в базе эндшпилей числилось 40 миллиардов позиций, которые в сжатом виде занимали около 2 Гб. Среди них были все возможные позиции из семи и менее шашек и часть позиций из восьми шашек. К 1994 году в базе насчитывалось уже 148 миллиардов позиций, среди которых были все позиции с восемью шашками.

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

Дебютная база

За последние 125 лет накопилось огромное множество литературы, освещающей шашечные дебюты. Все шашисты изучают эту литературу и знают как хорошие, так и плохие способы начала игры. Анализ матчей 1992 года показал, что три из четырех партий были сданы Chinook уже в завязке. Поэтому в дебютную базу занесли 6000 наиболее известных дебютов и проигрышных ходов, которые дают противнику тактическое преимущество.

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

Однако достаточно ли этого, чтобы победить Мариона Тинсли? Создатели программы задумали несколько психологических трюков, чтобы обмануть Тинсли и заставить его понервничать в ожидании игры.

Был сыгран показательный матч Chinook против Дерека Олдбери, ставшего чемпионом мира в 1991 году, когда Марион Тинсли добровольно сложил с себя титул. Матч проходил в закрытой обстановке, а итоговый счет по партиям, несмотря на все старания, в том числе журналистов, не был обнародован. Известен лишь конечный результат - общая победа Chinook. Вничью завершился матч с Доном Лафферти - еще одним выдающимся шашистом. Затем на прошедшем в Далласе Чемпионате южных штатов по шашкам Тинсли и Chinook оба заняли первое место - это был первый случай за 40 лет, когда кто-то умудрился хотя бы "не проиграть" Тинсли в общем зачете.

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

Реванш

15 Августа 1994 года наступило-таки время долгожданного матча-реванша. Значительно усовершенствованная Chinook (что именно было сделано, тщательно скрывалось разработчиками), работающая на мощной станции, предоставленной компанией Silicon Graphics, была готова помериться силами с Марионом Тинсли.

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

17 августа, за минуту до начала седьмой игры Марион Тинсли пожаловался на плохое самочувствие из-за бессонно проведенной ночи и изъявил желание видеть врача. Игра была отменено, и Тинсли провел остаток дня на обследовании в больнице. Ничего угрожающего врачи не заметили, и было принято соглашение продолжить матч на следующий день. Однако утром Тинсли неожиданно отказался продолжать турнир, ссылаясь на проблемы со здоровьем. Все попытки переубедить его не увенчались успехом. В пятницу Марион Тинсли лег в клинику на стационарное обследование, и в следующий вторник ему поставили диагноз - рак.

Согласно правилам, Chinook одержала техническую победу и получила титул Чемпиона мира по версии "Человек против машины". Однако такой исход не устраивал авторов программы, и, поскольку для проведения матча все было готово, организаторы предложили Дону Лафферти оспорить обретенный программой титул. Турнир завершился вничью - оба соперника одержали по победе и сыграли 18 ничейных партий. Chinook сохранила титул. В 1995 году был проведен матч-реванш с Лафферти, окончательным победителем из которого вышла Chinook. Лафферти проиграл одну игру, не одержав ни одной победы и заключив 31 одну ничью.

Заключение

В январе 1995 года Марион Тинсли заявил, что чувствует себя лучше и готов побороться с Chinook, чтобы вернуть титул. Однако этому не суждено было случиться - 3 апреля 1995 года Марион Тинсли умер.

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

Не секрет, что своим успехом Chinook во многом обязана именно Тинсли. Достаточно ему было в свое время сказать "нет", и проект бы умер еще в 1990 году из-за банальной нехватки человеческих противников. Только благодаря поддержке Тинсли Chinook получила право участвовать во многих турнирах и меряться силой с сильнейшими игроками планеты. Именно Марионом Тинсли был создан прецедент, которым впоследствии воспользовались IBM и разработчики шахматной программы Deep Blue.

Самое интересное, что и Тинсли, и создатели Сhinook добились своего, но по-своему. Марион Тинсли ушел из жизни непобежденным. Chinook же стала, формально и фактически, сильнейшим игроком планеты, хотя вопрос о том, достаточной ли мощью обладала Chinook в 1994 году, чтобы победить Тинсли, так и не получил ответа.

Chinook продолжает оставаться самым сильным шашистом планеты. Не верите? Тогда можете сами попытать счастья, схлестнувшись с Chinook посредством интернета.

Источники:

1. computerra.ru