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