Создана программа, умеющая играть в NES-игры

    На известной шуточной конференции SIGBOVIK2013, которая проходила 1-го апреля 2013-го года и представляет собой, как правило, фальшивые шуточные исследования д-р Том Мерфи подготовил работу, которая, на мой взгляд, довольно интересна.
    Если вкратце — он научил программу играть в старые добрые денди-игры на NES-эмуляторе. Как это происходит?

    На первом этапе, человек играет в игру, а программа внимательно наблюдает за состоянием памяти эмулятора и ищет ячейки, которые неуклонно увеличивают свои значения. ( Скорее всего, это будут клетки — очки, жизни и т.д. ) Далее, логично предположить, что цель игры заключается в увеличении значений этих ячеек. На втором этапе, программа уже сама пробует играть в эти игры. Т.к. состояние игры полностью детерминированно от состояния RAM-памяти и входных клавиш, то можно считать, что все свелось к классической переборной задаче, в которой у нас есть возможные варианты «нажатий клавиш» и есть оценочная функция. Проблема, понятно, в крайне большом пространстве поиска ( у нас есть 60 фреймов в секунду, в каждом из которых эмулятор может зарегистрировать одно из восьми возможных нажатий клавиши ), т.е. в общем случае, количество возможных вариантов увеличивается в 8 в 60-й степени раз каждую секунду.
    Но используя комбинацию жадных и переборных алгоритмов ему удалось заставить AI играть в некоторые игры весьма впечатляюще, и даже в насквозь изученном и затертом до дыр Super Mario Brothers находить такие эксплойты, о которых, ручаюсь, большинство из вас не знали.
    В более интеллектуальные игры ( типа Тетриса ), конечно, успехи скромнее.

    Видео, с презентацией и фрагментами игр компьютера:



    Для тех, кто хочет поподробнее почитать про архитектуру программы и алгоритмы вот ссылка
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 30

      +31
      Марио начинается на 6:16
        –18
        Тетрис не осилил, импортному железному мозгу не совладать с сумрачным российским гением)
          –26
          artmoney — не не слышал…
            +12
            Понравилось в конце — «And only winning move is to pause game»
              +4
              <зануда>Вы хотели сказать «The only winning move is not to play»</зануда>

              и даже в насквозь изученном и затертом до дыр Super Mario Brothers находить такие эксплойты, о которых, ручаюсь, большинство из вас не знали
              — нехорошо так людей обманывать. Заинтриговали, а на деле ерунда оказалась.

              А вообще интересная затея, конечно
                +6
                Ну я, например, не знал того, что показали на 10:01 и 10:50. Это похоже и правда баг в марио и программа научилась его использовать.
                  +2
                  Совсем даже не ерунда. Эти баги как правило гораздо сложнее воспроизвести человеку.
                –7
                Правильно я понимаю, что это брутфорс — грубо говоря, программа сыграет миллион раз в Марио, и один раз пройдёт уровень до конца — это и будет тот случай, когда «программа научилась играть в игры», а стальные 999999 раз не учитываем?
                  0
                  Нет, не так. Программа анализирует свое поведение на несколько шагов вперед. Т.к. игра полностью детерминированна, то она может рассчитать, что будет, если она нажмет те или иные клавиши, и выбрать такой вариант развития событий, который ей наиболее выгоден. Автор пишет что уровень 1-1 и 1-2, например, проходится программой в 100% случаев, дальше есть некоторые проблемы.
                    +7
                    Интересно как эта программа справится с лабиринтом на 8-4.
                    +4
                    Про жадные алгоритмы почитайте. Да, она играет миллион раз, но каждый раз продвигается дальше, учитывает особенности, что повлияло на прогресс, как повлияло, и старается максимизировать выгоду на каждом отдельном этапе. Так что от неразумного тыканья во все кнопки подряд программа переходит к осознанному прохождению игры так, чтобы получить максимальный результат.

                    Считайте, что ребенок с годовалого возраста растёт с этой консолью и игрушкой, только очень быстро. Поначалу — неэффективно, но с каждым разом — всё лучше и дальше.
                      +2
                      а чем эта схема отличается от того, как работает мозг? Мы анализируем ближайшую ситуацию и выбираем наилучший вариант развития события. Так и тут, порграмма наперед делает анализ и выбирает лучший вариант.
                        0
                        Тем, что в мозгу строится модель мира (игры), выделяются абстракции, законы функционирования объекта (игры) и аналитически строится тактика игры.
                          0
                          ну и? именно это и делает программа. что не так? Просчитывает алгоритмы на пару ходов вперед, как и ваш мозг, по сути.
                            0
                            Может быть я неправильно понял, но вроде бы программа просто «подбирает» подходящую последовательность команд чтобы пройти игру. Там ведь есть целевая функция. Т.е. она не занимается аналитикой как таковой, а просто методом проб и ошибок находит оптимальное решение.
                              +1
                              Данный бот не «видит» мира. Он видит только циферки.
                        0
                        Брутфорс игр с современными мощностями, строго говоря, вообще неразрешимая задача. В секунду ваша NES проверяет состояние кнопок джойстика 60 раз. Состояние кнопок в каждый момент кодируется 1 байтом. То есть имеется 8 битов, каждый из которых сигнализирует нажатость той или иной клавиши. Итого полный брутфорс одной секунды игрового времени потребует (2^8)^60 итераций. Такая алгоритмическая сложность подразумевает невозможность brute-force даже с учётом дальнейшего развития ЭВМ, так как каждый сгенерированный кадр умножает число попыток, необходимых для полного перебора, на 2^8. Собственно, если бы полноценный brute-force был возможен, не существовало бы такого явления, как tool-assisted speedrunning, который обязательно подразумевает применение человеческого интеллекта.
                        +6
                        хы, боты для марио. Никогда бы не подумал.
                          +1
                          Да. И давно. Вот. И вот. Ну и так далее.
                          +2
                          Это просто мега круто!
                            +1
                            Впечатляюще.
                            Интересно, а если попробовать генетические алгоритмы туда как-нибудь прикрутить.
                              –2
                              *facepalm* народ реально повелся
                                0
                                Сможете повторить самостоятельно перебежки пакмана между дырками в монстрах, как на 14:18?
                                  0
                                  www.youtube.com/watch?v=DlkMs4ZHHr8 — написать конкретного бота под конкретную игру: Да.
                                  Прочитать память и брутфорсом «обучить» непонятно что, непонятно чему… сами закончите мысль?
                                    +4
                                    … — бесценно. Для всего остального есть МастерКард. =)
                                    Не считать рекламой
                              • UFO just landed and posted this here
                                  +8
                                  Алексей, скажите, вот как так получается, вы и программист и вроде уже не подросток и
                                  вы всерьез считаете, что человек писал «бота для Денди»?
                                  • UFO just landed and posted this here
                                  0
                                  А ничего что видео 1 апреля опубликовано?
                                    0
                                    Не думаю, что это шутка. :)

                                  Only users with full accounts can post comments. Log in, please.