Comments 9
Спасибо, интересно! Любопытно будет почитать вторую часть про алгоритмы бота, который играет в тетрис, потому что в строгом смысле эта задача NP-полная. Подозреваю, что там будет просто разумное приближение с допущениями, и ИИ всё-таки будет в конце концов проигрывать.
Кстати, жалко, что статья об этом NES-тетрисе, а не от Tengen. Лично мне тот сильно больше нравится.
Кстати, жалко, что статья об этом NES-тетрисе, а не от Tengen. Лично мне тот сильно больше нравится.
0
Хотя, кстати, запамятовал: NP-полная задача — задача какой-либо оптимизации стратегии с известной заранее лентой фигур. И разумное приближение как раз, наверное, будет в том, что состояние стакана в итерации будет фиксировано, а известны будут только текущая и следующая фигуры — т.е. естественные ограничения игры. А все такие комбинации расположения двух фигур можно, думаю, и просто перебрать. Но, всё-таки, рано или поздно ИИ всё равно должен проиграть.
arxiv.org/pdf/cs/0210020.pdf
arxiv.org/pdf/cs/0210020.pdf
0
Там как и во многих других местах — простое соседствует с безумно сложным.
Просто — доказать, что если фигурки генерируются случайно, то независимо от действий игрока он рано или поздно проигрывает.
Дальше — вопрос уже с полным знанием: есть заранее известная последовательность фигур, которые будут бросать, сколько продержится игрок? Вот эта задача — уже NP-трудная.
Но это всё при случайных фигурах. А в настоящем Тетрисе там PRNG… вовсе не факт, что тут AI должен вообще проиграть!
Просто — доказать, что если фигурки генерируются случайно, то независимо от действий игрока он рано или поздно проигрывает.
Дальше — вопрос уже с полным знанием: есть заранее известная последовательность фигур, которые будут бросать, сколько продержится игрок? Вот эта задача — уже NP-трудная.
Но это всё при случайных фигурах. А в настоящем Тетрисе там PRNG… вовсе не факт, что тут AI должен вообще проиграть!
0
Статью до конца не осилил, но очень люблю, когда люди вот так вот упарываются, приятно посмотреть!
+3
Не могу представить какая могла бы быть восьмая фигура? По моему всё что можно уже есть, а остальные либо требуют больше-меньше четырех блоков или не были бы целыми.
0
А её и нет: ru.wikipedia.org/wiki/Тетрамино
0
«Аббревиатура V/O на экране юридической информации» из статьи — это скорее всего «внешнеэкономическое объединение», форма юр. лица, только таким разрешалось заключать контракты с иностранными структурами в то время.
0
Спасибо за подробный разбор
0
Sign up to leave a comment.
Articles
Change theme settings
Как я научил ИИ играть в Tetris для NES. Часть 1: анализ кода игры