Carlos Diuk, Andre Cohen, and Michael L. Littman of Littman’s RL3 Laboratory at Rutgers devised a new way of doing reinforcement learning, using Object-Oriented Markov Decision Processes, a representation that looks at a higher level than usual and considers objects and interactions. They had a paper about this at last year’s International Conference on Machine Learning (ICML). Better yet, they demonstrated their OO-MDPs representation by using it in a system that learned to play Pitfall in an emulator. I don’t believe that the system got all the treasures, but watching it play and explore the environment was certainly impressive. It seems like the technique is an interesting advance. By trying it out on a classic game, the researchers suggest that it will have plenty of “serious” uses in addition to being used in video game testing and in game AI.
Nick Montfort
yay!
I think I’ve talked about this with you before, but someone had a program working through a hacked version of MAME that was discovering Pac-Man patterns. I wish I could have found that software and helped make it actually do non-reversing pattern checking. This program was a side project of someone many years ago.
Are there any papers/discussions out there about the close relationship video games have with MDPs?
MDPs are a great way to formally describe video games are and (to me) RL, or value-function approximation, is a good metaphor for describing what gamers enjoy doing.
(for sfingram) there was a lot about RL and video games at this tutorial: http://research.microsoft.com/en-us/projects/mlgames2008/
Check out these people’s work!
Nice work!
However, there’s lots of work on using reinforcement learning algorithms of different kinds (temporal difference learning, evolution strategies etc.) to learn to play games. My previous supervisor Simon Lucas worked on learning to play Pac-Man (using the Microsoft Revenge of Arcade version), I’ve worked on various car racing games, Unreal Tournament, Super Mario Bros etc. The proceedings of the yearly Computational Intelligence and Games conferences are full of examples of this kind of research.
Apart from a good way of testing the various kinds of RL algorithms, it’s also a good way of learning about the game you’re testing, and might actually be useful in game design.