6.8. ROBIN — интеллектуальная программа для игры в шахматы

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

Поэтому фундаментальной проблемой для исследователей в области искусственного интеллекта является понимание того, как человеку удается достигать таких высоких результатов, если доступное ему для анализа дерево ходов по своим размерам в тысячи раз меньше, чем для ЭВМ. На основании полученных результатов могут быть разработаны принципы построения игровых программ, отличные от систематического перебора ходов. Именно в этом направлении начал работать в 1972 г. французский ученый Жак Питра (CNRS, Париж).

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

Это подтверждают и исследования Бине, де Грота, Саймона. Они показали, что шахматист быстро схватывает существенные особенности позиции, ему «бросаются» в глаза ходы, на которые нужно обратить внимание в первую очередь. Таким образом, хороший шахматист начинает исследование с углубленного

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

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

Из рассмотренной картины можно сделать вывод, что в мозге шахматиста возникает не что иное, как дерево планов, а не слепое дерево ходов, имеющее к тому же и громадные размеры. Программа Жака Питра работает по тому же принципу. Большая часть ходов, найденных с ее помощью, вообще не замечается другими программами, а иногда даже и специалистами! Ее можно отнести ко второму поколению игровых программ, которое существенно отличается от первого и представляет настоящий интерес с точки зрения искусственного интеллекта, так как заложенные в его основу принципы можно перенести на многие другие области человеческой деятельности.

Приведем сначала пример игры программы Жака Питра, которая называется ROBIN, а затем более подробно рассмотрим принцип ее работы.

6.8.1. Пример анализа, выполняемого программой

Встретившись с позицией, приведенной на рис. 6.16, программа начинает поиск хода с ее детального анализа. На этом этапе основной задачей программы является составление возможных в данной позиции планов продолжения игры, к которым в данном случае могут относиться:

1) прямая атака на короля противника, начинающаяся ходом

2) связка ферзя ходом ладьи на поле

3) взятие незащищенного черного ферзя

Эти планы на практике могут реализоваться с помощью последовательности элементарных ходов, приближающих

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

Рис. 6.16. Е42. Ход белых.

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

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

— программа нацелена на взятие ферзя, занимающего поле ходом Ф X Ф;

— для этого белым нужно убрать своего коня с поля

— на это последует ответ черных

— следовательно, белым нужно убрать коня, нападая на фигуру противника, как минимум равную ферзю. Это может быть только король;

— возникает промежуточная цель — поставить конем королю, находящемуся на поле

— прямой невозможен, единственными доступными для коия полями вблизи короля являются

— возникает новая промежуточная цель — переместить короля черных;

— только ладья белых, расположенная на поле в принципе может сделать это (ходы ферзем нужно отбросить, так как должна сохраниться возможность взятия

— поле не защищено (см. план 2);

— таким образом, остается только поле для объявления шаха королю;

— отсюда следует ключевой ход со следующими основными вариантами: (но не из-за и ферзь уходит из-под боя) и Программа проверяет также ходы которые ничего не дают черным;

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

Безусловно, эта позиция находится в пределах досягаемости предыдущих программ полуходов), но она очень хорошо иллюстрирует возможности поиска наилучшего хода с помощью очень небольшого дерева — всего 305 ходов против 407 или для программы, работающей с помощью перебора ходов. Как мы увидим ниже, в сложных позициях ROBIN может спускаться до глубины 20 полуходов и более.