Slashdot Mirror
AI Takes On Pac-Man
mikejuk writes "AI takes on Pac-Man — well, in fact it plays both sides. An annual competition challenges participants to write Java programs to control Pac-Man or the ghosts. It might not be chess, but it pits machine against machine, with algorithms going head-to-head as the AI ghosts try and eat AI Pac-Man."
i have no idea what 'arabic pacman' would look like, but i was so eager to click and find out. imagine my disappointment.
The contest for this year is now over.
It would have been nice to know when it started... Guess I'll just have to prepare for next year.
To be fair, AI isn't required to beat the original quarter sucking machine - simply memorize the map patterns. Heck I remember buying a book that had the patters for all of the levels when I was a young lad...
Don't blame me, I voted for Kodos
I once got bored of the same old pac-man levels and made a clone called Snack-Man in JavaScript (before canvas, w/ ms paint).
When the levels are always the same, you can make certain optimizations to the AI, but when the levels can change a lot, it does add another layer of complexity. I once trained a neural network for each of the 20 levels of the clone -- the AI was as good as I was, but change the level, and it had to be re-trained.
Looks like Snack-Man it's still being hosted, IIRC, it used to work in Firefox and some version of IE, never did work all the bugs out (hence "epsilon"), oops, looks like I left the enter key = reset ghosts on too. Oh well, I've always used an honor system anyhow (game speed is controllable).
Man, just listen to those crappy MIDI tracks... (brings back memories of Y2K), at least the volume controls still work.
Ah yes, if you paste this into the address bar while paused it turns off the, er, noms, while leaving other sound effects in place...
javascript:void(NOM_NOM_NOM_NOM = false);
(I guess I never did upload the version with that option toggle.)
Entering: javascript:void(debug = true);
in the address bar, then using "new game" will show the ghost's "vision" boxes.
Yep, looks like the exponential ghost-point glitch never got fixed either.
Each ghost you eat while they are "scared" doubles the point value of the next ghost you eat. So, all you have to do is keep at least one ghost edible while the others respawn, then eat more diet pills, ghosts & 1ups, and you can max out the score on the second level.
Been so long since I coded any JS... I might try to port this over to Android and give it a face lift.
Oh, back on topic -- It's pretty neat to watch TFA's AI vs AI, but IMHO, even crappy AI is good enough to best most humans.
The first incarnation of my clone used a dynamic heuristic shortest-path algorithm for the smartest ghost instances, and other techniques for the other ghosts, but it really was too hard to be enjoyable for most everyone, and the JS engines circa Y2K were too slow to run the advance AI unless you have a very fast rig. It's still pretty tricky with just "dumb magnetic" attractors -- I even had to add blind spots, and make it so the ghosts never reverse directions (unless they have to) before anyone ever got half way through.
Sometimes fun is more important than clever AI -- I guess in today's very complicated shooters and strategy games the AI would have a much harder time catching up to human opponents, but Pac-Man should be a breeze.
Assuming they're pitting their Pac-Man bots against the logic of the original arcade game, there isn't a whole lot of complexity to deal with. All four of the ghosts behave in different, but very predictable fashion. In a nutshell, every ghost chooses its target space on the board differently, but they all close in on their respective target space in exactly the same manner. Knowing how these target spaces are chosen, one could probably write a reasonably effective AI player only needing to "think" a few hundred frames in advance. This is difficult for a human player to do in real time, of course
There are a couple of interesting articles about how the game works. If you've played the game and know how unpredictable the ghosts can seem at times, it's remarkable to find out that the algorithms behind their behavior are so incredibly simple. I used to wonder if the game employed some kind of sophisticated path-finding algorithm like A*, but it's actually nowhere near that level of complexity.
Anyway, this seems like it would make a cool undergrad project for an AI class.
I guess it would say that your friends and coworkers are thick as shit or really aren't that interested in video games.
But then, you can also ask the AI, "where's the salt?" or other some such question and wait for a sensible response. Or ask it to catch a ball. Or navigate its way through a town, find a nice birthday present, bake a cake, create spontaneous conversations with strangers... Lots of things that I'm sure it would fail at.
bang goes my karma... again...
It always amazes me when I show Pac-man to various people and they "It's too hard." And yet here's an AI that can apparently beat it..... what does that say about my friends and coworkers?
What does this dumb comment say about you?
I got introduced to programming via Advanced T-Robots, actually. Similar, but assembly-like code.
But no, programming games have moved on since P-Robots. Not much. Depressingly little, actually. But there is only the hazy genre link between this pacman AI competition and P-robots.
Gamasutra did an awesome article a few years ago talking about the creation of PacMan. Link: http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php
It included a fascinating discussion of the Ghost AI behavior. The short version is that the Ghosts can't turn around*, and try for the shortest path to their target tile. The Red ghost is aiming right under you, the Blue ghost is aiming for 3 tiles ahead of you, the Yellow ghost is aiming for 3 tiles behind you, and the Orange ghost is aiming for the center of the map (which he can't reach, so he orbits the spawning area).
This leads to interesting tricks where you manipulate the Blue and Yellow ghost by changing directions right as they pathfind, so that they target a tile that you don't care about and get out of your way until the next fork in the maze.
It is my understanding the current world record holder did NOT memorize map patterns and timing, but by learning the AI behavior and manipulating the ghosts. This was successful because people who memorize the routes are screwed if they mess up timing on a turn or something, but this technique lets you have a fighting chance to recover.
*The ghosts take short breaks every ~15 seconds where they stop targeting you and start targeting an assigned corner of the maze. When a break starts or stops all ghosts suddenly reverse direction as a tell. They reverse direction even if it means not killing you, and even if it means they're going away from their target tile.
You are awash in a sea of fiercely stated opinions. Obvious exits are: 'File->Quit', 'Reply', and 'Page Down'.
It always amazes me when I show Pac-man to various people and they "It's too hard." And yet here's an AI that can apparently beat it..... what does that say about my friends and coworkers?
I can't beat level 3, yet I'm sure I can program an AI that could play better than me. What that's supposed to mean? :)
I rarely respond to comments. Also, don't ask for clarifications: a brain and Google are faster, believe me!
AI is not about finding an algorithm to beat the machine, it should be about an algorithm that can learn while playing an improving itself until it can beat the machine. This is AI. Finding and programming an algorithm beating the machine isn't AI, it is real intelligence since the programmer has done all the work until his/her algorithm effectively beat the machine.
Achille Talon
Hop!