LINUX.ORG.RU
Форум — Talks  

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


0

0
Здравствуйте!


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

Вот меня интересует такой вопрос. Одно время была известна досовая игрушка Snake Battle (Змеиный Бой). В игре игрок "программирует" менемосхемами поведение змеи, затем выпускает змею на ринг (двумерное поле из клеточек ~50x35). Змея должна пытаться кусать за хвост своих соперников. Если змея откусила кусок, длина змеи увеличивается на одну клетку, а длина змеи, у которой откусили кусок, соответсвенно на одну клетку именьшается. Задача во время боя - скушать до последней клетки всех соперников.

Правила, игра, описание тут

http://5kr.mosuzedu.ru/white04/snakes.htm
http://www.almanzor.chat.ru/snake/Sb_doc.txt

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

Вопрос - так ли это? Действительно ли для игр такого типа существуют методы создания "идеального" игрока? Я что-то представить себе не могу. Ну ладно если вырастить змеюку по методу генетических алгоритмов. И так, чтоб при отборе тренировать её с разными противниками и с разным количеством противников. Это понять можно.

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

★
← [нищебродство] делать надписи на дисках
[оффтопик][3D][Java][личный Google] Помогите найти смотрелку m3g →
Насколько я помню там ограниченное количество слотов, так что теоретически наверное можно написать "универсальный" алгоритм.
sysmouse ★
()
Ответ на: комментарий от sysmouse
Что имеешь в виду под слотами? Количество змей?

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

Из-за того, что змей максимум 4, теоретически можно написать "универсальный" алгоритм?
xintrea ★
() автор топика
> Действительно ли для игр такого типа существуют методы создания "идеального" игрока

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

Starduster
()
Ответ на: комментарий от xintrea
> Что имеешь в виду под слотами? Количество змей?

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

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

sysmouse ★
()
Ответ на: комментарий от Starduster
> Мне в лом было читать правила игры со змеями, но впечатление такое, что...

Ну, давай, договаривай!
xintrea ★
() автор топика
Ответ на: комментарий от sysmouse
Ты смотришь слишком по-бытовому на игру.

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

Вопросов таких сколько угодно можно задать, но есть более обширный вопрос - существует ли методика определения, что в данной игре важнее, и как следствие, однозначная, математически верная и доказуемая методика разработки правил поведения змеюк?
xintrea ★
() автор топика
В правилах есть элемент случайности - перемешивание, значит решения в чистых стратегиях не будет, будет только решение с максимальной вероятностью выигрыша. Перебором можно, тут же 4 возможности двигаться
dimon555 ★★★★★
()
А генетические алгоритмы, это случайный перебор
dimon555 ★★★★★
()
Ответ на: комментарий от dimon555
> В правилах есть элемент случайности - перемешивание, значит решения в чистых стратегиях не будет, будет только решение с максимальной вероятностью выигрыша.

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

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

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

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

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


Значит, получается, на практике получить идеальную змею нельзя! Можно получить "идеальную на текущий момент", но всегда будет оставаться возможность что появится лучше.
xintrea ★
() автор топика
Ответ на: комментарий от xintrea
Всякие алгоритмы искусственного интеллекта направлены на сокращение перебора, если найдёшь как его сократить, то получишь решение

ведь картина не может измениться радикально на следующий ход, каждая змея продвинется только на 1 клетку и твоя змея тоже... перебор сокращается
dimon555 ★★★★★
()
Ответ на: комментарий от xintrea
> Ты смотришь слишком по-бытовому на игру.

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

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

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

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

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

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

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

Starduster
()
Вы не можете добавлять комментарии в эту тему: топик перемещен в архив.
← [нищебродство] делать надписи на дисках
Talks
[оффтопик][3D][Java][личный Google] Помогите найти смотрелку m3g →