Минимакс для Бомбермана

Я занимаюсь разработкой клона игры Bomberman и экспериментирую с разными типами ИИ. Сначала я использовал поиск в пространстве состояний с помощью A *, а теперь я хочу попробовать другой подход с алгоритмом Minimax. Моя проблема в том, что каждая найденная мимаксная статья предполагаемых игроков чередуется. Но в Bomberman каждый игрок совершает какое-то действие одновременно. Я думаю, что мог бы сгенерировать все возможные состояния для одного игрового тика, но с четырьмя игроками и 5 базовыми действиями (4 хода и место бомбы) это дает 5 ^ 4 состояния на первом уровне дерева игры. Это значение будет расти экспоненциально с каждым следующим уровнем. Я что-то упускаю? Есть ли способы реализовать это или я должен использовать совершенно другой алгоритм? Спасибо за любые предложения

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

Если ИИ совершенен, ваши игроки будут разочарованы. Либо потому, что они всегда проигрывают, либо вы получаете 0,3 кадра в секунду.

Если он не достаточно умен, ваши игроки будут скучать.

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

В зависимости от сложности вы можете изменить эти функции, чтобы улучшить или уменьшить сложность.

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

Вместо этого вы должны использовать более стратегический подход.

Вы должны спросить себя: как игрок-человек принимает решения, играя в Bomberman? Обычно игрок должен следовать четырем основным приоритетам:

1. избегать взрывных зон бомб
2. размещать бомбы, чтобы другие не могли избежать взрывоопасных зон
3. собирать бонусы
4. разместить бомбы, чтобы взорвать камни

Первый приоритет может быть выполнен путем создания «карты опасности». Когда бомба установлена, все плитки, покрытые ею, должны быть помечены как «опасные». Чем раньше взорвется бомба (помните о цепных реакциях!), Тем выше уровень опасности. Всякий раз, когда ИИ замечает, что он находится на поле с высокой опасностью, он должен отойти. При прокладке пути (по какой-либо причине) следует избегать полей с высоким уровнем опасности (их можно реализовать путем искусственного добавления к ним более высокой стоимости пути).

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

Это уже должно создать разумный защитный ИИ. Так что насчет обиды?

Когда ИИ понимает, что сейчас он достаточно безопасен, он должен планировать наступательные маневры: он должен подумать, как он может увеличить карту опасности вокруг других игроков, размещая бомбы. Выбирая место для установки бомбы, он должен отдавать предпочтение близким местам, чтобы ему не приходилось двигаться далеко. Следует также не учитывать места расположения бомб, когда карта опасностей не дает разумного пути эвакуации.

Я думаю, что мог бы сгенерировать все возможные состояния для одного игрового тика, но с четырьмя игроками и 5 базовыми действиями (4 хода и место бомбы) это дает 5 ^ 4 состояния на первом уровне дерева игры.

Верный! Вам нужно искать все 5 ^ 4 (или даже 6 ^ 4, так как вы можете идти в 4 направлениях, останавливаться и «ставить бомбу»?) Действия для каждого игрового тика. НО, когда игрок уже решил двигаться, требуется некоторое время, чтобы ход был выполнен (например, 10 игровых тактов). В этот период количество возможностей уменьшается.

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

Вы можете использовать Hash-Table, чтобы вычислять одно и то же игровое состояние «поддерево» только один раз. Представьте, что игрок А идет вверх и вниз, в то время как все остальные игроки «ждут», вы попадаете в одно игровое состояние. Это так же, как для «левый-правый» или «правый-левый». Также перемещение «вверх-в -лево» и «влево-вверх» приводит к тому же состоянию. Используя хэш-таблицу, вы можете «повторно» использовать рассчитанный счет для игрового состояния, которое уже было оценено. Это значительно снижает скорость роста. Математически это уменьшает основание вашей функции экспоненциального роста. Чтобы понять, насколько это снижает сложность, давайте посмотрим на ходы, которые возможны только для одного игрока, по сравнению с достижимыми позициями на карте (= разные игровые состояния), если игрок может просто двигаться вверх / вниз / влево / вправо / остановить ,

глубина 1: 5 ходов, 5 разных состояний, 5 дополнительных состояний для этой рекурсии

глубина 2: 25 ходов, 13 различных состояний, 8 дополнительных состояний для этой рекурсии

глубина 3: 6125 ходов, 25 различных состояний, 12 дополнительных состояний для этой рекурсии

Чтобы визуализировать это, ответьте себе: какие поля на карте могут быть достигнуты одним движением, двумя ходами, тремя ходами. Ответ: Все поля с максимальным расстоянием = 1, 2 или 3 от начальной позиции.

При использовании HashTable вам нужно оценивать каждое достижимое игровое состояние (в нашем примере 25 на глубине 3) один раз. Принимая во внимание, что без HashTable вам нужно оценивать их несколько раз, что будет означать 6125 оценок вместо 25 на уровне глубины 3. Лучшее: после того, как вы вычислили запись HashTable, вы можете повторно использовать ее в последующих временных шагах ...

Вы также можете использовать инкрементные углубления и альфа-бета-обрезку поддеревьев, которые не стоит искать более подробно. Для шахмат это уменьшает количество искомых узлов примерно до 1%. Краткое введение в обрезку альфа-бета можно найти в видео здесь: http://www.teachingtree.co/cs/watch?concept_name=Alpha-beta+Pruning

Хорошее начало для дальнейших исследований - http://chessprogramming.wikispaces.com/Search . Страница относится к шахматам, но алгоритмы поиска и оптимизации практически одинаковы.

Другой (но сложный) алгоритм ИИ, который больше подходит для игры, - это «Изучение временных различий».

С уважением

Стефан

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

--редактировать--

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

- изменить № 2 -

Если вы пересчитываете свои лучшие ходы только раз в 1 секунду, вы также можете попытаться выполнять более строгое планирование уровня. Что я имею в виду под этим? Вы знаете, сколько ходов вы можете сделать за 1 секунду. Таким образом, вы можете составить список доступных позиций (например, если это будет 3 хода в 1 секунду, у вас будет 25 доступных позиций). Тогда вы можете планировать, как: перейти в «положение х и разместить бомбу». Как предлагали некоторые другие, вы можете создать карту «опасности», которая используется для алгоритма маршрутизации (как перейти в положение x? Какой путь следует отдавать предпочтение [в большинстве случаев возможны некоторые вариации]). Это меньше потребляет памяти по сравнению с огромным HashTable, но дает менее оптимальные результаты. Но поскольку он использует меньше памяти, он может быть быстрее из-за эффектов кэширования (более эффективное использование кэшей памяти L1 / L2).

ДОПОЛНИТЕЛЬНО: Вы можете выполнить предварительный поиск, который содержит ходы только для одного игрока каждый, чтобы отсортировать варианты, которые приводят к проигрышу. Поэтому выведите всех других игроков из игры ... Сохраните комбинации, которые может выбрать каждый игрок, не теряя. Если есть только проигрышные ходы, ищите комбинации ходов, в которых игрок остается живым дольше всего. Чтобы сохранить / обработать этот вид древовидных структур, вы должны использовать массив с указателями индекса, например так:

class Gamestate {
  int value;
  int bestmove;
  int moves[5];
};

#define MAX 1000000
Gamestate[MAX] tree;

int rootindex = 0;
int nextfree = 1;

Каждое состояние имеет оценочное «значение» и ссылки на следующие состояния игры при движении (0 = стоп, 1 = вверх, 2 = вправо, 3 = вниз, 4 = влево) путем сохранения индекса массива в «дереве» в ходах [0 ] на ходы [4]. Чтобы построить ваше дерево рекурсивно, это может выглядеть так:

const int dx[5] = { 0,  0, 1, 0, -1 };
const int dy[5] = { 0, -1, 0, 1,  0 };

int search(int x, int y, int current_state, int depth_left) {
  // TODO: simulate bombs here...
  if (died) return RESULT_DEAD;

  if (depth_left == 0) {
    return estimate_result();
  }

  int bestresult = RESULT_DEAD;

  for(int m=0; m<5; ++m) {
    int nx = x + dx[m];
    int ny = y + dy[m];
    if (m == 0 || is_map_free(nx,ny)) {
      int newstateindex = nextfree;
      tree[current_state].move[m] = newstateindex ;
      ++nextfree;

      if (newstateindex >= MAX) { 
        // ERROR-MESSAGE!!!
      }

      do_move(m, &undodata);
      int result = search(nx, ny, newstateindex, depth_left-1);
      undo_move(undodata);

      if (result == RESULT_DEAD) {
        tree[current_state].move[m] = -1; // cut subtree...
      }

      if (result > bestresult) {
        bestresult = result;
        tree[current_state].bestmove = m;
      }
    }
  }

  return bestresult;
}

Этот вид древовидной структуры намного быстрее, поскольку динамическое распределение памяти действительно очень медленное! Но хранение дерева поиска тоже довольно медленное ... Так что это больше вдохновение.

Поможет ли это представить, что все по очереди?

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

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