Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

 



Forgot your password?
typodupeerror
AI Java Games News

AI Takes On Pac-Man 113

Posted by CmdrTaco
from the wakka-wakka-wakka-wakka dept.
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."
This discussion has been archived. No new comments can be posted.

AI Takes On Pac-Man

Comments Filter:
  • by decora (1710862) on Monday June 13, 2011 @07:49AM (#36424134) Journal

    i have no idea what 'arabic pacman' would look like, but i was so eager to click and find out. imagine my disappointment.

    • by lennier1 (264730) on Monday June 13, 2011 @07:59AM (#36424202)

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

      • by Anonymous Coward

        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?

      • by EdIII (1114411)

        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.

        • by lennier1 (264730)

          At best you'd see a darker spot near the eyes.
          Sure you're not thinking of a niquab?

          • by EdIII (1114411)

            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

    • by yincrash (854885)
      I thought it meant Weird Al takes on Pac-Man.
    • Re: (Score:3, Funny)

      by haystor (102186)

      One of the pacman clones was OPECman.

    • by mikejuk (1801200)
      Look I'm the one who submitted it and I read it as AL - as in the Paul Simon song. So to me it reads - someone called AL is taking on Pac-man..... who is a she anyway,,,, there is no hope....
    • 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).

      • by Anonymous Coward

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

    • by xmousex (661995)

      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

      • Hell I'd just be happy for game AI that doesn't blow rancid chunks before falling over and dying. Any game designers here? For the love of kittens and everything decent in the world STOP WITH THE BAD AI as it just ruins a game, it really really does.

        There was a time, a short time mind you, but still a time, along about Far Cry I and Fear I where I was thinking "hey, finally! Thank fricking God! These guys are trying to flank me! They aren't lining up to be shot! Woo hoo, I'm having fun!" but then developers went back to caring only about bling and burst my little happiness bubble. Play RF:Guerrilla? You will spend most of your time shooting the good guys as they all can't wait to run right out in front of you while you are trying to fire. For the hell of it I put in the explosive pistol mod so I can just stand there and watch them ragdoll each other since none of them have the sense not to fire if their friends step in front of them.

        So maybe stuff like TFA will help them learn how not to design dumb as stumps AI, hell if I know. Everyone talks about "realism" but nothing completely blows realism right out the airlock like watching a bad guy bang himself against a wall over and over again, or having them take "cover" behind the EXACT SAME CHEST HIGH WALL where I've piled three dozen of the friends in a kill box because their fricking heads stick out, or the worst having AI "help" that don't know which end of the gun to point at the enemy and who promptly run out into the open with such inane stupidity it seems like a race to see whether you or the bad guy will cap them first.

        So please game devs, for the love of titties and beer and all that is good and right in this world, just stop okay? Nobody is asking for Einstein here, just not so damned retarded that they make Forest Gump look like Carl Sagan.

        • by EdIII (1114411)

          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

        • by hellop2 (1271166)
          ARMA/ARMA2 has some pretty good AI. Great game too.
    • 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*

  • by Anonymous Coward

    if course the screen shot is from Ms Pac-Man

  • Already Over (Score:3, Informative)

    by ctrimm (1955430) on Monday June 13, 2011 @07:57AM (#36424180)

    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)

      by ByOhTek (1181381) on Monday June 13, 2011 @08:06AM (#36424246) Journal

      That's slashdot for you. "Olds for geeks, stuff that probably doesn't matter."

      • Somehow the fact that your quote includes a grammatical error makes it even more appropriate.

        • by arth1 (260657)

          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.

    • by mikejuk (1801200)
      Agreed... the publicity for it was low key until the results were out. Maybe next year. The good news is that the interface between the game engine and the controller is very easy to work with. Start with the random move example and work up. mikej
    • Re: (Score:2, Insightful)

      by Anonymous Coward

      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.

      • by opus (543) *

        The article gets it wrong. The competition is actually run with Ms Pac-Man, which is more random than the original Pac-Man.

        • 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)

    by cpu6502 (1960974) on Monday June 13, 2011 @08:15AM (#36424308)

    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.

    • by h4x0t (1245872)
      There's an AI that can rule Chess too, also Jeopardy. What does that say about your friends and coworkers? Nothing
    • Re: (Score:2, Insightful)

      by Anonymous Coward

      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?

    • by i.r.id10t (595143) on Monday June 13, 2011 @08:52AM (#36424614)

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

      • by Jaqenn (996058) on Monday June 13, 2011 @10:32AM (#36425422)
        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 [gamasutra.com]

        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.
        • by arth1 (260657)

          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?

          • by opus (543) *

            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

            • by arth1 (260657)

              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

        • by opus (543) *

          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

          • by opus (543) *

            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.

        • by 0137 (45586)

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

      • by AchilleTalon (540925) on Monday June 13, 2011 @10:37AM (#36425458) Homepage
        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.
    • by 19061969 (939279) on Monday June 13, 2011 @09:47AM (#36425030)

      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.

    • 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

    • by Raenex (947668) on Monday June 13, 2011 @09:54AM (#36425106)

      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?

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

    • by elsurexiste (1758620) on Monday June 13, 2011 @10:34AM (#36425438) Journal

      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? :)

    • by antdude (79039)

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

  • by N1tr0u5 (819066)
    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.
    • by Rogerborg (306625)
      Well, it's Monday morning, so I guess that's the traditional time for verbal quarterbacking.
    • Re: (Score:2, Interesting)

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

    • by bbeagle (2262032)
      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.
      • by ifrag (984323)
        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.
    • by JTsyo (1338447)
      Does the AI ghosts "talk" to each other or just run their algorithm? Do they all even run the same algorithm?
  • 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.

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

  • by Machtyn (759119) on Monday June 13, 2011 @09:35AM (#36424930) Homepage Journal
    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 [corewar.co.uk].
    • Re:P-Robots (Score:4, Interesting)

      by HeckRuler (1369601) on Monday June 13, 2011 @10:05AM (#36425208)
      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.
      • by Anonymous Coward

        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.

    • by ctrimm (1955430)
      I did something similar in Java back in a HS Tech-prep class. It was called J-Robots, naturally. I wouldn't consider this competition the same concept, though. Sure, they both battle AI bots against each other, but the constraints are different. For instance, the J/P-Robots (in my experience) had an open "field" for the robots to operate in, while Pacman has a map. Robots was a free for all, while Pacman was one vs many.
    • Anyone remember a robot war variation on the old Research Machines (RM) 480Z systems ? I would love to play with it again for nostalga's sake.
  • by davidbrit2 (775091) on Monday June 13, 2011 @09:42AM (#36424988) Homepage

    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.

    • Yes, against the ghosts' logic in the original game. But what if, and this is just a crazy idea, we pit the pacman-AI against the ghost-AI? It'd be some sort of competitive contest.

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

  • by Anonymous Coward

    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.

  • by Anonymous Coward

    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.

  • by crow (16139) on Monday June 13, 2011 @12:21PM (#36426486) Homepage Journal

    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.

  • 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

  • Wake me up when they can play Starcraft
    oh wait...
    http://eis.ucsc.edu/StarCraftAICompetition [ucsc.edu]

"No job too big; no fee too big!" -- Dr. Peter Venkman, "Ghost-busters"

Working...