Охота на электроовец. Большая книга искусственного интеллекта - Сергей Сергеевич Марков
В случае эвристической оценки мы в подавляющем большинстве случаев не уверены в её точности. Из-за этой неуверенности оценка приобретает вероятностный характер. Казалось бы, разумно использовать в качестве оценки математическое ожидание количества очков: s ∈ [0; 1], s = 1 × p(W) + 0,5 × p(D), где p(W) — вероятность победы, p(D) — вероятность ничьей, а для удобства можно было бы преобразовать оценку к виду v ∈ [–1; 1], чтобы работал трюк с переменой знака. Однако вместо этого создатели первых шашечных и шахматных программ выбрали на первый взгляд весьма неудобную полиномиальную форму оценки f, где она может принимать большие по модулю положительные и отрицательные значения. Получается, что позиция, в которой у машины все 12 шашек стали дамками, а у противника не осталось ни одной шашки, будет иметь оценку, равную, например, 48, а если бы дамки оценивались не в 4 единицы, а в 40, то мы получили бы число 480. Но каков смысл этого числа? Каким образом оно связано с ожидаемым результатом партии?
На самом деле такая аддитивная оценка, безусловно, связана с вероятностью победы каждой из сторон. Если бы мы взяли программу Стрейчи и заставили её разыграть астрономическое количество случайных позиций, а затем построили график, в котором по оси x отложили оценку позиции f, а по оси y — среднее количество очков, набранных в играх, начатых с позиции с оценкой x, то получили бы график, напоминающий график логистической функции: s(x) = 1 / (1 + e–kx), где k — некоторый масштабный коэффициент, e — основание натурального логарифма.
Рис. 60. График зависимости вероятности выигрыша от оценки позиции
То есть выбранный Стрейчи способ оценки всё-таки был связан с вероятностью победы, хотя и неочевидным образом. Но к чему такие сложности, почему бы не использовать в качестве оценки собственно вероятность?
Всё дело в том, что именно такой способ оценки позиции, при котором мы просто представляем её в виде суммы оценок каждого взятого по отдельности признака, является более привычным для людей. В любом шашечном или шахматном учебнике вы найдёте способы оценки, сформулированные именно в таком виде. Например, шахматный учебник скажет, что слон и конь сто́ят примерно по три пешки, ладья — пять, а ферзь — девять. Такой способ оценки позиции является частью старинной традиции. Ещё итальянские шахматные мастера XVII–XVIII вв. пытались оценить «стоимость» фигур в пешках, а их последователи стали аналогичным образом оценивать и различные позиционные факторы. В шашках тоже удобно принять за эталон «стоимость» одной шашки и исчислять «стоимость» дамки, а также различных позиционных элементов оценки, сравнивая их с принятым эталоном. В XX в. машины учились играть в игры у людей и не слишком часто преподавали уроки людям, поэтому и развитие ИИ было в очень большой степени основано на человеческих экспертных знаниях. В 1967 г. Сэмюэл так охарактеризовал современное ему положение вещей: «…при нынешнем уровне развития знаний единственным практическим подходом будет, даже при наличии помощи со стороны цифрового компьютера, разработка эвристик, основанных на копировании (тут автор применяет глагол to ape, т. е. дословно «собезьянивании». — С. М.) поведения человека»[556].
Итак, программа Стрейчи стремилась выбрать ход, который максимизировал бы значение оценочной функции при наилучших ответных действиях оппонента. Такой метод обычно называют минимаксом, поскольку, рассматривая собственные ходы (на нечётных уровнях дерева), программа выбирает ход с максимальной оценкой, а рассматривая ходы оппонента (на чётных уровнях дерева), выбирает ходы, минимизирующие оценку. Если на каждом уровне дерева менять знак оценки на противоположный, то можно обойтись одной только максимизацией. Такую модификацию минимакса обычно называют негамаксом.
Рис. 61. Упрощённая диаграмма, показывающая, как оценки поднимаются по дереву возможных ходов, чтобы получить наилучший следующий ход. Процесс оценки начинается на уровне (3), где машина выбирает ветку с наиболее положительной оценкой. Далее на уровне (2) от противника ожидается выбор ветки с наименьшей оценкой, и на уровне (1) машина выбирает ветку с наибольшей оценкой
Изобретение минимакса часто приписывают фон Нейману, ведь он рассматривается в одной из его ранних работ — «К теории стратегических игр» (Zur Theorie der Gesellschaftsspiele), написанной в 1928 г.[557] В действительности приоритет в данном случае, по всей видимости, принадлежит Сирио Форелю Эмилю Борелю, который сформулировал отдельные положения теории игр раньше фон Неймана и независимо от него[558]. При некоторой фантазии можно говорить и о приоритете Бэббиджа[559], который предложил похожий алгоритм для выбора хода в крестиках-ноликах. Как бы то ни было, и Борель, и фон Нейман, и Бэббидж отталкивались от окончательных оценок в терминальных узлах дерева перебора, использовать же усечённое дерево и приближённые оценки первым предложил Норберт Винер[560].
Максимальная скорость перебора, осуществляемого программой Стрейчи в 1950-е гг., могла достигать, по-видимому, нескольких десятков, быть может ста позиций в секунду, что позволяло программе за разумное время анализировать варианты на глубину три-четыре полухода[561]. Конечно, при столь неглубоком анализе вариантов и крайне примитивной оценочной функции рассчитывать на сильную игру программы не приходилось. Стрейчи не уделял особого внимания дальнейшему развитию алгоритмов, заложенных в программу, и следующий этап развития компьютерных шашек был связан уже с программой Сэмюэла.
3.4.2 Продолжение. Шашечная программа Артура Сэмюэла
Программа, описанная Сэмюэлом в статье 1967 г., отличается от программы Стрейчи примерно так же, как ВАЗ-2101 («копейка», которую, к слову, начали производить тремя годами позже) от крестьянской телеги. В программе Сэмюэла уже можно разглядеть многие черты современных шашечных и шахматных программ.
Для начала Сэмюэл выбрал для оценки обычных шашек и дамок величины, относящиеся друг к другу как 3 : 4, что более точно соответствовало человеческим экспертным знаниям. Помимо подсчёта шашек и дамок на доске, Сэмюэл добавил в оценочную функцию множество позиционных факторов. Например, учитывались мобильность (количество потенциальных ходов у каждого из игроков без учёта взятий) и контроль каждой из сторон над различными участками поля. Сама игра была разделена на шесть стадий, в каждой из которых значения оценок каждого из факторов могли быть разными. Кроме того, оценочная функция Сэмюэла учитывала сочетания некоторых факторов, а также тот факт, что в зависимости от очерёдности хода эти сочетания могут иметь различную оценку. В результате итоговая оценочная функция имела более 10 000 параметров. Хотя Сэмюэл и использовал фиксированный набор факторов, он замахнулся ещё и на автоматический подбор их значений. Действительно, установить значения для такого внушительного набора параметров экспертным путём представлялось малореальным.
Однако для автоматической
