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

Pac-Man is too hard

[cpu6502]

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?

For me the Arcade versions are just about right, as far as difficulty. The home versions (Atari, Commodore) are all too easy (ghosts are dumb), except for the Jr. Pac-Man variant released in 1984 that has intelligent ghosts.

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.

Re:4 1

[Anonymous Coward]

This is one of the real weaknesses of the topic of AI as it relates to games.
We can make the AI more and more advanced, but this is not in the end what is needed. In most games the opponents will have to outnumber the player(s) for the game to be fun, and have to be tough enough as well. If you make them too smart, they'll always win, so you'll have to keep their intelligence down - and possibly their reactiveness, precision &c. as well.

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.

Re:P-Robots

[HeckRuler]

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.