Summary_6_Galkina_Shramov (лекции), страница 2

Подсчёт происходит достаточно быстро, но в3реальных играх глубина дерева достигает 10, а коэффициент ветвления — 14-15 и больше.Мы знаем, что количество статических параметров растёт экспоненциально в зависимости от глубины дерева. Как показывает опыт, 7-8 уровней недостаточно, чтобы создатьсильного игрока. Но если спуститься до 15-16 уровня, то такой искусственный интеллектспособен обыграть чемпиона мира. Поэтому важно уметь доходить до максимально возможной глубины дерева игры, вычисляя как можно меньше статических оценок.Альфа-бета отсечениеПри рассмотрении метода ветвей и границ мы старались оптимизировать его такимобразом, чтобы не просматривать некоторые поддеревья в дереве поиска.

Мы можем поступать подобным образом и с деревом игры, не вычисляя лишние статические оценки.Рассмотрим то же самое дерево игры, в котором первый ход делает максимизирующийигрок, только в этот раз будем вычислять статические оценки по очереди (рис. 3). Перваяиз них равна двум, поэтому минимизирующий игрок, находясь на среднем уровне дерева,знает, что итоговое значение оценки в узле не может быть больше 2. Следующее значениеравно 7, это больше 2, поэтому теперь минимизирующий игрок может быть уверен, чтозначение в левой ветви на среднем уровне в точности равно 2. Как только получено точноезначение, максимизирующий игрок в корне дерева может считать, что оценка итоговогохода будет больше либо равна 2.Рис.

3: Пример работы алгоритма минимакс с альфа-бета отсечениемВычислим оценку в следующем листе. Она равна 1, поэтому в правой ветви минимизирующий игрок получит значение не больше, чем 1. Нужно ли производить вычислениядальше? С точки зрения максимизирующего игрока становится видно, что если он пойдёт по левой ветви, он может получить итоговую оценку, равную 2. Если же он пойдётпо правой, то она будет не больше 1.

Таким образом, для принятия решения не нужновычислять значение оценки в последнем листе. Совершенно не важно, чему на самом делеравно это значение, 8, 1000, бесконечность или минус бесконечность.Итак, альфа-бета алгоритм является «надстройкой» над алгоритмом минимакс и позволяет отсекать ветви в дереве игры. Важно понять, что это не альтернатива алгоритму минимакс, а его оптимизация.Рассмотрим более сложный пример, чтобы увидеть те особенности альфа-бета отсечения, которые проявляются на деревьях глубины 4 и больше. Дерево игры приведенона рисунке 4.

Красным цветом выделены те листья, в которых происходило вычислениестатической оценки. В левой части дерева алгоритм работает аналогично предыдущемупримеру, при этом 3 из 8 значений не были вычислены из-за отсечения. В результатеполучена оценка для корневой вершины: значение в ней не может быть меньше 7.4Рис. 4: Пример работы алгоритма минимакс с альфа-бета отсечением на дереве глубины 4В правой части поддерева первой будет вычислена оценка, равная 1.

Поэтому минимизирующий игрок может гарантированно получить значение, не превышающее 1, если играпойдёт по этой ветви. Но в корневой вершине уже есть оценка, т. е. максимизирующийигрок знает, что может гарантированно сделать ход с оценкой, равной 7. До этого момента в ходе работы алгоритма сравнивались значения оценок только на соседних уровняхдерева. В данной ситуации мы сравниваем оценки, разделённые несколькими уровнями,но всё равно можем сделать вывод, что дальнейшее рассмотрение узла бессмысленно.

Втакой ситуации говорят, что происходит глубокое отсечение. Дальнейших ход работыалгоритма и его результат также представлены на рисунке 4.Постепенное углублениеРанее мы предполагали, что коэффициент ветвления не изменяется. Но на самом делеон может изменяться в ходе игры в зависимости от состояния игрового поля. Вы можете посчитать, сколько вычислений придётся сделать за 2 минуты или сколько временитратится в среднем на один ход. Но вы не можете точно сказать, насколько глубоко выможете пройти по дереву игры, потому что это зависит от хода самой игры.Когда программы для игр только начали появляться, они пренебрегали многими вычислениями и вычисляли ход за пару секунд.

Но они могли бы пойти совершенно подругому, если бы использовали все вычислительные возможности. С другой стороны, онимогли бы усердно вычислять ходы, но через несколько минут у них всё ещё не было быответа, поэтому они делали случайный ход. Это не очень хорошая ситуация, но это происходило, потому что программа не знала, насколько глубоко может зайти в дереве игры.Рассмотрим дерево игры глубины d и коэффициентом ветвления b. На нижнем уровнеdb листьев.

Если мы пока забудем про альфа-бета отсечение, то нам придётся вычислятьвсе bd статические оценки. На уровне выше их будет bd−1 , то есть в b раз меньше. Еслинам не получится продвинуться в вычислениях дальше предпоследнего уровня, нам нужнагарантия, что в результате всё равно получится верный ход. Если коэффициент ветвленияравен 10, то можно вычислить оценки ходов на предпоследнем уровне, и это составляет10% от вычислений, которые необходимо было бы произвести на нижнем уровне. А еслиокажется, что коэффициент ветвления настолько велик, что мы не сможем вычислитьзначения и на предпоследнем уровне? Тогда у нас должен быть готов ответ ещё на уровеньраньше.5Таким образом, нашей целью является наличие хода в любой момент времени.

Дляэтого необходимо производить вычисления в вершинах на каждом уровне. Всего получимS = 1 + b + ... + bd оценок, которые нужно вычислить. Насколько большое это число?d −1Его можно представить в виде bb−1, что приближенно равно bd−1 . С учётом этого приближения можно сказать, что количество вычислений, необходимых для гарантированногоналичия ответа на любом уровне, примерно равно количеству вычислений на предпоследнем уровне. Эта идея получила название «постепенное углубление».ЗаключениеПовторим основные идеи и принципы, которые мы обсудили ранее:1. Альфа-бета отсечение позволяет не вычислять значительное количество статических оценок и даже не генерировать лишние ходы. Они всё равно не привели бы кответу.

Это является не альтернативой алгоритму минимакс, а его оптимизацией,дающей от же ответ.2. Последовательное углубление позволяет получить ответ, на каком бы уровне дереваигры не происходили вычисления.3. Эта идея может быть рассмотрена как простой частный случай алгоритма с отсечением по времени. Такой алгоритм может дать ответ как только он понадобится,в любой момент времени.Итак, программы, играющие в игры, работают на основе алгоритма минимакс с альфабета отсечением и постепенным углублением. Следующим шагом к увеличению производительности является использование альфа-бета отсечения при вычислении промежуточныхчастей дерева игры при постепенном углублении.То, как работал Deep Blue, не сильно отличалось от рассмотренных нами алгоритмов. В 1997 году он вычислял примерно 200 миллионов статических оценок в секундуи опускался по дереву игры на 14-16 уровней. В нём применялись алгоритм минимакс сальфа-бета отсечением и последовательное углубление, отдельно учитывались ситуацииначала и конца игры, использовались параллельные вычисления, а также неравномерноедерево игры.

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