Как я научил ИИ играть в Tetris для NES. Часть 1: анализ кода игры

[@multiprogramm]

Спасибо, интересно! Любопытно будет почитать вторую часть про алгоритмы бота, который играет в тетрис, потому что в строгом смысле эта задача NP-полная. Подозреваю, что там будет просто разумное приближение с допущениями, и ИИ всё-таки будет в конце концов проигрывать.
Кстати, жалко, что статья об этом NES-тетрисе, а не от Tengen. Лично мне тот сильно больше нравится.

[@multiprogramm]

Хотя, кстати, запамятовал: NP-полная задача — задача какой-либо оптимизации стратегии с известной заранее лентой фигур. И разумное приближение как раз, наверное, будет в том, что состояние стакана в итерации будет фиксировано, а известны будут только текущая и следующая фигуры — т.е. естественные ограничения игры. А все такие комбинации расположения двух фигур можно, думаю, и просто перебрать. Но, всё-таки, рано или поздно ИИ всё равно должен проиграть.
arxiv.org/pdf/cs/0210020.pdf

[@khim]

Там как и во многих других местах — простое соседствует с безумно сложным.

Просто — доказать, что если фигурки генерируются случайно, то независимо от действий игрока он рано или поздно проигрывает.

Дальше — вопрос уже с полным знанием: есть заранее известная последовательность фигур, которые будут бросать, сколько продержится игрок? Вот эта задача — уже NP-трудная.

Но это всё при случайных фигурах. А в настоящем Тетрисе там PRNG… вовсе не факт, что тут AI должен вообще проиграть!

[@gmother]

Статью до конца не осилил, но очень люблю, когда люди вот так вот упарываются, приятно посмотреть!

[@AngReload]

Не могу представить какая могла бы быть восьмая фигура? По моему всё что можно уже есть, а остальные либо требуют больше-меньше четырех блоков или не были бы целыми.

[@Bhudh]

А её и нет: ru.wikipedia.org/wiki/Тетрамино

[@AngReload]

Даже жаль что так.

[@Atamah]

«Аббревиатура V/O на экране юридической информации» из статьи — это скорее всего «внешнеэкономическое объединение», форма юр. лица, только таким разрешалось заключать контракты с иностранными структурами в то время.

[@ThomasMorg]

Спасибо за подробный разбор