Summary_6_Galkina_Shramov (лекции)

Галкина Екатерина, Шрамов ГеоргийLecture 6: Search: Games, Minimax, and Alpha-BetaВведениеПримерно в 1963 году известный в МТИ философ по имени Хьюберт Дрейфус написалстатью, в которой был заголовок «Компьютеры не умеют играть в шахматы». Его послеэтого пригласили в лабораторию искусственного интеллекта, чтобы сыграть в шахматы смашиной Гринблатта. И, конечно, он проиграл.После этого Саймур Павитт написал опровержение известной статьи Дрейфуса, в котором был заголовок «Дрейфус тоже не умеет играть в шахматы».

Как ни странно, Дрейфусмог бы быть прав и был бы прав, если бы написал, что компьютеры не умеют играть вшахматы таким же образом, как и люди.Как бы то ни было, примерно в 1968 году шахматист по имени Дэвид Леви поспорилс выдающимся основателем искусственного интеллекта Джоном Маккарти, что ни одинкомпьютер не сможет обыграть чемпиона мира в течение следующих 10 лет. И спустя 5 летМаккарти сдался, потому что уже стало понятно, что ни один компьютер не выиграет так,как хочет Маккарти, то есть играя в шахматы тем же образом, как это делает человек.Но спустя 30 лет, в 1997 году, Deep Blue обыграл чемпиона мира, и интерес к шахматамвнезапно упал.Но мы сегодня будем говорить об играх, поскольку в ходе игры возникают элементы,которые моделируют некоторый вид интеллекта. И если мы хотим понять что такое интеллект в общем случае, мы хотим понять и этот вид интеллекта в частности.Возможные подходы к созданию искусственного интеллекта для игрРассмотрим несколько возможных подходов к созданию искусственного интеллекта,способного играть в игры, например в шахматы.Первый подход состоит в том, чтобы компьютер описывал игровую доскутак же, как и человек, с учётом пешечной структуры, безопасности короля, правильного момента для рокировки и т.

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

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

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

У шахматной доски есть множество характеристик. Обозначимих f1 , f2 , .., fn . Применим к этим характеристикам функцию и получим статическую оценку s = g(f1 , .., fn ). Она называется статической, поскольку не исследуются все возможныеслучаи. Вы просто смотрите на доску, оценивая безопасность короля, пешечную структуруи т. д. Каждое из этих свойств характеризуется числом, которое является аргументом оценочной функции, которая также возвращает число.

Это число и является оценкой конфигурации игровой доски с вашей точки зрения. Обычно в качестве функции g используетсялинейный полином, называемый линейной оценочной функцией: g = c1 f1 + c2 f2 + ... + cn fn ,где ci — константы.Таким образом, мы можем использовать эту функцию, чтобы получить числа, характеризующие каждую из возможных игровых ситуаций, и выбрать наибольшее из этихчисел.

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

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

При условии, что коэффициент ветвления постоянный, количество терминальных узлов будет равно bd .Рис. 1: b = 2, d = 3, bd = 8Попробуем оценить количество вычислений в алгоритме полного перебора для игры вшахматы. Каждый игрок в среднем делает 50 ходов, поэтому глубина дерева игры равнапримерно 100. Коэффициент ветвления зависит от стадии игры и многого другого, но всреднем равен 14-15. Если бы он был равен 10, то число листьев было бы 10100 .

Для удобства вычисления оценим число листьев как 10120 , поскольку на самом деле коэффициентветвления больше 10. Именно столько вычислений статического параметра пришлось бысделать, если использовать алгоритм полного перебора. Насколько это возможно сделатьсегодня, с использованием облачных вычислений и т. п.?Считается, что во вселенной порядка 1080 атомов. Количество секунд в году примерно равно π107 , а в каждой секунде 109 наносекунд. С начала истории вселенной прошло2приблизительно 1010 лет. В итоге получаем 1080+7+9+10 = 10106 наносекунд в истории вселенной.Итак, если бы все атомы во вселенной вычисляли статические оценки каждую наносекунду с момента Большого взрыва, они бы до сих пор отставали на 14 порядков.

Очевидно,что переборный алгоритм в данном случае бесполезен.Далее мы будем рассматривать ещё один подход. Он состоит в том, чтобы оценивать не один уровень, а попытаться заглянуть настолько далеко, насколько этовозможно. Эта идея была предложена несколько раз, в том числе Клодом Шенноном иАланом Тьюрингом.Алгоритм минимаксРассмотрим простое дерево игры с коэффициентом ветвления и глубиной равнымидвум (рис. 2). Числа в листьях дерева означают оценку игрового поля с точки зрения игрока, который делает первый ход.

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

Аналогично для соседнейветви: минимизирующий игрок выберет ход с оценкой 1, а не 8. Итак, мы взяли значенияс последнего уровня и получили оценки ходов на среднем уровне. Мы можем продолжитьделать то же самое.Рис. 2: Пример работы алгоритма минимаксТеперь очередь максимизирующего игрока делать ход. Если он пойдёт по левой ветви,то оценка хода равна 2, по правой ветви — 1. Таким образом, игрок пойдёт по левой ветви,и в итоге игра закончится с конфигурацией, оценённой значением 2. Это не максимальноеи не минимальное значение, но игроки соревнуются друг с другом, играя в состязательнуюигру, поэтому и не рассчитывают получить эти значения.В общем случае алгоритм минимакс работает так: вычисляются статические оценки,сравниваются друг с другом и сохраняются на следующем уровне, пока не будет полученозначение в корне дерева.Если запустить программу для дерева игры глубиной 4 и коэффициентом ветвления 2,то будет подсчитано 16 статических значений.