Популярно об ИИ
Недавно, подходя к мосту через Свислочь по ныне названному проспекту Машерова, заметил удивительную вещь. Деревья посажены прямо под воздушной линией электропередач. Вот она, преемственность поколений! То есть мое или предыдущее моему позаботилось, чтобы следующим было не скучно в жизни, чтобы и они нашли, чем заняться. Например, спиливать деревья, дабы те не повреждали ЛЭП по мере своего роста. Многие, возможно, подумали, что ваш покорный слуга — злой. Нет, это еще не злой.
А вот когда меня уговорили оптимизировать код для одной разработки, а потом этот самый код показали, ситуация с деревьями, высаженными под ЛЭП, вдруг снова всплыла в памяти. Я сказал: «Знаете, отдайте лучше этот код на оптимизацию тем преподавателям, которые учили таких программистов». На что был ответ: «Вот ты и научи, как правильно делать!». Поговорили… Вообще, люди новой формации иногда пугают своей непосредственностью. Ну что ж, в данном случае, обсуждая уже не тривиальные рекурсивные алгоритмы, мы будем все разжевывать так, чтобы было понятно даже ребенку...Хм, ну ладно, продвинутому ребенку.
***
Долгое время то, что касалось компьютерных шахматных программ, являлось, чуть ли не государственной тайной за семью печатями. Сейчас ситуация несколько видоизменена, поскольку вместо политического противостояния имеет место противостояние коммерческое. Хороший и быстро функционирующий ИИ в играх — это большая находка.
Шахматы — конкретная, а не абстрактная задача, в ее рамках мы сталкиваемся с большим ветвлением деревьев, количество рассматриваемых позиций растет в экспоненциальной прогрессии. При этом необходимо считать на как можно большую глубину, и тут мы упираемся в физические возможности аппаратных ресурсов. Полный перебор даже на среднюю глубину становится невозможным, поэтому нам необходим вариант выборочного перебора с оценочной функцией и продлением наиболее значимых ветвей. В принципе, шахматы — это классика. И, например, рассматривая алгоритмы поиска чего- либо (маршрутов и т.п.), вы нередко найдете схожие алгоритмы.
***
Что самое интересное, очень часто алгоритмисты ИИ и программисты-проектировщики шахматных программ не пересекаются:), хотя должны. То есть они используют идентичные методы, но называют их по-разному. Еще веселее ситуация обстоит в случаях, когда, например, в книге одной из этих сфер отдельный алгоритмический блок решается громоздко, а в другой сфере для этого же вопроса применяется одна из самых простых реализаций. Примеры? В одном из прошлых материалов я намекнул на это. В оценочной функции, чем ближе ферзь находится к королю соперника, тем большая премия (позиционная оценка) ему начисляется. Так вот, в шахматном программировании, во множестве книг и рекомендаций для определения расстояния даются листинги с выявлением «квадратов», некоторые даже и впрямь решаются считать все по теореме Пифагора, хотя это и очень накладно.
Но в ИИ, а именно в алгоритме поиска А*, который широко применяется в ПО и компьютерных играх, например, для нахождения оптимального маршрута, эту проблему уже давно решили — используют сумму строк и столбцов (можно привязаться и к координатной сетке) между исследуемым узлом и целью. Это всегда работало! В то же время в шахматной сфере очень хорошо решены проблемы выборочного поиска на большую глубину. Кстати, далеко не во всех играх, если вы даете персонажу задание дойти из одной точки карты в другую на приличное расстояние, этот персонаж дойдет. Причем такой неприятный казус можно встретить и в мировых разработках ААА-класса.
Итак, продолжаем нашу тему.
Подробное разъяснение 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], начинается перебор всех возможных для нее полуходов черных.
По существу, если представлять абстрактно, в рамках рекурсивной генерации позиций мы имеем дело с наполнением двумерного массива, если бы глубина равнялась трем — трехмерного, 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. Второй полуход белых. Второе перемещение, функция MakeMove() записывает новую позицию [2].
18. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для черных, maxWhite=300, maxBlack=-100000 и глубина равна 1. 19. Как мы уже договорились, функция GenerateAllMoves(false) генерирует только один ответ.
20. MakeMove() создает новую позицию [2][1].
21. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для белых, maxWhite=300, maxBlack=-100000 и глубина равна 0. 22. Поскольку глубина равна 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<<{
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 тыс.)!
Как вам оптимизация? Хотя, запустите Windows’вский калькулятор в инженерном режиме, наберите 64000 и вычислите факториал (кнопка «n»). Что произойдет? Он практически зависнет! Пример не совсем уместный, поскольку больше демонстрирует все «прелести» реализации компьютерного умножения, но вы можете увидеть, как компьютер работает в экстремальном режиме.
В принципе, для первоначального перебора достаточно глубины 4 или 5, плюс к этому используется множество дополнительных вариантов оптимизации расчетов, хотя нередко это идет вразрез с оптимизацией качества.
Эффективность alpha-beta отсечений очень сильно зависит от порядка поступления ходов. В наихудшем варианте alpha-beta будет считать столько же позиций, сколько и NegaMax, поэтому применяются специальные функции сортировки, которые в первую очередь ставят на обработку ходы, дающие наибольшие приращения оценки.
Также на количество рассчитываемых позиций влияет стратегическая оценка. Например, если мы оцениваем только материал, то вариант без взятий просто вернет отказ, а с учетом позиции придется считать.
На этом пока остановимся.
Продолжение следует…
Кристофер christopher@tut.by
А вот когда меня уговорили оптимизировать код для одной разработки, а потом этот самый код показали, ситуация с деревьями, высаженными под ЛЭП, вдруг снова всплыла в памяти. Я сказал: «Знаете, отдайте лучше этот код на оптимизацию тем преподавателям, которые учили таких программистов». На что был ответ: «Вот ты и научи, как правильно делать!». Поговорили… Вообще, люди новой формации иногда пугают своей непосредственностью. Ну что ж, в данном случае, обсуждая уже не тривиальные рекурсивные алгоритмы, мы будем все разжевывать так, чтобы было понятно даже ребенку...Хм, ну ладно, продвинутому ребенку.
***
Долгое время то, что касалось компьютерных шахматных программ, являлось, чуть ли не государственной тайной за семью печатями. Сейчас ситуация несколько видоизменена, поскольку вместо политического противостояния имеет место противостояние коммерческое. Хороший и быстро функционирующий ИИ в играх — это большая находка.
Шахматы — конкретная, а не абстрактная задача, в ее рамках мы сталкиваемся с большим ветвлением деревьев, количество рассматриваемых позиций растет в экспоненциальной прогрессии. При этом необходимо считать на как можно большую глубину, и тут мы упираемся в физические возможности аппаратных ресурсов. Полный перебор даже на среднюю глубину становится невозможным, поэтому нам необходим вариант выборочного перебора с оценочной функцией и продлением наиболее значимых ветвей. В принципе, шахматы — это классика. И, например, рассматривая алгоритмы поиска чего- либо (маршрутов и т.п.), вы нередко найдете схожие алгоритмы.
***
Что самое интересное, очень часто алгоритмисты ИИ и программисты-проектировщики шахматных программ не пересекаются:), хотя должны. То есть они используют идентичные методы, но называют их по-разному. Еще веселее ситуация обстоит в случаях, когда, например, в книге одной из этих сфер отдельный алгоритмический блок решается громоздко, а в другой сфере для этого же вопроса применяется одна из самых простых реализаций. Примеры? В одном из прошлых материалов я намекнул на это. В оценочной функции, чем ближе ферзь находится к королю соперника, тем большая премия (позиционная оценка) ему начисляется. Так вот, в шахматном программировании, во множестве книг и рекомендаций для определения расстояния даются листинги с выявлением «квадратов», некоторые даже и впрямь решаются считать все по теореме Пифагора, хотя это и очень накладно.
Но в ИИ, а именно в алгоритме поиска А*, который широко применяется в ПО и компьютерных играх, например, для нахождения оптимального маршрута, эту проблему уже давно решили — используют сумму строк и столбцов (можно привязаться и к координатной сетке) между исследуемым узлом и целью. Это всегда работало! В то же время в шахматной сфере очень хорошо решены проблемы выборочного поиска на большую глубину. Кстати, далеко не во всех играх, если вы даете персонажу задание дойти из одной точки карты в другую на приличное расстояние, этот персонаж дойдет. Причем такой неприятный казус можно встретить и в мировых разработках ААА-класса.
Итак, продолжаем нашу тему.
Подробное разъяснение 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], начинается перебор всех возможных для нее полуходов черных.
По существу, если представлять абстрактно, в рамках рекурсивной генерации позиций мы имеем дело с наполнением двумерного массива, если бы глубина равнялась трем — трехмерного, 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. Второй полуход белых. Второе перемещение, функция MakeMove() записывает новую позицию [2].
18. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для черных, maxWhite=300, maxBlack=-100000 и глубина равна 1. 19. Как мы уже договорились, функция GenerateAllMoves(false) генерирует только один ответ.
20. MakeMove() создает новую позицию [2][1].
21. Рекурсивно вызывается Search(), которой сообщается, что расчет должен идти для белых, maxWhite=300, maxBlack=-100000 и глубина равна 0. 22. Поскольку глубина равна 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<<
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 тыс.)!
Как вам оптимизация? Хотя, запустите Windows’вский калькулятор в инженерном режиме, наберите 64000 и вычислите факториал (кнопка «n»). Что произойдет? Он практически зависнет! Пример не совсем уместный, поскольку больше демонстрирует все «прелести» реализации компьютерного умножения, но вы можете увидеть, как компьютер работает в экстремальном режиме.
В принципе, для первоначального перебора достаточно глубины 4 или 5, плюс к этому используется множество дополнительных вариантов оптимизации расчетов, хотя нередко это идет вразрез с оптимизацией качества.
Эффективность alpha-beta отсечений очень сильно зависит от порядка поступления ходов. В наихудшем варианте alpha-beta будет считать столько же позиций, сколько и NegaMax, поэтому применяются специальные функции сортировки, которые в первую очередь ставят на обработку ходы, дающие наибольшие приращения оценки.
Также на количество рассчитываемых позиций влияет стратегическая оценка. Например, если мы оцениваем только материал, то вариант без взятий просто вернет отказ, а с учетом позиции придется считать.
На этом пока остановимся.
Продолжение следует…
Кристофер christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 28 за 2009 год в рубрике программирование
