Охота на электроовец. Большая книга искусственного интеллекта
Шрифт:
Хотя некоторые авторы и считали, что «люди не могли сравниться с Paaslow» [574] , шашечные эксперты не разделяли столь безудержного энтузиазма, и дело было даже не в том, что Лаудер выиграл этот небольшой матч.
Известный эксперт в области шашек и многократный чемпион Иллинойса Ричард Фортман, комментируя игру Duke против программы Сэмюэла, писал: «Игра в окончании, особенно во второй игре, была ужасной. Должен сказать, что в настоящее время есть несколько тысяч средних игроков-второразрядников [class B players], которые могут без проблем победить любой компьютер». Уильям Гранжан, секретарь Американской шашечной федерации, прокомментировал качество игры так: «Мнение доктора Бирмана, что программа Duke близка к статусу чемпиона мира, — смехотворно».
574
Reilly E. D. (2003). Milestones in Computer Science and Information Technology. Greenwood Press // https://books.google.ru/books?id=JTYPKxug49IC
Команда
575
Gardner M. (2007). The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications. Springer New York // https://books.google.ru/books?id=RHCkV2YaGoEC
576
https://www.in2013dollars.com/us/inflation/1977?endYear=2023&amount=5000
577
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
Удивительно, но чрезмерно оптимистичное освещение успехов первых шашечных программ имело отрицательный эффект. Оптимизм Сэмюэла, многократно усиленный прессой, привёл к распространению заблуждения о том, что шашки были «решены», или по крайней мере о том, что компьютерные программы бесповоротно превзошли человека в этой игре. Отчасти здесь сыграла роль, по всей видимости, иллюзорная простота шашек — ведь по сравнению с шахматами в них всего два вида фигур, да и перемещаться они могут лишь по чёрным клеткам доски. Многие научные и научно-популярные книги и статьи упорно плодили заблуждения, и даже пари, объявленное Тинсли, не смогло переломить силу многократно растиражированного невежества.
Со времён Paaslow и до 1989 г. в области компьютерных шашек царило затишье [578] , а когда в 1992 г. Джонатан Шеффер, встретившись на одной из конференций с членом Совета естественных наук и инженерии Канады (NSERC), основного агентства финансирования научных исследований в стране, поинтересовался, почему прошлогодний запрос на финансирование исследований ИИ с использованием шашек в качестве экспериментального испытательного стенда был отклонён, то получил ответ: «А разве Сэмюэл не решил эту игру ещё тридцать лет назад?»
578
Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ
3.4.3 Дебют программы Chinook Джонатана Шеффера
В 1989 г. в Лондоне под эгидой ICGA состоялась первая Компьютерная олимпиада. Она включала следующие дисциплины: шахматы, шашки, го на доске 9 x 9, го на доске 19 x 19, бридж, нарды, домино, «четыре в ряд», отелло (реверси), рэндзю, скрэббл, го-моку, китайские шахматы и авари. В соревновании по шашкам участвовало шесть программ, и первое место с отрывом в одно очко заняла канадская программа Chinook (по-русски читается как «шинук»), созданная командой под руководством Джонатана Шеффера. Вообще-то, изначально программа называлась The Beast («Зверь»), но перед Олимпиадой название было решено изменить на более нейтральное Chinook в честь юго-западного ветра (фёна) на восточных склонах Скалистых гор в Канаде. Дело в том, что в Великобритании шашки называются draughts, а draught или draft — это среди прочего «сквозняк» или «порыв ветра» (вообще говоря, у слова draft есть 63 значения, если верить словарю Google), поэтому для канадской шашечной программы хорошо подходило название тёплого канадского ветра. Также словом chinook в Канаде называют чавычу — рыбу семейства лососёвых. Норман Трелоар, один из членов команды Chinook, занимавшийся разработкой библиотеки дебютов и оценочной функцией, задавался перед Олимпиадой вопросом: будет ли Chinook играть как ветер или как рыба (рыбой — fish — иногда уничижительно называют слабых
579
* Здесь и далее я буду использовать мужской род для программ Chinook, Fritz и нескольких других. Формально это неправильно, но фразы типа «Chinook играла» или «Fritz выиграла» звучат неестественно и режут мне слух.
К моменту начала работы над Chinook Шеффер уже имел богатый опыт шахматного программирования: его шахматная программа Phoenix, или Sun Phoenix («Феникс», или «Солнечный Феникс»), разделила с тремя другими программами первое место (оказавшись, правда, на четвёртом месте по дополнительным показателям) на V чемпионате мира по шахматам среди компьютерных программ в 1986 г. в Кёльне. Chinook использовал богатый набор техник, разработанных к тому времени создателями шахматных программ.
Во-первых, в программе Шеффера применялись таблицы окончаний, содержавшие готовые ответы для окончаний с четырьмя и менее шашками на доске. Это во многом решало проблему плохой игры шашечных программ в окончаниях. Во-вторых, Chinook также использовал широко применяемую и в наши дни технику под названием «итеративное углубление» (iterative deepening). Её суть заключается в том, что программа сначала перебирает варианты на минимальную глубину, затем увеличивает глубину рассмотрения, выполняет повторный перебор и так далее, пока не закончится отведённое на перебор время. Благодаря использованию хеш-таблицы для хранения результатов анализа уже рассмотренных узлов дерева (так называемая таблица перестановок или перестановок/опровержений — transposition/refutation table), предыдущие шаги перебора не пропадают напрасно. Результаты анализа, полученные на предыдущей итерации, используются для более эффективного упорядочения ходов, что делает альфа-бета-отсечения более эффективными. Кроме того, таблица перестановок эффективно решает собственно проблему перестановок: если разные последовательности ходов приводят к одной и той же позиции, то повторного изучения вариантов не будет.
Заметим, что более качественное упорядочивание ходов при переборе позволяет заменить классические альфа-бета-отсечения на так называемый перебор с единичным окном, то есть перебор, при котором beta = alpha + 1. Идея этого подхода заключается в том, что если перебор для первого рассматриваемого хода в узле дерева перебора вернул оценку, не превышающую верхнюю границу (т. е. значение параметра beta), то, скорее всего, остальные ходы будут не лучше первого и для проверки этой гипотезы для всех последующих ходов в данном узле вместо перебора с полным окном (т. е. с нижней границей, равной alpha, и верхней границей, равной beta) мы будем использовать перебор с единичным окном (с v до v + 1, где v — оценка для первого хода). Если при переборе с таким окном мы для очередного хода получили оценку меньше или равную v, то для данного хода нет необходимости перебора с полным окном, потому что его результат не будет лучше v (а может оказаться только хуже или равным ему), то есть данный ход необходимо отвергнуть. И только если оценка для какого-либо из ходов превысит v, тогда этот ход оказывается лучше первого и мы повторяем для него перебор, но уже с расширенным окном, чтобы узнать его точную оценку. Такой подход при условии хороших методов упорядочивания ходов-кандидатов позволяет добиться дополнительного уменьшения количества перебираемых позиций. Существует несколько алгоритмов, реализующих данный подход, наиболее широко известные — «поиск основного варианта» (Principal Variation Search, PVS) и NegaScout.
Программа Шеффера также содержала набор эвристик для принятия решения об увеличении или уменьшении глубины перебора в отдельных узлах дерева. Весь этот сложный набор алгоритмов позволял при использовании компьютеров, доступных в 1980-е, анализировать варианты на 13–20 (а иногда и более) полуходов в глубину при минутном контроле.
На конец 1989 г. программа Шеффера победила в компьютерной олимпиаде (четыре победы и одна ничья), сыграла три партии по телефону с бывшим чемпионом Канады 1971 и 1972 г. Эдом Томпсоном (две победы Chinook и ничья), из шести партий с одним из сильнейших игроков Великобритании Ричардом Паском пять закончились вничью и одна поражением программы, а в матче из четырёх партий с Дереком Олдбери, в своё время обыгравшим со счётом 4 : 0 программу Сэмюэла, Chinook победил, завершив две партии победой и две ничьей.
Однако в определённый момент позиция Олдбери в одной из проигранных партий была выигрышной, а во второй британский чемпион явно экспериментировал. Олдбери, сам к тому времени увлёкшийся программированием и разработавший собственную шашечную программу Checker Hustler, показал Шефферу некоторые недостатки его программы.
Таким образом, несмотря на очевидный прогресс в области компьютерных шашек, было не до конца понятно, способны ли лучшие шашечные программы соревноваться с лучшими игроками-людьми и заявить претензии на чемпионский титул.