Применение машинного обучения в построении ИИ для игры в японские шахматы (сёги)

Доброго времени суток.

Уже довольно давно мы с моим другом Gorkoff увлекаемся игрой в сёги. Причем увлекаемся настолько, что решили написать собственного бота для этой замечательной игры. Данная статья является дальнейшим описанием процесса разработки бота, которым мы, с некоторыми перерывами, занимаемся уже несколько месяцев.

Про альфа-бета отсечение или почему важно сортировать ходы

Для принятия решения о том, какой ход совершить в антагонистических играх, таких как шахматы (как и традиционные, так и японские), шашки и крестики-нолики используется стратегия минимакса с оптимизацией, называемой альфа-бета отсечением.
Данный алгоритм неоднократно рассматривался на Хабре, как в статье моего друга, так и в других статьях.
Вкратце напомню его суть следующей картинкой:

Цифры в квадратах обозначают оценку позиции после совершения соответствующей последовательности ходов.

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

Количество хранимых на этом сайте партий очень велико (миллионы), поэтому было принято решение создать базу данных для локального хранения параметров партий и ходов.
Стоит сказать, что задача хранения таких данных весьма не тривиальна, так как процессе работы с базой требуется выполнение большого количества операций получения ходов по номеру партии.
Т.е. в случае SQL — выборкой нескольких десятков строк из таблицы, содержащей миллионы строк.
Я рассматривал возможность применения NoSQL баз, таких как MongoDB. В случае NoSQL подобная операция сводилась бы к простому переходу по указателю. Не смотря на это преимущество NoSQL, в текущей реализации используется PostgreSQL, а таблица ходов имеет индекс по номеру партии.

Скрипты, реализующие загрузку партий с сайта playok.com и занесение их в базу данных, а также скрипты, выполняющие подготовку данных (т.е. те функции, время выполнения которых не критично), написаны на Ruby, т.к. этот язык обеспечивает высокую скорость написания кода, а также имеет все необходимые компоненты для работы с базой данных. Ссылки на исходные коды приведены в конце статьи.

Про описание ходов

Для того, чтобы применение методов машинного обучения было возможным, необходимо описать каждый ход с помощью набора признаков. Такое описание, как ни странно, называется признаковым описанием объекта.

Признаковое описание является вектором значений, который, в свою очередь, является координатами точки в признаковом пространстве.
Например признаковым описанием коробки могут служить ее габариты и вес. Так коробка размером 2 на 3 на 1 метр и весом 10 килограмм будет иметь признаковое описание (2,3,1,10) в четырехмерном пространстве признаков.

В связи с тем, что одинаковый по обозначению ход (e2e4) в разных партиях может привести к противоположным результатам, то в признаковое описание хода необходимо включить признаки, содержащие информацию о положении других фигур на доске.
Для признаков также необходимо соблюдать инвариантность относительно цвета фигуры, совершившей ход, так как в обучающей выборке хорошими могут быть как ходы черных, так и белых. Например номер горизонтали хода лучше заменить на количество горизонталей до начальной позиции (в данном случае считается, что черные начинают с горизонтали 9, а белые — с горизонтали 1).

Используемый вариант признакового описания состоит из следующих параметров:

Про выбор алгоритма классификации

Постановка задачи подразумевает классификацию ходов на перспективные и неперспективные (хорошие и плохие), однако на алгоритм наложены также некоторые дополнительные условия:

• Должна быть возможность ранжирования ходов от лучших к худшим.
• Должна быть обеспечена высокая скорость, так как классификация(и сортировка) должна производиться на каждом этапе просмотра дерева.

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

Один из способов решения этой проблемы — применение кластеризации.
Заменив множество исходных точек на множество точек, являющихся центрами кластеров, мы существенно сократим количество операций, требуемых для классификации объекта. Такая замена, очевидно, ухудшит качество классификации, и чем меньше кластеров будет в выходном множестве, тем хуже будет качество. Таким образом, количество кластеров — это величина, отражающая компромисс между точностью и скоростью.

Про выбор ходов

Прежде чем переходить к обработке партий необходимо решить, какие же ходы считать хорошими, а какие плохими нашей базе. На ум сразу приходят несколько вариантов:

• Ходы, которые привели к материальному перевесу.
• Ходы, которые привели к мату.
• Ходы, сделанные игроками с высоким рейтингом.

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

В текущей реализации ходы выбираются следующим образом:

• Задается нижний и верхний пороги рейтингов
• В каждой партии, рейтинг победителя в которой выше верхнего порога, выбираются последние 2/3 ходов победителя и помечаются как хорошие.
• В каждой партии, рейтинг проигравнего в которой меньше нижнего порога, выбираются последние 2/3 ходов проигравшего и помечаются как плохие.

Отсеивание первых ходов обоснованно тем, что для дебюта партии существуют другие, более эффективные алгоритмы, рассмотрение которых выходит за рамки статьи.

Про кластеризацию

В отличие от классификации, которая должна выполняться на каждом шаге просмотра игрового дерева, к кластеризации, в нашем случае, предъявляются менее жесткие требования.
В первую очередь, кластеризация должна быть выполнена всего 1 раз, что дает право применять алгоритмы, требующие большего времени чем то, которым мы располагаем непосредственно в момент игры.

Сама по себе задача кластеризации сформулирована не четко, что дает множество вариантов ее интерпретации. Мы будем пользоваться следующим определением:

Кластеризация заключается в разбиении множества объектов на непересекающие множества (кластеры) таким образом, чтобы минимизировать расстояние между объектами внутри кластера и максимизировать расстояние между кластерами.

Формально данное определение можно записать следующим образом:

Где K_y — кластер с номером y
p(x,y) — функция, определяющая расстояние в заданной метрике
μ_y — центр кластера с номером y
x_i — объект с номером i

В своей реализации я использовал алгоритм кластеризации k-means, его подробное описание можно найти, например, в википедии.
Особенность алгоритма заключается в том, что он в качестве начального разбиения на кластеры использует случайные значения, выбор которых сильно влияет на результат дальнейшего разбиения, что дает возможно многократного выполнения кластеризации добиться лучший результатов, а мы не ограничены по времени выполнения на данном этапе.

Например кластеризации случайных точек в двумерном пространстве выглядит так:

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) точек, которые являются центрами кластеров хороших и плохих ходов в пространстве признаков.
Расстояние до этих точек и будет использоваться при сортировке порядка просмотра ходов.

Про классификацию

Теперь, когда у нас имеется существенно меньшее число точек по сравнению с исходной базой, можно применять сортировку на основе близости к этим точкам.

Как и на предыдущих этапах, мы встаем перед выбором. А именно выбором метрики, в которой будут вычисляться расстояние до кластеров.
Можно применять как и привычную Евклидову метрику, так и метрику Махаланобиса, учитывающую корреляцию между координатами точек.

Картинки для наглядности:

Евклидова метрика в двумерном пространстве.

Метрика Махаланобиса в двухмерном пространстве. Эллипсами показана дисперсия значений.

Какая метрика лучше и по каким параметрам — отдельный и весьма сложный вопрос, поэтому для начала остановимся на простом варианте — Евклидовой метрике.

Значение, по которому будет происходить сортировка ходов выберем следующее: ((Расстояние до ближайшего кластера плохих ходов) — (Расстояние до ближайшего кластера хороших ходов)).
Таким образом, чем больше указанное значение у хода, тем раньше он должен быть рассмотрен при построении игрового дерева.
Здесь также возможно использование и других выражений для получения оценки хода, например среднего расстояния до кластеров хороших ходов и т.п..

   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;
    }

Результат

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

Недостатки метода

• Долго.

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

• Ограниченность применения.

Как было отмечено выше, для некоторых ситуаций метод машинного обучения может давать худший результат чем простая эвристика.

Возможные способы улучшения

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

Для решения проблемы применимости эвристики машинного обучения возможны следующие улучшения:

• Рассмотрение ходов в контексте ситуации на доске, что включает в себя построение графа взаимодействия фигур и добавление информации из этого графа в параметры хода.
• Создание разных вариантов кластеров для разных типов позиции на доске (В зависимости от количества фигур, в случае атакующей стратегии, в случае защитной стратегии и т.д.) и применение того или иного набора кластеров в зависимости от игровой ситуации.

Ссылки и литература

• По машинному обучению существует замечательный курс лекций К. В. Воронцова, откуда я и брал информацию о используемых методах. Его же лекции недавно были выложены на Хабр.
• Репозиторий с самим ботом, написанный на java: https://github.com/gorkoff/Shogi/tree/DataMining
• Репозиторий со вспомогательными скриптами на Ruby: https://github.com/generall/ScriptsForShogi

Спасибо за внимание.

Автор: generall

Источник