Охота на электроовец. Большая книга искусственного интеллекта
Шрифт:
Им владел «ужасный Тинсли» — самый опасный соперник.
Американский математик и шашист Марион Тинсли был сильнейшим игроком мира в английские шашки на протяжении тридцати лет. Тинсли ни разу в жизни не проигрывал матч за первенство мира и с 1958 г. проиграл в официальных турнирах всего три партии.
В середине 1990 г. Шеффер задался вопросом: насколько хорош Тинсли на самом деле? Чемпионы мира по шахматам тоже очень хороши в игре против других людей, но всё же они периодически проигрывают партии другим игрокам, а последующий анализ турнирных партий нередко выявляет ошибки, допущенные в пылу сражения. Союзником чемпиона всегда является его имя: противники оказываются психологически подавлены репутацией чемпиона. Из-за волнения они не верят в то, что чемпион мог допустить просчёт, отказываются от решительных действий, ведущих к победе. Сильной стороной машины, напротив, является её бесстрастность: она ничего не знает о своём оппоненте, свободна от страха, спокойно действует даже в, казалось бы, безнадёжных позициях. В итоге нередко выясняется, что эти позиции в действительности не являются такими уж безнадёжными. Действительно ли партии Тинсли так идеальны, пройдут ли они скрупулёзную проверку машинным интеллектом?
Найти игры Тинсли было легко [580] . Книга «Шашки по-тинслевски» (Checkers the Tinsley Way) содержала около семисот игр Тинсли с 1945 по 1981 г. [581] Конечно, игр за последнее десятилетие не
Шеффер взял 732 партии из книги, разделил их между четырьмя компьютерами и запрограммировал Chinook осуществлять анализ позиций из этих партий, при этом игнорировались проигрышные ходы в играх, которые Тинсли проиграл, а также первые десять ходов партии, поскольку выбор дебютов был во многом вопросом индивидуального вкуса. Для каждой позиции Chinook на основе глубокого перебора должен был выбрать лучший ход. Если ход совпадал с решением Тинсли, то Chinook переходил к следующей позиции, если нет — производился перебор для хода, сделанного Тинсли, и оценки обоих ходов сохранялись в файле. Обычно значения оценок были близки. Шеффера и его команду интересовали ситуации, в которых Тинсли совершал ход, по оценке сильно уступающий ходу, предложенному Chinook. Иначе говоря, позиции, в которых программа считала, что Тинсли допустил серьёзный просчёт.
580
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
581
Shuffett R. L. (1982). Checkers, the Tinsley Way: Featuring the Checker Games of the World’s Greatest Player, Dr. Marion F. Tinsley. R.L. Shuffett // https://books.google.ru/books?id=LHOxHAAACAAJ
В результате анализа Шефферу удалось найти 17 позиций, в которых ход, предложенный Chinook, по оценке превосходил ход, сделанный в партии Тинсли, хотя бы на 100 единиц, то есть на «стоимость» одной шашки. Однако анализ уже первых из них показал, что в число этих ходов входят неоптимальные выигрывающие ходы. То есть Chinook придумал, как Тинсли мог бы выиграть партии немного быстрее, но конечный результат от этого бы не изменился. Расстроенный Шеффер изменил значение разницы оценок до 50 единиц, но и это радикально не поменяло картину. Удалось найти всего две позиции, в которых Тинсли вроде бы действительно ошибался. Шеффер заставил программу проанализировать эти позиции более глубоко — отведя на каждую из них целую ночь вычислений. В первой позиции ошибка не подтвердилась: позиция, казавшаяся проигранной, оказалась ничейной. Но в последней позиции ночь анализа не изменила оценку программы: она считала, что Тинсли ошибался. Итак, Тинсли был смертным — он был способен допустить ошибки, точнее — одну ошибку.
Впрочем, радость Шеффера продолжалась недолго. Немного позже гроссмейстер Лео Левитт, которому Шеффер показал найденную позицию, продемонстрировал, что, хотя белые на первый взгляд и имели преимущество, у них не было способа его реализовать [582] .
Но хотя Шеффер и думал уже о возможности победы над самим Тинсли, вначале Chinook должен был явно продемонстрировать, что превосходит других возможных претендентов на титул.
С 13 по 18 августа 1990 г. в городе Тупело (штат Миссисипи) должен был состояться чемпионат США по шашкам.
582
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
Шеффер обратился в Американскую шашечную федерацию с просьбой разрешить его программе участвовать в чемпионате при условии, что он не будет претендовать на призовой фонд в случае победы. Шеффер получил соответствующее разрешение, а также разрешение выступить в качестве «разогрева» на чемпионате штата Миссисипи, который предшествовал национальному и должен был пройти в том же отеле в Тупело двумя днями раньше.
Чемпионат Миссисипи завершился победой Chinook — восемь побед, шесть ничейных партий и ни одного поражения. Впереди был чемпионат США, а почти одновременно с ним, с 15 по 21 августа 1990 г., в Лондоне проводилась II Компьютерная олимпиада. Спортсменам-людям в подобных случаях приходится выбирать, ведь человек не может одновременно находиться в двух местах. Для компьютерной программы это не помеха. Пока Шеффер и Трелоар в качестве операторов Chinook находились на турнире в Тупело, за океаном копия программы участвовала в Компьютерной олимпиаде под управлением другого члена команды — Пола Лю [583] .
583
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
На Компьютерной олимпиаде в Лондоне у 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] .
584
1st Computer Olympiad, Checkers / ICGA Tournaments. Tournaments between computer programs: chess, draughts, checkers, Go, backgammon, and more // https://www.game-ai-forum.org/icga-tournaments/tournament.php?id=126
585
Millett A. (1994). Derek Oldbury: A Eulogy / Journal of the International Computer Chess Association, 17, Vol. 3, pp. 174–175 // https://content.iospress.com/download/icga-journal/icg17-3-14?id=icga-journal%2Ficg17-3-14
586
2nd Computer Olympiad, Checkers / ICGA Tournaments. Tournaments between computer programs: chess, draughts, checkers, Go, backgammon, and more // https://www.game-ai-forum.org/icga-tournaments/tournament.php?id=136
Интересно,
587
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
588
1st Computer Olympiad, Checkers / ICGA Tournaments. Tournaments between computer programs: chess, draughts, checkers, Go, backgammon, and more // https://www.game-ai-forum.org/icga-tournaments/tournament.php?id=126
589
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
590
Mephisto (Computer) vs Deep Thought (Computer). 20th NACCC (1989), Reno, NV USA, rd 5, Nov-15. Queen's Gambit Accepted: Janowski-Larsen Variation (D25). 1-0 / chessgames.com: online chess database and community // http://www.chessgames.com/perl/chessgame?gid=1472135
591
Mephisto Portorose / Chess Programming Wiki // https://www.chessprogramming.org/Mephisto_Portorose
Но вернёмся к чемпионату США в Тупело. Он стал серьёзным испытанием для Chinook, которое программа успешно преодолела, — не проиграв ни одной партии, Chinook занял второе место, уступив лишь действующему чемпиону мира Мариону Тинсли. Программа Checkers Experimental Гила Доджена заняла восьмое место [592] .
Напряжение в определённые моменты турнира было очень велико. Вот как описывает Шеффер одну из партий — против гроссмейстера, будущего чемпиона мира Рональда Кинга:
592
1990 3-Move Nationals Location: Tupelo, Mississippi / The American Checker Federation // https://www.usacheckers.com/nats1990.php
Как обычно, я спокойно сидел за доской, читая книгу, время от времени поглядывая на экран компьютера. С покерфейсом, как обычно, — я старался не выдавать волнение, которое ощущал. Но поскольку мы выигрывали, мне было трудно сосредоточиться на книге, и я стал чаще поглядывать на экран. Кинг был сосредоточен, лениво барабаня пальцами по столу, не подавая никаких признаков того, понял ли он, что проигрывал, или нет. Я прочитал страницу и снова поднял глаза. Он по-прежнему был сосредоточен и всё ещё барабанил пальцами. На этот раз пальцы, казалось, переместились на доску. Ещё одной страницей позже я увидел его пальцы, танцующие вперёд-назад над шашкой Chinook. Я притворился, что читаю, но подглядывал за ним уголком глаза. Я с недоверием наблюдал, как эти пальцы медленно толкают шашку к краю доски и наконец — через край. Постепенно шашка была скинута в кучу шашек, ранее снятых с доски. В этот момент я вежливо протянул руку, поднял шашку и поставил её обратно на доску. Он не выказал никакой реакции. Неужели он действительно думал, что компьютер «забудет» о шашке?
По возвращении с соревнований Шеффер попытался связаться с Артуром Сэмюэлом. Он был уверен, что тот будет рад услышать об успехе Chinook, воплощении в реальность своей сорокалетней мечты. Но в ответ получил печальное известие: профессор Артур Сэмюэл умер 29 июля 1990 г. от осложнений, вызванных болезнью Паркинсона [593] .
Артур Сэмюэл оставил в истории компьютерных технологий значительный след, не ограничивающийся одними только компьютерными шашками. Например, он, совместно с Дональдом Кнутом, работал над популярной в научной среде системой компьютерной вёрстки TeX, внеся в её создание весьма существенный вклад, несмотря на то что в те годы ему уже перевалило за 80 лет [594] . Своими смелыми попытками решить задачу создания шашечного ИИ в условиях крайне ограниченных аппаратных ресурсов 1950–1970-х гг. Сэмюэл вдохновил многих молодых исследователей, и, хотя его работы и вызвали некоторое головокружение от успехов, даже это стало в конечном счёте полезным уроком для специалистов.
593
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
594
Knuth D. (1990) Arthur Lee Samuel, 1901–1990 / TUGboat, Volume 11, No. 4 // https://tug.org/TUGboat/tb11-4/tb30knut-samuel.pdf