Как искать путь к победе на Russian AI Cup 2016, но не в том направлении

[Vaspo]

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

[xomachine]

Большое спасибо за Вашу статью. После прочтения её и статьи от Commandos, я стал понимать, почему мой лучший результат был таким не радужным (удалось войти в первую сотню, и то не надолго, в основном на 100-200 местах болтался).

Моя стратегия была намного проще.
Ключевым местом в механизме принятия решений была цепочка правил, которые срабатывали в зависимости от ситуации вокруг или передавали управление дальше по цепочке.
Первые несколько версий вообще не умели в поиск пути, а обход препятствий осуществлялся по факту застревания. Волшебник просто ходил за союзными миньонами, пока не натыкался на противников и не срабатывало более приоритетное правило.
После был прикручен обход препятствий по касательной. Т. е. если луч, построенный от центра волшебника до цели пересекал окружность с центром в центре препятствия и радиусом равном сумме радиусов волшебника и препятствия, то результирующий угол поворота волшебника отклонялся минимальную величину, при которой траектория волшебника шла по касательной к препятствию.
Через несколько игр я обнаружил, что подбор бонусов дает ощутимое преимущество, после чего пришлось реализовывать полноценный поиск пути по путевым точкам в дополнение к обходу препятствий. За основу был взят алгоритм Ли, с добавлением к нему возможности учет веса вершин и ребер графа (вес ребер зависел от длины ребра и наличия на ребре врагов, а вершины только от наличия врагов). Граф состоял всего из 5 точек: углы карты и центр. Для реализации плавного движения, в окрестностях точек результирующее направление движения получалось сложением углов до ближайшей точки и до следующей.

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

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