valergrad Apr 11 2013 at 11:49

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

1 min

48K

Algorithms *

+84

Comments 30

zvirusz Apr 11 2013 at 12:34

Марио начинается на 6:16

+31

wowscheg Apr 11 2013 at 12:45

Тетрис не осилил, импортному железному мозгу не совладать с сумрачным российским гением)

-18

garbager Apr 11 2013 at 12:55

artmoney — не не слышал…

-26

dmandreev Apr 11 2013 at 12:57

Понравилось в конце — «And only winning move is to pause game»

+12

UFO just landed and posted this here

Graphite Apr 11 2013 at 17:58

Ну я, например, не знал того, что показали на 10:01 и 10:50. Это похоже и правда баг в марио и программа научилась его использовать.

Fedcomp Apr 11 2013 at 19:33

Совсем даже не ерунда. Эти баги как правило гораздо сложнее воспроизвести человеку.

Goodkat Apr 11 2013 at 13:06

Правильно я понимаю, что это брутфорс — грубо говоря, программа сыграет миллион раз в Марио, и один раз пройдёт уровень до конца — это и будет тот случай, когда «программа научилась играть в игры», а стальные 999999 раз не учитываем?

-7

valergrad Apr 11 2013 at 13:13

Нет, не так. Программа анализирует свое поведение на несколько шагов вперед. Т.к. игра полностью детерминированна, то она может рассчитать, что будет, если она нажмет те или иные клавиши, и выбрать такой вариант развития событий, который ей наиболее выгоден. Автор пишет что уровень 1-1 и 1-2, например, проходится программой в 100% случаев, дальше есть некоторые проблемы.

matich Apr 11 2013 at 14:32

Интересно как эта программа справится с лабиринтом на 8-4.

Shirixae Apr 11 2013 at 13:17

Про жадные алгоритмы почитайте. Да, она играет миллион раз, но каждый раз продвигается дальше, учитывает особенности, что повлияло на прогресс, как повлияло, и старается максимизировать выгоду на каждом отдельном этапе. Так что от неразумного тыканья во все кнопки подряд программа переходит к осознанному прохождению игры так, чтобы получить максимальный результат.

Считайте, что ребенок с годовалого возраста растёт с этой консолью и игрушкой, только очень быстро. Поначалу — неэффективно, но с каждым разом — всё лучше и дальше.

Jholinar Apr 11 2013 at 15:53

а чем эта схема отличается от того, как работает мозг? Мы анализируем ближайшую ситуацию и выбираем наилучший вариант развития события. Так и тут, порграмма наперед делает анализ и выбирает лучший вариант.

paradoxs Apr 11 2013 at 18:16

Тем, что в мозгу строится модель мира (игры), выделяются абстракции, законы функционирования объекта (игры) и аналитически строится тактика игры.

Jholinar Apr 11 2013 at 21:24

ну и? именно это и делает программа. что не так? Просчитывает алгоритмы на пару ходов вперед, как и ваш мозг, по сути.

paradoxs Apr 11 2013 at 22:54

Может быть я неправильно понял, но вроде бы программа просто «подбирает» подходящую последовательность команд чтобы пройти игру. Там ведь есть целевая функция. Т.е. она не занимается аналитикой как таковой, а просто методом проб и ошибок находит оптимальное решение.

Eternalko Apr 12 2013 at 02:59

Данный бот не «видит» мира. Он видит только циферки.

WST Apr 11 2013 at 19:00

Брутфорс игр с современными мощностями, строго говоря, вообще неразрешимая задача. В секунду ваша NES проверяет состояние кнопок джойстика 60 раз. Состояние кнопок в каждый момент кодируется 1 байтом. То есть имеется 8 битов, каждый из которых сигнализирует нажатость той или иной клавиши. Итого полный брутфорс одной секунды игрового времени потребует (2^8)^60 итераций. Такая алгоритмическая сложность подразумевает невозможность brute-force даже с учётом дальнейшего развития ЭВМ, так как каждый сгенерированный кадр умножает число попыток, необходимых для полного перебора, на 2^8. Собственно, если бы полноценный brute-force был возможен, не существовало бы такого явления, как tool-assisted speedrunning, который обязательно подразумевает применение человеческого интеллекта.

raspezdal Apr 11 2013 at 15:08

хы, боты для марио. Никогда бы не подумал.

sao Apr 11 2013 at 18:33

Да. И давно. Вот. И вот. Ну и так далее.

Eternalko Apr 11 2013 at 16:46

Это просто мега круто!

efimich Apr 11 2013 at 19:41

Впечатляюще.
Интересно, а если попробовать генетические алгоритмы туда как-нибудь прикрутить.

novoselov Apr 11 2013 at 20:33

*facepalm* народ реально повелся

-2

UnknownGosu Apr 11 2013 at 22:10

Сможете повторить самостоятельно перебежки пакмана между дырками в монстрах, как на 14:18?

novoselov Apr 12 2013 at 00:52

www.youtube.com/watch?v=DlkMs4ZHHr8 — написать конкретного бота под конкретную игру: Да.
Прочитать память и брутфорсом «обучить» непонятно что, непонятно чему… сами закончите мысль?