Распараллеливание алгоритмов ретроанализа для решения переборных задач в вычислительных системах без общей памяти

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

Одним из классов таких задач является построение оптимальной стратегии для игры двух противников методом ретроанализа [1—5]. Оптимальная стратегия — полный план действий, который при безошибочных действиях обоих игроков позволяет либо достичь выигрыша за наименьшее число ходов (в случае, если выигрыш достижим), либо (в противном случае) максимально отдалить проигрыш или добиться ничьей, если это возможно [6]. При построении такой стратегии требуется оптимизировать количество ходов как в сторону минимума (в случае выигрыша), так и в сторону максимума (при проигрыше), что обусловливает нетривиальность решения задачи [7].

Метод ретроанализа применяется к играм с полной информацией, игровой процесс которых заключается в поочередном выполнении игроками действий («ходов»), каждое из которых изменяет состояние игрыпримерами таких игр могут служить шахматы, шашки, рэндзю, го [8] (в этих играх состояние игры принято называть «положением на доске» или «позицией»).

Широко используемый для поиска оптимальной стратегии в играх этого класса метод ветвей и границ [9] (метод ветвей и границ для решения игровых задач носит название «альфа-бета-перебор» [10]), как правило, дает лишь приблизительное решение, поскольку количество перебираемых вариантов слишком велико, чтобы перебор мог достичь конца игры. Кроме того, распараллеливание алгоритма ветвей и границ сопряжено со значительными трудностями: алгоритм предполагает отсечение бесперспективных ветвей перебора за счет уже известных оценок для результата, что, во-первых, влечет необходимость постоянного распространения текущих оценок между всеми узлами вычислительной системы, а во-вторых — приводит к неустойчивости всего алгоритма в силу приблизительности оценок: из-за того, что перебор не достигает конечных состояний игры, оценки результата носят приблизительный характер и в распределенной системе могут противоречить друг другу [11,12].

В теории, метод ретроанализа позволяет построить оптимальную стратегию для всей игры, но на практике из-за ограниченных вычислительных мощностей удается построить оптимальную стратегию лишь для некоторого класса состояний игры. Результаты, получаемые при помощи ретроанализа, традиционно имеют большую ценность как для практиков, так и для теоретиков соответствующих игр (например, при помощи этого метода было получено полное решение для игры в шашки [13], а построение решения для 3−4-5−6-фигурных окончаний в шахматах позволило существенно повысить силу игры шахматных программ в эндшпилях [14,15]).

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

Построение оптимальной стратегии для новых классов состояний игры на персональных компьютерах упирается в огромные объемы данных и вычислений. Объем доступной оперативной памяти компьютера — одно из основных препятствий на пути решения задач большой размерности алгоритмом ретроанализа. Например, для задачи игры в шахматы при наличии на доске не более семи фигур количество позиций, данные о которых необходимо хранить одновременно, даже после применения различных оптимизаций составляет не менее 640 миллиардов, что требует порядка 2 терабайт оперативной памяти. Такой объем недостижим для персональных компьютеров на сегодняшний день, но для современных суперкомпьютеров наличие десятков терабайт оперативной памяти является нормой. Построение параллельного алгоритма, обладающего высокой производительностью в системах с большим количеством процессоров (в частности, близкие к этой проблематике идеи содержатся в работах В. В. Топоркова [16,17]), позволяет использовать всю эту память, а также выполнить все вычислительные операции (их количество в подобных задачах составляет порядка 1017) за приемлемое время. При этом подавляющее большинство современных суперкомпьютеров не имеют общей памяти, поэтому наибольший интерес представляет распараллеливание алгоритма ретроанализа именно для систем без общей памяти.

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

1. Исследовать последовательный алгоритм ретроанализа и выяснить препятствия к его работе в системах без общей памяти.

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

3. Провести апробацию и оценить эффективность предложенного алгоритма на практических задачах.

4. Исследовать масштабируемость алгоритма и разработать шаги по ее улучшению.

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

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

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

Реализован программный комплекс, реализующий разработанный алгоритм.

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

Апробация работы и публикации. Результаты работы рассматривались:

— на Всероссийской научной конференции «Научный сервис в сети Интернет» (Новороссийск, 2004 г.);

— на конференции «Ломоносовские чтения» (Москва, 2009 год);

— на конференции «Ломоносовские чтения» (Москва, 2012 год).

По теме работы опубликовано 7 статей, раскрывающие все основные научные результаты диссертации.

Заключение

.

В заключении представлены основные результаты диссертации.

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

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

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

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

Публикации автора по теме диссертации.

1. Махнычев B.C. Распараллеливание сложных интеллектуальных задач, основанных на обходе дерева перебора. // Программные системы и инструменты. Тематический сборник № 5. — М.: Изд-во факультета ВМК МГУ. — 2005. — С. 81—93.

2. Гуляев A.B., Махнычев В. С. Об одном подходе к реализации метода ветвей и границ на распределенной системе. // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2008. — № 3. — С. 60—63.

3. Махнычев B.C., Ильичев А. Б. Распараллеливание задачи о составлении вузовского расписания с использованием распределенного обхода дерева перебора. // Программные системы и инструменты. Тематический сборник № 8. — М.: Изд-во факультета ВМК МГУ, 2007. — С. 37—42.

4. Захаров В. Б., Махнычев B.C. Распараллеливание алгоритма ретроанализа для задач сверхбольшой размерности. Получение точного решения для 7-фигурных шахматных окончаний. // Отчет по использованию суперкомпьютеров МГУ в 2009;2010 гг. — М., МГУ, 2010. — С. 20—22.

5. Захаров В. Б., Махнычев B.C. Алгоритм ретроанализа в суперкомпыотерных системах на примере задачи игры в шахматы. // Программные системы и инструменты. Тематический сборник № 11. — М.: Изд. отделения ф-та ВМК МГУ, 2010. — С. 45—52.

6. Захаров В. Б., Махнычев B.C. Об опыте создания российского национального сервера «Шахматная планета». // Программные системы и инструменты. Тематический сборник № 6. — М.: Изд. отделения ф-та ВМК МГУ, 2005 г.—С. 49—51.

7. Захаров В. Б., Махнычев B.C. Особенности вычислительного практикума на суперкомпьютерах. // Материалы Международной научно-практической конференции «Информатизация образования — 2011» ЕГУ, Елец, 2011 г. —С. 117—120.