Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
Первая версия программы демонстрировала неплохой уровень игры, однако испытывала трудности в момент перехода игры из одной стадии в другую (например, из миттельшпиля [765] в эндшпиль [766]). Это привело Берлинера к выводу, что слабость HiTech заключалась в недостаточной гладкости оценочной функции. Например, в миттельшпиле плохо защищённый король в центре доски — существенная слабость позиции, в то время как в эндшпиле централизованный король обычно является преимуществом. Но где проходит граница между миттельшпилем и эндшпилем? Программа, играющая за сторону, король которой хорошо защищён, в отличие от короля противника, будет стараться максимально оттянуть размен фигур, формально определяющий переход в эндшпиль, и тем самым может критически ухудшить свою позицию. Это было похоже на уже упоминавшийся нами «эффект горизонта» (этот термин, кстати говоря, ввёл Берлинер).
Берлинер уже применял идею повышения гладкости оценочной функции при создании программы для другой игры — нардов. Коэффициент ветвления игрового дерева в нардах существенно выше, чем в шахматах: в каждом из его узлов существует порядка восьми сотен альтернатив [767], причём многие из них равнозначны, так как связаны с различными равновероятными вариантами выпадения игральных костей. При таком обилии вариантов их перебор не может заметно улучшить качество выбора ходов программой, поэтому наличие эффективной оценочной функции является одним из ключевых факторов успеха. Программа для игры в нарды, созданная Берлинером в конце 1970-х, предназначалась для компьютера DEC PDP-10 и получила название BKG. Ранние версии BKG (вплоть до 8.0) играли в целом довольно неплохо, но всё же не могли соперничать с сильнейшими игроками-людьми. В очередной версии Берлинер решил применить новый подход, использующий нечёткую логику для определения фаз игры. Этот подход получил название SNAC (Smoothness, Nonlinearity, and Application Coefficients — «Гладкость, нелинейность и коэффициенты применения»). Использование этого подхода усилило программу в достаточной мере, чтобы Берлинер смог бросить перчатку действующему чемпиону мира по нардам Луиджи Вилле.
В состоявшемся в 1979 г. матче BKG 9.8 выиграла у Виллы со счётом 7 : 1, став первой компьютерной программой, победившей чемпиона мира в какой-либо игре. Впрочем, Берлинер позже утверждал, что победа была в значительной степени обусловлена случаем, поскольку машине больше везло с выпадениями костей. По крайней мере, более поздний анализ показал, что игра Виллы была практически безупречной, в то время как программа в ряде случаев допускала ошибки (которыми Вилле не посчастливилось воспользоваться) [768].
В середине 1980-х Берлинер пребывал в расцвете своего творческого периода. В конце 1985 г. его программа HiTech заняла первое место на Шестнадцатом Северо-Американском чемпионате по шахматам среди компьютерных программ, в 1986 г. победила со счётом 2 : 0 международного гроссмейстера по шахматам среди женщин Яну Майлс, а двумя годами позже одержала победу в товарищеском матче со счётом 3,5 : 0,5 над 74-летним гроссмейстером Арнольдом Денкером.
Так какие проблемы могли возникнуть у всемирно известного специалиста с простым тайваньским аспирантом?..
В начале 1985 г. профессор Кунг, куратор (faculty advisor) Фэнсюна Сюя, попросил юношу помочь Берлинеру с одной из технических проблем. Обсуждаемое решение не нравилось ни Берлинеру, ни самому Сюю, который после некоторых раздумий пришёл к выводу, что корень проблемы кроется в самом подходе Берлинера. Фэнсюн предложил радикально новую конструкцию, основанную отчасти на идеях конкурентов мэтра, однако последний отверг подобную новацию. В ответ Фэнсюн Сюй в недипломатичной форме раскритиковал подход Берлинера и заявил, что утратил интерес к проекту. Мудрый Кунг постарался вразумить юношу, объяснив, что ему следовало бы проявить побольше такта. С учётом предшествующих проступков академическая карьера Фэнсюна Сюя была под угрозой, и Кунг настоял на том, чтобы Сюй подготовил детальное обоснование своей идеи в виде технического отчёта и устроил по нему презентацию. Так Фэнсюн Сюй очутился в дивном новом мире компьютерных шахмат [769].
3.5.8 Появление и развитие проекта Фэнсюна Сюя
Несмотря на исключительный авторитет Берлинера в области компьютерных шахмат, Фэнсюн Сюй осмелился вступить в спор с мэтром, и с этого момента в Университете Карнеги — Меллона появился второй шахматный проект — программа, получившая название ChipTest. Вместе с Фэнсюном над проектом работали Томас Анантараман и Мюррей Кэмпбелл. Основой ChipTest стал аппаратный генератор ходов — микросхема, разработанная Фэнсюном на базе СБИС-технологии (сверхбольшие интегральные схемы, Very-large-scale integration, VLSI). В отличие от HiTech, в котором за генерацию легальных ходов отвечали 64 микросхемы (по одной на каждое поле шахматной доски), Фэнсюну удалось запихнуть эту функцию в один CMOS-чип (Complementary metal-oxide-semiconductor, комплементарная структура металл — оксид — полупроводник), благодаря чему шахматная программа, выполнявшаяся на рабочей станции Sun-3/160, могла просматривать около 30 000 позиций в секунду [770]. Персональные компьютеры смогли достичь подобных скоростей лишь во второй половине 1990-х гг.
Публичный дебют ChipTest на XVII Северо-Американском чемпионате по шахматам среди компьютерных программ в 1986 г. оказался довольно скромным — 2,5 очка из 5 и 11-е место среди 16 участников [771]. Но Фэнсюн Сюй и его коллеги не собирались сдаваться. В августе 1987 г. после ряда доработок ChipTest был переименован в ChipTest-M (M означало «микрокод»). Новая версия не только содержала исправление ошибок, найденных в ChipTest, но и была в десять раз быстрее, просматривая 400 000 позиций в секунду на рабочей станции Sun-4. Заслуженной наградой для команды стала победа в Северо-Американском чемпионате по шахматам среди компьютерных программ 1987 г. со впечатляющим результатом — четыре очка из четырёх возможных.
Опыты с ChipTest открыли множество новых возможностей. Взвесив все pro et contra, Фэнсюн Сюй и коллеги приняли решение о разработке новой машины. Она получила название Deep Thought (произносится близко к «Дип Сот», переводится как «Великий думатель» или «Глубокомысленный») — в честь одноимённого компьютера из фантастического романа Дугласа Адамса «Путеводитель хитч-хайкера по Галактике». Первая версия Deep Thought — 0.01 — была готова в мае 1988 г., а версия 0.02 — в ноябре того же года. Новая версия имела два настраиваемых шахматных процессора на базе СБИС, аппаратную оценочную функцию, реализованную на основе FPGA-чипа (Field-Programmable Gate Array, программируемая пользователем вентильная матрица), и была способна просматривать 720 000 ходов в секунду. Именно эта версия в 1989 г. выиграла чемпионат мира по шахматам среди компьютерных программ, набрав пять очков из пяти (обогнав на полтора очка HiTech, разделившую 3−5‑е места) [772], [773].
Хотя за Deep Thought и закрепилась репутация машины, побеждающей благодаря «грубой силе», её алгоритмы вовсе не были примитивными. Более того, одна из немногих заметных алгоритмических инноваций в компьютерных шахматах, появившихся в 1980-е, — метод сингулярного поиска (singular search) — была изобретена именно командой Сюя. Идея заключалась в том, чтобы увеличивать глубину анализа для ходов, не имеющих сравнимой по оценке альтернативы. Благодаря этому методу, использующемуся и по сей день, машины способны более эффективно находить сложные тактические комбинации. Например, в одной из турнирных партий 1988 г. Deep Thought нашёл за доской форсированный мат в 19 ходов (что требовало нахождения варианта глубиной в 37 полуходов).
