Соревнование Back to the Code закончилось и мы получили огромное удовольствие от просмотра различных повторов игр и изучения стратегий в каждой. Мы увидели достаточное количество хороших идей и мы надеемся вы насладились игрой в той же степени, что и мы.

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

Recar

Для игры с 3 или 4-мя:

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

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

Ищем лучший вариант хода для заполнения:

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

Если в прямоугольнике есть вражеские клетки, то очки = 0 и выходим.

Для области меньше 3 по любой из осей очки = 1 / расстояние до верхней левой точки
Смотрим, где есть наши клетки на периметре, и находим клетку, с которой нам надо идти по кругу, чтобы число шагов до момента закрашивания области было минимально.

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

Очки считаем как (число нейтральных клеток / число шагов)

Очки * 2 если нейтральных клеток хватит для победы.

Для двух игроков:
Очки * 2 за то что прямоугольник касается краем через x=17 и эта средняя линия еще мало заполнена — там больше 10 нейтральных клеток.
Очки / 2 если размер прямоугольника больше 14 по любой из осей.

Для трех или четырех игроков:
Очки * 1.1, если прямоугольник касается края поля.
Очки / 2 если размер прямоугольника больше 13, 12 по любой из осей для 3 и 4 игроков соответственно.
Очки / 2 если за каждого из противников ближе чем на 2 клетки к прямоугольнику.
Очки / 10 если информация из будущего сообщает что на этот прямоугольник претендуют соперники.
Для более стабильного поведения выбранному прямоугольнику с прошлого кадра даем бонус к оценке 1.1.

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

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

В результате получаем точку в которую нам оптимально сейчас идти чтобы заполнить «оптимальную» выбранную область.

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

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

Olaf69

Я только что залил на GutHub репозиторий, который я создал для игры. В нём вы cможете среди прочего найти список примечаний к коммитам.

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

Дерево всех возможных состояний было внушительно большим (близко к 5^кол-во игроков^350 нодов), так что было необходимым придумать несколько правил, которые бы ограничивали поле вариантов состояний. К концу игры правила расширения дерева были такими:

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

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

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

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

Эти правила предполагали, что оппонент не будет действовать агрессивно и отдадут предпочтение увеличению своего счёта, вместо попыток помешать моему прогрессу.

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

На самом деле, с теми правилами расширения я всё ещё был слишком ограничен доступным временем, я только мог оценивать пути небольшой глубины(близко к 10-12, примерно 60000 ответвлений). Скудных 12 клеток было недостаточно, чтобы сформировать большой прямоугольник на сетке размером 35х20 клеток. В действительности это больше заставило меня двигаться по спиралевидной траектории.

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

Если у меня получалось просмотреть всё дерево (частенько за время игры), тогда я пытался уменьшить шаг до 2 клеток, а потом – до одной.

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

00000000001111111111222222222233333
01234567890123456789012345678901234
+-----------------------------------+
0|xxxxxxxxxxxx................ooooooo|0 o: клетки, принадлежащие мне
1|xxxxxxxxxxxx. o o|1 O: Моё положение
2|xxxxxxxxxxxx. oo o|2 .: Лучший расчётный путь
3|xxxxxxxxxxxx. o o|3
4|xxxxxxxxxxxx. o o|4 Проблема, я закрою область только через 22 раунда…
5|xxxxxxxxxxxx..Ooooooo o o|5
6|xxxxxxxxxxxx oo o o|6
7|xxxxxxxxxxxx o oo o|7
8|xxxxxxxxxxxx ooo o|8
9|xxxxxxxxxxxx oo o|9
10|xxxxxxxxxxxx o o|10
11|xxxxxxxxxxxx o o|11
12| x x o o|12
13| x o o|13
14| x o ooooooooo|14
15| x ooo |15
16| x |16
17| x |17
18| x |18
19| Xxxxxxx |19
+-----------------------------------+
00000000001111111111222222222233333
01234567890123456789012345678901234

С единственным критерием в виде количества очков захват всё больших и больших областей является наиболее интересным поведением. И в конце концов твои планы срываются твоими противниками. Я решил использовать две различны формулы:

• Количество дополнительных очков / оставшееся количество шагов > становится интереснее закрывать маленькие области
• Общее количество очков / общее количество шагов > немного оптимизирует области, но они остаются слишком большими

В конечном итоге я решил остановиться на следующем: Количество дополнительных очков + 20 / оставшееся количество шагов + 20

В дополнение, были ещё несколько улучшений, которые помогли мне продвинуться вперёд. Например:

• Ограничивать насколько возможно количество запросов к заполняющей функции;
• Оптимизировать калькуляцию счёта;
• Оптимизировать поиск ближайшей нейтральной клетки;
• Эффективное управление памятью ответвлениями дерева поиска;

И всё же, я сожалею, что мне не хватило времени применить все мои идеи, а именно использовать возможность отправиться назад во времени!