Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

Примечательно, что с математической точки зрения оценочная функция, выбранная Стрейчи, является полиномом: f = M_c – M_p + 4K_c – 4K_p, где M_c — число шашек машины, M_p — число шашек противника, K_c — число дамок машины, K_p — число дамок противника. Все позиции в шашках, согласно теореме Цермело, должны быть либо выигрышными, либо проигранными, либо ничейными при идеальной игре обеих сторон. В примере с крестиками-ноликами мы использовали для выигрышной позиции оценку «1», для ничейной — «0» и для проигрышной — «–1». Такая оценка очевидным образом связана с числом очков, которое игрок получит при соответствующем результате, s = (v + 1) / 2, где s — число очков, а v ∈ {−1, 0, 1} — оценка, которую мы использовали в крестиках-ноликах. Оценка со знаком позволяла нам легко получить значение оценки для противника, достаточно было просто поменять у оценки знак: v_c = –v_p, вместо того чтобы выполнять менее наглядную операцию вычитания оценки из единицы: s_c = 1 – s_p, но это в некоторой степени дело вкуса.

В случае эвристической оценки мы в подавляющем большинстве случаев не уверены в её точности. Из-за этой неуверенности оценка приобретает вероятностный характер. Казалось бы, разумно использовать в качестве оценки математическое ожидание количества очков: 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 — основание натурального логарифма.

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

Всё дело в том, что именно такой способ оценки позиции, при котором мы просто представляем её в виде суммы оценок каждого взятого по отдельности признака, является более привычным для людей. В любом шашечном или шахматном учебнике вы найдёте способы оценки, сформулированные именно в таком виде. Например, шахматный учебник скажет, что слон и конь сто́ят примерно по три пешки, ладья — пять, а ферзь — девять. Такой способ оценки позиции является частью старинной традиции. Ещё итальянские шахматные мастера XVII–XVIII вв. пытались оценить «стоимость» фигур в пешках, а их последователи стали аналогичным образом оценивать и различные позиционные факторы. В шашках тоже удобно принять за эталон «стоимость» одной шашки и исчислять «стоимость» дамки, а также различных позиционных элементов оценки, сравнивая их с принятым эталоном. В XX в. машины учились играть в игры у людей и не слишком часто преподавали уроки людям, поэтому и развитие ИИ было в очень большой степени основано на человеческих экспертных знаниях. В 1967 г. Сэмюэл так охарактеризовал современное ему положение вещей: «…при нынешнем уровне развития знаний единственным практическим подходом будет, даже при наличии помощи со стороны цифрового компьютера, разработка эвристик, основанных на копировании (тут автор применяет глагол to ape, т. е. дословно «собезьянивании». — С. М.) поведения человека» [556].

Итак, программа Стрейчи стремилась выбрать ход, который максимизировал бы значение оценочной функции при наилучших ответных действиях оппонента. Такой метод обычно называют минимаксом, поскольку, рассматривая собственные ходы (на нечётных уровнях дерева), программа выбирает ход с максимальной оценкой, а рассматривая ходы оппонента (на чётных уровнях дерева), выбирает ходы, минимизирующие оценку. Если на каждом уровне дерева менять знак оценки на противоположный, то можно обойтись одной только максимизацией. Такую модификацию минимакса обычно называют негамаксом.

Изобретение минимакса часто приписывают фон Нейману, ведь он рассматривается в одной из его ранних работ — «К теории стратегических игр» (Zur Theorie der Gesellschaftsspiele), написанной в 1928 г. [557] В действительности приоритет в данном случае, по всей видимости, принадлежит Сирио Форелю Эмилю Борелю, который сформулировал отдельные положения теории игр раньше фон Неймана и независимо от него [558]. При некоторой фантазии можно говорить и о приоритете Бэббиджа [559], который предложил похожий алгоритм для выбора хода в крестиках-ноликах. Как бы то ни было, и Борель, и фон Нейман, и Бэббидж отталкивались от окончательных оценок в терминальных узлах дерева перебора, использовать же усечённое дерево и приближённые оценки первым предложил Норберт Винер [560].

Максимальная скорость перебора, осуществляемого программой Стрейчи в 1950-е гг., могла достигать, по-видимому, нескольких десятков, быть может ста позиций в секунду, что позволяло программе за разумное время анализировать варианты на глубину три-четыре полухода [561]. Конечно, при столь неглубоком анализе вариантов и крайне примитивной оценочной функции рассчитывать на сильную игру программы не приходилось. Стрейчи не уделял особого внимания дальнейшему развитию алгоритмов, заложенных в программу, и следующий этап развития компьютерных шашек был связан уже с программой Сэмюэла.

3.4.2 Продолжение. Шашечная программа Артура Сэмюэла

Программа, описанная Сэмюэлом в статье 1967 г., отличается от программы Стрейчи примерно так же, как ВАЗ-2101 («копейка», которую, к слову, начали производить тремя годами позже) от крестьянской телеги. В программе Сэмюэла уже можно разглядеть многие черты современных шашечных и шахматных программ.