Разработка параллельной шахматной программы с использованием инструментов Intel® Parallel Studio

Создать новую статью

Published On :   29.09.2009 00:00
Рейтинг
 


Аннотация

В данной статье рассказывается об использовании Intel® Parallel Studio для распараллеливания алгоритма обхода дерева игры с alpha-beta отсечениями в шахматной программе с целью повышения ее масштабируемости. Кратко описан ход работы и приведены результаты экспериментов по оценке масштабируемости полученного решения. Пока разработанная шахматная программа играет примерно в силу первого разряда, но, возможно, приведенное в данной статье описание будет вам полезно при реализации различных алгоритмов с использованием библиотеки TBB, например, алгоритмов, использующих метод ветвей и границ.

Введение

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

дерево игры

Последовательную версию алгоритма определения оценки позиции в виде псевдокода можно представить следующим образом:

Value negamax(Position pos, int depth)
{ 
	if( мы находимся в листе дерева перебора )
	{
		return оценка текущей позиции;
	}

	moves = сгенерировать ходы из текущей позиции;
	result = минимальное значение оценки;

	for(int i=0; i<numMoves; i++)
	{
		pos.MakeMove(moves[i]);
		result = max(result, -negamax(pos, depth-1));
		pos.UndoMove(moves[i]);
	}
	return result;
}

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

Псевдокод последовательного перебора с альфа-бета отсечениями:

Value alphabeta(Position pos, int depth, Value alpha, Value beta)
{
	if( мы находимся в листе дерева перебора )
	{
		return оценка текущей позиции; 
	}

	moves = сгенерировать ходы из текущей позиции;
	result = минимальное значение оценки;

	for(int i=0; i<numMoves; i++)
	{
		pos.MakeMove(moves[i]);
		Value cur = - alphabeta(pos, depth-1, -beta, -alpha);
		pos.UndoMove(moves[i]);
		if( cur>result )
		{
			result = cur;
			if( cur>alpha )
			{
				alpha = cur;
				if( alpha>=beta ) // отсечение
				break;
			}
		}
	}
	return result;
}

Cложность в распараллеливании перебора с отсечениями заключается в том, что при параллельном обходе дерева параллельность достигается за счет выполнения «лишней» (с точки зрения последовательного алгоритма) работы, но при этом ускорение достигается за счет того, что обычно мы заранее не знаем, какая работа лишняя. При обновлении альфа-границы узла дерева, необходимо соответственно обновить бета-границу у тех узлов, родителем которых является текущий, так как при этом в них может произойти отсечение. При хорошем упорядочении ходов обычно выгоднее обойти несколько первых ходов последовательно, а после этого начинать параллельный обход.

В данной статье рассматривается распараллеливание процедуры перебора с использованием библиотеки Intel® Threading Building Blocks и инструментов Intel® Parallel Studio.

Распараллеливание алгоритма перебора без отсечений

При распараллеливании последовательной версии использовались tbb::task, при этом в структуре task-а хранилась текущая позиция, глубина и указатель на результат. При этом (до определенной глубины в дереве игры) в цикле обхода ходов вместо рекурсивного вызова создавались новые task-и и добавлялись в список заданий tbb::task_list. После этого в данном узле производилось ожидание порожденных заданий (spawn_and_wait_for_all) и выбор максимума. Начиная с некоторой глубины (в данном случае - когда остается 4 полухода до листьев дерева) производился обычный рекурсивный перебор без распараллеливания, чтобы избежать лишних накладных расходов на создание task-ов. В принципе, аналогичного результата можно было бы достичь, используя parallel_for по всем сгенерированным в данном узле ходам.
Перебор без отсечений практически идеально распараллеливается (т.е. имеет почти линейную масштабируемость). Более интересен перебор с отсечениями, которые позволяют существенно ускорить определение оценки позиции.

Использование tbb::task для распараллеливания перебора с отсечениями

В первоначальной версии разработанного параллельного алгоритма перебора с использованием task-ов каждый узел (task) по завершении определения оценки своего поддерева обновлял оценку родительского task-а. После этого, в случае отсечения вызывался метод отмены перебора. Он выставлял в true переменную отмены текущего узла, которая проверялась перед генерацией ходов из данной позиции. Также эта переменная проверялась в функции последовательного перебора (которая запускалась при достижении некоторой глубины). Кроме того, данная переменная рекурсивно устанавливалась для всех потомков узла, для хранения которых использовался vector указателей на task-и. Для синхронизации при возврате значения родительскому task-у использовался spin_mutex. Данная версия показала недостаточную масштабируемость. Значительное время затрачивалось на ожидание в критической секции (spin_mutex) при обновлении значения родительского узла.

В ходе обсуждения было решено попробовать использовать для обновления значения родительского узла atomic значения, что позволило обойтись без синхронизации, использующей spin_mutex, и положительно сказалось на масштабируемости. Таким образом, структура узла task содержала позицию, оставшуюся глубину, значения результата, границы alpha, beta. Однако для снижения накладных расходов на копирование позиции выгоднее было бы из одного task-узла обходить сразу несколько ходов. Соответственно, после генерации ходов и их сортировки в этом случае можно не создавать по одному task-у на каждый ход, а разделить количество ходов на некоторое количество частей. В данном случае удобна конструкция parallel_for, которая позволяет обойтись без использования task-ов напрямую, а параллельный обход сгенерированных ходов записать в функторе путем определения оператора (). Таким образом, было решено использовать parallel_for, об использовании которого рассказывается ниже.

Использование tbb::atomic для обмена значениями между рабочими потоками

При обновлении в процессе перебора значения alpha некоторого узла (т.е. когда завершается определение оценки одного из узлов – его потомков) может произойти отсечение в самом узле (alpha превышает его beta), а также в любом из оставшихся узлов – потомков (у которых beta == -alpha родительского узла). Таким образом, для того чтобы производить своевременную остановку излишней работы, необходимо обновлять значения beta узлов-потомков, которые в это время могут уже исполняться.

При обсуждении было решено вместо обновления значений хранить в узле atomic значение alpha и обращаться к нему из узлов-потомков.

Также atomic значения использовались для подсчета во время перебора статистических данных: количества рассмотренных позиций, количества отсечений и узлов, в которых произошла отмена обхода. На 2-х и 4-х- ядерных процессорах такой способ подсчета статистики практически не сказался на производительности, однако на 24-ядерной машине было выявлено существенное снижение производительности:

Режим Hotspots Amplifier

При помощи Amplifier (в режиме «Hotspots») было выявлено, что снижение производительности вызывалось совместным доступом к atomic-переменной подсчета количества позиций. Таким образом, подсчет статистики эффективнее вести в локальных переменных task-ов. После исправления данного "бутылочного горлышка" затраты времени распределяются следующим образом:

Распределение временных затрат

Использование tbb::parallel_for для распараллеливания перебора с отсечениями

Для распараллеливания перебора было решено использовать parallel_for по ходам из текущей позиции. Такой код имеет несколько преимуществ:

  • более высокоуровневый (проще читается), по сравнению с непосредственной работой с task;
  • в данном случае по скорости не уступает версии с task-ами;
  • менее всего визуально отличается от последовательного перебора;
  • т.к. parallel_for реализован через использование task-ов, то приоритет также имеют задания на большей глубине, что в данной задаче является наиболее эффективным способом обхода дерева.

В функции search, которая производит рекурсивный обход дерева игры, выполняется следующая последовательность действий:

  1. Проверка, не пора ли останавливать перебор по оставшемуся времени
  2. Возврат оценки, если мы находимся в листе дереве
  3. Проверка, можно ли не проводить перебор, а вернуть готовое значение текущей позиции из таблицы перестановок (также из таблицы выбирается лучший ход для последующего использования при сортировке ходов)
  4. Попытка сделать пустой ход и таким образом отменить поиск в данном поддереве (эвристика)
  5. Подрезание дерева – уменьшение оставшейся глубины, если скорее всего данная ветвь не улучшит результат (эвристика futility)
  6. Расширения (увеличение оставшейся глубины, если текущая позиция под шахом или есть пешка на предпоследней горизонтали)
  7. Генерация ходов из текущей позиции
  8. Сортировка ходов (в первую очередь необходимо рассматривать ходы, которые с наибольшей вероятностью приведут к отсечению)
  9. Обход ходов и определение оценки позиции (здесь производится распараллеливание с помощью parallel_for)
  10. Сохранение результатов в таблицу перестановок и возврат результата

В зависимости от глубины, для обхода ходов используется либо последовательный перебор, либо параллельный (в последней версии используется только параллельный, т.к. на форсированный последовательный перебор из листьев затрачивается достаточно времени и вызов parallel_for практически не вносит ощутимого замедления). В parallel_for используется функтор MoveEvaluator, который в операторе () копирует позицию у родительского узла (т.к. в процессе перебора она будет меняться) и последовательно обходит ходы из переданного range, а также tbb::auto_partitioner.

Масштабируемость разработанной программы

Для оценки масштабируемости разработанной программы проведены эксперименты на многопроцессорном SMP компьютере с процессорами Itel Xeon, имеющем в общей сложности 24 ядра. Запускался обход дерева игры из тестовых позиций на одну и ту же глубину, при этом измерялось затраченное на него время с разным количеством рабочих потоков tbb (устанавливаемых при помощи tbb::task_scheduler_init).

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

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

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

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

Заключение

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

При разработке программы использовалась библиотека Intel® Threading Building Blocks, а именно parallel_for для параллельного обхода ходов из текущей позиции в рекурсивной функции. Поскольку parallel_for реализован через использование task-ов, то приоритет, также как и при использовании task-ов напрямую, имеют задания на большей глубине, что представляется наиболее эффективным способом обхода дерева игры. При обновлении значений оценки и границ родительского узла используется переменные типа tbb::atomic.

Активно использовались Intel® Parallel Inspector для проверки корректности и Intel® Parallel Amplifier для профилировки и повышения производительности. В данной статье описаны некоторые случаи использования Amplifier. Проведены эксперименты для оценки масштабируемости разработанной программы.

Благодарности

Я хотел бы выразить благодарность Прохорову Дмитрию, Рябцеву Дмитрию, Еремину Дмитрию, Федоровой Юлии, которые принимали участие в обсуждениях по проекту, а также организаторам летней школы. Также хочу поблагодарить всех участников Летней школы. Как выяснилось, некоторые из них играют сильнее моей программы!

Планы на будущее

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

Об авторе

Александр Эдуардович Мусман, студент Волгоградского государственного технического университета (кафедра ПОАС), проходил стажировку в Нижнем Новгороде. Для меня участие в Летней Школе - это не только интересные лекции, экскурсии, общение с интересными людьми, но и 4-6 недель работы в команде первоклассных специалистов!