- PVSM.RU - https://www.pvsm.ru -
Доброго времени суток.
Уже довольно давно мы с моим другом Gorkoff [1] увлекаемся игрой в сёги [2]. Причем увлекаемся настолько, что решили написать собственного бота для этой замечательной игры. Данная статья является дальнейшим описанием процесса разработки бота, которым мы, с некоторыми перерывами, занимаемся уже несколько месяцев.
Для принятия решения о том, какой ход совершить в антагонистических [3] играх, таких как шахматы (как и традиционные, так и японские), шашки и крестики-нолики используется стратегия минимакса с оптимизацией, называемой альфа-бета отсечением.
Данный алгоритм неоднократно рассматривался на Хабре, как в статье [2] моего друга, так и в других статьях [2].
Вкратце напомню его суть следующей картинкой:
Цифры в квадратах обозначают оценку позиции после совершения соответствующей последовательности ходов.
В данном примере происходит отсечение узла, значение которого отмечено знаками вопроса.
Можно убедиться в справедливости такого отсечения составив выражение, по которому вычисляется значение в узле b:
b = min(c,d) = min(max(4,6), max(7, X))
Очевидно, что значение данного выражения не зависит от X, так как выражение max(7, X) заведомо больше либо равно 7, следоватьно, оно больше чем max(4,6) и значение b будет равно b = 6.
Таким образом, алгоритм альфа-бета отсечения дает возможность не рассматривать ветви, дающие заведомо худший результат, чем тот, который уже получен.
Следовательно, рассмотрение более перспективных ходов в первыми дает ускорение работы алгоритма. Определение того, какой ход более перспективный — и есть цель данной статьи.
В игре человеку часто бывает очевидно, что некоторые ходы рассматривать просто не обязательно. Например двигать пешку, стоящую с краю доски в тот момент, когда противник подставил ладью под удар.
Для компьютера же понятия «очевидно» не существует, он проверит последовательно все возможные ходы и только после этого сделает вывод, что съесть ладью — верное решение.
Если же каким-либо образом упорядочить рассмотрение ходов так, чтобы ход взятия ладьи оказался первым в рассмотрении, то алгоритм альфа-бета отсечения быстро завершится, отбросив все ветви, оценка которых заведомо хуже чем при взятии ладьи.
В этом примере рассмотрен частный случай эвристического выбора порядка рассмотрения ходов, и отдельно его вряд ли можно использовать в программе. Ручное описание набора частных случаев весьма трудоемко, более того, всегда остается вероятность, что в каком-либо подмножестве вариантов с оставлением ладьи под ударом, ход пешкой — единственно верный.
Здесь и появляется идея о возможности автоматически получить информацию о перспективных ходах из уже сыгранных партий. Применение методов машинного обучения обоснованно в данном случае гипотезой о том, что ходы со схожими параметрами (о них ниже) дают схожий результат.
Первый вопрос, который необходимо решить при использовании машинного обучения — получение обучающей выборки, по которой и будет определяться качество ходов.
Как ни странно, это оказалось наименьшей проблемой, не смотря на уступающую популярность сёги в сравнении с обычными шахматами.
В Сети существует сайт playok.com [4], который предоставляет возможность бесплатно играть в разнообразные настольные игры с другими игроками. Среди предоставляемых игр есть и сёги. Более того, все сыгранные на этом сайте партии сохраняются и формате кифу [5] и находятся в открытом доступе, что дает возможность написать простой скрипт, скачивающий необходимое количество партий.
Количество хранимых на этом сайте партий очень велико (миллионы), поэтому было принято решение создать базу данных для локального хранения параметров партий и ходов.
Стоит сказать, что задача хранения таких данных весьма не тривиальна, так как процессе работы с базой требуется выполнение большого количества операций получения ходов по номеру партии.
Т.е. в случае SQL — выборкой нескольких десятков строк из таблицы, содержащей миллионы строк.
Я рассматривал возможность применения NoSQL баз, таких как MongoDB. В случае NoSQL подобная операция сводилась бы к простому переходу по указателю. Не смотря на это преимущество NoSQL, в текущей реализации используется PostgreSQL, а таблица ходов имеет индекс по номеру партии.
Скрипты, реализующие загрузку партий с сайта playok.com и занесение их в базу данных, а также скрипты, выполняющие подготовку данных (т.е. те функции, время выполнения которых не критично), написаны на Ruby, т.к. этот язык обеспечивает высокую скорость написания кода, а также имеет все необходимые компоненты для работы с базой данных. Ссылки на исходные коды приведены в конце статьи.
Для того, чтобы применение методов машинного обучения было возможным, необходимо описать каждый ход с помощью набора признаков. Такое описание, как ни странно, называется признаковым описанием объекта.
Признаковое описание является вектором значений, который, в свою очередь, является координатами точки в признаковом пространстве.
Например признаковым описанием коробки могут служить ее габариты и вес. Так коробка размером 2 на 3 на 1 метр и весом 10 килограмм будет иметь признаковое описание (2,3,1,10) в четырехмерном пространстве признаков.
В связи с тем, что одинаковый по обозначению ход (e2e4) в разных партиях может привести к противоположным результатам, то в признаковое описание хода необходимо включить признаки, содержащие информацию о положении других фигур на доске.
Для признаков также необходимо соблюдать инвариантность относительно цвета фигуры, совершившей ход, так как в обучающей выборке хорошими могут быть как ходы черных, так и белых. Например номер горизонтали хода лучше заменить на количество горизонталей до начальной позиции (в данном случае считается, что черные начинают с горизонтали 9, а белые — с горизонтали 1).
Используемый вариант признакового описания состоит из следующих параметров:
Постановка задачи подразумевает классификацию ходов на перспективные и неперспективные (хорошие и плохие), однако на алгоритм наложены также некоторые дополнительные условия:
Среди алгоритмов классификации для нашей задачи хорошо подходит метод ближайшего соседа [6].
Метод заключается в определении кого, объект какого класса в пространстве признаков расположен ближе всего к классифицируемому объекту.
Данный метод хорош тем, что для него естественным образом определяется то, какой из двух рассматриваемых ходов лучше. Для этого достаточно сравнить расстояния до их ближайших соседей.
Однако у метода есть и существенный недостаток: требуется проверить большое количество объектов прежде чем можно будет утверждать, что найден ближайший.
Один из способов решения этой проблемы — применение кластеризации.
Заменив множество исходных точек на множество точек, являющихся центрами кластеров, мы существенно сократим количество операций, требуемых для классификации объекта. Такая замена, очевидно, ухудшит качество классификации, и чем меньше кластеров будет в выходном множестве, тем хуже будет качество. Таким образом, количество кластеров — это величина, отражающая компромисс между точностью и скоростью.
Прежде чем переходить к обработке партий необходимо решить, какие же ходы считать хорошими, а какие плохими нашей базе. На ум сразу приходят несколько вариантов:
Если поразмышлять еще немного, становится понятно, что первый и второй варианты не гарантированно хороши.
Так как, во-первых, бывают ситуации, в которых игрок, в которых жертва сильной фигуры в последствие приводит проигрышу игрока, принявшего жертву.
Во-вторых, мат может быть поставлен из-за невнимательности проигравшего игрока, что случается довольно часто.
Если же игрок с высоким рейтингом выигрывает партию, то мы можем утверждать, что однозначно глупых ходов он не совершал (на достаточном уровне игры зевки гарантированно ведут к поражению), а наша задача, напомню, заключается не в установлении абсолютно точных ходов в конкретных ситуациях, а а сортировке ходов по качеству в среднем.
Исходя из выше изложенных аргументов получаем, что для решения нашей задачи придется довериться авторитетам.
В текущей реализации ходы выбираются следующим образом:
Отсеивание первых ходов обоснованно тем, что для дебюта партии существуют другие, более эффективные алгоритмы, рассмотрение которых выходит за рамки статьи.
В отличие от классификации, которая должна выполняться на каждом шаге просмотра игрового дерева, к кластеризации, в нашем случае, предъявляются менее жесткие требования.
В первую очередь, кластеризация должна быть выполнена всего 1 раз, что дает право применять алгоритмы, требующие большего времени чем то, которым мы располагаем непосредственно в момент игры.
Сама по себе задача кластеризации сформулирована не четко, что дает множество вариантов ее интерпретации. Мы будем пользоваться следующим определением:
Кластеризация заключается в разбиении множества объектов на непересекающие множества (кластеры) таким образом, чтобы минимизировать расстояние между объектами внутри кластера и максимизировать расстояние между кластерами.
Формально данное определение можно записать следующим образом:
Где Ky — кластер с номером y
p(x,y) — функция, определяющая расстояние в заданной метрике
μy — центр кластера с номером y
xi — объект с номером i
В своей реализации я использовал алгоритм кластеризации k-means, его подробное описание можно найти, например, в википедии [7].
Особенность алгоритма заключается в том, что он в качестве начального разбиения на кластеры использует случайные значения, выбор которых сильно влияет на результат дальнейшего разбиения, что дает возможно многократного выполнения кластеризации добиться лучший результатов, а мы не ограничены по времени выполнения на данном этапе.
Например кластеризации случайных точек в двумерном пространстве выглядит так:
def midle(cluster)
#Центр "масс"
res = [0]*cluster[0].size();
cluster.each do |e|
i = 0;
e.each do |x|
res[i] += x;
i+=1;
end
end
res.map! {|x| x/cluster.size.to_f}
return res;
end
def dist(x1,x2)
if(x1.size != x2.size)
raise "WrongSizeException";
end
mode = 1
if mode ==1 then # евклидово расстояние без корня
dist = 0;
for i in 0..x1.size-1
dist += (x1[i]-x2[i])**2
end
return dist;
end
if mode == 2 then # косинусная мера
dist = 0;
x1_s = 0;
x2_s = 0;
for i in 0..x1.size-1
dist += x1[i]*x2[i]
x1_s += x1[i]**2;
x2_s += x2[i]**2;
end
dist =1 - dist / Math.sqrt(x1_s) / Math.sqrt(x2_s)
end
end
def quality1 (clusters)
# Среднее внутрикластерное расстояние (относительно центра, ибо квадратичная сложность - зло)
sum = 0;
clusters.each do |cluster|
center = midle(cluster)
local_sum = 0
cluster.each do |vector|
local_sum += dist(vector, center);
end
sum += local_sum / cluster.size.to_f;
end
return sum;
end
def quality2 (clusters)
# среднее межклассовое расстояние
centers = [];
clusters.each do |cl|
centers += [midle(cl)];
end
sum = 0
centers.each do |c1|
centers.each do |c2|
sum += dist(c1,c2)
end
end
return sum;
end
def quality (clusters)
# сие надо минимизировать
return quality1(clusters)/quality2(clusters);
end
def find_nearest(vectors, point)
min = Float::INFINITY
imin = 0
i = 0
vectors.each do |vector|
d = dist(vector, point)
if(d < min) then
min = d;
imin = i;
end
i += 1;
end
return imin
end
def k_means(vectors, k)
len = vectors.size;
clusters = [];
centers_index = [];
if len < k then
raise "count of clusters more than objects";
end
while centers_index.size != k do # пока не нарандомим k уникальных индексов
centers_index = (1..k).map { Random.rand(len)}; # выбираем k случайных центров
centers_index.uniq!
end
centers = centers_index.map{ |e| vectors[e] }
clusters_new = []
begin
# Распределение по кластерам на основе центов
clusters = clusters_new;
clusters_new = k.times.map {[]};
vectors.each do |vector|
clusters_new[find_nearest(centers, vector)] += [vector];
end
#вычислить новые центры кластеров
centers = [];
clusters_new.each do |cluster|
return nil if cluster == nil; # вернуть ничего, если какой-либо класстер оказался пуст
return nil if cluster.size == 0;
centers += [midle(cluster)]
end
end until clusters_new == clusters
return clusters_new
end
В результате кластеризации получаем N (я выбрал N = 20) точек, которые являются центрами кластеров хороших и плохих ходов в пространстве признаков.
Расстояние до этих точек и будет использоваться при сортировке порядка просмотра ходов.
Теперь, когда у нас имеется существенно меньшее число точек по сравнению с исходной базой, можно применять сортировку на основе близости к этим точкам.
Как и на предыдущих этапах, мы встаем перед выбором. А именно выбором метрики, в которой будут вычисляться расстояние до кластеров.
Можно применять как и привычную Евклидову метрику, так и метрику Махаланобиса [8], учитывающую корреляцию между координатами точек.
Метрика Махаланобиса в двухмерном пространстве. Эллипсами показана дисперсия значений.
Какая метрика лучше и по каким параметрам — отдельный и весьма сложный вопрос, поэтому для начала остановимся на простом варианте — Евклидовой метрике.
Значение, по которому будет происходить сортировка ходов выберем следующее: ((Расстояние до ближайшего кластера плохих ходов) — (Расстояние до ближайшего кластера хороших ходов)).
Таким образом, чем больше указанное значение у хода, тем раньше он должен быть рассмотрен при построении игрового дерева.
Здесь также возможно использование и других выражений для получения оценки хода, например среднего расстояния до кластеров хороших ходов и т.п..
public static double euclidian(ArrayList<Double> p1, ArrayList<Double> p2) {
Double sum = 0.0;
for (int i = 0; i < p1.size(); i++) {
sum += (p1.get(i) - p2.get(i)) * (p1.get(i) - p2.get(i));
}
return sum;
}
public static double getMinDist(ArrayList<Double> point, ArrayList<ArrayList<Double>> clusters) {
Double min = Double.MAX_VALUE;
for (ArrayList<Double> cluster : clusters) {
min = Math.min(min, euclidian(cluster, point));
}
return min;
}
private void sortMoves(CMovesList movesList) {
// (Расстояние до хорошего кластера) - (Расстояние до плохого)
for (CMove move : movesList.Moves) {
ArrayList<Double> move_params = CDataMining.getFeature(localBoard, move).toArray(); // получаем параметры
// хода
Double good_dist = CAdviser.getMinDist(move_params, clusters_good); // Ищем ближайшие точки
Double bad_dist = CAdviser.getMinDist(move_params, clusters_bad);
move.H = bad_dist - good_dist;
}
movesList.sortH();
}
/**
* Альфа-Бета отсечение
*
* @param color за кого начинать
* @param D глубина
* @param A
* @param B
* @return
*/
public int AB(boolean color, int D, int A, int B) {
ABtimes++;
if ((D == 0) || Math.abs(localBoard.Evaluate(color)) >= 15000)
return localBoard.Evaluate(color);
CMovesList ML;
ML = localBoard.getAllMoves(color);
if (D == MaxD) { // только первый ход
sortMoves(ML); // < ----- Сортирует исходя из близости к кластеру доброты.
} else {
ML.sortH();
}
while ((ML.getMovesCount() > 0) && (A < B)) {
CMove Move = ML.getMoveByIndex(0);
CFigure previousFigure = localBoard.makeMove(Move);
int tmp = -AB(!color, D - 1, -B, -A);
localBoard.unmakeMove(Move, previousFigure);
if (tmp > A) {
A = tmp;
if (D == MaxD)
BestMove.cp(Move);
}
ML.removeByIndex(0);
}
return A;
}
Основным критерием при оценке эффективности описанного метода служило количество рекурсивных вызовов процедуры Альфа-Бета отсечения, так как этот критерий не зависит от реализации и, следовательно, является наиболее объективным.
Эксперименты показали, что эффективность метода сильно зависит от того, какая ситуация складывается на доске. Это и не удивительно, так как обучение классификатора происходило на реальных партиях, следовательно его эффективность для решения искусственно сконструированных задач может быть значительно ниже чем у простых эвристик, сортирующих ходы по весу атакованных фигур.
Случайная позиция, взятая из реальной партии.
Простая эвристика:
Количество рекурсивных вызовов — 22027
Эвристика с использованием Машинного обучения для первого, для последующих ходов — простая эвристика:
Количество рекурсивных вызовов — 18719
Сделанные ходы отличаются, так как в построенном дереве игры на максимальной глубине имеют одинаковую оценку.
Простая эвристика:
Количество рекурсивных вызовов — 32561
Эвристика с использованием Машинного обучения для первого, для последующих ходов — простая эвристика:
Количество рекурсивных вызовов — 28524
Искусственная ситуация с малым количеством фигур на доске и несколькими фигурами в руке.
(Грубина просмотра — 3 полухода)
Простая эвристика:
Количество рекурсивных вызовов — 379376
Эвристика с использованием Машинного обучения для первого, для последующих ходов — простая эвристика:
Количество рекурсивных вызовов — 541866
Как видно, в случае с искусственно сформированной ситуацией на доске, эвристика, основанная на машинном обучении, как и предполагалось, дает худшую эффективность по сравнению с простой эвристикой.
В процессе вычисления ближайших точек используются операции с вещественными числами, что существенно увеличивает время просмотра игрового дерева.
Как было отмечено выше, для некоторых ситуаций метод машинного обучения может давать худший результат чем простая эвристика.
Избавиться от вещественных операций можно, например, используя Манхеттенское [9] расстояние.
Количество вещественных операций можно также уменьшить посредствам сокращения количества кластеров. Такое сокращение приведет к потере точности и, следовательно, к ухудшению работы алгоритма Альфа-Бета отсечения, что увеличит время работы. Поэтому, в идеале, необходимо решить задачу оптимизации для данного параметра.
Для решения проблемы применимости эвристики машинного обучения возможны следующие улучшения:
Спасибо за внимание.
Автор: generall
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/news/52432
Ссылки в тексте:
[1] Gorkoff: http://habrahabr.ru/users/gorkoff/
[2] сёги: http://habrahabr.ru/post/168867/
[3] антагонистических: http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1%82%D0%B0%D0%B3%D0%BE%D0%BD%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0
[4] playok.com: http://playok.com
[5] кифу: http://ru.wikipedia.org/wiki/%D0%9A%D0%B8%D1%84%D1%83_(%D1%81%D1%91%D0%B3%D0%B8)
[6] ближайшего соседа: http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
[7] википедии: http://en.wikipedia.org/wiki/K-means_clustering
[8] Махаланобиса: http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9C%D0%B0%D1%85%D0%B0%D0%BB%D0%B0%D0%BD%D0%BE%D0%B1%D0%B8%D1%81%D0%B0
[9] Манхеттенское: http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%B3%D0%BE%D1%80%D0%BE%D0%B4%D1%81%D0%BA%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D1%80%D1%82%D0%B0%D0%BB%D0%BE%D0%B2
[10] курс лекций: http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_(%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2)
[11] выложены: http://habrahabr.ru/company/yandex/blog/208034/
[12] https://github.com/gorkoff/Shogi/tree/DataMining: https://github.com/gorkoff/Shogi/tree/DataMining
[13] https://github.com/generall/ScriptsForShogi: https://github.com/generall/ScriptsForShogi
[14] Источник: http://habrahabr.ru/post/208580/
Нажмите здесь для печати.