Алгоритм борьбы с змеей

Вопрос:

В сетке (10 * 10) есть две змеи: A и B. В каждом повороте змея оставляет еще одну часть. Так выглядит:

Шаг 1:

. . . . . . . . . .
.                 .
.     B           .
.                 .
.                 .
.                 .
.                 .
.     A           .
.                 .
. . . . . . . . . .

Шаг 2:

. . . . . . . . . .
.                 .
.     _B          .
.                 .
.                 .
.                 .
.     A           .
.     |           .
.                 .
. . . . . . . . . .

Шаг 3:

. . . . . . . . . .
.                 .
.     __B         .
.                 .
.                 .
.     A           .
.     |           .
.     |           .
.                 .
. . . . . . . . . .

Цель каждой змеи – выжить дольше, чем предыдущая, если он прорывается в стену или часть тела кого-то, он умирает, а противник выигрывает.

Вопрос в том, есть ли какие-либо известные алгоритмы, которые определяли бы, каким образом должна идти змея? Единственные, о которых я могу думать, действительно просты и, вероятно, бесполезны.

Ответ №1

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

Что вам нужно сделать, так это (как во многих играх (как в шахматах)), чтобы присвоить значение данной ситуации на основе некоторой системы классификации. Они вычислили все следующее возможное “состояние” (вы перемещали и или враг перемещался). Сравните эти два государства и выберите лучший.

Вы можете оценивать “делает возможности противника меньшим + делает собственные возможности больше”. Вы также можете предположить, что вражеская змея будет выбирать на основе подобной системы (я предполагаю, что игрок-человек).

Ответ №2

Вы можете попробовать альфа-бета-обрезку/глубину-ограниченный подход или поиск Expectimax. Таким образом, каждая змея будет вычислять оптимальный способ игры на основе заданной глубины, так как было бы довольно сложно перечислить все пространство.

Ответ №3

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

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

Ответ №4

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

Оцените статью
TechArks.Ru
Добавить комментарий