Мой игровой ИИ использует алгоритм, который ищет все возможные будущие состояния на основе ходов, которые я могу сделать (минимакс / монте-карло эск). Он оценивает эти состояния, используя систему оценки, выбирает конечное состояние с наивысшей оценкой и следует ему.
Это хорошо работает в большинстве ситуаций, но ужасно, когда награды редки. Например: есть желаемый коллекционный объект, который находится на расстоянии 3 плиток справа от меня. Естественным решением было бы пойти направо-> направо-> направо.
Но мой алгоритм ищет 6 оборотов. И он найдет множество путей, которые в конечном итоге собирают объект, в том числе те, которые занимают более 3 ходов. Например, он может найти путь: вверх-> вправо-> вниз-> вправо-> вправо-> вниз, собирая объект на 5-м ходу.
Поскольку в обоих случаях конечные конечные узлы обнаруживают объект как собранный, он, естественно, не предпочитает один или другой. Таким образом, вместо того, чтобы идти направо на 1-м ходу, он может идти вверх, вниз или влево. Это поведение будет повторяться точно на следующем ходу, так что оно в основном танцует случайным образом перед собираемым предметом, только удача заставит его наступить на него.
Это явно неоптимально, и я хочу это исправить, но у меня закончились идеи, как правильно с этим справиться. Есть ли какие-либо решения для этой проблемы или есть теоретическая работа, касающаяся решения этой проблемы?
Решения, которые я пробовал:
Увеличьте коллекцию объектов на более ранних ходах. Хотя это работает, чтобы превзойти «шум» оценщика, разница между поворотами должна быть довольно высокой. Ход 1 должен быть оценен выше 2, ход 2 - выше 3 и т. Д. Разница между ходом 1 и 6 должна быть настолько высокой, чтобы в итоге поведение стало жадным, что нежелательно в большинстве ситуаций. В среде с несколькими объектами он может в конечном итоге выбрать путь, который захватывает объект на 1-м ходу, вместо гораздо лучшего пути, который может захватывать объекты на 5-м и 6-м поворотах.
Назначить объект в качестве цели и значение расстояния до него. Если не сделано по очереди, исходная проблема сохраняется. Если это сделано по очереди, то разница в важности, необходимая для каждого хода, делает его слишком жадным. Этот метод также снижает гибкость и вызывает другие проблемы. Выбор цели не тривиален и как бы разрушает смысл алгоритма минимаксного стиля
Идя намного глубже в моих поисках, чтобы он всегда мог найти второй объект. Это стоило бы столько вычислительной мощности, что мне пришлось бы пойти на уступки, например, сократить пути гораздо агрессивнее. Если я сделаю это, я вернусь к той же проблеме, так как не знаю, как заставить ее предпочесть обрезку 5-поворотной версии по сравнению с 3-поворотной.
Придайте дополнительное значение планам, изложенным в последнем повороте. Если бы он мог по крайней мере следовать по неоптимальному пути, не было бы такой большой проблемы. К сожалению, это опять-таки должно быть довольно сильным эффектом, чтобы он работал надежно, заставляя его следовать неоптимальным путям во всех сценариях, снижая общую производительность.