Pac-Man AI Research and Competitions | AI and Games #06

Key Takeaways

[Music] So, what is the deal with Pac-Man? That is an excellent question, largely because this video is here to explain why AI researchers kind of like myself have been so interested in Pac-Man for the last kind of 10 years or so. I'm Tommy Thompson and this video accompanies a written piece on this subject over on my website that goes into a lot more detail on the topic. But let's start at the beginning. Pac-Man is a video game dating back to the 1980s which not only proved rather popular but was also largely influential at the time given that it helped define a genre of games that deviated from the likes of kind of Space Invaders which was arguably one of the biggest games in the arcades back at the time of release. To be fair, I'm assuming that anybody who watches this video has at least seen or heard of Pac-Man before now. It was quite popular. It's still quite pervasive in the kind of gaming culture. And to be fair, if you don't really know much about it, I'd just go and watch the opening 20 minutes of Scott Pilgrim Versus the World. If you want to then watch the rest of it, and it is a pretty good movie, then you go ahead and do that. I'd encourage you to do so. Be a good spend of your time. [Music] Hey, what's up? Nothing. Hey, you know Pac-Man? I know of him. Well, Pac-Man was originally called Puckman. They changed it because uh not because Pac-Man looks like a hockey puck. Pu. Pacu means flap your mouth. and that they were worried people would change scratch out the P, turn it into an F, like Yeah, that's amazing. Um, am I dreaming? I'll leave you alone forever now. Thank you. So, you know, in summary, for those of you who can't be bothered watching the movie is Pac-Man, you know, the protagonist who provides his name for the game is tasked with choing on pills lying in corridors of a maze. Don't ask, it's video games in the 80s. It didn't have to make sense. But it had an added task of avoiding ghosts that hunt the player down. Like I say, the Pac-Man series is now well established in gaming history, but it doesn't really carry the novelty and popularity that it once did. I mean, this is often the case with games. You know, technologies advancing, and video games continue to change in size, scope, and complexity. As a result, outside of a dedicated fan base and the odd re-release, Pac-Man is not as popular as it once was. While the gaming masses have largely lost interest in Pac-Man, AI researchers became increasingly interested in the game around the sort of late 1990s to early 2000s. This was during the formative years of what is now an established body of research on computational and artificial intelligence and its applications within games. Back in the early 1990s, John Kosa and Justinian Rosska had experimented with the idea of writing AI software that could control characters in video games. While players nowadays are accustomed to AI controlling non-player characters in games, they were suggesting that AI controls the avatar of the player. It might seem crazy, but it's part of what makes games so interesting for AI researchers, given that games are designed to test the mind of a human. So by extension it provides an interesting problem for AI researchers to see if we can write software that can play a game like a human. In time momentum was established largely thanks to work by Marcus Gallagher, Mark Lewitch, Adichia Kalyanur and Moan Simon who provided highquality research in problems that often mimicked the Pac-Man game. Given that Pac-Man's copyrighted and owned by Namco, developers could not use the original game and access the source code in order to write their own AI bots. Though in time a workaround was found, but instead of playing Pac-Man, researchers focused on Miz Pac-Man, the sequel. Atari introduces the woman of the year, Miz Pac-Man. With a style of entertainment that Pac-Man never knew, an endless supply of floating goodies. Ms. Pac-Man, the sequel that was released in 1982, introduces a number of changes to the formula. One of these changes, in particular, makes the game far more interesting for AI research. The most obvious changes are not particularly relevant, such as the change of art style and the use of a female protagonist. Even the changes to the maps have little effect given that many AI solutions would not be relying upon the original maps given the way the AI would model the environment. Good solutions would be more intuitive and be able to adapt to the new maze designs. The big and allimportant change is remarkably subtle and it's all to do with the ghosts. In the original game, the four ghosts, Inky, Blinky, Pinky, and Clyde, all have a set of specific rules that dictate how they chase the player around the maze. So, at each junction, they make a decision based upon their rule set. This rule is not immediately apparent to you, but expert players have been able to discern how each of them operate. As a result, a good player can predict what a ghost will do at a given junction. This means that the ghost and by extension the game is deterministic. Meaning that with some effort we can predict how the game would look 10, 20, even 100 frames in the future. This is how expert gamers play given they know on an implicit level how to avoid the ghosts given they can predict their behavior. Meanwhile, in Miss Pac-Man, the four ghosts, Inky, Blinky Pinky, and Sue use the same rule sets from the previous game, but with one added rule. At a given junction, a ghost can opt to follow their usual rules or take a completely random action. That's it. I hear you say that's what all the fuss is about. Well, allow me to explain. If a ghost can now take a completely random action rather than the expected action, it completely breaks any assumptions we have of how the ghosts play. Unlike Pac-Man, where we could predict the future state with 100% accuracy, we can't do it anymore. It's impossible. In AI terms, we consider this now to be a non-deterministic system, or in layman's terms, a problem where random things happen. This means that the game becomes a lot harder, not just for the AI, but for human players as well. In 2007, Professor Simon Lucas of the University of Essex formed the Miz Pac-Man AI competition. Well, the challenge was to create an AI bot that could reach the highest score possible in the game. Competitions are important in scientific research as they provide a benchmark that's recognized by the community and allows for researchers to focus their efforts on a particular problem domain. This was achieved using a screen scraping framework that played the Windows release of Miz Pac-Man. In time, this was replaced with a new framework deemed more palatable for developers to work on and became the Mis Pac-Man versus Ghosts competition where the players could not only write Pac-Man bots, but also experiment with writing their own ghost teams. Now, in 2014, the AI research community has largely expanded into other areas such as the platformer AI competition, which has since succeeded the Mario AI competition, Starcraft, and also recently the general video game AI competition. However, Miss Pac-Man still has a large presence and is one of the most prominent benchmarks has been established in the game AI research field. This is largely because of the challenge it introduces is so fundamental to AI that it merits continued investigation. And that's it for now. That's why AI people are so interested in Pac-Man. I hope you learned a thing or two or, you know, at bare minimum just enjoyed listening to my lovely Scottish accent. Don't forget to read the written piece attached to this video if you want to learn more. And please check out my other videos. Thanks for watching. This video along with all my other videos on YouTube as well as my written pieces are supported thanks to awesome people like Michael Tardono over on patreon.com. To find out a little bit more about my work and how you can support it, please check out patreon.comiingames. AI_and_game underscores are pretty important. Thanks for watching.