Компьютерные шахматы со всех точек зрения

Вступление

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

Атака Клонов

С прошлого десятилетия компьютеры приобрели огромное значение в подготовке шахматистов. Разросшиеся до гигантских размеров базы дебютных вариантов и огромные базы партий стало уже невозможно эффективно анализировать без применения персональных компьютеров. Теперь компьютер с личной дебютной библиотекой стал непременным атрибутом шахматиста. Процесс проникновения вычислительных систем шёл постепенно, но неуклонно. Вот про Крамника говорили, что он последним из супергроссмейстеров перешёл на использование компьютеров. Когда его остальные, "более продвинутые", коллеги вовсю использовали шахматные программы, он ещё продолжал по старинке записывать варианты в тетрадочку. Но и он поддался веяньям прогресса.
С появлением игровых шахматных программ и мощных персональных компьютеров интенсивность изучения дебюта резко возросла. Дома можно поставить компьютер на длительное время анализировать без участия человека какой-нибудь вариант, потом использовать этот анализ. Сейчас очень и очень многие дебютные варианты, особенно, популярные, изучены до глубокого эндшпиля. Дебютная теория простирается на десятки ходов. Новинка на двадцатом ходу не вызывает никакого удивления, в отличие от новинки на десятом ходу, где, казалось бы, уже всё исследовано. Оказывается, пока что ещё не всё.
Многих известных шахматистов подвергают обвинениям в том, что они выигрывают партии за счёт большего количества компьютеров и, таким образом, более глубоких дебютных знаний. Дебютных новинок больше применяют и т.п. Каспаров чаще других подвергается подобным обвинениям. С одной стороны, к этому располагает его стиль игры от преимущества в дебюте. С другой стороны, он сам дал такой повод, явившись активным первопроходцем использования компьютеров в подготовке.
Но аспекты аналитической работы профессиональных шахматистов не так интересны простым шахматистам и болельщикам. Гораздо интереснее следить за противостоянием компьютерных программ и шахматистов за доской. К анализу которого мы сейчас и перейдём.
За последние несколько месяцев прошло два знаменательных матча Человек-Компьютер, они получили большую огласку и имели солидный призовой фонд. Сначала чемпион мира Владимир Крамник играл матч из восьми партий с шахматной программой Fritz - чемпионом мира среди компьютерных программ. Потом настала очередь лидера мирового рейтинг листа Каспарова сразится в матче из шести партий с шахматной программой Junior. Так же чемпионом мира, но другого года. Эти версии программ не играли официальных матчей между собой, так что, какая из них сильней, мы сможем узнать только на следующем чемпионате мира среди компьютеров. Тем не менее, известно различие стилей этих программ. Если Fritz тяготеет к позиционной игре, то Junior можно назвать атакёром. Кто-то даже сравнил стиль программы Fritz со стилем самого Крамника, а стиль Junior соответственно со стилем Каспарова. Говорилось о том, что гроссмейстеры играют со своим электронным воплощением.
Компьютерная тематика сайта обязывает меня писать об успехах клонированного электронного разума, однако, предполагается, что читатель знаком с фамилиями Каспаров, Крамник. Если нет, то в конце статьи я привёл ссылку на образное литературное описание обитателей шахматного королевства.

Матчи Человек-Компьютер

Давайте теперь подробно рассмотрим, как наши шахматные чемпионы сражались с искусственным разумом. Начнём мы со ставшего знаменитым матча Каспаров - Deep Blue - шахматным суперкомпьютером, специально созданным корпорацией IBM.
Итак, это случилось в 1997 году. Тогда ещё персональные компьютеры были недостаточно мощными, что бы соперничать с гроссмейстерами, и корпорация IBM специально создала гигантский многопроцессорный шахматный компьютер. Первая версия машины была не особенно совершенна, и проиграла Каспарову по всем статьям. Но вторая версия в новом матче сумела обыграть действующего чемпиона мира по шахматам. Это наделало много шума, привлекло внимание всех средств массовой информации. Что же произошло? Рассмотрим с научной точки зрения.
Всего было шесть партий. В первой партии Каспаров играл белыми. Что бы шахматная программа не смогла воспользоваться заложенной в память компьютера дебютной библиотекой, Каспаров почти во всех партиях избирал "кривые" дебюты, которых нет в базе. Дебюты со странными выжидательными первыми ходами, против людей так не играют, поскольку это просто отдача инициативы. Тем не менее, Каспаров в этой партии смог получить перевес, используя позиционные промахи компьютерной программы, и одержать победу.
Во второй партии Каспаров играл чёрными. Неожиданно, компьютер заиграл в этой партии очень сильно. Ему удалось сделать подряд несколько очень сильных плановых позиционных ходов, что поставило позицию чёрных под угрозу. Далее мы ещё рассмотрим принципы действия шахматных программ, сейчас же отметим, что вот плановая игра плохо получается у программ, они оперируют не планами, а отдельными ходами. Что бы спасти позицию, Каспаров жертвует две пешки, взамен получая шансы на атаку короля, вечный шах благодаря активизации фигур. И тут случилось чудо, компьютер задумывается на пятнадцать минут, такого никогда не было, он всегда думал ровно три минуты над каждым ходом. И отклоняет жертву! Все компьютерные шахматные программы - большие материалисты. Они не видят позиционных угроз, а пешки считать умеют. И один из хороших методов борьбы против программ заключается в том, что бы что-нибудь пожертвовать за позиционную компенсацию, которую программа оценить не в состоянии. Расстроенный и удивлённый Каспаров делает ещё несколько ходов, компьютер усиливает свою позицию, создаёт угрозы, но неожиданно всё-таки предоставляет шансы Каспарову пошаховать короля, попытаться спасти партию вечным шахом. Но Каспаров сдаётся. Однако он тут же с удивлением узнаёт от комментаторов, что сдался в ничейной позиции, у него был вечный шах!
Своё решение Каспаров объяснил тем, что не верил, что компьютер сознательно пошёл на вариант с вечным шахом, если несколькими ходами ранее он от него уклонился, не соблазнившись двумя(!) пешками.
Три следующих партии Каспаров очень сильно давил на шахматную программу, но она всё время чудом ускользала на ничью. Какие-то тактические нюансы спасали компьютер.
В последней, шестой партии, Каспаров играл чёрными, он пошёл на дебютный вариант, в котором белые жертвуют коня за сильнейшую атаку. Шахматисты на этот вариант никогда не идут. Компьютер пожертвовал коня и легко выиграл, не сразу, правда. После партии Каспаров объяснял, что компьютеры никогда не жертвуют материал за инициативу, толком оценить которую они не в состоянии. Однако многие комментаторы говорили, что этот вариант мог быть уже в дебютной библиотеке, которую использовала шахматная программа. Каспаров по совсем непонятным причинам исключал такую возможность. Выдвигалось предположение, что Каспаров просто перепутал порядок ходов, то есть, сделал сначала второй ход варианта вместо первого. Такое бывает с шахматистами, тем более, что Каспаров был уже утомлён и измотан предыдущими партиями.
Итак, матч закончился со счётом 3.5-2.5 в пользу шахматного компьютера. IBM по полной программе раскрутила этот успех своего детища. Я даже в каком-то американском фильме слышал во вступлении, что вот, наступил такой-то год, Компьютер обыграл Человека в шахматы, почти что конец человечества. После этого матча акции фирмы IBM существенно поднялись в цене.
Основываясь на странном поведении компьютера во второй партии матча, команда Каспарова заподозрила команду IBM в нечестной игре. В том, что они пригласили гроссмейстера подсказывать стратегические моменты шахматной программе. То есть, шахматист - помощник подсказал программе не принимать жертву двух пешек из-за угроз атаки, которую программа не может до конца просчитать и правильно оценить, а когда было достигнуто решающие преимущество, советчик потерял бдительность, дав возможность объявить вечный шах.
Косвенным подтверждением такой гипотезы может служить коммерческая заинтересованность фирмы в результате матча. Первый матч шахматный компьютер проиграл в чистую, а в разработку вложены большие деньги, так что второй раз осечки быть не должно. И так же тот факт, что после матча компьютер был демонтирован.
Однако, с тем же успехом можно обвинить самого Каспарова в том, что он сыграл договорной матч, сам все партии придумал и разучил наизусть, ещё добавив драматический элемент. Зачем он так рано сдался, не попытавшись дать несколько шахов, зачем пошёл на очень рискованный вариант в последней решающей партии? Вопросов больше, чем ответов.
Ходили твёрдые слухи, что во время партий огромный многопроцессорный компьютер иногда зависал, и его приходилось перезагружать. Технический персонал приводил его в чувство, как побитого боксёра в перерыве между раундами. Я могу высказать гипотезу, что во второй партии компьютер сначала относительно случайно сделал подряд несколько хороших ходов, даже слабый шахматист на такое способен, а потом завис. А перезагружается такая машина долго. А когда перезагрузился, ещё не вошёл в игру, играл по принципу надёжности. Может, у него такая опция, играть сразу после перезагрузки, когда, возможно, ещё не все блоки включились, от защиты короля. А потом он уже нормально стал играть, но угрозу вечного шаха просмотрел, поскольку она многоходовая. Вообщем, программа подвисала, что так удивило и поразило Каспарова, что он в себя уже не смог прийти. Мы ещё вернёмся к предметному шахматному разбору этой партии, когда будем рассматривать алгоритмы работы шахматных программ.
Естественно, этот горе-компьютер пришлось разобрать. Фирма IBM не может же признаться, что сделала склонную к перезагрузкам вычислительную машину. Злобные конкуренты будут смеяться. А может всё ещё прозаичнее, просто каким-то образом случайно выиграли одну партию, чисто случайно, и, таким образом, матч. И увидели, что это сложнейшее дело, изготавливать шахматные компьютеры, и вовремя свернули программу на мажорной ноте. Может быть, они уже после первого матча хотели всё свернуть, но гордость супер- корпорации не позволяла.
Оценим с чисто шахматной точки зрения матч. Последняя партия шахматного значения не имеет, что там было - зевок усталого Каспарова или "сплав" матча - шахматного значения не имеет. В остальных партиях компьютер спасался с переменным успехом. В "выигранной" компьютером партии приходится присудить ничью, поскольку заключительная позиция с шахматной точки зрения совершенно ничейна. Так что в любом случае искусственный разум ничего особенного с точки зрения уровня чемпиона мира по шахматам не показал. Даже несколько странно, что специальный многопроцессорный шахматный компьютер так относительно слабо играет.
Я далёк от мысли подозревать фирму IBM, как выразился Каспаров, в "нечестной игре", но всё равно обидно, что совершенно посредственный результат, игра на "вынос мяча", случайные соскоки на ничью, преподносится как победа в шахматах (!) искусственного разума над человеческим. Такое впечатление, что в руководство IBM вошли продвинувшиеся по служебной лестнице IBM совместимые компьютеры. Конечно, в области шахматного компьютеростроения даже такая игра - это огромный шаг вперёд, но не более того. Таких шагов ещё нужно очень и очень много, что бы хотя бы достичь уровня человеческого чемпиона по шахматам.
Итак, мы плавно переходим к рассмотрению следующих шагов в области развития шахматных компьютеров.

Новейшие матчи

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

Матч-реванш Каспарова

Рассмотрим теперь самый последний матч, поединок Каспарова с шахматной программой Junior. Хотя эта программа не имеет отношения к детищу IBM, матч воспринимался как реванш за поражение от суперкомпьютера.
Первую партию выиграл Каспаров, на этот раз он не стал разыгрывать неправильные начала, придерживался классических схем. Не смотря на то, что шахматная программа смогла воспользоваться дебютной библиотекой, решить дебютные проблемы ей не удалось. После дебюта у неё уже было плохо, и Каспаров её спокойно обыграл.
Во второй партии компьютер играл белыми, Каспаров опять не стал прятаться и выбрал острую Сицилианскую защиту. Тем не менее, ему удалось позиционно переиграть программу. В один момент жадная недальновидная программа соблазнилась жертвой качества за сильную атаку, и получила проигранную позицию. Однако Каспаров сделал торопливый ход, позволив программе объявить, по сути, вечный шах.
В третий партии Каспаров играл белыми и атаковал. Но позиция носила открытый счётный характер, и компьютер уверенно защищался. Тем не менее, кроме возможности сделать ничью у него ничего не было. Однако Каспаров нарушил правила игры с компьютером, увлёкшись атакой, он оставил необеспеченным своего собственного короля. И, вместо того, что бы троекратным повторением ходов зафиксировать ничью, Каспаров зевнул угрозу мата и был вынужден сдаться. Человеческое внимание имеет тенденцию концентрироваться на чём-либо одном, в данном случае, на атаке, что позволяет строить планы. Компьютер играет беспланово, но все ходы равноправны. Поэтому он имеет тенденцию сочетать контр угрозы с оборонительными идеями. Я много раз играл с компьютером в шахматы и обращал внимание, что он любит при обороне неожиданно выскочить ферзём на один флаг, создав угрозу королю, и тут же неожиданно перевести ферзя на помощь своему атакованному королю. Такой защитительный манёвр легко просмотреть.
В четвёртой партии Каспаров черными играл на ничью и получил ладейный эндшпиль без пешки. Глупый компьютер с радостью пошёл на него, не понимая, что он, несмотря на лишнюю пешку, совершенно ничеен. Так ничья и получилась.
В предпоследней пятой партии Каспаров изготовился атаковать, но, совершенно неожиданно, компьютер пожертвовал (!) ему слона на поле h2 за атаку. Каспаров долго продумал, и не пошёл на позицию с лишним слоном, но обильно насыщённую тактическими угрозами. Он потом объяснял, что такую позицию очень легко проиграть прекрасно считающему компьютеру. Тем более, имея мало времени. Получилась ничья повторением ходов.
Эта партия преподносится как большой успех искусственного интеллекта. Компьютер совершил жертву материала за инициативу, такое было раньше только прерогативой человеческого разума. Не стоит, однако, слишком спешить с выводами. Это жертва была осуществлена в дебюте, быть может, она уже была заложена в программу при подготовке к матчу. Ведь с программой работали сильные гроссмейстеры, они изучали дебютный репертуар Каспарова.
В последней партии Каспаров опять переиграл программу, получил сложный эндшпиль с большим преимуществом. Некоторые комментаторы утверждали, что он технически выигран. Однако, Каспаров предпочёл зафиксировать ничью. Он объяснил, что ему было более важно не проиграть матч, чем выиграть.
Если представить, что это был поединок двух боксёров, то в первом раунде компьютерный боксёр был сильно побит, во втором он сдуру раскрылся, и получил сполна, но чудом избежал добивающего удара. В третьем раунде после хладнокровной защиты ему удалось в контратаке наказать слегка зарвавшегося и раскрывшегося противника. В следующем раунде он сам уже ничего не смог поделать с защитой оппонента, все удары прошли мимо, ни разу не попал. В пятом раунде Каспаров собрался крепко побить соперника, но получил сильный, очень точный, а, главное, совершенно неожиданный удар в область печени. Пока думал, стоит ли атаковать, или лучше отдохнуть, раунд кончился. В последнем раунде Каспаров бил соперника сильно, но решил не допускать никакого риска, и соперник где-то там, в углу у канатов, устоял.
Матч в этот раз завершился в ничью, но интересен вопрос, играл ли Junior сильнее, чем Deep Blue? С одной стороны, в распоряжении Deep Blue была большая вычислительная мощность, но, всё-таки, за 7 лет развитие компьютеров не стояло на месте, мощность персональных компьютеров значительно возросла. Тем не менее, можно отметить значительное развитие шахматных программ, которое компенсировало отставание в мощности.
Однако, давайте окинем взглядом эти двадцать партий. В них компьютер одержал 5 побед, 4 раза проиграл и 11 партий свёл вничью. Ни одной вразумительной победы. Всё только на зевках и поддавках. Не говоря уже о сдачах в ничейных позициях. А поражения, наоборот, совершенно разгромные, выявляющие большие позиционные ошибки. Совершенно непонятно, как компьютер собирается выигрывать без помощи человека.
В целом, знаете, что мне напоминает стиль игры компьютерных программ? Раньше были, да и сейчас встречаются, игроки, играющие в блиц в кофейнях, парках на деньги. В их арсенале всегда богатый набор ловушек и заученных дебютных вариантов, они любят смущать соперника провокационными ходами и подлавливать на мелкой тактике, но настоящего понимания шахмат у них нет.
Как же так получилось, что искусственный интеллект играет, как шахматный шулер?

Принцип работы шахматных программ

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


В конце он оценивает получившиеся позиции, и выбирает наилучший ход. В данном случае, он выберет первый вариант, поскольку в нём на любой ответный ход соперника он сможет получить позицию с наибольшим преимуществом.
Каким образом программа оценивает позицию, присваивает ей число? Она опирается на факторы, которые можно аналитически вычислить. В первую очередь, это соотношение материала, выраженное в условных пешках. Это, конечно, самый важный фактор, поэтому все остальные факторы тоже принято измерять в условных пешках. Например, в этой позиции активность фигур тянет на полторы пешки. Условно говоря, можно трансформировать активность фигур в выигрыш пешки, и ещё небольшое преимущество останется.
Что ещё можно подсчитать алгоритмическим образом? Достаточно просто вычислить ту же активность фигур, то есть, количество возможных ходов, несложно оценить контроль фигурами и пешками центра. Можно подсчитать перевес в пространстве, количество контролируемых полей. Учесть простейшие факторы, связанные с расположением пешек. Как-то наличие сдвоенных пешек, слабых изолированных пешек, проходных пешек, отсталых пешек. Можно ввести простейший фактор, отражающий безопасность короля, например, степень контроля полей вокруг него.
Но следует понимать, что эти факторы вычисляются чисто формально, механически. Просто констатируется наличие сдвоенных пешек, что, как правило, плохо, или изолированной пешки. Но слабость в данном случае или сила эта изолированная пешка, понять нельзя. Для этого нужно перебирать варианты, но они уже и так просчитаны на максимальную глубину.
Мнимая или реальная эта фигурная активность, тоже неизвестно. Просто формально констатируется наличие большого количества возможных ходов.
Такой принцип работы делает программы чрезвычайно сильными в счётных позициях, где можно тактическими манёврами добиться материального преимущества. Программы просто перебирают все варианты и идут на тот, в котором у них больше лишних пешек. На этом их можно и подлавливать, что с успехом было продемонстрировано в вышеописанных матчах.
Оценим теперь, какую глубину расчёта вариантов можно достичь, реализуя этот простой переборный метод на современных персональных компьютерах.
Допустим, у нас есть гигагерцовый процессор, и на ход отводится 100 секунд. То есть, в распоряжении программы находится 100 миллиардов тактов. Пусть на оценку позиции тратится 1000 тактов. Это примерная, конечно заниженная величина. Учитывающая различные оптимизации вычисления оценки. Связанные, например, с тем, что позиции, полученные из одной позиции различными ходами, имеют сходную оценку с исходной позицией. Их надо не полностью переоценивать. Понятно, что основной вклад во время работы даёт оценка позиций, получающихся на самом последнем уровне.
Теперь нужно оценить количество возможных ходов в типичных шахматных позициях. В дебюте, миттельшпиле, многофигурном эндшпиле это количество колеблется в пределах 30-60 ходов. Для простоты примем его равному квадратному корню из 1000.
100 миллиардов тактов мы делим на 1000 тактов и получаем количество позиций на самом глубоком уровне расчёта. После этого логарифмируем по основанию, равному количеству возможных ходов. Получается, глубина расчёта равна 5-6 полу ходам. То есть, почти три полных хода. Это совсем не густо. Экспоненциальная природа перебора шахматных ходов сделала своё дело и уничтожила производительность.
Но, может быть, если дать побольше времени и более мощный процессор, удастся продвинуться глубже? Приведём таблицу, пусть время будет не 100 секунд, а 1000.


Видно, что шахматы перебору не поддаются. Вся надежда на увеличение мастерства шахматных программ связана с улучшением алгоритмов их работы.
Действительно, на 5 ходов даже кандидаты в мастера считают. Что же такое сделали с этим переборным алгоритмом, что бы стало возможно бороться с чемпионами мира?

Оптимизация дерева вариантов

С пушистым деревом вариантов сделали две главные вещи, в некоторых местах укоротили, а в некоторых - удлинили. В шахматных программах есть функция, "обрубающая" расчёт варианта при достижении критического преимущества. Что бы не считать многочисленные взаимные взятия ферзями защищённых пешек. Однако, не всё так просто. Это взятие может быть началом матовой комбинации, после которой соотношение материала и другие позиционные факторы значения не имеют. Поэтому вариант можно обрубать не сразу, а только по истечению некоторого количества ходов.
Вторая принципиальная идея состоит в том, чтобы, раз уж не получается считать всё, давайте считать самые важные варианты, но глубоко. Беда в том, что определить эти самые важные варианты крайне сложно. Поэтому в первую очередь компьютер считает во всех позициях все взятия и шахи. Чтобы не получилось так, что расчёт прекращён в тот момент, когда можно съесть ферзя или дать мат в два хода.
Когда вы играете с шахматными программами, такими, как Fritz или Chess Master, они пишут в маленьком окошечке варианты, над которыми думают, и глубину ходов. Типовое значение этой глубины - 12-14 полу ходов. Но на самом деле они совсем не все варианты просмотрели на эту глубину, а некоторые - гораздо дальше, на десятки ходов. Таким образом, компьютер может поставить мат в сто ходов, если он - форсированный, то есть, на каждом ходу - шах. И не поставить мат в десять ходов, если там сплошные "тихие" ходы без взятий и шахов.
Именно манера оптимизации дерева вариантов определяет в наибольшей степени стиль игры компьютерной программы. Большее влияние имеет не оценочная функция позиции, а баланс между расчётами вариантов вглубь и вширь. Если программа быстро отбрасывает подозрительные варианты, то она может упускать скрытые тактические возможности, зато больше времени тратить на оценку позиций.
Рассмотрим теперь на практике работу шахматных программ. Далее я приведу пример неожиданной тактической (!) слепоты программы Fritz, на сначала рассмотрим моменты из матча Каспаров-Deep Blue.

Мышление шахматных программ

В этой позиции был сделан ход Лa6. Вместо того, что бы просто перейти в вот этот абсолютно выигранный эндшпиль,




компьютер дал возможность Каспарову объявить вечный шах путём 45. … Фe3 46. Ф:d6 Лe8! 47. h4! h5! и нет защиты от вечного шаха.




Как же так получается, что шахматная программа допускает такие глупые ошибки? Даже не особенно квалифицированный шахматист поймёт, что лучше пойти на технически выигранную позицию, чем подвергнуть своего короля угрозе вечного шаха.
Однако большинство компьютерных программ, даже после продолжительного раздумья, делают это ход, Лa6. Тут два основных момента. То, что выше указанный эндшпиль выигран, они совершенно не могут понять. Если к его оценке подходить формально, то на стороне белых только более активное положение ладьи. Зато, у чёрных защищённая проходная пешка, а у белых - проходная, но изолированная. Слоны с формальной точки зрения имеют примерно одинаковое количество доступных полей. Компьютерная программа, скорее всего, выиграет это эндшпиль путём постепенного усиления позиции и положения фигур, но выигрывающего плана она не видит. Материальные приобретения, превращения пешек в ферзи, будут только через десятки ходов, что лежит вне пределов расчёта. При реализации преимущества неизбежна некоторая активизация фигур чёрных, создание чёрных проходных, всё это программа оценить не в состоянии.
А в варианте с вечным шахом у программы большое материальное преимущество, целый слон, и много ещё плюсов в позиции. Что же касается самого вечного шаха, то дело в том, что программа может зафиксировать вечный шах, только если во всех вариантах у неё будет либо хуже, либо будет троекратное повторение позиции. А троекратного повторения позиции здесь нужно ждать десятки ходов. Сначала белый король может пойти на ферзевый фланг, потом вернётся, начнёт закрываться слоном, потом опять отправится в путешествие. Вариантов море, но всё бес толку, однако программа этого не поймёт, пока не просчитает. Я в этой позиции бегал около 30 ходов от программы Fritz.




Так что не стоит удивляться выбору компьютеров. Кстати, все шахматные программы, с которыми мне довелось исследовать эту позицию, необыкновенно часто зависали и глючили.
Каспарову показалось странным, что в некоторых позициях, ранее встретившихся в партии, программа отражала угрозу вечного шаха. Однако, можно запустить современную шахматную программу даже на персональном компьютере и увидеть, что разница в оценке хода, сделанного Deep Blue, и хода, ведущего к вечному шаху, находится в районе одной десятой пешки. Такая разница находится в пределах колебаний, порождаемых различной настройкой программы. Программа может с несколько различными весами оценивать позиционные и материальные факторы.
С другой стороны, в предыдущих позициях угроза вечного шаха была более чёткой, троекратное повторение позиции получалось гораздо раньше, и современные программы относительно быстро её обнаруживают.
Зная склонность программ быстро "обрубать" мало обещающие варианты с большими материальными потерями, можно предполагать существование тактических позиций, совершенно неправильно оцениваемых шахматными программами.
Действительно, вот пример такой позиции (из партии гроссмейстеров).




Я не претендую на полный анализ этой сложной позиции, но, несмотря на лишнюю пешку, белым в ней надо спасаться этюдными методами. Чёрные активизируют ладью, Лe4! и брать её нельзя из-за взятия слона на c4. На ход Сc3 находится в нужный момент жертва коня на g5 с развалом позиции белых, а на перекрытие Кc6! есть тихий ход Фe8! В позиции ещё много тактических идей. Казалось бы, шахматные программы, построенные на расчёте вариантов, должны быстро разбираться в подобных позициях. Не тут то было!
Программе Fritz7, недавнему чемпиону среди компьютерных программ, нужно около часа на полутогигагерцовом процессоре, что бы только начать понимать, что не всё в позиции белых ладно. И часы, что бы приблизиться к верной оценке. Она долго не видит "тихих" ходов и т.п.
А что же другие программы, есть и более новая версия Fritz8? Они все по силе игры недалеко ушли от Fritz7. Если и лучше разбираются, то ценой ослабления стратегического мышления. Кстати, старенький ChessMaster 5000, 1996 года, быстрее Fritz7 начинает понимать эту позицию. Но у него много других пробелов.
Может быть, увеличение мощности процессоров скажется благотворно на анализе таких позиций? Может быть, но дело в том, что программа при анализе предыдущей позиции, из которой получается данная, должна рассмотреть десятки ходов. Это опять уничтожит весь прирост скорости.
Многие шахматисты, особенно любители, любят "загонять" партии для анализа в шахматные программы. Однако следует осторожно относиться к компьютерным оценкам. Позиция может быть выиграна, а программа писать даже после продолжительного раздумья преимущество всего в пол пешки. И, наоборот, позиция может быть ничейной, а компьютер давать оценку пешка преимущества одной из сторон. В данном случае не следует обольщаться высоким рейтингом шахматных программ, между практической силой их игры и пониманием позиции есть большая разница.
Поиграв с шахматными программами, я пришёл к выводу, что для достижения положительного результата необходимо в каждой позиции стараться делать абсолютно сильнейший ход, может, только поспокойнее, а не какой вздумается. Часто стараешься делать не лучший ход, а ход, который тебе нравится, с компьютером это может привести к плохим последствиям.

Игра шахматных программ

Имея такой примитивный по сути и медленный алгоритм работы, каким же образом шахматным программам удаётся побеждать гроссмейстеров? За счёт чего они обыгрывают человеческий разум?
А за счёт чего выигрывают шахматные шулеры?

Шахматный шулер имеет в левом кармане дебютную шпаргалку с ловушечными вариантами и подсматривает в неё.
Действительно, шахматная программа имеет в своём распоряжении записанную на жёстком диске гигантскую дебютную библиотеку, а человек лишен такой возможности. Однако, человеческую память можно рассматривать обобщенно, как внутреннюю и на внешних носителях типа бумаги. Глаза в данном случае это что-то типа головок CD-ROM, а лист бумаги - как лазерный диск. Человек получается искусственно лишённым не просто половины памяти, а специальной её части, имеющей отдельные функции постоянного хранения информации. Это хорошо для спортивных соревнований между людьми, но неприемлемо для соревнований между разумами.

В другом кармане шахматного шулера лежит сборник эндшпилей.
Действительно, разработчики шахматных программ, отчаявшись усилить игру своих созданий, стали загонять в программы базы данных известных эндшпилей. Без них программа будет плавать и совершенно неверно оценивать даже простейший пешечный эндшпиль с образованием отдалённой проходной пешки. То-то шахматные программы разрослись последнее время, стали занимать целые диски. Получается, человек играет не с искусственным разумом, а с собственной базой знаний. Это хорошо для подготовки шахматистов, но говорить об успехе искусственного интеллекта тут не приходится.

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

Шулеры "подсаживают" клиентов.
Жулики любят сначала дать выиграть, войти человеку в азарт, а потом обставляют его. Так и шахматные программы, от партии к партии меняют свои параметры, причём, делают это не сами, этим занимается человеческая команда. Они почти что подменяют оппонента. А как бы им самим понравилось, если бы они готовились играть с Каспаровым, а получили в соперники Крамника?

Шахматный шулер держит под столом запасную доску и на ней просматривает варианты.
Шахматные программы имеют в своём распоряжении огромное количество стабильной памяти, можно сказать, они передвигают фигуры на миллионах досок. А человек, как я писал выше, оставлен без памяти. Ни прочитать нельзя, ни записать. Я бы на месте Каспарова или Крамника пришёл на матч с компьютером со своей шахматной доской и просматривал бы всякие варианты. Всё равно компьютер ничего не может видеть. Кто сказал, что при игре с программой нельзя трогать фигуры? Нет таких правил.
Это всё равно, что с шулером играть в "слепые" шахматы, не глядя на доску. Вы будете что-то воображать с закрытыми глазами, а жулик - передвигать фигуры на настоящей доске.
С другой стороны, и зрителям было бы интереснее смотреть, над какими вариантами размышляет шахматист, чем просто наблюдать его задумчивое лицо.

Шулер выигрывает на зевках.
Действительно, все выигранные компьютерами партии в вышеописанных матчах выигрывались за счёт зевков всего, что только можно. Фигуры, мата, ничьи, дебюта. Без зевков шулер не выигрывает.

Заключение

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

P.S. И я хотел бы поблагодарить своего друга В за написание концептуальной версии шахматной программы.

Ссылки

Матч Каспаров-Deep Blue. Вопросы, оставшиеся без ответа - Команда Каспарова делится своими сомнениями по поводу матча.

Garry Kasparov on Chess Computers - Каспаров рассказывает о противостоянии человека и компьютера в шахматах.

Гари Каспаров: "Я принял открытый бой!" - Интервью Гари Каспарова после матча с программой Junior.

Шахматные Джедаи (Chess Jedies) - Авторское образное художественное описание взаимоотношений обитателей шахматного королевства на основе сравнения с популярным кино сериалом Звёздные Войны.