задача заяц выше волка

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

this->map[n.y()][n.x()] = this->map[pos.y()][pos.x()] + 1;

QPoint n = pos + this->possibleMoves[i];

if (canMove(pos + this->possibleMoves[i]))

for (int i = 0; i < 4; i++)

QPoint pos = this->queue.dequeue();

while (!this->queue.empty())

this->queue.enqueue(this->rabbitPosition);

Код, выполняющий поиск в ширину, а точнее заполнение карты значениями равными расстоянию от зайца:

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

Пример оценочной функции 2. Заяц тем вероятней победит, чем меньше ему нужно сделать ходов для победы, при замороженных волках. Это более громоздкий алгоритм со сложностью О(n), где n количество клеточек. Расчет количества ходов сводится к поиску в ширину:

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

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

ЭвристикаВ практическом инженерном понимании, метод минимакса опирается на , которую мы рассмотрим прежде, чем переходить к сути алгоритмов.

Перед продолжением чтения, рекомендую , так будет легче понимать.

На шахматной доске есть 4 волка сверху (на черных клеточках), и 1 заяц снизу (на одной из черных). Заяц ходит первым. Ходить можно только на одну клеточку по диагонали, притом волки могут ходить только вниз, а заяц в любую сторону. Заяц побеждает, когда достиг одной из верхних клеточек, а волки, когда они окружили или прижали зайца (когда зайцу некуда ходить).

Игра «Заяц и волки»

Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном ). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.

Минимакс на примере игры в зайца и волков

Минимакс на примере игры в зайца и волков / Хабрахабр