Сегодня: Пятница, 29.03.2024, 02:46 (МСК)| Здравствуйте, Гость| Мой профиль | Регистрация | Вход | RSS

Что такое matte painting?

Спецэффекты в Cinema4D

Эргономика компьютерных клавиатур

Новинки в области цифровых камер

Плагины Sonnox Oxford
Главная » РАЗРАБОТКА КОМПЬЮТЕРНЫХ ИГР

Популярно об ИИ. Сезон 2. Программирование шахмат и логических игр-1

06.08.2010

«Наиболее ценная жертва — наименее ценный нападающий». 
Расшифровка аббревиатуры MVV/LVA

В недавних материалах серии «Популярно об ИИ» мы рассмотрели: сортировку, стек, рекурсию, несколько приемов оптимизации алгоритмов. Что должно стать логическим продолжением? Немногие сходу догадаются… — шахматы. 

Ведь, по существу, очень часто, говоря об успехах в области искусственного интеллекта (ИИ), в качестве примера приводят не невнятные персептроны, и не роботов, которые умны только в новостях науч-попа, а компьютерные программы, обыгрывающие чемпионов мира.

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

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

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


***


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

Для каждого из двух случаев, программируя «компьютерного» игрока, мы можем использовать концептуально различную алгоритмическую начинку, например, для детерминированных игр подходит булева логика, для недетерминированных — вероятностная. Хотя… вероятностная логика ближе к мышлению человека. То есть, взглянув на шахматную доску, опытный игрок способен не только выделить наиболее перспективные ветви развития, но и просчитать ситуацию на несколько ходов вперед. Машина сможет сделать такое же только благодаря переборному принципу поиска решений. Все это мы подробно рассмотрим, а для начала выведем два главных правила, от которых будем отталкиваться:
  1. Написание шахматной программы — это конкретная, а не абстрактная задача. Мы знаем правила, расстановку и т.п.
  2. Универсального алгоритма или метода для расчетов не придумано. Есть несколько базовых находок. 
Говоря о вероятностной логике и схожих направлениях, можно отметить, что… да, некоторые из используемых в шахматной сфере приемов и технологических ноу-хау стоят близко к нечеткой логике (привязанной к нечеткой теории множеств), кою любят использовать в системах управления и в том же ИИ для компьютерных игр, но! Шахматные алгоритмы в большинстве случаев бронебойные! Они эмулируют только одну модель поведения — стремление к победе с минимальными потерями и быстрыми расчетами. 

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


Общая информация


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

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

Полный перебор для современных компьютеров — вещь утопическая, потому как ветвление дерева поиска происходит экспоненциально. В среднем из каждой позиции имеется 40 вариантов перемещений для одного игрока. При глубине 4 получается 40х40х40х40, то есть, 2560000, а при глубине 5 — 40х40х40х40х40 вариантов, что равняется 102400000 (102 млн. 400 тыс.). А дальше рост вычислений продолжает увеличиваться в экспоненциальной прогрессии. Глубина 6 является предельной для реализации полного перебора в рамках современных вычислительных систем, а это подразумевает рассмотрение чуть больше, чем 24 млрд. позиций (чуть больше — это 96 млн). Именно поэтому нужно вводить особые условия и ограничения с выделением наиболее перспективных ветвей.

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

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

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


GenerateAllMoves()


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


SortMoves()


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

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

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


MakeMove()


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


UnMakeMove()


Эта функция возвращает исходную позицию, которая была до применения MakeMove().


EvaluatePosition()


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

Например, шкала оценок у нас такая:
  • Пешка — 100.
  • Конь — 300.
  • Слон — 300.
  • Ладья — 500.
  • Ферзь — 900.
  • Король — 10000 (можно и больше, иногда просто ставят бесконечность, иногда 1200, все зависит от дальнейшей настройки, король является самой ценной фигурой).
Если у белых на одного слона больше, то материальная оценка выдает для них — плюс 300, для черных она будет значить — минус 300.

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

В качестве наглядного примера или просто ориентира (показать, как это может считаться) я приведу некоторые варианты из возможных, написанное или подобное ему вы можете встретить во многих листингах известных разработок. В данном случае заимствуем из GNU Chess (Free Software Foundation).

Итак, стратегическая оценка белой пешки (напомним, что ее «материальный» вес равен 100):

int WhitePawn[64] {
  0,  0,  0,  0,  0,  0,  0,  0,
12,16,24,32,32,24,16,12,
12,16,24,32,32,24,16,12,
  8,12,16,24,24,16,12,  8,
  6,  8,12,16,16,12,  8,  6,
  6,  8,  2,10,10,  2,  8,  6,
  4,  4,  4,  0,  0,  4,  4,  4,
  0,  0,  0,  0,  0,  0,  0,  0
};

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

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

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

Теперь рассмотрим самого короля, при этом раздельно должно оцениваться два случая — начало игры и конец. Для начала:

int KingStart[64] {
0,0,-4,-10,-10,-4,0,0,
-4,-4,-8,-12,-12,-8,-4,-4,
-12,-16,-20,-20,-20,-20,-16,-12,
-16,-20,-24,-24,-24,-24,-20,-12,
-16,-20,-24,-24,-24,-24,-20,-12,
-12,-16,-20,-20,-20,-20,-16,-12,
-4,-4,-8,-12,-12,-8,-4,-4,
0,0,-4,-10,-10,-4,0,0,
};

Из данного массива оценок очевидно, что королю выгоднее всего сделать рокировку и/или оставаться на своей линии.

В конце игры приоритеты меняются, то есть королю выгоднее всего быть в центре. 

int KingEnd[64] {
  0,  6,12,18,18,12,  6,  0,
  6,12,18,24,24,18,12,  6,
12,18,24,30,30,24,18,12,
18,24,30,36,36,30,24,18,
18,24,30,36,36,30,24,18,
12,18,24,30,30,24,18,12,
  6,12,18,24,24,18,12,  6,
  0,  6,12,18,18,12,  6,  0
};

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

int Knight[64] {
  0,  4,  8,10,10,  8,  4,  0,
  4,  8,16,20,20,16,  8,  4,
  8,16,20,24,24,20,16,  8,
10,20,28,32,32,28,20,10,
10,20,28,32,32,28,20,10,
  8,16,20,24,24,20,16,  8,
  4,  8,16,20,20,16,  8,  4,
  0,  4,  8,10,10,  8,  4,  0
};

Основным приоритетом слона является занятие одной из главных диагоналей:

int Bishop{
14,14,14,14,14,14,14,14,
14,22,18,18,18,18,22,14,
14,18,22,22,22,22,18,14,
14,18,22,22,22,22,18,14,
14,18,22,22,22,22,18,14,
14,18,22,22,22,22,18,14,
14,22,18,18,18,18,22,14,
14,14,14,14,14,14,14,14,
};

Помимо этого позиционная оценка должна учитывать дополнительные факторы, среди которых:
  • Премия за количество атакуемых фигурой полей. Чем больше, тем лучше. Этот параметр также можно назвать «мобильностью» фигуры. 
  • X-Ray-атака, когда одна дальнобойная фигура стоит за другой (премия).
  • Наличие двух слонов (это небольшое преимущество по сравнению с другими сочетаниями легких фигур — премия).
  • Оценка структуры пешек. Штрафы — изолированные пешки, незащищенные пешки, сдвоенные пешки, сдвоенные заблокированные пешки.
  • Премия за занятие открытых линий ладьями, слонами, ферзем.  
  • Функция оценки приоритета центра. 
  • Функция оценки защищенности короля. 
  • Очень многие программы считают общее количество атакуемых полей. Этот параметр также можно назвать «мобильностью» игрока. 
Стратегическая оценка может учитывать огромное количество различных параметров. В ведущих разработках для создания и регулировки этого очень важного модуля приглашаются гроссмейстеры. С их помощью расставляется система ценностей.

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

Дополнительная информация

№1 ***

Достаточно интересной и популярной даже сейчас среди разработчиков является битовая техника. Суть ее объяснить просто, показав, например:

0000000
0000000
0000000
0000000
0001000
0010000
1100111 
0000000

… структуру для хранения позиций белых пешек. С помощью битовых операций (&, |, ^, <<, >>) в данном случае можно сделать очень многое: маски взятий, атак и т.п. Эта техника математически очень интересна, хотя не всегда выгодна. Мы поговорим об этом подробнее позже.


№2 ***




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



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


№3 ***




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

Кристофер

Перепечатка материалов или их фрагментов возможна только с согласия автора








Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Ассоциация боевых роботов
Рекомендуем...
Новости

Разделы

Опросы

Какой язык программирования вы считаете наиболее актуальным сегодня?
Всего ответов: 329

Друзья

3D-кино






Найти на сайте:








Об авторе       Контакты      Вопрос-ответ        Хостинг от uCoz