Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

Удивительно, но чрезмерно оптимистичное освещение успехов первых шашечных программ имело отрицательный эффект. Оптимизм Сэмюэла, многократно усиленный прессой, привёл к распространению заблуждения о том, что шашки были «решены», или по крайней мере о том, что компьютерные программы бесповоротно превзошли человека в этой игре. Отчасти здесь сыграла роль, по всей видимости, иллюзорная простота шашек — ведь по сравнению с шахматами в них всего два вида фигур, да и перемещаться они могут лишь по чёрным клеткам доски. Многие научные и научно-популярные книги и статьи упорно плодили заблуждения, и даже пари, объявленное Тинсли, не смогло переломить силу многократно растиражированного невежества.

Со времён Paaslow и до 1989 г. в области компьютерных шашек царило затишье [578], а когда в 1992 г. Джонатан Шеффер, встретившись на одной из конференций с членом Совета естественных наук и инженерии Канады (NSERC), основного агентства финансирования научных исследований в стране, поинтересовался, почему прошлогодний запрос на финансирование исследований ИИ с использованием шашек в качестве экспериментального испытательного стенда был отклонён, то получил ответ: «А разве Сэмюэл не решил эту игру ещё тридцать лет назад?»

3.4.3 Дебют программы Chinook Джонатана Шеффера

В 1989 г. в Лондоне под эгидой ICGA состоялась первая Компьютерная олимпиада. Она включала следующие дисциплины: шахматы, шашки, го на доске 9 × 9, го на доске 19 × 19, бридж, нарды, домино, «четыре в ряд», отелло (реверси), рэндзю, скрэббл, го-моку, китайские шахматы и авари. В соревновании по шашкам участвовало шесть программ, и первое место с отрывом в одно очко заняла канадская программа Chinook (по-русски читается как «шинук»), созданная командой под руководством Джонатана Шеффера. Вообще-то, изначально программа называлась The Beast («Зверь»), но перед Олимпиадой название было решено изменить на более нейтральное Chinook в честь юго-западного ветра (фёна) на восточных склонах Скалистых гор в Канаде. Дело в том, что в Великобритании шашки называются draughts, а draught или draft — это среди прочего «сквозняк» или «порыв ветра» (вообще говоря, у слова draft есть 63 значения, если верить словарю Google), поэтому для канадской шашечной программы хорошо подходило название тёплого канадского ветра. Также словом chinook в Канаде называют чавычу — рыбу семейства лососёвых. Норман Трелоар, один из членов команды Chinook, занимавшийся разработкой библиотеки дебютов и оценочной функцией, задавался перед Олимпиадой вопросом: будет ли Chinook играть как ветер или как рыба (рыбой — fish — иногда уничижительно называют слабых игроков)? К счастью для команды, Chinook играл скорее как ветер [579].

К моменту начала работы над 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, показал Шефферу некоторые недостатки его программы.

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

Им владел «ужасный Тинсли» — самый опасный соперник.

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