Лучшая эвристическая функция для игры (AI Minimax)

Есть игра, которую я программировал на java. Игра простая (см. Рисунок ниже). Всего 4 птицы и 1 личинка. Это игра для двоих (AI против человека).

введите описание изображения здесь

  • Личинка может двигаться по диагонали вперед И по диагонали назад.
  • Птицы могут двигаться ТОЛЬКО по диагонали вперед
  • Личинка побеждает, если сможет добраться до линии 1 (забор).
  • Личинка также побеждает, если у птиц не осталось ходов.
  • Птицы НЕ МОГУТ «съесть» личинку.
  • Птицы побеждают, если у личинки НЕ осталось хода (не может двигаться вообще).

введите описание изображения здесь

Когда игра начинается, начинается Личинка, затем может двигаться ОДНА птица (любая), затем Личинка и т. Д.

Я реализовал MiniMax (альфа-бета-обрезка) и использую следующую функцию Assessment () (эвристическая функция).

Дадим следующие числа каждому квадрату на доске.

введите описание изображения здесь

Следовательно, наша функция оценки будет

h (n) = значение положения личинки - значение положения птицы 1 - значение положения птицы 2 - значение положения птицы 3 - значение положения птицы 4

Личинка попытается МАКСИМИЗИРОВАТЬ эвристическое значение, тогда как Птицы попытаются МИНИМИЗИРОВАТЬ его.

Пример:

введите описание изображения здесь

Однако это простая и наивная эвристика. Он не действует разумно. Я новичок в искусственном интеллекте и хотел бы знать, что я могу сделать, чтобы УЛУЧШИТЬ эту эвристическую функцию?

Что было бы хорошей / информированной эвристикой?


artificial-intelligence heuristics minimax alpha-beta-pruning evaluation-function
person Matt    schedule 11.11.2015    source источник
comment
функция оценки, которую вы дали, не имеет смысла (вроде ..).   -  person 柯鴻儀    schedule 11.11.2015
comment
как насчет того, чтобы учесть положение птиц относительно личинки?   -  person 柯鴻儀    schedule 11.11.2015
comment
@Porcelain Вы имеете в виду евклидово расстояние? В этом случае личинка будет стараться отойти от птиц как можно дальше и не будет пытаться добраться до забора (что является приоритетом).   -  person Matt    schedule 11.11.2015
comment
нет, но что-то вроде Манхэттенского Дистанции по диагонали. о расстоянии Манхэттена: en.wiktionary.org/wiki/Manhattan_distance   -  person 柯鴻儀    schedule 11.11.2015
comment
Вы говорите, что одна птица может двигаться - она ​​должна двигаться? или это вариант для любой из сторон?   -  person Ian Mercer    schedule 11.11.2015
comment
@IanMercer Нет, это не вариант. Они ДОЛЖНЫ двигаться, когда пришла их очередь   -  person Matt    schedule 11.11.2015
comment
На сколько квадратов могут двигаться личинка и птицы одновременно?   -  person Aadit M Shah    schedule 27.08.2018

Ответы (3)


arrow_upward
2
arrow_downward

Как насчет этого :

Максимум: личинка

Минимум: птицы

H(t)=max_distance(larva,line_8)+Σmin_distance(bird_n,larva)

or

H(t)=Σmin_distance(bird_n,larva) - min_distance(larva,line_1)

max_distance (larva, line_8): чтобы отразить условие, что личинка находится ближе к линии 1.

Σmin_distance (bird_n, larva): чтобы отразить состояние, при котором птицы находятся ближе к личинке (чтобы заблокировать ее).

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

person 柯鴻儀    schedule 11.11.2015
comment
Это действительно хорошая эвристика. Однако в эту игру можно играть как Личинка (ИИ) против Птиц (Человек) И Птицы (ИИ) против Личинки (Человек). Учитывает ли эта функция оценки птичий аспект игры? (например, если птицы играют за ИИ) - person Matt; 11.11.2015
comment
Кроме того, в этом случае функция оценки будет НИЖЕ, когда личинка приближается к строке 1 ... Личинка пытается максимизировать значение .. Или, может быть, я что-то упускаю? - person Matt; 11.11.2015
comment
Я думаю, что в дереве игр max-min один должен максимизировать счет, а другой должен его минимизировать. учитывая правило победы птиц в вашем случае: птицы побеждают, если у личинки НЕ осталось хода, птицы должны попытаться заблокировать личинку, просто подойдя к ней вплотную. - person 柯鴻儀; 11.11.2015
comment
просто изменение min_distance(larva,line_1) на max_distance(larva,line_8) или -1* min_distance(larva,line_1) может соответствовать максимальным требованиям. - person 柯鴻儀; 11.11.2015
comment
Под max_distance(larva, line_8), что вы имеете в виду точно. Допустим, личинка находится на D2, тогда максимальное расстояние равно 6, верно? Я имею в виду, вы просто посчитаете, как далеко (по вертикали) личинка от линии 8? - person Matt; 11.11.2015
comment
Я думаю, что и расстояние по вертикали, и количество шагов от строки 8 в порядке, и то, и другое может отражать тот факт, что личинка ближе к условию победы. - person 柯鴻儀; 11.11.2015
comment
Разве эвристика не была бы умнее, если бы я КВАДРАТНЫЙ к dist(larva,line_8)? Поскольку чем ближе он подходит к строке 1, тем больше становится функция оценки. Также для птиц я мог бы сказать, когда птица находится ближе всего к личинке (внизу справа ИЛИ внизу слева), тогда удвойте ценность этой птицы. - person Matt; 11.11.2015
comment
да, я полностью согласен с вами насчет КВАДРАТА, нет единого стандартного ответа, но квадратное расстояние лучше. - person 柯鴻儀; 11.11.2015

arrow_upward
2
arrow_downward

Есть 1 простой способ значительно улучшить вашу эвристику. В вашей текущей эвристике значение квадрата A1 на 8 меньше, чем значение квадрата A8. Это заставляет Птиц склоняться к левому краю игрового поля, так как движение влево всегда будет выше, чем движение вправо. Это абсолютно точно. Все квадраты в строке 1 должны иметь одинаковое значение. Таким образом, назначьте все квадраты в строке 1 на 1, в строке 2 на 2 и т. Д. Таким образом, птицы и личинка не будут склонны двигаться влево, а вместо этого могут сосредоточиться на том, чтобы сделать хороший ход.

person chessprogrammer    schedule 11.11.2015

arrow_upward
1
arrow_downward

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

person Iche    schedule 11.11.2015
comment
Я пробовал это. Работает немного лучше. Спасибо. Но это не так умнее ... предложенная мной эвристика очень наивна ... - person Matt; 11.11.2015