Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
В середине 1990 г. Шеффер задался вопросом: насколько хорош Тинсли на самом деле? Чемпионы мира по шахматам тоже очень хороши в игре против других людей, но всё же они периодически проигрывают партии другим игрокам, а последующий анализ турнирных партий нередко выявляет ошибки, допущенные в пылу сражения. Союзником чемпиона всегда является его имя: противники оказываются психологически подавлены репутацией чемпиона. Из-за волнения они не верят в то, что чемпион мог допустить просчёт, отказываются от решительных действий, ведущих к победе. Сильной стороной машины, напротив, является её бесстрастность: она ничего не знает о своём оппоненте, свободна от страха, спокойно действует даже в, казалось бы, безнадёжных позициях. В итоге нередко выясняется, что эти позиции в действительности не являются такими уж безнадёжными. Действительно ли партии Тинсли так идеальны, пройдут ли они скрупулёзную проверку машинным интеллектом?
Найти игры Тинсли было легко [580]. Книга «Шашки по-тинслевски» (Checkers the Tinsley Way) содержала около семисот игр Тинсли с 1945 по 1981 г. [581] Конечно, игр за последнее десятилетие не хватало, но Шеффер предположил, что в таком возрасте (а Тинсли в 1981 г. исполнилось 54 года) стиль игры вряд ли мог радикально измениться.
Шеффер взял 732 партии из книги, разделил их между четырьмя компьютерами и запрограммировал Chinook осуществлять анализ позиций из этих партий, при этом игнорировались проигрышные ходы в играх, которые Тинсли проиграл, а также первые десять ходов партии, поскольку выбор дебютов был во многом вопросом индивидуального вкуса. Для каждой позиции Chinook на основе глубокого перебора должен был выбрать лучший ход. Если ход совпадал с решением Тинсли, то Chinook переходил к следующей позиции, если нет — производился перебор для хода, сделанного Тинсли, и оценки обоих ходов сохранялись в файле. Обычно значения оценок были близки. Шеффера и его команду интересовали ситуации, в которых Тинсли совершал ход, по оценке сильно уступающий ходу, предложенному Chinook. Иначе говоря, позиции, в которых программа считала, что Тинсли допустил серьёзный просчёт.
В результате анализа Шефферу удалось найти 17 позиций, в которых ход, предложенный Chinook, по оценке превосходил ход, сделанный в партии Тинсли, хотя бы на 100 единиц, то есть на «стоимость» одной шашки. Однако анализ уже первых из них показал, что в число этих ходов входят неоптимальные выигрывающие ходы. То есть Chinook придумал, как Тинсли мог бы выиграть партии немного быстрее, но конечный результат от этого бы не изменился. Расстроенный Шеффер изменил значение разницы оценок до 50 единиц, но и это радикально не поменяло картину. Удалось найти всего две позиции, в которых Тинсли вроде бы действительно ошибался. Шеффер заставил программу проанализировать эти позиции более глубоко — отведя на каждую из них целую ночь вычислений. В первой позиции ошибка не подтвердилась: позиция, казавшаяся проигранной, оказалась ничейной. Но в последней позиции ночь анализа не изменила оценку программы: она считала, что Тинсли ошибался. Итак, Тинсли был смертным — он был способен допустить ошибки, точнее — одну ошибку.
Впрочем, радость Шеффера продолжалась недолго. Немного позже гроссмейстер Лео Левитт, которому Шеффер показал найденную позицию, продемонстрировал, что, хотя белые на первый взгляд и имели преимущество, у них не было способа его реализовать [582].
Но хотя Шеффер и думал уже о возможности победы над самим Тинсли, вначале Chinook должен был явно продемонстрировать, что превосходит других возможных претендентов на титул.
С 13 по 18 августа 1990 г. в городе Тупело (штат Миссисипи) должен был состояться чемпионат США по шашкам.
Шеффер обратился в Американскую шашечную федерацию с просьбой разрешить его программе участвовать в чемпионате при условии, что он не будет претендовать на призовой фонд в случае победы. Шеффер получил соответствующее разрешение, а также разрешение выступить в качестве «разогрева» на чемпионате штата Миссисипи, который предшествовал национальному и должен был пройти в том же отеле в Тупело двумя днями раньше.
Чемпионат Миссисипи завершился победой Chinook — восемь побед, шесть ничейных партий и ни одного поражения. Впереди был чемпионат США, а почти одновременно с ним, с 15 по 21 августа 1990 г., в Лондоне проводилась II Компьютерная олимпиада. Спортсменам-людям в подобных случаях приходится выбирать, ведь человек не может одновременно находиться в двух местах. Для компьютерной программы это не помеха. Пока Шеффер и Трелоар в качестве операторов Chinook находились на турнире в Тупело, за океаном копия программы участвовала в Компьютерной олимпиаде под управлением другого члена команды — Пола Лю [583].
На Компьютерной олимпиаде в Лондоне у Chinook было всего два противника: Colossus, программа, созданная Мартином Брайантом, и Checker-Mate Эдриана Миллетта и Дерека Олдбери.
Colossus — шашечная программа Брайанта, в создании которой он опирался на опыт в работе с одноимённой шахматной программой, — была сильным противником: незадолго до того, как Chinook победил в Миссисипи, она одержала победу на чемпионате Западной Англии (23–24 июня 1990 г.).
Миллетт и Олдбери, выступавшие на предыдущей, 1989-го, Олимпиаде каждый со своей программой (Sage Draughts и Checker Hustler) и занявшие соответственно второе и первое места с конца турнирной таблицы [584], для выступления в 1990 г. решили объединить свои сильные стороны — высококлассную шашечную экспертизу Олдбери с опытом Миллетта в области программирования. Олдбери приготовил для Checker-Mate продвинутую дебютную библиотеку, заложив в неё ряд ловушек — дебютных вариантов, приводивших игру к позициям, в которых программе противника было бы трудно найти правильный ход в условиях ограниченного времени. В одну из таких ловушек и попал Chinook, однако крышка мышеловки не захлопнулась: вариант в дебютной библиотеке Checker-Mate заканчивался слишком рано — и в ответ на ошибку Chinook его противник не смог ответить правильным ходом. В итоге из-за ошибки в алгоритме распределения времени Checker-Mate просрочил время, и партия завершилась победой Chinook. Казалось бы, угроза миновала, тучи рассеялись и на небе снова засияло солнце. Это действительно было бы так, если бы противниками программы Шеффера на турнире были новички, а не закалённые турнирными соревнованиями ветераны компьютерных шахматных и шашечных баталий. Быстро сообразив, что именно произошло в партии Checker-Mate с Chinook, автор программы Colossus быстро добавил в свою дебютную библиотеку ту же самую ловушку, дополнив дебютную линию ходом, который не удалось найти программе Миллетта и Олдбери, и в партии с Colossus Chinook повторно заглотил наживку, что обернулось для программы Шеффера «баранкой» в турнирной таблице [585]. Пол Лю, в отличие от Шеффера и Трелоара, не обладал должным опытом, чтобы после партии с Checker-Mate принять необходимые контрмеры. Турнирное золото ушло в копилку Брайанта, в то время как команде Chinook пришлось довольствоваться вторым местом [586].
Интересно, что и на чемпионате США в Тупело у Шеффера неожиданно появился компьютерный оппонент. Американская шашечная федерация вполне резонно решила, что если в матче разрешено участвовать Chinook, то на аналогичных условиях в нём могут принять участие и другие программы. Этим не преминул воспользоваться Гил Доджен, автор программы Checkers Experimental [587]. Предыдущая версия его программы — Checkers! — участвовала в Компьютерной олимпиаде 1989-го и заняла второе место, отстав от Chinook всего на одно очко [588]. После олимпиады Шеффер и Доджен обменялись исходными кодами своих программ. Правда, за время, прошедшее с олимпиады, команде Шеффера удалось создать пятифигурные таблицы окончаний, но всё же кто знал, как много пользы автор Checkers! смог извлечь из изучения Chinook за прошедший год. Хотя Доджен и использовал в качестве аппаратной платформы для своей программы компьютер MIPS MI20, в полтора раза более медленный, чем IBM RS/6000, на котором работал Chinook [589], это могло и не быть решающим фактором. Все прекрасно помнили урок [590], который преподал в 1989 г. Ричард Лэнг со своей шахматной программой Mephisto, одержав победу над шестипроцессорным монстром Deep Thought (прародителем Deep Blue) на Северо-Американском чемпионате по шахматам среди компьютерных программ. А ведь Mephisto использовала скромный даже по тем временам процессор Motorola 68030 с тактовой частотой 36 МГц [591]. Кроме того, гроссмейстеры Лео Левитт и Эд Маркузик жили недалеко от Доджена и могли помочь ему с профессиональной экспертизой в области шашек. Словом, Гил Доджен со своей программой был серьёзным противником, которого нельзя было недооценивать.
