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."

Comments

Re:am i the only one who misread it as al-Pacman?

[lennier1]

Ms Pac-Man would be a lot easier. The burqa reduces the whole thing to a dark featureless circle that's moving around.

Re:Pac-Man is too hard

[i.r.id10t]

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...

Hmm. That reminds me of Snack-Man

[VortexCortex]

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.

Not a terribly complex game, surprisingly

[davidbrit2]

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.

• A brief summary of the ghosts' behavior
• "The Pac-Man Dossier" - a much more in-depth look at many aspects of the game

Anyway, this seems like it would make a cool undergrad project for an AI class.

Re:Pac-Man is too hard

[Raenex]

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?

Re:Pac-Man is too hard

[Jaqenn]

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.