ITCS - Популярно об ИИ. Сезон 2. Программирование шахмат и логических игр-3 - РАЗРАБОТКА КОМПЬЮТЕРНЫХ ИГР
Сегодня: Понедельник, 05.12.2016, 23:38 (МСК)| Здравствуйте, Гость| Мой профиль | Регистрация | Вход | RSS

Что такое matte painting?

Визуальная среда Flowstone

Устройства с беспроводным питанием

ТВ-тюнеры. Как выбирать?

Adobe Audition 3. Лучшая в 2010-м
Главная » РАЗРАБОТКА КОМПЬЮТЕРНЫХ ИГР

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

24.09.2010

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

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


***


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

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

Дело в том, что в ИИ, а именно, в алгоритме А*-поиска, который широко применяется в ПО и компьютерных играх, например, для нахождения оптимального маршрута, эту проблему уже давно решили — используют сумму строк и столбцов (можно привязаться и к координатной сетке) между исследуемым узлом и целью. Это всегда быстро и эффективно работало! В то же время в шахматной сфере очень хорошо решены проблемы выборочного поиска на большую глубину. И, кстати, далеко не во всех играх, если вы даете персонажу задание дойти из одной точки карты в другую на приличное расстояние, этот персонаж дойдет. Причем, такой неприятный казус можно встретить и в мировых разработках ААА-класса. 
Итак, продолжаем нашу тему. 


Подробное разъяснение NegaMax


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

int Search(bool color, int Depth)
{
//оценка конечной точки
if (Depth == 0) 
return EvaluatePosition(color);
//минимальное 
//значение score
int score=-100000;
PMove = move;
move= GenerateAllMoves(color);
while(move) {
MakeMove(move);
int tmp_score=
-Search(color?false:true, Depth-1, score);
UnMakeMove();
if (tmp_score>score) 
score = tmp_score;
move=move->next;
}
return score;
}

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

Самое главное в рекурсии — это разобраться с ней:). Будем учиться и этому. Давайте рассмотрим вариант с глубиной 2, первыми ходят белые, т.е. вызываем Search(true, 2). С помощью GenerateAllMoves(true) находим все возможные перемещения для белых, например, их найдено 40.  

Запускаем цикл, в рамках которого:

  1. Первый найденный полуход вступает в силу. По терминологии за ход считается ситуация, когда походили обе стороны, при этом стоит понимать, что глубина — это фактически количество рассчитываемых полуходов.
  2. Функция MakeMove() просто меняет расположение фигур на доске после этого полухода (назовем это позицией [1]).  
  3. Рекурсивно вызывается функция Search(), но уже с изменениями, то есть дальнейшие расчеты производятся для черных. Вызов будет аналогичен строке Search(false, 1).
  4. С помощью GenerateAllMoves(false) находим все перемещения для черных в рамках позиции [1], допустим их найдено 41.
  5. Входим в цикл while. 
  6. MakeMove() для первого варианта полухода черных делает новую расстановку (назовем ее позицией [1][1]). После идет рекурсивный вызов Search  с параметрами (true, 0).
  7. Поскольку Depth=0, то мы вызываем функцию оценки EvaluatePosition(), которая оценит позицию [1][1].
  8. Оценка вернется в переменную tmp_score внутри цикла while для черных.
  9. Функция UnMakeMove() возвращает первоначальную позицию [1].
  10. Если tmp_score>-100000, то score=tmp_score.
  11. Переход к вычислению второго варианта перемещения черных.
  12. MakeMove() для второго варианта хода черных делает новую расстановку (назовем ее позицией [1][2])… 
  13. …и так далее пока не просчитаются все варианты 2-го полухода (перемещения черных), с выявлением наиболее выгодного из них.
  14. Как только посчитается весь спектр позиций от [1][1] до [1][41] (мы условились, что якобы в данной ситуации для первого рассчитанного перемещения белых найден 41 вариант перемещений черных), происходит завершение работы рекурсивно вызванной функции, и мы переходим к циклу белых в исходной функции.
  15. Функция UnMakeMove() возвращает первоначальную базовую расстановку, которая была до вызова Search.
  16. Лучший ответ черных запоминается в переменной score. Вызывается следующий ход. Создается расстановка [2], начинается перебор всех возможных полуходов черных для нее. 
  17. По существу, если представлять абстрактно, в рамках рекурсивной генерации позиций мы имеем дело с наполнением двумерного массива, если бы глубина равнялась трем — трехмерного, n — n-мерного. 

Ключевыми в этом алгоритме можно назвать функции: MakeMove(), которая всякий раз меняет расстановку согласно перемещению, и EvaluatePosition(), которая (внимание!!!) считает только конечную точку. 

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

Во-вторых, обратите внимание на то, что наша задача — получить как можно большее значение score для белых. Но вычисление максимального score для черных (расчет максимально адекватного ответа) по результатам каждого полухода белых, ставит ограничения. Это очень тонкий и важный момент, его нужно понимать.


Краткое напоминание


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

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

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

Также еще раз напоминаю, что для минимизации кода мы использовали тернарный оператор «?» в строке color?false:true. «?» — замена конструкции if-then-else. 
И еще одно важное напоминание. Сегодня мы в рамках оценочной функции будем опираться только на материальную (статическую) оценку без позиционной (стратегической). Материальная шкала оценок у нас такая:
  • Пешка — 100.
  • Конь — 300.
  • Слон — 300.
  • Ладья — 500.
  • Ферзь — 900.
  • Король — 10000.


Перепишем нашу функцию


Для более точного объяснения момента взаимодействия оценок для черных и белых давайте введем переменные maxWhite и maxBlack, которые высчитывают максимумы оценочной функции для белых и черных.
 
int Search (bool color, int Depth, 
int maxWhite, int maxBlack) 
{
if (Depth == 0) 
return EvaluatePosition(color); 
int score=-100000;
PMove move= GenerateAllMoves(color);
while(move) 
{
MakeMove(move);
int tmp_score=
-AlphaBeta(color?false:true, Depth-1, maxWhite, maxBlack);
UnMakeMove(move);
//…………
//блок if
if (tmp_score>score)
{score=tmp_score; 
if(color)
{if (score> maxWhite) 
maxWhite = score;}
else
{if (score> MaxBlack) 
MaxBlack = score;}
}
//конец блока if
//…………
move=move->next;
}
return score;
}

Первый вызов функции будет, например, таким: Search(true, 2, -100000, -100000);.  

В принципе, от предыдущего кода отличий не много, разве что мы добавили maxWhite и maxBlack в аргументы основной функции Search() и сделали отдельный блок if, который нам после понадобится для введения оптимизации перебора.

Разберитесь внимательно с написанным кодом, потому как многих сейчас ждет настоящая головоломка. Отмечу лишь, что в рамках первых полуходов переменная maxBlack всегда будет равна -100000, потому как мы здесь ей ничего не присваиваем. При расчете второго полухода рекурсивно вызванной функции сообщается текущее значение maxWhite по результатам вычислений, уже прошедших в рамках первого полухода, а все вычисления ведутся с переменной  maxBlack. 

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

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

  1. При первом вызове формируется массив из всех возможных перемещений для белых — GenerateAllMoves(true);. 
  2. Запускается цикл. 
  3. Первое перемещение, функция MakeMove() записывает новую позицию [1].
  4. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для черных, maxWhite=-100000, maxBlack=-100000 и глубина равна 1.
  5. Как мы уже договорились, функция GenerateAllMoves(false) генерирует только один ответ.
  6. MakeMove() создает новую позицию [1][1]. 
  7. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для белых, maxWhite=-100000, maxBlack=-100000 и глубина равна 0.
  8. Поскольку глубина равна 0, запускается оценочная функция применительно к последней позиции [1][1], созданной MakeMove(). Допустим, в рамках сложившейся ситуации у белых преимущество, и функция EvaluatePosition(true) отдает результат 300.
  9. Начинается разматывание стека. Мы переходим в тело цикла расчета полухода черных, то есть в предыдущую функцию Search(). Там временная переменная tmp_score получает значение 300 со знаком минус. 
  10. Функция UnMakeMove() возвращает позицию к первому полуходу, то есть восстанавливает позицию [1].
  11. Если -300>-100000, тогда переменная score=-300.
  12. Если цвет (color) не true, то есть, это не белые, смотрим тело else{}. 
  13. Если значение score>-100000, тогда переменной maxBlack присваивается значение score, т.е. -300.
  14. По завершении работы функция Search() возвращает значение score.
  15. Переходим в первую Search(). Переменной tmp_score присваивается значение –(-300), т.е. 300. 
  16. … ля-ля тополя, возврат к исходной позиции, maxWhite = 300.
  17. А теперь интересное. 
  18. Второй полуход белых… Второе перемещение, функция MakeMove() записывает новую позицию [2].
  19. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для черных, maxWhite=300, maxBlack=-100000 и глубина равна 1.
  20. Как мы уже договорились, функция GenerateAllMoves(false) генерирует только один ответ.
  21. MakeMove() создает новую позицию [2][1]. 
  22. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для белых, maxWhite=300, maxBlack=-100000 и глубина равна 0.
  23. Поскольку глубина равна 0, запускается оценочная функция применительно к последней позиции [2][1], созданной MakeMove(). Допустим, в рамках сложившейся ситуации у белых преимущество на пешку, и функция EvaluatePosition(true) отдает результат 100.

И вот тут самое интересное. Дело в том, что 100 меньше 300 и расчет этого хода ничего для роста maxWhite в первой функции не даст. То есть, эта ветвь вычислений не нужна. Как ее убрать?
 
Изменим в коде наш блок if на следующий:

//…………
//блок if
if (tmp_score>score)
{score=tmp_score; 
if(color)
{if (score> maxWhite) 
maxWhite = score;
if (-maxWhite<=maxBlack)
return maxWhite;
}
else
{if (score> MaxBlack) 
MaxBlack = score;
if (-maxBlack<=maxWhite)
return maxBlack;
}
}
//конец блока if
//…………

То есть, мы вписали строки сравнения if (-maxWhite<=maxBlack) и if (-maxBlack<=maxWhite). maxWhite и maxBlack — инвертированные величины, поэтому при их сравнении мы одну из них берем со знаком минус. При столкновении с одним из таких условий, например, как в случае с нашим вторым полуходом, второй рекурсивный вызов функции вернет значение maxBlack, равное -100.
И чем это выгодно? Если черные отвечают одним перемещением, то ничем, а если 40, то выход из функции по условию if (-maxBlack<=maxWhite) return maxBlack; значительно сокращает расчеты. Если, например, при втором варианте полухода черных появляется прецедент выполнения такого условия, то дальше считать не имеет смысла, и мы возвращаемся из функции, не досчитав остальные 38 вариантов. 
maxWhite и maxBlack имеют другие названия — alpha и beta. А метод, который мы сейчас рассмотрели, называется alpha-beta отсечениями (или просто alpha-beta алгоритмом). 
Обратите внимание на то, что у нас отсекаются и те ветви, в которых максимумы сравниваются. То есть, например, если расчеты идут на определенную глубину, оценка у нас только материальная и нет никаких взятий — ветвь упраздняется.  
 

Alpha-beta отсечения


В предыдущем примере мы раздули код, но это только для лучшего понимания происходящего. Обычно рекурсия пишется очень емко, поэтому классический alpha-beta алгоритм выглядит так:

int AlphaBeta (bool color, int Depth, 
int alpha, int beta) 
{
if (Depth == 0) 
return EvaluatePosition(color);
move= GenerateAllMoves(color);
while(move && alpha<beta) 
{
MakeMove(move);
int tmp_score=
-AlphaBeta(color?false:true, Depth-1, -beta, -alpha);
UnMakeMove(move);
if (tmp_score>alpha) 
alpha=tmp_score;
move=move->next;
}
return alpha;
}

Вызываем функцию в первый раз примерно так: AlphaBeta(true, 4, -100000, 100000), где true — ходить должны белые, 4 — глубина, maxWhite =-100000 (минимальное недостижимое значение), maxBlack = 100000 (максимальное недостижимое значение). При рекурсивных вызовах alpha и beta меняется местами с инверсией знаков. То есть, данный алгоритм не совсем прост в логическом осмыслении. 

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

Работа данного алгоритма практически ничем не отличается от предыдущего, он просто по-другому представлен. 

Диапазон -1000000 — 100000 является окном функции поиска AlphaBeta. Если мы укажем другие числа, то поиск будет производиться в другом же диапазоне.


В чем выгода?


Точность алгоритма alpha-beta такая же, как и при полном переборе (NegaMax).

Alpha-beta отсечения в варианте, близком к идеальному, построят гораздо меньшее дерево перебора, количество рассматриваемых позиций может равняться корню из общего числа позиций при NegaMax. Много это или мало? 

Допустим, мы говорили, что глубина 6 при NegaMax при среднем числе возможных перемещений из одной позиции 40, потребует рассмотрения 40х40х40х40х40х40 (т.е. 40 в 6-й степени), это число равно 4 млрд. 96 млн. позиций. Alpha-beta оптимизация при варианте, близком к идеальному, может уменьшить это число до 64000 (64 тыс.)!

Ну, как вам оптимизация? Хотя… 64000. Запустите Windows’вский калькулятор в инженерном режиме, наберите 64000 и вычислите факториал (кнопка «n!»). Что произойдет? Он практически зависнет. Пример не совсем уместный, поскольку больше демонстрирует все «прелести» реализации компьютерного умножения, но вы можете увидеть, как компьютер работает в экстремальном режиме. 

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

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

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

На этой красивой ноте пока все.


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




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

Разделы

Опросы

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

Друзья

3D-кино






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








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