Алгоритм для прогнозирования ботов, продвигающихся к призам

Question

Для этой игры есть доска 10x10 и несколько разных призов со значениями от 1 до 9, есть несколько простых ботов, играющих там, где всегда идет после ближайшего приза, а другой всегда идет за призом с наибольшим количеством назначенных ему очков. Боты и призы размещаются случайным образом на доске. Задача состоит в создании еще одного простого ИИ, который всегда собирает наибольшее количество очков и выигрывает игру.

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

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

Answer 1

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

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

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

Обратите внимание, что могут быть другие листья, где у вас больше балл, но проиграть, потому что один из других ботов доминировал над другим. То есть (вы: 12, a: 1, b: 17) vs. (вы: 11, a: 10, b: 9)

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