[Математикам] Можно ли создать идеальную змею?

Насколько я помню там ограниченное количество слотов, так что теоретически наверное можно написать "универсальный" алгоритм.

Что имеешь в виду под слотами? Количество змей?

В игре могут участвовать 2, 3, или 4 змеи.

Из-за того, что змей максимум 4, теоретически можно написать "универсальный" алгоритм?

> Действительно ли для игр такого типа существуют методы создания "идеального" игрока

Существует раздел математики "теория игр". Я с ним знаком лишь поверхностно, но там с помощью теории вероятностей рассчитывают, например, оптимальные стратегии поведения игроков при условии, что стратегии поведения противников заранее не известны. Теория игр занимается, например, некоторыми экономическими задачами, ну и, конечно, их абстрактными и абстрактнейшими обобщениями. Мне в лом было читать правила игры со змеями, но впечатление такое, что... Да, хочу сказать, что когда я знакомился с теорией игр, мне тоже казалось, что алгоритм нужно "тренировать", но натренированные-накачанные-жутко-сложные алгоритмы всё-таки уступили теоретическому идеальному алгоритму ; )

> Что имеешь в виду под слотами? Количество змей?

Нет. Для каждой змеи можно задать до 9 возможных вариантов поведения, т.е. 9 программируемых слотов.

Причем если выкинуть как-минимум 2-3 слота на то, чтобы змея не запутывалась, то остается не так много для нападения.

> Мне в лом было читать правила игры со змеями, но впечатление такое, что...

Ну, давай, договаривай!

Ты смотришь слишком по-бытовому на игру.

Откуда знаешь, что на блокировку запутывания нужно отдавать 30% слотов? А может, эффективнее былоб прикрывать хвост телом (всё время изгибаться чтоб хвост к телу был прижат)? А может на хвост можно положить, и нужно нападение развивать?

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

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

А генетические алгоритмы, это случайный перебор

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

Если решения в чистых стратегиях нет, значит выигрышные стратегии неустойчивы, седловой точки однозначно нет. Посему остаётся вопрос - как найти решение с максимальной вероятностью выигрыша.

Пока что вижу два пути

1. Перебором. Практически на данный момент нереально. Одна мнемосхема состоит из 9x9 клеток, в каждой клетке может быть ~16 возможных значений (голова, туловище, хвост, барьер, НЕ-гтхб, И-гтхб, ИЛИ-гтхб), и таких мнемосхем 9. (Т.е. если представить линейно, нужно перебирать 729 клеток, в каждой из которых возможное значение 1...16. Сколько же это комбинаций? 729^16 ? Т.е. ~10^45 ?).

Чтобы проверить одну комбинацию, надо запускать серию, ну, пусть из ~100 игр, чтоб получить какую-то оценку. Ускорить процесс, тем же минимаксом, практически невозможно, потому что неясно, какие взаимные расположения элементов заведомо неудачные (хотя, наверное, какие-то карты можно составить).

2. Геналгоритмом. Более реально по времени, и в результате будет если и не самая мощная змеюка, но достаточно разумная.


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

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

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

> Ты смотришь слишком по-бытовому на игру.

Я исхожу из опыта игры =)

По мне так в данной игре это возможно! Не так и много вариантов если подумать. Я не совсем понял, вы как геналгоритмы писать здесь собрались?:) Тут ИМХО чистая стратегия и умение просчитывать шаги на пару ходов вперед.

Кстати игруха рульная!:) Жаль что под досом... Надо написать то же самое но под Линь что ли...

П.С. Вот где можно геналгоритмами развлекаться так это в игре robocode. Аналогичная Snake Battle только управлять танками, а поведение их описывать на Java. По ней даже проводят турниры!

> Кстати игруха рульная!:) Жаль что под досом... Надо написать то же самое но под Линь что ли...

Не надо ничего переписывать! Есть такая очень удобная штука - DOSBox, лежит на сайте http://dosbox.com/ . Её просто собираешь, делаешь make install, и можно потом любые досовские игрушки под ДОС! Немного неприятно, что нельзя собрать пакет, потому что параметр "DESTDIR" не работает, но DOSBox того стОит. Кстати, недавно версия 0.73 вышла...

Я бы вообще DOSBox встроил в ядро и добавил бы в эту виртуальную машину команды процессора для взаимодействия с системой. Программы для DOS благодаря системе DOSBox обладают гораздо большей переносимостью, чем программы чисто для GCC: потому что чем переписывать программу под новую платформу, достаточно переписать лишь GCC и DOSBox, и под DOSBox'ом мпокойно запускать программу на новой платформе...