Tool Assisted Speedrun

[Dimon157]

Есть такое забавное направление как скоросное прохождение игр.
То есть требуется пройти какую-либо игру за наименее возможное кол-во времени (Центральный сайт, Вики, Английское Вики).
Далее, если использовать некие возможности эмулятора приставочных игр (замедленная скорость проигрывания, возможность сохранения/загрузки в любом месте и т.д.), то можно добиться существенно лучшего результата. Такие прохождения называются tool assisted speedrun (далее TAS, дословный перевод - скоросное прохождение с использованием инструментов). Центральный сайт, английское Вики.
И наконец для TAS'а одной игры (Mega Men) было сделано следующее:
1) дезассемблирован ROM игры
2) написана программа (BisqBot), которая в некоторых частях игры находила с помощью полного перебора оптимальные нажатия приставочных кнопок.
Благодаря этому:
1) было заметно улучшено время прохождения
2) (!) находились новые премы
К сожалению, из-за того что сложность полного перебора экспоненциальная, не было возможности "пройти" таким образом всю игру. Я вполне допускаю что применение генетического алгоритма может решить дело. Тогда, вне сомнения, это будет большой прорыв.

А теперь посмотрим на это дело в контексте цивилизации:
например требуется на открытой карте без врагов как можно быстрее улететь в космос. То есть полностью исключен элемент рендома.
Вполне можно было бы написать полный перебор. Для OCC и скорости UltraQuick (<100 ходов).
И, вполне вероятно, нашлись бы новые интересные приемы ведения игры.

Или другая задача: на островной/континентальной карте как можно быстрее получить Астрономию.
Полагаю и много других задач можно было бы придумать и получить интересные приемы.


К сожалению мне написание полного перебора не осилить, и было бы замечательно если бы кто из мододелов помог.

Ваши мысли?

[Vox]

Для цивы полный перебор возможных дейсвий уже ходов за 30-40 даст количество вариантов, недоступное современным компьютерам .

Если речь идет о полном переборе .

[Dimon157]

Ну во-первых 30-40 ходов - это тоже результат.
А так, конечно нужно чем-то жертвовать или как-то улучшать алгоритм. Например в ОСС без оппонентов юнитам ходить нет смысла. Поэтому там разветвления идут по рабочим, выбору что учить и что строить.

Или предложить другой алгоритм, например, генетический.
Ну или как вариант разбить цель на подцели и оптимизировать каждую по отдельности.
В СГОТМах, кстати, возникала потребность в локальной оптимизации.

[Vox]

Все равно после пятнадцатого хода количество разветвлений будет 3-4 за ход. А что такое 4 скажем в 20й степени ты сам представляешь

[Dimon157]

2^10=10^3
4^10=10^6
4^20=10^12
Да многовато. Нужно дробить или улучшать алгоритм.

[Линник]

<div class='quotetop'>Цитата(Dimon_157 * 4.6.2008, 17:18) [snapback]249657[/snapback]</div>

Да многовато. Нужно дробить или улучшать алгоритм.
[/b]

Вот БуддаХ в Театре не плохо продвинулся в этом направлении:
http://www.civfanatics.ru/forum/index.php?...ic=7664&hl=

з.ы. сорри

[BuDDaH]

Все в Театр!
Первый звонок уже прозвенел!

[Lexad]

Не совсем понимаю, зачем вообще это нужно. Так можно и в шахматы играть не самому, а дублировать через чессмастер. Об осуществимости промолчу.

[Dimon157]

Чтоб:
1) возможно обнаружить новые приемы.
Вот, например, взять финт строительства стен защитным лидером. Он довольно важный, а обнаружился только через год после выхода игры. Поэтому я не исключаю что есть еще полезные финты, которые еще не обнаружены.
Можно посмотреть на это и под другим ракурсом. Для некоторых соревнований используются моды (а не оригинальная игра) и для них групповой опыт не такой большой как для ориг. игры. Уж там то точно есть хорошие необнаруженные приемы.
2) увидеть идеальную игру и сделать соответствующие выводы (последовательность наук, обработка тайлов, последовательность построек и т.д.)
Поясню на примере. Axius для OCC UQC выложил алгоритм игры. Ну и будем считать, чисто для примера, что если не идти сначала к медитации (а Axius предложил рискнуть и пойти), то у свода мы первые, а за счет такой экономии в Космос улетается раньше на 1 ход.
Увидев бы идеальную игру был бы сделан этот вывод, а также какой приоритет обработки стартового золота (после 1-2 ресурсов еды или сразу), какие тайлы в какой ситуации стоит обрабатывать (вдруг и тут найдется что-то новое) и т.д.

И напоследок такой взгляд: обучение чему-либо очень эффективно, если анализировать действия мастера. А такой подход позволит создать "мастера".