Уже много лет человечество воспитывает себе электронного соперника, скрупулезно приближая его к совершенству. За это время программисты и ученые разработали множество методов и средств. Создатели машинных игроков давно уже не полагаются только на «грубую силу» — в дело идут различные методы эвристики: оценка позиции, выбор хода-кандидата, обучение, а также многое-многое другое. Напряженные исследования команд ученых, программистов и гроссмейстеров привели к огромным успехам. Вспомним основные вехи этого трудного, но очень быстрого (с исторической точки зрения) пути.

Рождение компьютера  — появление компьютерных игр

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

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

Компьютерное моделирование логических игр имеет столь же давнюю историю, что и сами компьютеры. Программы для простых игр типа «крестики-нолики» или «Ханойская башня» появились в конце 40-х годов XX в. С течением времени число таких программ стремительно увеличивалось. На ЭВМ стали воспроизводить процесс игры и моделировать поведение игроков во всевозможных карточных играх, домино, шашках, шахматах и т. п., так что сейчас, пожалуй, нет ни одной более-менее популярной игры, которая не имела бы компьютерной реализации.

Первую работу по «игровому компьютеру», получившую известность в научном мире, выполнил один из родоначальников информатики и кибернетики — Клод Шеннон. Его статья, названная «Программирование компьютера для игры в шахматы» («Programming a Computer for Playing Chess»), была опубликована в 1950 г. в журнале Philosophical Magazine.

В то время компьютеры не были производительными (по сравнению даже с современными микрокомпьютерами) и распространенными, а создание программ для них являлось весьма трудоемким занятием. Шеннон понимал, что «эта задача, не имея, возможно, практической ценности, представляет теоретический интерес», ибо вычислительные способности ЭВМ в середине XX в. были далеки от необходимых для успешной игры в шахматы.

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

Клод Шеннон объявил, что компьютеры могут играть в шахматы (а уж эта задача никак не вычислительная!), и ввел термин «символическое программирование» — в отличие от «численного программирования». В основу игрового алгоритма он предложил заложить следующие три принципа, остающиеся и до настоящего времени основными для большинства игровых программ, начиная от «крестиков-ноликов» и заканчивая шахматами и го:

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

Последний принцип, как было отмечено в предыдущей статье из серии «Компьютер играет в игры», особенно важен, так как рост перебора вариантов при увеличении глубины просмотра продолжения партии, как правило, происходит весьма быстро (имеет экспоненциальный характер), а это предъявляет повышенные требования к скорости работы компьютера. Именно поэтому в шахматных программах зародились идеи методов сокращения перебора. В СССР первый такой метод (метод граней и оценок) был предложен А. С. Брудно, а первая наиболее удачная реализация эвристических приемов была воплощена в шахматной программе «Каисса», созданной в СССР В. Л. Арлазаровым, Г. М. Адельсоном-Вельским и М. Б. Донским.

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

Шахматные баталии

Первый чемпионат мира по шахматам среди компьютеров состоялся в 1974 г. в Стокгольме, и на нем собралось большое количество участников из технологически развитых стран мира. Учитывая размеры «носителей электронного разума» в то время, большая часть программ не выезжала для участия в соревновании за пределы научных учреждений, в которых они создавались, поэтому их ходы разработчики передавали по телефону, а весь процесс игры тщательно контролировали наблюдатели международной организации IFIP (International Federation of Information Processing). Победителем и, следовательно, первым чемпионом мира среди компьютеров стала советская программа «Каисса», разработанная в Институте проблем управления Академии наук.

После долгих лет разработок и научных изысканий авторы компьютерной шахматной программы бросили вызов чемпиону мира Гарри Каспарову. Напряженный матч привлек к себе большое внимание. Он закончился победой человека. В результате, несмотря на одну выигранную партию и две ничьи, программа Deep Blue отправилась на доработку. Но уже год спустя усовершенствованная и обновленная Deep Blue одержала победу (правда, с точки зрения Г. Каспарова, и «нечестную»).

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

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

Компьютер проходит в «дамки»

С шашками были связаны не столь долгие и упорные изыскания. Первая программа, играющая в шашки (английский вариант  —  checkers), также была создана в начале 1950-х. Хотя шашкам уделялось значительно меньше внимания, чем шахматам, уже в 1995 г. сильнейшая шашечная программа Chinook устояла против самого сильного игрока в шашки: оба соперника  — и программа, и человек  — одержали по одной победе, а остальные 30 партий свели на ничью.

Спустя 12 лет (в июле 2007 г.) создатели Chinook объявили о том, что шашки полностью пересчитаны и смысла в проведении турниров с участием компьютера больше нет.

Последний рубеж

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

Первую программу, играющую в го, создал Альберт Зобрист в 1968 г. в рамках работы по распознаванию образов, а в 1984 г. прошел первый турнир по го среди компьютеров. Несмотря на такую историю (вполне сравнимую с шахматной), игра го все еще остается неприступной для искусственного интеллекта.

В литературе часто приводится следующий исторический эпизод. В 1997 г. (спустя пару месяцев после того, как Deep Blue выиграл у Г. Каспарова!) на ежегодной конференции Американской ассоциации искусственного интеллекта (American Association for Artificial Intelligence  — AAAI) состоялся турнир между программами, играющими в логические игры, и людьми. На этом турнире Дженис Ким из Нью-Мексико (профессиональная спортсменка, одна из сильнейших игроков в го на Западе) сразилась с лучшей из известных на тот момент го-программой Handtalk (разработчики приписывали ей уровень 3-го кю; кю — единица в японской системе рейтингов игроков в го). Мало кто верил в победу Ким — перед началом игры компьютерная программа получила фору в 25 камней (это приблизительно то же самое, что фора в ферзя и обеих ладей в шахматах). Тем не менее даже такой огромной форы программе не хватило — Дженис Ким победила. Если исходить из стандартной японской рейтинговой системы (один камень форы — разница в одну ступень в рейтинге), можно заключить, что компьютер в этой партии играл на уровне не выше 17-го кю (уровень любителя, занимающегося го не более полугода).

Несмотря на то что с момента этого памятного матча прошло уже больше десятилетия, успехи го-программ остаются весьма скромными. Широко распространенная OpenSource-реализация го — GNU Go, играет примерно на уровне 8—9 кю, коммерческие го-программы превосходят ее примерно на один-два уровня, т. е. имеют не более чем 5-й кю.

С 1987 г. фонд Инга (Ing Foundation) проводит ежегодный турнир среди компьютерных программ, победители которого получают денежные призы. Самое известное предложение фонда — The Ing Challenge, гарантирующее 40 млн. тайваньских долларов (около 1 млн. евро) за программу, способную победить чемпиона среди тайваньских любителей, — осталось нереализованным из-за отсутствия компьютерной го-программы достаточной «квалификации».

* * *

Появление компьютеров практически сразу же привело к рождению игровых программ. Пытливые умы ученых получили шанс на создание равных и даже превосходящих человека электронных соперников. Искусственный интеллект обрел реальные очертания и цели  — «мыслящая электроника» рвется к титулу сильнейшего игрока во всех популярных логических играх. Многие забавы уже пали под этим стремительным напором…

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