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.
if course the screen shot is from Ms Pac-Man
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.
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.
My AC stalker: " I personally agree with your posts most of the time, but that won't keep me from modding you troll"
Given equal AI (and ghost speed of, say, 75% of Pac Man), the ghosts will always win. If you assume that they are programmed to give PM a little bit of room around the power pellets, taking that time to spread out around the possible exits from the pellet area, then a four mob coordinated predator pack will have no problem tagging a one mob prey, even with the occasional role switch.
Well, it's Monday morning, so I guess that's the traditional time for verbal quarterbacking.
If you were blocking sigs, you wouldn't have to read this.
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.
I got quite a few hits for "nerblack", but none apparently in the same context. "pahasian/payasian" & "bougnordafricain" came up dry, I'm afraid.
Sloriental was a hit.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
Well, ghost have some movement restrictions while pacman is free to move as she wants. Furthermore she wins if she survives till time runs out.
It looks like pacman and ghost have the same speed, though. Even around corners and tunnels.
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.
Anyone get the idea that this is a rip from the P-Robots idea? I was first introduced to this "game" in high school in my Pascal class. Essentially, each coder uses Pascal to create a robot. The game would load the robots and have them battle it out. Apparently, there is still a following.
I thought that you can play pacman on
http://www.spelletjespaats.be
NO?
It's not that simple. The rules for the ghosts are different from Pac man. Pac man can change directions at any time, while the ghosts can only make decisions at intersections, and cannot go backwards. When the ghosts get to an intersection, they only have 3 possible directions to go. Pac Man, on the other hand has 4 possible directions to go (including backwards), and can do this at any time, not just intersections.
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.
A.I. starts with Pac Man and then soon enough it becomes global thermonuclear war.
"Hello Dr. Falken. Would you like to play a game?"
AI ghosts try and eat AI Ms. Pac-Man
Giggity.
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF
This brought on a strong blast of deja vu; there was a program called Rog-O-Matic that successfully played the text-based (but 2-D) game Rogue back in 1984. Rogue was actually a bit like Pac-Man, in some ways; in both you wander around a rectangular grid picking up treasure and avoiding monsters.
In addition to this, the contest adds a random low probability chance each cycle that the ghosts directions actually will be reversed (different from behavior in the vanilla game, but equally no choice in the matter). So even repeat simulations vs the same AI's could yield different results.
Fear is the mind killer.
Tea Tardiers
Why do people think that juvenile name-calling like that will actually help their cause? The best you can hope for is that people think both you AND the tea party are idiots; the worst is that they leave with the impression that you're an idiot, and that the tea party is that which an idiot hates.
The same thing holds for the right when they call Democrats "Demotards" or some such juvenile name. Or when somebody calls Obama OR Bush stupid names. Or, for that matter, when they do the same think to Apple, Microsoft, Linux, or Sony.
I'm all for arguing about and insulting people, organizations, and political parties. You should realize, though, that when they're on the level of an eight year old, they're not going to sway anybody except other third graders. To converse with adults, you should learn to speak as an adult.
If you have an AI competing against another AI, it doesn't matter if one AI always wins, because the other AI isn't in it to have "fun". You just pick an arbitrary metric and try to make the losing AI "better"... i.e. last longer without dying, get a higher score, etc.
This would be a great contest for other games, especially ones that already have a computer player that, in theory, is supposed to be equivalent to the human player. When I played FreeCiv, I was thinking that it might be more fun to program a strategy than to play it live. You could then run tournaments among the different AIs, rank them, and then when playing for real, let the player select a skill level that determines which AIs are selected.
That might be complex, but some games, like Settlers of Catan would also work for this.
http://www.google.com/pacman/
Straw man arguments are lies.
arabic does not mean 'terrorist' , it doesnt even necessarily mean 'muslim'.
serves me right for trying to make an innocent joke that was even remotely related to culture. i should have predicted what would happen.
and will soon be replaced by arduinos
I have yet to meet a Tea Tardier that functioned on the level of an adult. It starts around Sarah Palin and quickly goes downhill from there.
Thanks, it was fun diversion. I don't mind the NOM NOM sounds, but perhaps they could be at a softer volume compared to the other sounds.
As for difficulty, it feels a little like the ghosts are ignoring me much of the time. I think your post was trying to say the ghosts have line-of-sight? So they don't head for me until they see me?
I like the idea of the walls which you can only go through in one direction, but the ghosts can go through in either direction.
It starts around Sarah Palin and quickly goes downhill from there...and at the foot of that hill is you.
If you draw horizontal cross-sections through the map, there really is never more than 4 paths up or down through the map for Pac-Man to escape. Ghosts would have to orbit until everyone is in position, but Pacman is raping the map anyway until all the ghosts show up. All the ghosts have to do is get themselves to these bottlenecks, determine if Pacman is up or down, then migrate their blockade in that direction. Even if Pacman moves through the wrap-arounds, they can reestablish their blockades and repeat.
At best, Pacman gets trivial points. Now, there might be some small windows where Pacman can duck through the blockade as ghosts orbrit, but I bet the mutual support would still be able to pick him off.
I swear to God...I swear to God! That is NOT how you treat your human!
due to the font, i kept reading that wondering who the hell al was
this is a good reason why we should go back to using the dots
Does the AI ghosts "talk" to each other or just run their algorithm? Do they all even run the same algorithm?
Wake me up when they can play Starcraft
oh wait...
http://eis.ucsc.edu/StarCraftAICompetition