Конь-светлячок
FireFly.zip Основные идеи алгоритма "Конь-Светлячок":
1) Рассматриваем все возможные цепочки ходов нашего коня на столько ходов вперед (на такую глубину), на сколько хватит времени. Т.е. строим "дерево всех возможных ходов" из начальной позиции.
Глубина 0 - от 1 до 8 возможных ходов из начальной позиции.
...
Глубина N+1 - от 1 до 8 возможных ходов, для КАЖДОГО возможного хода глубины N.
2) У каждого хода есть вес/рейтинг. Вес цепочки равен сумме весов каждого хода из неё.
3) В конце алгоритма на выход подаём координаты клетки с которой началась цепочка с максимальным весом. Т.е. фактически ходим нашим конем в эту клетку.
4) Вес незанятой клетки всегда (на любой глубине анализа) больше нуля.
5) Вес уже занятой нами клетки всегда равен нулю. Т.о. ход на занятую клетку возможен только благодаря большому весу последующей цепочки ходов.
6) Вес хода падает с увеличением глубины анализа. Т.о. при прочих равных, будет выгоднее сходить в ту пустую клетку, которая ближе.
7) Рассматривать все возможные ходы противников слишком затратно. Вместо этого будем учитывать в весе хода расстояние противника до данной клетки.
8) Вес незанятой клетки, до которой не может добраться ни один противник, существенно меньше, чем вес всех остальных пустых клеток (даже на большой глубине), но больше нуля. Т.о. конь до самого конца игры будет игнорировать такие клетки, и стремиться занимать клетки доступные врагу. И только когда спорные клетки закончатся, "добьет" все недоступные врагам клетки.
9) В самом начале работы алгоритма "Конь-Светлячок" для каждого соперника с помощью волнового алгоритма считаем сколько ходов ему нужно из его позиции до каждой пустой клетки. Тут же определяем до каких пустых клеток он не способен добраться.
10) Вес хода на пустую клетку складывается из трех составляющих:
а) Константа больше нуля. Реализует п.4
б) Стратегическая ценность клетки. Определяется как произведение константы, на количество пустых клеток, из неё доступных.
в) Агрессивный вклад. Некая функция зависящая от расстояний всех противников до данной клетки. На N-ой глубине анализа максимальный агрессивный вклад будет у тех клеток, расстояние противника до которой совпадает с глубиной анализа. Т.е. нам до клетки столько же ходов, сколько и противнику, следовательно есть возможность его "подрезать". Функция максимальна, когда расстояние до клетки совпадает, равна нулю, когда противник к клетке ближе и убывает в с торону "противник от клетки дальше", но не должна убывать слишком быстро, чтобы избежать ситуации, когда наш конь из двух путей до клетки при прочих равных выберет тот, что длиннее (из-за того что расстояние станет сильнее совпадать с расстоянием до неё противника, агрессивный вклад станет больше, и превысит падение рейтинга от глубины анализа). В случае нескольких соперников их агрессивный вклад складывается и делится на их количество. Деление агрессивного вклада не дает нашему коню увлечься "подрезанием" одного противника забив на других, т.к. влияние стратегической ценности клетки становится больше.
Все три составляющие складываются и делятся на функцию, возрастающую с глубиной, и отвечающую за п.6
На данный момент функция в знаменателе это 1.2^N, где N-глубина анализа
Константа в стратегической ценности 0.15
Агрессивный вклад высчитывается через Case. Значения можно посмотреть в алгоритме.
Все цифры получены после долгих расчетов различных ситуаций на бумажке.
11) В ходе работы алгоритма будем работать с кластером "Игровая ситуация" (далее ИС), включающим в себя:
а) Текущее состояние поля. Каждый ход в пустую клетку в цепочке изменяет игровое поле, и результат сохраняется в ИС
б) Текущая позиция нашего коня на нынешней глубине анализа.
в) Суммарный вес цепочки ходов. Upd: Вместо одного значения храним массив - значение веса цепочки на каждой глубине.
г) Первый ход, который привел нас к текущей ИС. Хранить всю цепочку ходов не имеет смысла. В конце работы алгоритма, после выбора ИС с максимальным весом её первый ход и будет результатом работы алгоритма (ходом нашего коня).
12) Расстояние противников до каждой пустой клетки считаем только для начального игрового поля, а не для каждой ИС. Это немного угрубляет модель, но экономит ресурсы.
13) После получения всех возможных ИС на данной глубине проводим очистку от дублей, т.е. таких ИС, у которых совпадает текущее положение коня и игровое поле (разными путями пришли в одну и ту же клетку, одинаково изменив поле). Выбираем ИС с бОльшим рейтингом.
14) ИС первой глубины анализа рассчитываем отдельно (перед циклом). Очистку от дублей не проводим. Заполняем поле "первый ход" в ИС значением "текущая позиция".
15) По ходу работы алгоритма постоянно смотрим время. Если на некоторой глубине анализа обнаруживаем, что время больше, чем время старта алгоритма+2.6 сек - останавливаем работу алгоритма, и из ИС предыдущей глубины ищем ИС с максимальным рейтингом, берем её "первый ход" и подаем на выход.
16) Хочется отмечать повышенным рейтингом такие ходы, которые могут сделать одну или несколько пустых клеток недоступными для врагов (т.е. поощрять ходы, создающие области доступные только нам, для захвата их в конце игры). Но пока не придумал не слишком затратной реализации этого. Скорее всего так и останется нереализованным :(
17) По хорошему нужно сильнее подрезать противников, с бОльшим счетом и слабее с меньшим. не успеваю сделать :(
