"Кентавр"

Эта страница поясвящена одной из наиболее успешных отечественных шахматных программ - "Кентавру" . О своей программе рассказывает автор - доктор физико-математических наук Виктор Викторович Вихрев.

.

В настоящее время во всем мире ведутся большие работы по созданию искусственного интеллекта. Эта проблема тесно связана с принятием решения в таких сложных условиях как разрешение конфликта, ведение военных действий, тактика "научных исследований, лечение сложных заболеваний, ведение экономической политики. Однако в этих областях трудно проверить правильность того или иного разрабатываемого подхода, так как не всегда можно его внедрить, результат применения обычно сказывается через достаточно большое время к не всегда его можно интерпретировать однозначно.

Другое дело шахматы. На примере шахматной игры отлаживаются и проверяются алгоритмы решения многих сложных задач. Результат- применения конкретного алгоритма сказывается мгновение и имеется довольно объективный показатель - качество и результат сыгранных партий - Именно поэтому шахматной программирование стало в настоящее время обширным. полигоном отработки новых подходов в области искусственного интеллекта.

В 1971 г. в Институте атомной энергии мной была начата разработка шахматной программы, которая впоследствии стала "Кентавр". Программа была вначале написана. НА языке АЛГОЛ. В конце 1971 г. была сыграна первая партия на ЭВМ БЭСМ-6. В данный момент программа написана на языке Паскаль и работает на персональных компьютерах типа IВМ РС.

Одной из причин разработка шахматной программы КЕНТАВР было несогласие автора с имеющимися принципами распределения средств на научные исследования. Ноше принципы вклада средств в научные исследования в данной работе в сжатом виде сформулированы с пояснением их правильности. Они изложены в следующем разделе. Эти принципы, по-видимому, могут быть использованы в других областях, где решается задача поиска неизвестного при ограниченных ресурсах на этот поиск. Однако введение этих принципов в распределение средств на научные исследования оказалось Б то время невозможным. Это связано с тем, что любое распределение средств имеет больше политический, чем научный характер. В то же время на этих принципах удалось создать перспективную шахматную программу с оригинальной логикой мышления.

На состоявшемся 1 - ом чемпионате шахматных программ СССР (Улан-Удэ 1988 г.) программа КЕНТАВР стала победительницей. И в дальнейшем выступала как чемпион СССР на 6-ом международном чемпионате мира шахматных программ (Канада, г. Эдмонтон, 1989). На последних российских турнирах шахматная программа КЕНТАВР не потерпела ни одного поражения от российских шахматных программ, и достаточно достойно выступает на международных турнирах (на 7 чемпионате мира в Мадриде (1993 г.) она набрала 2 очка из 5, не турнире микрокомпьютеров, в Мюнхене (1993 г.) 3 очка из 7, на 3-ем турнире равных возможностей в Лондоне (1994 г.) 11 очков из 24-х.)

Однако не только турнирные достижения выделяют программу КЕНТАВР. Ее алгоритм резко отличается от всех других алгоритмов своим почти человеческим мышлением. Она существенно (в 100 - 10000 раз) меньше других шахматных программ занимается перебором позиций и имеет "туннельное видение" комбинаций, т.е. находит определяющую комбинацию в каждой конкретной позиции без подробного просмотра других возможных ходов. Если изложенные принципы поиска неизвестного положить в основу научно- исследовательских проектов, то затраты на поиск можно было бы сократятся в 100-1000 раз или при данных затратах во столько же раз повысится эффективность научного поиска.

Основные принципы построения алгоритма

Алгоритм шахматной программе КЕНТАВР возник в связи с попыткам: найти наилучшую стратегию распределения средств среди конкурирующих направлений исследований. Эта задача актуальна в связи с растущими затратами на научные исследования и может быть сформулирована следующим образом.

Пусть для достижения какой-либо цели предложено несколько путей и требуется найти лучший среди них. Для этого необходимо провести исследования этих путей. В тех случаях, когда имеются неограниченные ресурсы на исследования, проблема распределения средств не возникает. Если же средства, выделенные на исследования ограничены. то эти направления исследований являются конкурирующей (в том смысле, что если одном из направлений выделяется больше средств , то другим достанется меньше). В этом случае возникает задача оптимального распределения средств между конкурирующими направлениями, т.е. необходимо указать, во что эти средства надо вложить с тем, чтобы; с наибольшей достоверностью выяснить наилучший путь к поставленной цели.

На первый взгляд такую задачу решить невозможно, так как требуется предвидеть результат исследований, которые еще только будут проведены. Однако, если учесть, что ресурсы на исследования можно отдавать не все сразу, а постепенно, по мере накопления информации об этих исследованиях, то такая задача имеет смысл. Для решения ее необходимо определить порядок отчетности о проведенных исследованиях и ввести такое распределение средств, которое зависит от уже проведенных исследований и стимулирует поиски наилучшего пути. Примером простейшей стратегии, которая часто используется на практике, является равномерное распределение ресурсов среди конкурирующих направлений. Недостатком такой стратегии является малая глубина исследований. Можно поступить иначе - выделить один или несколько путей возможного достижения цели и исследовать только их. Тогда, эти выделенные направления можно будет проанализировать глубоко. Однако есть значительная вероятность оставить вне поля зрения те пути, которые действительно отвечают поставленной цели, но не были вовремя угаданы.

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

Sj1 - оптимистическая оценка

Sj0 - реалистическая

Sj-1 - пессимистическая.

При определении величин этих оценок приходится считаться с наличием ряда неисследованных факторов м как-то их учитывать. Некоторые да этих факторов могут быть положительными, а другие отрицательными для данного направления. Реалистическая оценка - это оценка, направленно пренебрегающая еще неисследованными факторами. Оптимистическая оценка направления - это сценка, сделанная при условии, что страдательные неисследованные факторы в конечном счете не повлияют на успех этого направления, а действие положительных факторов проявится в полкой мере. Поэтому оптимистическая оценка равна реалистической оценке плюс добавка, которая возникает в случае осуществления всех надежд на еще неисследованные положительные факторы. Пессимистическая оценка - это оценка, сделанная при предположении, что положительные неисследованные факторы не осуществятся, а отрицательные факторы сбудутся в полной мерз к воспрепятствуют достижению поставленной цели. Пессимистическая оценка ниже реалистической оценки на величину отрицательных неисследованных факторов. Разность оптимистической и пессимистической оценок Sj1 - Sj-1 выражает неопределенность в оценке направления J. Три оценки каждого направления исследования удобно выражать в виде схемы. показанной на рис.1, где разность Sj1 - Sj-1 образует вилку сценок. Эта вилка мала в случае хорошо исследованных или тривиальных направлений и велика для недостаточно изученных. В процессе исследований оценка направлений уточняется, то есть вилка уменьшается, а пессимистическая, оптимистическая и реалистическая оценки приближаются друг к другу.

Рассмотрим попарно конкурирующие направления. Возможны следующие три случая взаимного расположения их вилок:

а) Оптимистическая оценка направления В ниже пессимистической оценки направления A (рис.2а) В этом случае ясно, что направление A исследовать не надо, так как в лучшем случае оно может дать меньше, чем направление B в самых неблагоприятных условиях.

б) Вилка оценок направления А целиком лежит в вилке сценок направления Б (рис.2б). В этом случае исследование направления А можно приостановить в пользу исследования направления Б, имеющего более значительную неопределенность в оценке. Доследовать направление Е более важно из-за, того, что имеется вероятность подъема его пессимистической оценки оптимистической оценкой SA1 направления А. Тем самым расположение вилок приведется к случаю 1 и отпадет необходимость исследование направления A.

с) Вилки оценок двух направлений частично перекрываются (рис 2 с). В этом случае предпочтение на исследование отдается направлению Б, так как есть вероятность, что при этом исследовании оценка SB-1 станет выше Sa-1 и направление А можно будет не исследовать. Из этих трех случаев видно , что предпочтение на исследование отдается направлению с максимальной оптимистической оценкой. Это наиболее важный вывод из данного рассуждения.

На первой взгляд этот вывод может показаться странным, так как среди направлений, имевших большую оптимистическую оценку, обычно имеется много "бредовых", т.е. имеющих большую оптимистическую оценку, но резко оторванную от реальности (реалистической оценки) Кажется, что нет смысла тратить драгоценное время и средства на исследование "Бредовых" направлений. Однако, как показывает опыт, исследование "бредовых" направлении не вызывает больших затрат, поскольку их оптимистическая оценка быстро снижается при ничтожном изучении вглубь от этих направлений - в результате большая оптимистическая оценка остается лишь у тех направлений, которые действительно важны и требуют внимания и детального исследования. Каждый поиск наилучшего хода не может длиться бесконечно долго, если в процессе исследования создается ситуация, когда пессимистическая оценка одного из направлений становится выше всех оптимистических оценок конкурирующих направлений, то поиск наилучшего хода можно прекратить и выбрать путь с наибольшими оценками.

Вторым важным выводом приведенных рассуждений являются: если в ходе исследований какого-либо направления вилка его оценок становится малой , то такое направление не надо исследовать даже если оно важно в смысле внедрения. Это вызвано тем что при уменьшении вилки за счет снижения оптимистической оценки возрастает необходимость исследования других направлений, имеющих более высокие оптимистические опенки, а при уменьшении вилки за счет поднятия пессимистический оценки ( выше оптимистических оценок других направлений) появляется требование внедрения этого направления. а не продолжение исследования его. Если условие прекращения исследований не выполняется в течение времени, отведенного для выбора наилучшего пути. то наилучший путь определяется по, максимальной реалистической или пессимистической оценке. В результате имеем третий вывод: внедрение направления определяется реалистической или пессимистической оценкой, в то время как задание на исследование - оптимистической оценкой. Это означает , что те направления, которые надо, интенсивно исследовать, и те, которое можно внедрять, в общем случае не совпадают и определяются совершенно по-разному.

Оценка шахматной позиции

В отличие от других шахматных программ, "Кентавр" использует для каждой позиции не одну, а несколько оценок. Вначале оценок было три - те, о которых уже сказано. В дальнейшем к ним добавились еще две оценки:

Sj 2 - маловероятная оптимистическая

Sj -2 - маловероятная пессимистическая.

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

Первоначальная оценка

Реалистическая оценка со стороны белых определяется материальным преимуществом белых в данной позиции плюс позиционная оценка со стороны белых. В позиционную оценку входит оценка за контроль над центром, безопасность короля , активность фигур, оценка пешечного построения и т.д. Реалистическая оценка ее стороны черных определяется материальным преимуществом черных в данной позиции плюс позиционная оценка со стороны черных. Оптимистическая и пессимистическая оценки отличаются от реалистической на величину реальных угроз. В этих угрозах учитываются фигуры, находящиеся под боем, нападение на связанную фигуру нападения на защищающую фигуру, шах, залита от шаха, угроза мата, вилка. угроза превращения пешки в ферзи и т.д. Величина угрозы определяемся стоимостью фигуры, на которую нападают, а такая сто;1уостьв нападающей фигуры в том случае, когда эта фигура теряется при размене. Если, например, конь (стоимость которого 3,25 стоимости пешки) нападает на защищенную ладью (стоимостью в 5 пешек) , то величину угрозы составляет 1,25 стоимости пешки. Маловероятные оценки отличаются от реалистической на величину угроз, вероятность осуществления которых небольшая. К таким угрозам относятся, в частности, любые нападения на фигуры, в том числе и на фигуры, которые могут беспрепятственно отойти. Если имеется два нападения с маловероятными угрозами одним и тем же ходом, то это нападение переходит в разряд более вероятных. Таким образом в программе учитываются различные двойные удары.

Оценка позиции по оценкам ответных ходов

Если для какой-либо позиции исследованы ходы, то оценки такой позиции определяются из оценок позиций после ответных ходов. Реалистическая оценка такой "исследованной" позиции определяется как величина максимальной реалистической оценки позиций, получаемых после ответных ходов, взятая с обратным знаком. Т.е. если SA0- реалистическая оценка позиции после какого либо хода А, а мах (SB0) - максимальная реалистическая сценка позиций после ответных ходов В, то SA0= - мах(SB0) Аналогично для других оценок: SA1= - мах(SB-1), SA2= - мах(SB-2), SA-1= - мах(SB1), SA-2= - мах(SB2). Последняя запись, например, означает, что маловероятная пессимистическая оценка позиции (после хода А) равна отрицательной величине максимальной оптимистической оценке позиций, получающихся после ответных ходов В.

Описание работы программы "Кентавр"

В несколько упрощенном виде работу программы "Кентавр" можно представить следующим образом:

1. Вначале формируется список всех своих возможных ходов в текущей позиции. Для каждого из них делается первоначальная оценка, в которую, как было сказано, входят реалистическая оценка, две оптимистических и две пессимистических. Для каждого хода. Составляется список ответных ходов, с их оптимистическими оценками.

2. Сравниваются все ходы из исходной позиции и из них выбирается ход с наибольшей оптимистической оценкой.

3. "Мысленно" делается выбранный ход, и для получившейся позиции определяется ход с наибольшей оптимистической оценкой.

4. Проверяется, является ли ход с максимальной оптимистической оценкой проанализированным дальше. Если да, переходим к пункту 3, если нет, то производится первоначальная оценка полученной позиции и генерируется список ответных ходов с их оптимистическими оценками.

5. Если время для анализа истекло, или пессиместическая оценка одного из ходов в исходной позиции стала выше всех оптимистических, оценок других ходов в этой позиции, делается выбранный ход. В противном случае переходим к пункту 2.

Вначале алгоритм использует оценки S1 и S-1 . Если в процессе анализа разность между ними становится малой и уточнять оценку позиции на основе этих оценок более нет смысла, алгоритм переходит на поиск маловероятных комбинаций, используя вместо S1и S-1 оценки S2 и S -2. Таким образом, программа, если у нее есть время, рассматривает менее вероятные продолжения.

Система голосования для борьбы с истерикой.

Используя только предыдущий принцип поиска хода по оптимистической оценке и выбора хода по реалистической, программа КЕНТАВР уже играла довольно хорошо. Однако выяснилось, что в некоторых позициях появляется эффект истерики, т.е. неспособность принять правильное решение з ухудшающейся ситуации. Этот эффект имеется и в других шахматных программах и выражается В том, что когда программа проигрывает, то не может найти наилучшего хода. Более того., шахматная программа в этом случае может просто сделать плохие ходы. Истерика шахматных программ связана с тем, что при игре с более сильным противником программа вдруг обнаруживает, что на любой ее ход имеется комбинация противника, приводящая к резкому ухудшению ее позиции или потере фигуры. В этом случае ход, который отодвигает эту комбинацию, противника так, что программа начинает не " видеть" эту нежелательную для себя комбинацию, признается программой наилучшим.

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

Для борьбы с истерикой В программу была введена система голосования за тот или иной ход, а также более интенсивное исследование хода с максимальной: реалистической оценкой. Отражающие этот процесс изменения были внесены в пункт 3, касающийся выбора хода для анализа в исходной позиции. В этом пункте добавился: периодический выбор хода для анализа по максимальной реалистической оценке. В этот момент программа голосует за этот ход, т.е. подсчитывает число раз, когда этот ход дает максимальную реалистическую оценку. Кроме того, изменился пункт 5. По истечении времени, отведенного на анализ, программа делает ход, набравший Наибольшее число голосов. Программа с таким алгоритмом значительно лучше играет, т.к. не "шарахается" при обнаружении комбинаций противника и выбирает ход, которой наибольшее время считала оптимальным.

.

Участие "Кентавра" на 14-м чемпионате мира среди шахматных программ в октябре 1996 года

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

Среди 28 участниц из 11 стран наиболее мощно была представлена Германия (12 программ). Немецкая программа Shredder и стала чемпионом. Она, как и остальные четыре программы, составившие первую пятерку, относятся к категории "любительских". Неуспех "профессиональных" программ, среди которых был и знаменитый Fritz, стал главной неожиданностью чемпионата. Причины, которые привели к такому сюрпризу, обнаружить непросто. Видимо, чтобы войти в категорию "профессиональных" программ, нужно выполнить немалые требования. На это, а также на коммерческие достоинства (интерфейс, графика, документация) у авторов уходит много сил и времени, в то время как "любители" поглощены одним - поднятием уровня игры своих программ, что им, как видно, удается.

Выступление "Кентавра" надо признать успешным - место в первой десятке. Ярким было окончание партии из последнего тура против венгерской программы Pandix. Участники и зрители не сразу увидели, в чем заключалось обоснование предпринятой черными комбинации…

D59 Pandix - Centaur

1.d4 d5 2. c4 e6 3.Nc3 Nf6 4. Nf3 Be7 5. Bg5 0-0 6.e3 h6 7.Bh4 b6 8.cd Nd5 9. Be7 Qe7 10.Nd5 ed 11.Rc1 Be6 12.Bd3 c5 13.dc bc 14. 0-0 Nd7 15. e4 d4 16. Nd2 Ne5 17. Bb1 f6 18. Re1 Rab8 19.b3 Bg4 20. Qc2 Rbc8 21. Nc4 Be6 22. Ne5 fe 23.Qe2 Qf6 24. Bd3 Qf7 25. Rc2 Qe7 26.Qh5 Bd7 27. Rec1 Qd6 28. Bc4 Kh8 29. Bd3 a5 30. Qd1 Kg8 31.Qd2 Qb6 32.Bc4 Kh8 33. Bd5 Bb5 34.Bc4 a4 35.b4 cb 36.Qb4

...36…d3!! 37.Rb2 (37.Bd3 Qf2!! 38.Rf2 Rc1 39.Bf1 Rf1!!) 37…a3 38.Rd2 Qa6 39.Rd3 Bc4 40.Ra3 Bg8 41. Re1 Qc6 42. Ra5 Qc2 43. f3 Rc4!! 44. Qd6 (44.Qf8 Qd2 45.Rf1 Rc2!) 44…Rf3! 45.gf Qc3 46.Rf1 Qa5 47.Kh1 Qa2 0-1

Итоги: 1. Shredder - 9 (из11); 2. Ferret - 8,5; 3. Nimzo-3 -7.5; 4-5 Crafty , Gunda-1 по 7; 6-8.Fritz, Virtual Chess , Dark Thought по 6,5; 9-10 …Кентавр - 6 и т.д.

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

.