Компьютер играет в шахматы

В прошлой статье («Мир ПК», №1/08) речь шла о «трех китах» успеха разумного человека: это способность к обучению, определение хода-кандидата и оценка позиции. Разберемся с ними подробнее.

Голосуйте за нашего кандидата!

Михаил Ботвинник¹ сказал: «Человека от других живых существ на Земле отличает умение выделять главное». Трудно судить, насколько правильно это высказывание в общем, но применительно к логическим играм оно безусловно верно.

Обратимся к опыту этого великого шахматиста. В ноябре 1960 г. чемпион мира по шахматам прочитал лекцию в берлинском Университете им. Гумбольдта, сокращенный вариант которой был опубликован в «Комсомольской правде» в январе 1961 г. под названием «Люди и машины за шахматной доской», а полный появился месяц спустя в ведущем шахматном журнале «Шахматы в СССР».

Приведем наиболее интересный для нас отрывок из лекции, опустив несущественные детали:

«Рассмотрим процесс мышления шахматиста. Каждый знает, что никогда шахматист не рассчитывает все возможные варианты, не смотрит все ходы, возможные на доске. Шахматист во время партии в данной позиции, которую он обдумывает, рассматривает примерно 2—4 хода; определяет он эти ходы интуитивно, на основании опыта и т. п. Если учесть, что в среднем партия длится ходов 40, то примерно за партию шахматист должен проанализировать не более 100 первых ходов. Разумеется, шахматист в процессе расчета в общей сложности рассматривает не 100 ходов во время партии, а анализирует несравненно больше. Если в среднем вариант рассматривается хода на 2—3, то и тогда цифра анализируемых ходов получается достаточно внушительная».

Что же это получается? Только недавно мы говорили об астрономическом количестве вариантов, а теперь оказывается, что в каждой позиции человек (даже чемпион мира!) рассматривает (и этого ему вполне достаточно) лишь два–четыре хода! Если научить компьютерную программу подобно человеку правильно определять эти самые ходы-кандидаты, которые необходимо перебрать, то объем требуемых вычислений значительно сократится, а игровые возможности ПК значительно возрастут. Но не все так просто, и, чтобы это понять, нужно понаблюдать за игроками различной квалификации.

Не секрет, что начинающие шахматисты испытывают большую тягу к ходам крайними пешками и ферзем, а начинающие игроки в го стараются «съесть» как можно больше «камней» противника. В дальнейшем, с ростом квалификации, ситуация резко меняется. Ходы выстраивают стройную цепочку на пути к цели, партия обретает гармонию: каждая фигура, каждая шашка, каждый «камень» выполняют свою функцию… Значит, изменяется и набор ходов, привлекающих внимание игроков. Отсюда можно сделать вывод, что выбор ходов-кандидатов сильно зависит от квалификации, т. е. от опыта и интуиции игрока. Но разве можно запрограммировать человеческий опыт, а тем более интуицию?

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

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

Насколько ты хорош?

Ходы-кандидаты, безусловно, очень важны для сокращения перебора, но еще более важно правильно оценить позицию, поскольку даже по два–четыре хода-кандидата на позицию разрастаются в архисложное дерево перебора. Хорошая функция оценки поможет выбрать лучшую из множества позиций, получающихся после, скажем, десятого хода. Если мы используем перебор подобно тому, как это было описано в части 1 серии «Компьютер играет в игры», то функция оценки позволит подсчитать результат партии в каждом узле дерева перебора. Если после осуществления перебора на определенную глубину (когда ожидание становится слишком велико) не произошло мата или форсированной («теоретической») ничьей, то вместо перебора используется оценочная функция. Она приписывает текущей позиции (точнее, всему поддереву, начинающемуся с текущей позиции) некоторую оценку.

Конечно же, каждый игрок, не считая новичков, пытается оценить последствия своих ходов и ходов соперника — это жизненно необходимо в игре. Представьте, что вы можете очень точно предсказать исход любой партии, просчитав варианты на глубину два–три хода. Вас будут считать пророком! Лучшие из лучших будут смотреть на вас с мучительной тревогой и записывать каждое ваше слово! А через пару месяцев вам устроят матч на звание абсолютного чемпиона, который вы легко выиграете, разгромив соперника — некогда недостижимого авторитета всех профессионалов и любителей! И все это благодаря отличной функции оценки позиции.

Так на чем же она основывается?

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

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

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

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

Оценку позиции в шахматах, как правило, выражают в пешках.

При разработке первых шахматных программ начинать приходилось с самого простого — с числового определения сравнительной ценности фигур. Особых трудностей при этом не возникает: пешка, как самая слабая фигура, равна единице, конь — трем-четырем пешкам (единицам), ладья — пяти, ферзь — восьми – десяти.

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

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

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

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

Тем не менее, несмотря на все эти сложности, большая часть прогресса, связанного с «силой» шахматных программ высокого уровня, основана именно на улучшении функции оценки. Долгие годы лучшие шахматисты мира (гроссмейстеры и даже чемпионы мира!) занимались улучшением компьютерной оценки позиции.

Научи меня учиться

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

Вопросами создания алгоритмов, способных «обучаться», занимаются в рамках машинного обучения (machine learning) — подраздела огромного научного направления, нацеленного на изучение и создание искусственного интеллекта.

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

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

Хотите проверить, умеет ли ваш компьютерный соперник учиться? Попробуйте повторить однажды выигранную партию (см. врезку «Одна задача машинного обучения»)…

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

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

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

¹Михаил Ботвинник (1911-1995) — чемпион мира по шахматам с 1948 по 1963 г., одним из первых начал работать над созданием советской шахматной программы.

Фрэнк Саберхаген. Берсеркер

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

«Но капитана интересовало другое.
— Дел, ты научил Ньютона играть по диаграммам. Это я понимаю. Но как получилось, что он играл все лучше и лучше? Как он мог учиться играть?
Дел усмехнулся.
— Он учиться не мог. Но его игрушки — могли.
— Погоди, я не шучу.
Он позвал айана и взял из лапы животного коробочку. На крышке была наклеена карточка с диаграммой одной из возможных позиций, со стрелками разного цвета, указывающими вероятные ходы фигур Дела.
— Понадобилось около двух сотен таких коробочек. Вот эта из группы четвертого хода. Найдя в этой группе диаграмму, подходящую для позиции на доске, Ньютон брал коробочку, вынимал наугад бусину, — сказал Дел, демонстрируя операцию.
— Вот, я вытащил голубую. Делаем ход, указанный голубой стрелкой на диаграмме. Смотрите, на слабую позицию ведет оранжевая стрелка. Видите? — Он вытряхнул бусины на ладонь. — Оранжевых бусин не осталось. Хотя в начале игры было по шесть бусин каждого цвета. Вынимая бусину, Ньют обратно ее не клал до конца игры. Если табло показывало проигрыш, он выбрасывал все неудачные бусины. Постепенно были исключены все неудачные ходы. Через несколько часов Ньют и его коробочки научились играть не хуже Берсеркера».

Одна задача машинного обучения

Научное направление, названное искусственным интеллектом, родилось
в 50-х годах прошлого века. Одна из наиболее серьезных проблем, возникших при создании систем, способных выполнять работу за человека, — «обучение» компьютера. Как передать программе все те знания, которыми обладает специалист в своей области, да еще и научить их использовать?

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

Действительно, как сформулировать ту задачу, которую невозможно сформулировать? Как, например, объяснить компьютеру, чем отличаются различные способы рукописного написания цифры «1» от столь же разнообразных способов написания цифры «2»? Как «научить» воспринимать разницу между красивым и некрасивым?

С помощью примеров! Теория машинного обучения выработала следующую схему работы с задачами классификации объектов:

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

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

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