AI Takes On Pac-Man 113
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."
am i the only one who misread it as al-Pacman? (Score:4, Funny)
i have no idea what 'arabic pacman' would look like, but i was so eager to click and find out. imagine my disappointment.
Re: (Score:3)
I thought we had a video of Weird Al either playing Pac-man, or doing a song about Pac-Man.
Damnit Slashdot. You got my hopes up.
Re:am i the only one who misread it as al-Pacman? (Score:4, Funny)
Re: (Score:2)
Re:am i the only one who misread it as al-Pacman? (Score:5, Funny)
Ms Pac-Man would be a lot easier. The burqa reduces the whole thing to a dark featureless circle that's moving around.
Re: (Score:1)
Ms Pac-Man would be a lot easier. The burqa reduces the whole thing to a dark featureless circle that's moving around.
Wouldn't she looks like one of the ghosts?
Re:am i the only one who misread it as al-Pacman? (Score:4, Funny)
Ms Pac-Man would be a lot easier. The burqa reduces the whole thing to a dark featureless circle that's moving around.
Wouldn't she looks like one of the ghosts?
Except the ghosts would all have the remnants of detonated bombs strapped to their chests.
moderators frighten me sometimes (Score:3)
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.
Re: (Score:2)
It's not featureless. You would see some of her eyes through the "bars" on her face. So it would like a dark circle running around with weird Gothic looking eyes.
Not to mention she would have to lift her dress to eat the dots.... at which point she might... *might*... show some ankle. What that looks like is beyond me.
So I would imagine Ms Pac-Man would be easier to imagine as a yellow ball underneath a burqa that gets stoned to death if she does anything on the grid.
Re: (Score:2)
At best you'd see a darker spot near the eyes.
Sure you're not thinking of a niquab?
Re: (Score:2)
No, the niquab is the one where you get to see their eyes. Which can be a little sexy because you are just looking at their eyes which I guess does not work for the real hardcore Muslims that cannot allow even the smallest glimpse of a woman to reach their eyes.
The burqa is the head to toe one where you live your life looking out through prison bars so that a man from a distance would find it virtually impossible to see skin, much less eye contact. You could be a few feet away and have a hard time actuall
Re: (Score:2)
Re: (Score:3, Funny)
One of the pacman clones was OPECman.
Re: (Score:3)
Re: (Score:1)
Well, Arabic Pacman has of course a few extra rules:
There's Ramadan, a time where Pacman isn't allowed to eat anything. Eating during that time decreases score instead of increasing it.
There's the suicide attack option: Pacman can explode, which costs one life, but kills all the ghosts close to it (adding to the score accordingly).
Re: (Score:1)
Well, Arabic Pacman has of course a few extra rules:
There's Ramadan, a time where Pacman isn't allowed to eat anything. Eating during that time decreases score instead of increasing it.
There's the suicide attack option: Pacman can explode, which costs one life, but kills all the ghosts close to it (adding to the score accordingly).
If you blow up all 4 ghosts (genies), you immediately get to the highest level and hang out with 72 Ms Pacmans...
Re: (Score:2)
i read the title as A.I. Pacman, as in artificial intelligence and then when i clicked on the article i was like YEAAAAAAAAH!!!! IM RIGHT! WHOOOOOOO!!! IN YOUR FACE!
nah really i didnt even read it
Comment removed (Score:4, Insightful)
Re: (Score:2)
It's really really sad..... but I have to say you are kinda of wrong about the realism part here.
I have a friend who served in Iraq and he told me that many of the young men would run down the middle of street just spraying AK47 fire everywhere while they took cover behind various objects. He would pop up real quick and put one or two in the guys chest. Rinse, wash, repeat.
The worst part, and one I could tell hurt him quite a bit, is when one of the guys he put two in the chest was a 12 year old.
So perhap
Re: (Score:2)
Re: (Score:1)
i have no idea what 'arabic pacman' would look like, but i was so eager to click and find out. imagine my disappointment.
You're disappointed? I couldn't figure out why the hell anyone would care if Allen Iverson [wikipedia.org] could beat Pac-Man in the first place. Note to readers : This has nothing to do with the basketball player "AI" Allen Iverson. *sigh*
Re: (Score:1)
We would be interested to see if he would 'practice' first.
cross-dressing pac man (Score:1)
if course the screen shot is from Ms Pac-Man
Already Over (Score:3, Informative)
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.
Re:Already Over (Score:4, Insightful)
That's slashdot for you. "Olds for geeks, stuff that probably doesn't matter."
Re: (Score:2)
Somehow the fact that your quote includes a grammatical error makes it even more appropriate.
Re: (Score:2)
Looking at his post, I can't see any errors. Unless you mean whether punctuation should come before or after the closing quote, which depends on where in the world you are.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2, Insightful)
why the fuck? pacman can be played "perfectly" because the ghosts always move the same depending on what the player is doing. that's how some people can play it till they drop, it needs no thinking. and if you're writing control code for the ghosts then it's bye bye for pacman no matter how pacman is controlled.
you know what's a real challange? writing a cs bot that passes as a human. no need to wait for pesky competition either.
Re: (Score:2)
The article gets it wrong. The competition is actually run with Ms Pac-Man, which is more random than the original Pac-Man.
Re: (Score:2)
Wow, how are so many people in this thread wrong in so many different ways?
First of all, they *did* run this competition before, but they are re-running it next month. That's why if you play follow the links you get to the actual contest page [pacman-vs-ghosts.net] and you see this:
We have decided to run the competition for CIG 2011 (in addition to CEC 2012 next year)! We will open the submission server on July 1, 2011; you can then submit and evaluate your controllers. The deadline for final submissions will be August 17, 2011
Second of all, the contest is not just about writing Pac-Man AI, because you can enter ghost team AI as well. It turns out they are using Ms Pac-Man, but the original game's randomness doesn't matter. They've also tweaked certain aspects of the orig
Pac-Man is too hard (Score:3, Interesting)
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: (Score:1)
Re: (Score:2, Insightful)
And yet here's an AI that can apparently beat it..... what does that say about my friends and coworkers?
That apparently, there are some things computers are better at than people?
QUICK! What's the 761st decimal place [wikimedia.org] of pi?
Does it make some statement about you that a computer can calculate the above several of orders of magnitude faster than you?
yes. we are obsolete (Score:2)
and will soon be replaced by arduinos
Re:Pac-Man is too hard (Score:5, Informative)
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...
Re:Pac-Man is too hard (Score:5, Interesting)
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: (Score:2)
In addition, the two short corridors right under where the bonuses appear are special, in that ghosts cannot enter them from below. It's one of the few ways you can escape a trailing Binky, or catch a rest to let a ghost pass below you.
Anyhow, I can't see how someone's AI managed a 69000 score against modified AI ghosts. I would think that with four ghosts that can cooperate, you should be able to guarantee pac-man's capture within the first level?
Re: (Score:2)
I thought this too. I supposed that each ghost must be limited to line-of-sight information, and perhaps knowledge of the maze as well. However, I see no such restrictions:
Ghost-Team-Specific Rules
There are no restrictions regarding the actions of Ms Pac-Man: movement in any direction not blocked by a wall is allowed at all times. For the ghost team, on the other hand, three restrictions apply:
The first follows from the original game specifications and prevents a ghost from turning back on itself. In other
Re: (Score:2)
There are no restrictions regarding the actions of Ms Pac-Man: movement in any direction not blocked by a wall is allowed at all times.
Tsk, that's exploitable. It opens up for a Ms. Pacman that runs diagonally through intersections, enters the ghost den, and levitates to let the ghosts pass under her. No wonder someone scored 69,000 points!
each level finishes after 3000 time steps; all remaining pills are awarded to Ms Pac-Man. It is thus in the interest of the ghosts to catch Ms Pac-Man as quickly as possible.
No, that does not follow. Sheesh. These guys must have flunked logic 101. What follows is that it's in the interest of the ghosts to catch her before 3000 time steps, which is not the same as "as quickly as possible". If you can devise a plan that always catches her within 2800 time steps, that is
Re: (Score:2)
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.
You are mistaken, because first, there is a maximum score and the first person to reach it used patterns. Secondly, those who have the perfect score can go those hours withou
Re: (Score:2)
Some confusion in this topic is due to the title of the article. The actual competition uses Ms Pac-Man, which does not have patterns.
Re: (Score:1)
you got three out of four ghost behaviors wrong. actually i'm not sure that the yellow ghost description is wrong per see because there is no yellow ghost. :)
Re:Pac-Man is too hard (Score:4, Insightful)
Re: (Score:2)
What you are talking about is machine learning. It's not the same as AI.
Re: (Score:2)
Re:Pac-Man is too hard (Score:4, Insightful)
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.
Re: (Score:2)
As my AI prof often said, "AI is whatever we haven't taught a computer to do yet."
Re: (Score:3)
There is more to beating Pac-Man than simply knowing the algorithm for evading the ghosts. One must also be able to implement that algorithm, which requires a certain amount of physical skill (i.e. pushing the right buttons in the correct sequence at the appropriate times). Moreover, one actually has to play the game enough learn what the algorithm is (that is, there is no reason to expect a novice player to immediately see the movement patterns of the ghosts). Pac-Man might be easy to someone who has sp
Re:Pac-Man is too hard (Score:5, Insightful)
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: (Score:3)
AI chess programs have been beating chess grandmasters for years.
Machines are better than people for lots of things. That's why we build machines.
Re:Pac-Man is too hard (Score:4, Insightful)
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? :)
Re: (Score:2)
There is a monkey/chimp that play(s/ed) Ms. Pac-Man. See http://www.google.com/search?hl=en&tbm=vid&q=monkey+pac-man&aq=f&aqi=&aql=&oq= [google.com] for the video clips. :)
4 1 (Score:1)
Re: (Score:2)
Re: (Score:2, Interesting)
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.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Hmm. That reminds me of Snack-Man (Score:5, Interesting)
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 [memebot.com], 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: (Score:2)
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.
P-Robots (Score:3)
Re:P-Robots (Score:4, Interesting)
But no, programming [wikipedia.org] games [wikipedia.org] 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.
Re: (Score:1)
I got introduced to programming via Advanced T-Robots [necrobones.com], actually. Similar, but assembly-like code.
But no, programming [wikipedia.org] games [wikipedia.org] 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.
It's because people who might be interested in that kind of thing are busy writing farming bots for MMO's like WoW and aimbots for the FPS genre.
Re: (Score:1)
Re: (Score:1)
Not a terribly complex game, surprisingly (Score:5, Informative)
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.
Re: (Score:2)
Also, isn't the ghost's side trivial? Pacman can't cover the entire board while invisible, so why not have two ghosts guard the remaining pellets? Once the 4 power-ups are gone, Pacman can't force his way past. It's a draw at best, and Pacman is stuck on lvl 1 with an upper limit to his score.
Re: (Score:3)
http://www.pacman-vs-ghosts.net/rules [pacman-vs-ghosts.net]
Looks like they introduced a few rules to make the ghost team's life harder.
Re: (Score:3)
Re: (Score:1)
But how would you set it up that the ghost guard the pellets? They have to keep moving, so at some point the pellets will be exposed.
Re: (Score:2)
"Assuming they're pitting their Pac-Man bots against the logic of the original arcade game,"
Ghost have upgraded AI, not the original. Also, you can enter the competition writing ghost AI as well.
uh oh a.i. (Score:1)
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?"
FTFY (Score:1)
AI ghosts try and eat AI Ms. Pac-Man
Giggity.
Rog-O-Matic (Score:1)
This brought on a strong blast of deja vu; there was a program called Rog-O-Matic [wikipedia.org] 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.
Would love to see this for FreeCiv (Score:3)
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.
Cooperative ghosts should always wins (Score:2)
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 repe
Pac-man? (Score:2)
oh wait...
http://eis.ucsc.edu/StarCraftAICompetition [ucsc.edu]
Re: (Score:3)
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.
Re: (Score:1)
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 sam
Re: (Score:1)
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.