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

• Автор: Махнычев, Владимир Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 84 с. : ил.

Оглавление
Введение.

1 Обзор последовательного алгоритма ретроанализа

1.1 Последовательный алгоритм ретроанализа

1.2 Препятствия к работе алгоритма в системах без общей памяти. .

2 Параллельный алгоритм ретроанализа.

2.1 Параллельный алгоритм ретроанализа.

2.2 Способы уменьшения объема требуемой памяти.

3 Реализация параллельного алгоритма ретроанализа и его

применение к задаче игры в шахматы

3.1 Построение оптимальной стратегии для семифигурных шахматных окончаний.

3.2 Проверка корректности результатов
3.3 Результаты испытаний.
4 Балансировка нагрузки в параллельном алгоритме
ретроанализа
Заключение.
Публикации автора по теме диссертации
Список литературы


Однако, чтобы задействовать хотя бы часть этого потенциала, существующие последовательные алгоритмы необходимо основательно дорабатывать или же вовсе разрабатывать параллельный алгоритм «с нуля». При успешном создании параллельного алгоритма становится возможным получить совершенно новые, не достижимые ранее результаты для многих задач. Одним из классов таких задач является построение оптимальной стратегии для игры двух противников методом ретроанализа [1—5]. Оптимальная стратегия — полный план действий, который при безошибочных действиях обоих игроков позволяет либо достичь выигрыша за наименьшее число ходов (в случае, если выигрыш достижим), либо (в противном случае) максимально отдалить проигрыш или добиться ничьей, если это возможно [6]. При построении такой стратегии требуется оптимизировать количество ходов как в сторону минимума (в случае выигрыша), так и в сторону максимума (при проигрыше), что обусловливает нетривиальность решения задачи [7]. Широко используемый для поиска оптимальной стратегии в играх этого класса метод ветвей и границ [9] (метод ветвей и границ для решения игровых задач носит название «альфа-бета-перебор» []), как правило, даст лишь приблизительное решение, поскольку количество перебираемых вариантов слишком велико, чтобы перебор мог достичь конца игры. В теории, метод ретроанализа позволяет построить оптимальную стратегию для всей игры, но на практике из-за ограниченных вычислительных мощностей удается построить оптимальную стратегию лишь для некоторого класса состояний игры. Распараллеливание и адаптация алгоритма ретроаиализа к сунеркомпыотерным системам без общей памяти делает возможным построение оптимальной стратегии для гораздо более широкого класса состояний игры, чем это позволяют последовательные алгоритмы. Кроме того, алгоритм ретроанализа является частным случаем динамического программирования, и подходы, примененные в данной работе при его распараллеливании, могут быть использованы при распараллеливании некоторых других задач, решаемых методами динамического программирования. Построение оптимальной стратегии для новых классов состояний игры на персональных компьютерах упирается в огромные объемы данных и вычислений. Объем доступной оперативной памяти компьютера — одно из основных препятствий на пути решения задач большой размерности алгоритмом ретроанализа. Например, для задачи игры в шахматы при наличии на доске не более семи фигур количество позиций, данные о которых необходимо хранить одновременно, даже после применения различных оптимизаций составляет не менее 0 миллиардов, что требует порядка 2 терабайт оперативной памяти. Такой объем недостижим для персональных компьютеров на сегодняшний день, но для современных суперкомпьютеров наличие десятков терабайт оперативной памяти является нормой. Построение параллельного алгоритма, обладающего высокой производительностью в системах с большим количеством процессоров (в частности, близкие к этой проблематике идеи содержатся в работах В. При этом подавляющее большинство современных суперкомпьютеров не имеют общей памяти, поэтому наибольший интерес представляет распараллеливание алгоритма рстроанализа именно для систем без общей памяти. Цели и задачи работы. Целью работы являлась разработка эффективного метода построения оптимальной стратегии для указанного класса игр алгоритмом ретроанализа на суперкомпьютерных системах без общей памяти. Исследовать последовательный алгоритм ретроанализа и выяснить препятствия к его работе в системах без общей памяти. Разработать параллельный алгоритм ретроанализа, рассчитанный на работу в суперкомпьютерных системах без общей памяти. Провести апробацию и оценить эффективность предложенного алгоритма на практических задачах. Исследовать масштабируемость алгоритма и разработать шаги по сс улучшению. Научная новизна. В диссертационной работе предложен новый подход к эффективному построению оптимальной стратегии для пошаговых игр двух противников с полной информацией методом ретроанализа на суперкомпьютерных системах без общей памяти. Разработан и исследован новый параллельный алгоритм ретроанализа.