Created a program that can play NES-games
At the well-known comic conference SIGBOVIK2013 , which took place on April 1, 2013, and is usually fake comic research, Dr. Tom Murphy prepared a work that, in my opinion, is quite interesting.
In short - he taught the program to play the good old dandy games on the NES-emulator. How does this happen?
At the first stage, a person plays a game, and the program carefully monitors the state of the memory of the emulator and searches for cells that are steadily increasing their values. (Most likely, these will be cells - glasses, lives, etc.) Further, it is logical to assume that the goal of the game is to increase the values of these cells. At the second stage, the program itself tries to play these games. Since Since the state of the game is completely deterministic from the state of the RAM memory and input keys, then we can assume that everything has come down to the classic reborder problem, in which we have possible variants of keystrokes and an evaluation function. The problem is, of course, in an extremely large search space (we have 60 frames per second, in each of which the emulator can register one of eight possible keystrokes), i.e. In general, the number of possible variants increases by 8 to the 60th power every second.
But using a combination of greedy and reoriential algorithms, he managed to force AI to play some games very impressively, and even in the thoroughly studied and jammed holes of Super Mario Brothers to find such exploits that most of you did not know.
In more intellectual games (like Tetris), of course, success is more modest.
Video, with the presentation and fragments of computer games:
')
For those who want to read more in detail about the program architecture and algorithms, here is the link
In short - he taught the program to play the good old dandy games on the NES-emulator. How does this happen?
At the first stage, a person plays a game, and the program carefully monitors the state of the memory of the emulator and searches for cells that are steadily increasing their values. (Most likely, these will be cells - glasses, lives, etc.) Further, it is logical to assume that the goal of the game is to increase the values of these cells. At the second stage, the program itself tries to play these games. Since Since the state of the game is completely deterministic from the state of the RAM memory and input keys, then we can assume that everything has come down to the classic reborder problem, in which we have possible variants of keystrokes and an evaluation function. The problem is, of course, in an extremely large search space (we have 60 frames per second, in each of which the emulator can register one of eight possible keystrokes), i.e. In general, the number of possible variants increases by 8 to the 60th power every second.
But using a combination of greedy and reoriential algorithms, he managed to force AI to play some games very impressively, and even in the thoroughly studied and jammed holes of Super Mario Brothers to find such exploits that most of you did not know.
In more intellectual games (like Tetris), of course, success is more modest.
Video, with the presentation and fragments of computer games:
')
For those who want to read more in detail about the program architecture and algorithms, here is the link
Source: https://habr.com/ru/post/176309/
All Articles