Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 9
Спасибо, интересно! Любопытно будет почитать вторую часть про алгоритмы бота, который играет в тетрис, потому что в строгом смысле эта задача NP-полная. Подозреваю, что там будет просто разумное приближение с допущениями, и ИИ всё-таки будет в конце концов проигрывать.
Кстати, жалко, что статья об этом NES-тетрисе, а не от Tengen. Лично мне тот сильно больше нравится.
Кстати, жалко, что статья об этом NES-тетрисе, а не от Tengen. Лично мне тот сильно больше нравится.
Хотя, кстати, запамятовал: NP-полная задача — задача какой-либо оптимизации стратегии с известной заранее лентой фигур. И разумное приближение как раз, наверное, будет в том, что состояние стакана в итерации будет фиксировано, а известны будут только текущая и следующая фигуры — т.е. естественные ограничения игры. А все такие комбинации расположения двух фигур можно, думаю, и просто перебрать. Но, всё-таки, рано или поздно ИИ всё равно должен проиграть.
arxiv.org/pdf/cs/0210020.pdf
arxiv.org/pdf/cs/0210020.pdf
Там как и во многих других местах — простое соседствует с безумно сложным.
Просто — доказать, что если фигурки генерируются случайно, то независимо от действий игрока он рано или поздно проигрывает.
Дальше — вопрос уже с полным знанием: есть заранее известная последовательность фигур, которые будут бросать, сколько продержится игрок? Вот эта задача — уже NP-трудная.
Но это всё при случайных фигурах. А в настоящем Тетрисе там PRNG… вовсе не факт, что тут AI должен вообще проиграть!
Просто — доказать, что если фигурки генерируются случайно, то независимо от действий игрока он рано или поздно проигрывает.
Дальше — вопрос уже с полным знанием: есть заранее известная последовательность фигур, которые будут бросать, сколько продержится игрок? Вот эта задача — уже NP-трудная.
Но это всё при случайных фигурах. А в настоящем Тетрисе там PRNG… вовсе не факт, что тут AI должен вообще проиграть!
Статью до конца не осилил, но очень люблю, когда люди вот так вот упарываются, приятно посмотреть!
Не могу представить какая могла бы быть восьмая фигура? По моему всё что можно уже есть, а остальные либо требуют больше-меньше четырех блоков или не были бы целыми.
А её и нет: ru.wikipedia.org/wiki/Тетрамино
«Аббревиатура V/O на экране юридической информации» из статьи — это скорее всего «внешнеэкономическое объединение», форма юр. лица, только таким разрешалось заключать контракты с иностранными структурами в то время.
Спасибо за подробный разбор
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я научил ИИ играть в Tetris для NES. Часть 1: анализ кода игры