Главная » Игры, История » История развития шахматных программ

0

Когда же в первый раз машина заиграла в шахматы? На этот вопрос трудно ответить, наверное, в 1769 году. Венгерский инженер барон Вольфганг фон Компелен создал машину, способную играть в шахматы (рис. 1.1). Она была предназначена для развлечения королевы Марии-Терезии. Машина, дейст­вительно, неплохо играла — внутри ее сидел сильный шахматист, который и делал ходы. История примечательная и, в некоторой степени, актуальна и в наши дни. Что программист вложит в машину, то она и играет. Гарри Кас­паров, например, понимает этот тезис буквально. Он утверждает, что в его втором, решающем матче с DeepBlue (первый он выиграл), начиная со вто­рой партии, в игру машины вмешивался человек и компенсировал неспо­собность машины понимать позиционную игру. Оставим этот вопрос на совести корпорации IBM и Гарри Каспарова. Я лично нисколько не сомне­ваюсь, что Каспаров может выиграть еще один матч с DeepBlue (если этот матч возможен), если, конечно, ему повезет.

Рис. 1.1. Вольфганг фон Компелен и "играющий турка"

В 1951 году Алан Тьюринг (рис. 1.2) написал алгоритм, при помощи кото­рого машина могла бы играть в шахматы. Только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — "бумажная маши­на Тьюринга". Автору требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где "бумажная машина" Тьюринга проиграла одному из его коллег.

Рис. 1.3. Гарри Каспаров в решающем матче с DeepBlue

Оценочная функция DeepBlue не использует ни баз данных, известных из истории вариантов (кроме баз данных эндшпилей), ни генетических алго­ритмов, ни нейронных сетей. Вместо этого, DeepBlue оценивает аппаратно приблизительно 6 тыс. специфических для шахмат показателей. Как произ­водилась настройка этого множества показателей? В основном, вручную. Гроссмейстер Джон Бенджамен играл с машиной, пока не обнаруживал, что она неверно оценивает ту или иную позицию. После этого весь коллектив обсуждал проблему и изменял некоторые коэффициенты в оценочной функции. За большие деньги можно заниматься и не таким делом!

Немного об архитектуре DeepBlue. Основу машины представляет собой сер­вер RS6000SP. В сервере имеется 32 процессора, один объявлен главным. К каждому процессору подключено до 16 специализированных шахматных чипов — итого 512 на всю машину. Первые 4 полухода перебираются глав­ным процессором. После этого он передает работу остальным 31, и они пе­ребирают еще 4 полухода. Программа написана на обычном языке С, и ис­пользует алгоритм NegaScout. Предусмотрены выборочные продления неко­торых вариантов, так что 4 полухода могут значительно растянуться. Некоторые критерии для продлений в DeepBlue:

? если значение оценочной функции для данного хода значительно выше, чем для остальных;

?    по угрозе;

?    по влиянию;

?    проходные пешки;

?    некоторые варианты, выходящие за границы alpha-beta (видимо, это так называемая сингулярная эвристика продлений, или ожидание второй от­сечки за beta).

Система этих продлений описана несколько туманно. Такое впечатление, что продлевается все мыслимое и немыслимое. После основных процессо­ров работу перехватывают специализированные шахматные чипы. В них используются разработанные Кеном Томпсоном аппаратные средства для генерации перемещений, и осуществляется их сортировка. Аппаратно реа­лизован детектор шахов (он работает один такт), контроль X-rays, вилок, перегрузок фигур и пр. Коэффициенты оценочной функции загружаются с диска, что дает возможность вести их настройку. Весь комплекс обрабаты­вает миллиард или более позиций в секунду.

Но вернемся к шахматным программам. Ричард Лэнг, пишущий исключи­тельно на ассемблере (включая графическую часть!), сделал очень сильную программу выборочного поиска Genius. Любителям шахмат эта программа известна по шахматным компьютерам "Мефисто" с мощным специализиро­ванным процессором, в память которых зашит Genius. После проигрыша Каспарова в матче из двух партий (блиц) в 1995 году большинство ведущих гроссмейстеров потребовало запретить участие компьютеров в турнирах лю­дей. Genius и сегодня участвует в мировых компьютерных первенствах и стабильно держит 5—6 место. Из особенностей Genius известно, что он просматривает шахи (особенно если у противника есть единственный ответ) на очень большую глубину.

Нужно отметить Hiarcs Марка Униаке, играющего в сильные позиционные шахматы. Hiarcs долгое время был мировым чемпионом и сегодня входит в тройку лучших программ.

Из отечественных программ нужно отметить "Каиссу" (Битман, Арлазоров, Адельсон-Вельский). Это была революционная для своего времени про­грамма (1970-е годы). Она осуществляла с помощью итеративных углубле­ний перебор на 7 полуходов плюс довольно сложные форсированные вари­анты. Использовались фильтры ходов. На обдумывание одного хода уходило примерно полтора часа. В матче с американцами программа выиграла бук­вально в самом начале партии, найдя очень глубоко форсированный мат. Американцы не могли поверить, что программа могла считать так глубоко, но им показали, что вся комбинация состоит из форсированных ходов: взя­тий и шахов. К сожалению, развития эта победа не получила, и самые сильные программы стали появляться за рубежом. Исключение составляет "Мираж" (1992, 1998, Рыбинкин-Шпеер). Он по сей день остается чемпио­ном России. Чемпионаты, правда, уже не проводятся. Это очень интересная программа выборочного поиска (подробностей я, к сожалению, не знаю). Известно, что "Мираж" считает не все, но достаточно глубоко. Он участво­вал в мировых первенствах, но первого места (как и последнего) не зани­мал. Играет он очень интересно, но стабильно сильную игру не показывает. Известны его разгромные победы над Fritz и Hiarcs. В настоящее время Сергей Марков, автор SmarThink, утверждает, что его программа играет сильнее, чем "Мираж". Я лично нисколько не сомневаюсь, что некоторые варианты она просчитывает лучше, но надо еще доказать, что она стабильно сильнее играет. "Мираж" все-таки очень удачная программа.

Из развития шахматных алгоритмов хочется отметить появление эвристики пустого хода (NullMove). Идея состоит в том, что в большинстве случаев, если мы пропускаем ход (передаем очередь хода противнику и перебираем на меньшую глубину, на два или более полухода), то теряем, а не приобре­таем. Если после такого пропуска наша оценка все еще больше beta, то пе­ребор можно прервать — это неинтересная часть дерева игры. Точное время появления этой эвристики неизвестно. В 1986 году на мировом первенстве в Германии Дон Бил участвовал с программой, которая использовала технику недействительного перемещения в его статическом поиске. В течение тур­нира Франц Морш заинтересовался этой идеей и спустя несколько лет осу­ществил ее в программе Fritz. Ускорение получалось очень значительное, а результат очень точным. С середины 1990-х годов недействительное пере­мещение стало использоваться практически во всех шахматных программах, (правда, подход к его применению очень различный).

Следующее усовершенствование было сделано Эрнст Хайнц в его програм­ме DarkThough и называлось Futility pruning и Razoring. Это выборочное отсечение определенных пограничных ветвей дерева перебора, без их пред­варительного исследования. Отсекаемая позиция должна удовлетворять оп­ределенным условиям. Данные методы не вносят практически никакой по­грешности, но есть люди, не признающие их. Они никак не могут понять, что считать надо очень глубоко, а рост дерева выражается экспоненциаль­ной зависимостью и "засадит" любой мыслимый и немыслимый процессор.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии