Post image

The great escape challenge или первый блин комом

The great escape challenge

Конкурс "The great escape challenge" проводимый на сайте CodinGame.com подошел к концу. К сожалению я черезчур поздно зарегистрировался и мне не хватило времени для создания искуственного интелекта, достойного занять места в топе лидеров. Или хотя бы прорватся выше 360 места, которого я занял. К томе же я совершил ряд ошибок во время решения поставленной задачи, речь о которых пойдет ниже.

Задача конкурса:

Есть игровое поле размером 9х9 клеток. На поле, в начале игры, появляются от 2-х до 3-х Дракончиков - ботов. С помощью id указывается какой из них пренадлежит игроку. В зависимости от стартовой позиции бота его надо довести до противоположной грани поля:

  • id 0 - Бот появляется у левого края и его надо довести до правого края.
  • id 1 - Бот появляется у правого края и его надо довести до левого края.
  • id 2 - Бот появляется у верхнего края и его надо довести до нижнего края.

Дракончиков противника можно тормозить устанавливая стены. Стены ставятся между клетками поля. Стенами нельзя полностью перекрывать путь боту к его цели, только тормозить. Количество стен у игрока ограничено: 10 стен для игры с одним противником и 6 для игры с двумя. Стены могут быть либо вертикальными либо горизонтальными и имеют размер 2 клетки. Стены не могут пересекаться.

Каждый ход боты могут либо делать шаг влево, вправо, вверх, вниз (LEFT, RIGHT, UP, DOWN) либо устанавливать стену указывая её позицию и ориентацию (x y V|H).

Проигрывает тот у кого бот врежется в стенку, либо тот кто неправильно установит стену (Установленная стена пересечется с другой или полностью заблокирует путь противнику)

Выигрывает тот кто первым дойдет до противоположной грани.

game field

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

Систамы установки стен была моей второй ошибкой. Во первых, мое решение было нацелено исключительно на противодейстие одному боту. Когда на поле появляловь 2 игрока и они не ставили стены, а просто двигались к своим целям, мой бот гарантированно оставался на втором месте, так как мог блокировать лишь одного противника. Во вторых, установка стен происходило по факту, сразу перед ботом противника и не учитывала будующего поведения конкурентов. В третьих, отсутствовала система "защиты", когда стена ставится так чтобы обеспечить боту выгодный путь к цели и не позволяет другому игроку поставить препятствие перед мои ботом.

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

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

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

Теперь без сомнения я буду участвовать и в следующих конкурсах CodinGame.com. Чего и вам советую.