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

Для начала Сэмюэл выбрал для оценки обычных шашек и дамок величины, относящиеся друг к другу как 3 : 4, что более точно соответствовало человеческим экспертным знаниям. Помимо подсчёта шашек и дамок на доске, Сэмюэл добавил в оценочную функцию множество позиционных факторов. Например, учитывались мобильность (количество потенциальных ходов у каждого из игроков без учёта взятий) и контроль каждой из сторон над различными участками поля. Сама игра была разделена на шесть стадий, в каждой из которых значения оценок каждого из факторов могли быть разными. Кроме того, оценочная функция Сэмюэла учитывала сочетания некоторых факторов, а также тот факт, что в зависимости от очерёдности хода эти сочетания могут иметь различную оценку. В результате итоговая оценочная функция имела более 10 000 параметров. Хотя Сэмюэл и использовал фиксированный набор факторов, он замахнулся ещё и на автоматический подбор их значений. Действительно, установить значения для такого внушительного набора параметров экспертным путём представлялось малореальным.

Однако для автоматической подстройки нужна была обучающая выборка. Для того чтобы её создать, примерно 250 000 позиций из игр шашечных мастеров было выбито на перфокартах, а затем перенесено на магнитную ленту. Для каждой позиции был отмечен ход, сделанный игроком (использовались только позиции с ходами не проигравших партию игроков). Затем Сэмюэл использовал весьма нетривиальную процедуру, включающую специальные способы сглаживания значений параметров, для подбора таких их значений, чтобы при переборе на один полуход в глубину его программа как можно чаще «угадывала» ходы, сделанные мастерами (в случае взятий глубина перебора могла увеличиваться). Сеанс обучения длился около десяти часов.

Для оценки качества предсказания Сэмюэл использовал простую метрику, напоминающую коэффициент корреляции: C = (L – H) / (L + H), где L — суммарное количество всех возможных ходов, которые программа оценила ниже, чем «правильный» ход, сделанный мастером, H — суммарное количество всех возможных ходов, которые программа оценила выше, чем ход, сделанный мастером. Таким образом, при полном угадывании программой ходов мастера метрика C будет равна «1», при полном неугадывании — «–1», а при случайной оценке ходов — «0».

Хотя отдельные ходы мастеров могли быть ошибочными либо имели равные им по силе альтернативы, Сэмюэл считал, что при достаточно большом объёме выборки это не будет являться серьёзной проблемой. В результате экспериментов по подстройке параметров автору удалось получить значение C = 0,26 при использовании оценочной функции, учитывающей значение каждого из факторов по отдельности, и C = 0,48 для функции, использовавшей сочетания факторов. По оценке Сэмюэла, подобранные параметры позволяли программе при переборе в глубину на один полуход в 64% случаев ставить ход мастера по оценке на первое или второе место [562].

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

Ещё одним радикальным нововведением стало применение так называемого альфа-бета-отсечения [563]. Этот метод был в нескольких разных модификациях независимо открыт и развит в разное время целым рядом исследователей. К их числу относятся Джон Маккарти, который впервые выдвинул идею на ставшей впоследствии знаменитой Дартмутской конференции 1956 г.; Аллен Ньюэлл, Герберт Саймон и Клифф Шоу, описавшие в 1958 г. алгоритм перебора шахматной программы, использующей односторонний вариант альфа-бета-отсечения; Александр Брудно, в 1963 г. независимо от американцев разработавший этот метод (под названием «метод граней и оценок») и формально доказавший его корректность; Джеймс Слейгл, Филип Бурский, Джон Диксон и сам Сэмюэл, которые описали метод в своих статьях конца 1960-х, и, наконец, Дональд Кнут и Рональд Мур, уточнившие определение и посвятившие альфа-бета-отсечению в 1974 г. отдельное объёмное исследование [564].

Основная идея метода заключается в том, что в некоторых случаях нам не нужно знать точную оценку того или иного варианта в дереве перебора, достаточно лишь установить, что эта оценка выше или ниже определённой границы. Например, программа проанализировала некоторый ход X в определённой позиции и обнаружила, что он приводит к выигрышу шашки. Анализируя альтернативный ход Y, она обнаруживает, что у противника есть ответный ход, который приводит к ничейной позиции. В таком случае анализ всех остальных возможных ответов противника на ход Y избыточен: да, может быть, у противника есть ещё более сильный ответ, который, например, приводит к потере машиной шашки, но это уже совершенно не важно, ведь ход Y уже был опровергнут. Верхняя граница оценки (beta) для одного игрока является взятой с противоположным знаком нижней границей оценки (alpha) для второго игрока, и наоборот. Таким образом, процедура перебора получает в качестве параметров величины alpha и beta и осуществляет поиск внутри «окна», задаваемого этими параметрами. Если в ходе перебора машине всегда везло и первый рассмотренный ход в каждом из узлов дерева перебора оказывался действительно сильнейшим, то вместо рассмотрения N позиций в ходе перебора нам потребуется рассмотреть их только около

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

Помимо альфа-бета-отсечения, программа Сэмюэла использовала и набор весьма оригинальных эвристических отсечений.

И наконец, программа Сэмюэла использовала метод обучения, названный «зубрёжка» (rote learning) и заключавшийся в запоминании оценок позиций, уже встречавшихся в предыдущих партиях. Встретив такую позицию в нижних узлах дерева перебора, программа повторно использовала оценку, полученную в прошлый раз в результате более глубокого перебора, что позволяло не только сэкономить время, но и получить более надёжную оценку (поскольку глубина перебора в прошлый раз была больше, то меньше была и вероятность ошибки), избежав, возможно, ошибки, сделанной в предыдущий раз. Учитывая, что дебюты и окончания шашечных партий часто повторяются, этот метод был достаточно эффективен [565].