Jump to content

Photo

Pac-Man ghost AI question


89 replies to this topic

#26 PacManPlus OFFLINE  

PacManPlus

    River Patroller

  • 4,107 posts
  • Atari 7800 Dev
  • Location:SouthWest Florida

Posted Wed Apr 18, 2007 5:58 AM

Hey Dav / JamieVegas:

Without having done any disasemblies myself (just noting on behavior from playing the game so much), in Ms. Pac-Man just Pinky and Blinky are randomized in the first 7 seconds of each board - Inky and Clyde still (attempt to) go to their corners.
Also, there is no 'disperse mode' in Ms. Pac-Man any more; when the monsters reverse direction, they still chase you. :) As far as any minute changes to their AI, I don't sense any (Dav of course would know better from looking at the code all this time) - I still use the same strategies when playing either game and the monsters for the most part react the same way.

That's a cool discovery on Pac Plus and the Harder version of Pac-Man... I have to play the Harder version to see if I can 'feel' the difference.

Where exactly is the 'randomness' in the monsters AI in Plus? How is it implemented?

P.S. - Dav, congrats on your new home. Hope you're settled in well. :)

Bob

*edited for clarity

Edited by PacManPlus, Wed Apr 18, 2007 6:00 AM.


#27 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Mon May 7, 2007 8:20 PM

That is very interesting! So, there is are no more "waves" of attack in Ms. Pacman? The ghosts are just constantly attacking?

I've never really played Ms. Pac-man. I don't have a taste for it. The fact that the chase logic involves randomness in any way completely destroys the game for me. The magic of the original game was that the AI was completely deterministic. The action of the AI was completely based on player action. That's the only way to introduce a learning curve into a game. Once you introduce randonimity, you destroy the involvement of skill, memorization, and instinct. They're all replaced with luck. I assumed Ms. Pac-man was mostly random, and that's why I never played it. If it's only 7 seconds -- eh, that's not so bad.

Dav, do you have anything definitive to say about the Ms. Pac-man AI? Moreover, do you know what was changed between releases of the original Pacman when it was rumored that "Midway changed the ghost "patterns" to stop players from using their own established patterns?" Or, is that the "Pacman Harder" variant that you are talking about?

#28 Room 34 OFFLINE  

Room 34

    Quadrunner

  • 8,280 posts
  • room34.com
  • Location:Tha 612

Posted Fri May 11, 2007 7:37 AM

I was at Caribou Coffee this morning, and the trivia question was to name all of the ghosts in the original Pac-Man. Of course I said "Blinky, Pinky, Inky and Clyde," and was somewhat embarrassed that I could only remember their "nicknames" but it was enough to get my 10 cents off.

I remembered back in the '90s having had a Mac port of the original Japanese Pac-Man that a friend and I used to play, and I remembered 3 of the Japanese names: Guzuta, Otoboke, and Kimagure. I wanted to remember the rest, so I Googled it and this thread came up at the top of the list!

Edited by Room 34, Fri May 11, 2007 7:38 AM.


#29 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Mon May 14, 2007 12:53 PM

That is very interesting! So, there is are no more "waves" of attack in Ms. Pacman? The ghosts are just constantly attacking?

I've never really played Ms. Pac-man. I don't have a taste for it. The fact that the chase logic involves randomness in any way completely destroys the game for me. The magic of the original game was that the AI was completely deterministic. The action of the AI was completely based on player action. That's the only way to introduce a learning curve into a game. Once you introduce randonimity, you destroy the involvement of skill, memorization, and instinct. They're all replaced with luck. I assumed Ms. Pac-man was mostly random, and that's why I never played it. If it's only 7 seconds -- eh, that's not so bad.

Dav, do you have anything definitive to say about the Ms. Pac-man AI? Moreover, do you know what was changed between releases of the original Pacman when it was rumored that "Midway changed the ghost "patterns" to stop players from using their own established patterns?" Or, is that the "Pacman Harder" variant that you are talking about?


Most people like MsPac because the patterns don't work. I think from what I've been told by the really good ms pac players what they do is use small patterns that they can use when they see a certain situation. So they will tell you they don't have patterns but in fact they have a whole bunch of small patterns and they have to recognize when to apply that pattern. Most of the same behavior you see in Pac occurs in Ms Pac, it's just that long patterns are not possible. The disperse mode was when they went back to their home quadrant. There's a patch there, I was thinking it randomized it, but it might have removed it.

I can't really say anything definitive w/o looking at code and I just don't have the time right now. Maybe next week.

The harder version is the one that was released later to stop people from using the patterns. All it really did was force players to come up with new patters which bought a little time for the operators I guess.

A cool thing about the names is the pucman boards came with a solder pad to change them. There were 2 sets of names. And I believe there were even more names in the roms that couldn't be accessed. Micky,Macky Mucky are the names that come to mind but I'd have to check.

Midway didn't have the name option. :(

#30 Shannon OFFLINE  

Shannon

    Born To Be Insane

  • 7,497 posts
  • Pac-man Fever
  • Location:Arcade

Posted Mon May 14, 2007 6:16 PM

Someone needs to write a book... "Pac-man unplugged" or something. :lol:

Anyways I was just thinking about this recently while setting up my mame cab to play pac-man. I was playing the original "easier" rom set and found it easier (duh) and more familar to me, and no I did not use any patterns. When I grew up playing pac-man I always played the older rom set so I was pretty familar with the monster patterns.

It's kinda nice to see some of the more minor differences mentioned (like Inky's behaviour being affected by Blinky). As well as how Ms. Pac (my fav) is different.

I didn't see anyone cover why Blinky sometimes will chase you even when in scatter mode. (at least in more specific detail based on code analysis). Other mysteries. Why can you sometimes pass thru the ghosts when their eyes are changing directly? Deliberate or a bug?

What!?!? No love for Jr. Pac-man?

Edited by Shannon, Mon May 14, 2007 6:24 PM.


#31 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Tue May 15, 2007 7:46 AM

Why can you sometimes pass thru the ghosts when their eyes are changing directly? Deliberate or a bug?

What!?!? No love for Jr. Pac-man?



The collision detection works by keeping track of everyone's position in a grid. The grid squares are 8x8 pixels. Think of them like the squares on a side walk. If you walk directly at someone and they step off theirs onto yours at the same time as you step off yours and on to theirs, you are never on the same square at the same time. In the real world this would be difficult to do accidentally but with computers things don't happen in an infinite number of infinetly small time slices, there's only 30 or 60 time slices a second so it's easier than you would think.

I'm not a fan of the JR. although I did at one time make a hi score kit that kept track of the top ten names so I'm not completely unfamiliar with it. It's kind of like ms pac in that it's the pacman code with a bunch of patches on top. The board was modified to remove the color ram and reuse it for a larger screen.

#32 PacManPlus OFFLINE  

PacManPlus

    River Patroller

  • 4,107 posts
  • Atari 7800 Dev
  • Location:SouthWest Florida

Posted Tue May 15, 2007 10:09 AM

I didn't see anyone cover why Blinky sometimes will chase you even when in scatter mode. (at least in more specific detail based on code analysis).


Regarding Blinky chasing you while in scatter mode: it depends on the number of dots left on the board. On the Cherry Level, I think it's something like 16 (I forget the exact number) dots that is the trigger; once there are that many dots left on the board Blinky not only chases you in scatter mode (except the initial 7 seconds disperse mode - like if you die and you start your next life), but he also becomes faster than you (when *not* eating dots). As the game progresses, level by level the number of dots left on the screen needed to trigger this event increases all the way to the 9th key. :)

Bob

#33 Shannon OFFLINE  

Shannon

    Born To Be Insane

  • 7,497 posts
  • Pac-man Fever
  • Location:Arcade

Posted Tue May 15, 2007 8:05 PM

ok thanks guys.. That's cool to know even if I never recall it in the heat of the moment while playing the game. :lol:

#34 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Tue May 15, 2007 10:23 PM

I didn't see anyone cover why Blinky sometimes will chase you even when in scatter mode. (at least in more specific detail based on code analysis).


Regarding Blinky chasing you while in scatter mode: it depends on the number of dots left on the board. On the Cherry Level, I think it's something like 16 (I forget the exact number) dots that is the trigger; once there are that many dots left on the board Blinky not only chases you in scatter mode (except the initial 7 seconds disperse mode - like if you die and you start your next life), but he also becomes faster than you (when *not* eating dots). As the game progresses, level by level the number of dots left on the screen needed to trigger this event increases all the way to the 9th key. :)

Bob



Edited by Dav, Tue May 15, 2007 10:25 PM.


#35 Otoboke OFFLINE  

Otoboke

    Combat Commando

  • 4 posts

Posted Sun May 20, 2007 2:28 AM

Sorry for the possible breach of newbie ettiquette by jumping in at this point, but the topic is too dang fascinating to resist.

Here is what I've been able to come up with about the ghost AI in the "attack" mode, to supplement what's in the "ghost psychology" link and the excellent observations you all have made.

* Red ghost (Oikake): Input is Pac-Man's location. He doesn't consider which direction Pac-Man is going. He attempts to reduce the distance between himself and Pac-Man. He will turn in the direction that will immediately reduce whichever is GREATER of the horizontal distance or vertical distance between himself and Pac-Man. This usually has him tenaciously following Pac-Man, but will occasionally lead to a "stupid" choice (see illustration below).

* Pink ghost (Machibuse): Input is four tiles in front of Pac-Man. Therefore direction Pac-Man is facing as well as actual location of Pac-Man determine Pinky's "target." Pinky attempts to home in on this target using the same logic as the Red ghost uses to home in on Pac-Man. This does indeed effectively "set up an ambush" if Pinky manages to get in front of you. At close range, the direction you face can mean life or death. If you're facing away from Pinky, he will chase you (his "target" is now in front of both you and him). If you face him or turn off to a side, he may turn away from you if that provides a shorter route to the target than running through you. Note that if the space four tiles in front of you is on the other side of a wall, he will go over there in preference to the side you are on.

* Blue ghost (Kimagure): Inputs, as mentioned, are the square two tiles in front of Pac-Man, and the location of the Red ghost. (Edited out incorrect information here and replaced with correct information that follows-->) To envision Inky's target, draw a line from the Red ghost to the spot 2 tiles in front of Pac-Man. Now extend that line twice as far in the same direction and draw an "x" where it winds up. Inky wants to reach that "x." The fact that Inky's AI has two inputs instead of one makes his behavior more complex. On a fast-moving playing field with Pac-Man and the red ghost constantly changing position, that "x" can be jumping all over the place and sometimes Inky's behavior seems completely random - but it's not. No wonder his alternate name on the Puck-Man rom is "Stylist"! His regular name, Kimagure ("Whimsy") is also appropriate. It makes sense that the closer the red ghost is to Pac-Man (technically, the closer he is to the spot two spaces in front of Pac-Man), the more predictable Inky's behavior appears. Thanks to JamieVegas and Dav for getting this right the first time. Sorry I temporarily had completely wrong information on here!

* Orange ghost (Otoboke): Has two modes, "near" (within 8 tiles of Pac-Man) and "far" (farther away than 8 tiles). In "far" mode, he heads toward Pac-Man using Blinky's logic. This gets him in the same general area of the maze, but then in "near" mode, he has a bizarre change of heart and decides to head for his corner of the maze (lower left island). Unless you happen to be in the lower left region, his about-face will soon take him into "far" mode again, and he will circle back toward your area. If you are in the lower left, he will circle his favorite island indefinitely. He will usually only "chase" you if you happen to be in the path between him and the lower left of the screen. Orange's "far" mode rarely leaves him doubled up on top of Red due to the fact that their home quadrants are on opposite sides of the map and "scatter" mode repeatedly separates them. Plus, red is usually close enough to you that orange will go into "near" mode if he gets close to red.

Here's an illustration where all 4 of the ghosts' strategies work against them -

Posted Image

Pac has been on the board long enough that there are no more "scatter" modes. The ghosts are in constant "attack." Since it's a cherry board, Red is not in accelerated "Cruise Elroy" mode, so all 4 ghosts are travelling at the same speed. This keeps Red just in front of Blue. The ghosts will go around these islands forever without finding Pac. Here's why -

Red: When he reaches the SW corner of his island and could potentially approach Pac-Man by going straight rather than turning N like an idiot, his algorithm considers the following... his vertical distance from Pac is greater than his horizontal distance... turning N reduces that vertical distance while continuing W does not... therefore, go north! And around he goes again.

Pink: As long as Pac stays still and doesn't turn W or S, Pink's target is a spot along the north side of the island. He'll go around and around forever, the shortest route to the target always being to keep going around since he can't reverse his direction.

Blue: The spot two tiles in front of Pac-Man is approximately at the NW corner of the island Blue is circling. When Blue reaches the SW corner each time around, Red will always be just N of him. The line from Red to the spot two tiles in front of Pac-Man will point straight north. In fact, the "x" Blue is really aiming for would be drawn beyond the north end of the playing field (about where the "8" in the high score is). When this happens, treat the target as being at the extreme edge of the playing field. At any rate, Blue will head north. For hypothetical purposes, imagine what would happen if Red was situated where Pinky currently is when Blue reaches the SW corner. Now the line puts the "x" at a spot west of Pac-Man, Blue goest west, and Pac-Man very soon finds himself a very tasty morsel on Inky's dinner plate!

Orange: As often happens, he's the weirdo of the bunch. At the NE corner of his island, he's in "near" mode. Yipes! Panic! Head for the corner of safety! (Go S.) But then when he reaches the next turn at the SE corner, he's removed enough to be in "far" mode. Loop back around toward Pac-Man (orbiting the small island is more direct than going around the sideways "T" island to orange's east). At the NW corner of the island, he's still "far," so he attempts to reduce the greater horizontal separation between himself and Pac in preference to the smaller vertical separation (i.e. he goes E instead of N here). But then he's back at the NE corner in "near" mode again. Yipes! Panic! Etc.

Note that this "hold" will not work if there are still scatter modes left on the level, or if blue is not closely following red. If you set it up wrong, blue will invariably be the one that "breaks out" of his orbit and comes over to kill you. Try it!

I believe the game will not allow the ghosts to go up the tunnels immediately above the monster pen and above where Pac-Man starts out even if the AI would otherwise direct the ghosts there. It's one of the easiest ways to shake Blinky if he's too close on your tail.

I apologize for the length of this post, but I couldn't think of how to put it more concisely. In my opinion, the ghost AI was a key to this game's incredible success. Small sections of code (often 50 bytes or less) lead to complex phenomena that take paragraphs to describe and have players attributing it to the "personalities" of the monsters. It's what vintage gaming is all about.

Those of you who have really analyzed the assembly code, you rock! If you've spotted errors in my analysis (I'm going more off playing experience than a solid understanding of Z-80 code), by all means put me in my place.

Hope this helps-

"Guzuta"

Edited by Otoboke, Mon May 21, 2007 7:38 PM.


#36 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Sun May 20, 2007 9:13 AM

Speaking of holds there are some places on the board where normal AI doesn't apply. I call them slides because when I was controlling the red ghost in one of my game hacks when you hit one you would slide to the other side of it. Basically once a monster gets in one of these area's they can't change direction(unless they're blue) I modified the color prom and took this pic. It shows some of the screen looks like it's the same color but it's actually not. These colors control ghost movement. The red overrides the AI, the pink causes him to move slower.



pacm0016.png

#37 Otoboke OFFLINE  

Otoboke

    Combat Commando

  • 4 posts

Posted Sun May 20, 2007 6:10 PM

Speaking of holds there are some places on the board where normal AI doesn't apply. I call them slides because when I was controlling the red ghost in one of my game hacks when you hit one you would slide to the other side of it. Basically once a monster gets in one of these area's they can't change direction(unless they're blue) I modified the color prom and took this pic. It shows some of the screen looks like it's the same color but it's actually not. These colors control ghost movement. The red overrides the AI, the pink causes him to move slower.


Cool! That is an excellent illustration of what's really going on with that phenomenon. I'd be curious to play the game WITHOUT the AI override in those spots and see how much harder it makes it. I use those escape routes all the time in game play.

It's worth mentioning that the ghost AI does NOT take the "slides" into account when a ghost is plotting a route to reach Pac-Man. Example:

Posted Image

Blinky is at a decision point. His algorithm tells him to go north here (reducing the vertical separation between himself and Pac-Man). It would make more sense, and suit his "Shadow" character better, for him to go east, but he won't. Little does he know, the "slide" over the monster pen will force him to go all the way to the opposite side of the board. Sucker!

Incidentally, for you devoted students of ghost psychoanalysis, if Pac-Man turns right here, Pinky will enter the tunnel. This absurd detour will keep him out of your hair for a while, and you can mop up that corner with only the much less menacing Inky and Clyde to worry about.

Quick note to add: if a ghost's AI does not yield a decisive direction to head at a junction (e.g. Blinky reaches a spot where no direction he turns will reduce the parameter his algorithm is trying to reduce), the ghost's order of movement preference is up, left, down, right. I.e. he will go up if possible, left if he can't go up, down if he can't go either up or left, and right only if there is no other choice. An example of where this would happen in the illustration above is when Blinky finally gets over to the junction on the left side of the monster pen, while Pac-Man stays in the NE corner area of the board. Blinky is unable to reduce the horizontal distance between himself and Pac-Man (and remember that he is not "looking ahead" to realize that if he just kept going straight he could soon turn east under the monster pen... the ghosts do not assess their own future locations and turning possibilities when making decisions... they only look at the board at that exact instant). Blinky can't do a 180 and go up, so he does the next choice and goes left.

It is possible to have fun with Clyde's "near" AI. If you stay near him, you can chase him from anywhere on the board to the lower left corner. While taunting Clyde like this gives me a guilty feeling - it's sort of akin to bullying Ralph Wiggum - it can be useful sometimes.

Ah, Pac-Men can be so cruel at times...

"Guzuta"

#38 Shannon OFFLINE  

Shannon

    Born To Be Insane

  • 7,497 posts
  • Pac-man Fever
  • Location:Arcade

Posted Mon May 21, 2007 3:19 AM

I almost get the impression these quirks in the AI are modifications by to the original AI to either fix something, or make the monster AI a little less difficult.

#39 Otoboke OFFLINE  

Otoboke

    Combat Commando

  • 4 posts

Posted Mon May 21, 2007 1:45 PM

I almost get the impression these quirks in the AI are modifications by to the original AI to either fix something, or make the monster AI a little less difficult.


I believe you are right. Game designer Iwatani has said the hardest part for his team to get right was the ghost AI. Presumably they were endlessly tweaking the code for the ghosts and playtesting to see how it felt. Quirks like the "slides" were probably put in late in the process to give Pac-Man more of a fighting chance without going to the trouble of rewriting the ghost AI from scratch.

The harder mod Midway put out, with the AI modifications on Pinky and Clyde discussed earlier in this thread, does indeed make the game more challenging. I find myself getting devoured by Clyde (Oh! the humiliation!) much more often in that version. The new AI is inferior in terms of making the ghosts interesting, however. Basically, Pinky and Clyde behave somewhat more like the red ghost. Boring!

I am impressed with the elegant solution to the "patterns" problem that Ms. Pac-Man features. Randomizing the first two ghosts' movements for the first 7 seconds is enough to disrupt any large scale pattern the player would come up with, but then dropping those ghosts back into their normal AI afterward restores the element of skill to the game. Putting random elements into the ghost's permanent AI would have been a cop-out. I believe this is the mistake that many poorly designed Pac-Man clones make. The playability suffers.

"Guzuta"

#40 supercat OFFLINE  

supercat

    Quadrunner

  • 6,399 posts

Posted Mon May 21, 2007 7:46 PM

I am impressed with the elegant solution to the "patterns" problem that Ms. Pac-Man features. Randomizing the first two ghosts' movements for the first 7 seconds is enough to disrupt any large scale pattern the player would come up with, but then dropping those ghosts back into their normal AI afterward restores the element of skill to the game. Putting random elements into the ghost's permanent AI would have been a cop-out. I believe this is the mistake that many poorly designed Pac-Man clones make. The playability suffers.


What would be wrong with patterns, if every level required a different one (rather than having over 200 levels use the same one)? I wonder how many people would be able to reach level 256 of Pac-Man if the ghosts started out each "key" stage by travelling to spots on the board that were specific to each level? Define four such spots for each ghost and voila--256 different pattern for the 'key' stages.

#41 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Mon May 21, 2007 8:52 PM

Otoboke,

After my code analasys, it looks like the Ms. Pac-man AI solution is really just the remains of a failed, better solution.

Having only two ghosts move randomly is a bit silly, since all of the ghosts always moved randomly during blue mode in the last game.

They actually wanted to make each ghost go to a random home corner! They failed to be able to get each ghost to "remember" its destination between frames. Instead, each ghost picks a new homecorner every single frame. Even the blue and orange! The end result is that the ghosts move around in "blue mode" instead of spreading out to random corners.

The blue and orange ghosts were patched incorrectly, though. So, after they call the randomized home corner selector -- the old pacman code overwrites the decision with the home corners from the original maze that isn't even used in the game.

(Note, home corners are defined as actual map cells to seek out, not directional areas.)

There are tables for each maze in the game of new home corners for the ghosts to pick from. Unfortuanetly, they were never maintained in the code, and don't match up with the mazes, since the programmers found out they couldn't finish what they started.

The random home corner solution would have been very elegant -- or, if necessary, having all of the ghosts move randomly during the first 5 seconds would be decent (although, again it looks really unintelligent and weird -- and is already implemented by "blue ghost" behavior.) -- but the hybrid solution, with orange and blue seeking their old home corners and the other ghosts just bobbibng around mindlessly is just a mistake.

Edited by JamieVegas, Mon May 21, 2007 9:03 PM.


#42 DEBRO OFFLINE  

DEBRO

    Stargunner

  • 1,871 posts
  • Location:Atlanta, GA

Posted Tue May 22, 2007 3:02 AM

After reading Otoboke's post on monster behavior I guess I came pretty close with my Pacman4K :)

#43 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Tue May 22, 2007 7:08 AM

Otoboke,

After my code analasys, it looks like the Ms. Pac-man AI solution is really just the remains of a failed, better solution.

Having only two ghosts move randomly is a bit silly, since all of the ghosts always moved randomly during blue mode in the last game.

They actually wanted to make each ghost go to a random home corner! They failed to be able to get each ghost to "remember" its destination between frames. Instead, each ghost picks a new homecorner every single frame. Even the blue and orange! The end result is that the ghosts move around in "blue mode" instead of spreading out to random corners.

The blue and orange ghosts were patched incorrectly, though. So, after they call the randomized home corner selector -- the old pacman code overwrites the decision with the home corners from the original maze that isn't even used in the game.

(Note, home corners are defined as actual map cells to seek out, not directional areas.)

There are tables for each maze in the game of new home corners for the ghosts to pick from. Unfortuanetly, they were never maintained in the code, and don't match up with the mazes, since the programmers found out they couldn't finish what they started.

The random home corner solution would have been very elegant -- or, if necessary, having all of the ghosts move randomly during the first 5 seconds would be decent (although, again it looks really unintelligent and weird -- and is already implemented by "blue ghost" behavior.) -- but the hybrid solution, with orange and blue seeking their old home corners and the other ghosts just bobbibng around mindlessly is just a mistake.


I remembered the part about random home quadrants but I guess I never noticed it didn't work for 2 of them.

The blue ghost behavior isn't random, so it doesn't neccessarily mess up your pattern.

I agree the Ms Pac programmers had some good ideas but they weren't the programmers the original pacman programmers were. She's a lot more buggy.

#44 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Tue May 22, 2007 12:38 PM

Otoboke,

After my code analasys, it looks like the Ms. Pac-man AI solution is really just the remains of a failed, better solution.

Having only two ghosts move randomly is a bit silly, since all of the ghosts always moved randomly during blue mode in the last game.

They actually wanted to make each ghost go to a random home corner! They failed to be able to get each ghost to "remember" its destination between frames. Instead, each ghost picks a new homecorner every single frame. Even the blue and orange! The end result is that the ghosts move around in "blue mode" instead of spreading out to random corners.

The blue and orange ghosts were patched incorrectly, though. So, after they call the randomized home corner selector -- the old pacman code overwrites the decision with the home corners from the original maze that isn't even used in the game.

(Note, home corners are defined as actual map cells to seek out, not directional areas.)

There are tables for each maze in the game of new home corners for the ghosts to pick from. Unfortuanetly, they were never maintained in the code, and don't match up with the mazes, since the programmers found out they couldn't finish what they started.

The random home corner solution would have been very elegant -- or, if necessary, having all of the ghosts move randomly during the first 5 seconds would be decent (although, again it looks really unintelligent and weird -- and is already implemented by "blue ghost" behavior.) -- but the hybrid solution, with orange and blue seeking their old home corners and the other ghosts just bobbibng around mindlessly is just a mistake.


I remembered the part about random home quadrants but I guess I never noticed it didn't work for 2 of them.

The blue ghost behavior isn't random, so it doesn't neccessarily mess up your pattern.

I agree the Ms Pac programmers had some good ideas but they weren't the programmers the original pacman programmers were. She's a lot more buggy.



The random home corner thing doesn't even work for any of them, unfortuantely. It makes two move randomly.

I think there are some myths about the blue ghost behavior. It is random in that it uses a random seed generator that is called every time that a blue ghost needs to make a decision. The generator generates an address within 0x0000 and 0x1FFF to read the last few bits of. These bits are translated into the direction that the ghost must first try. If it is a wall, the ghost then just attempts through the remaining directions in sequence.

The only problem with this method is that the random seed is reset everytime you die, restart a level, etc.

Patterns work only if the random seed is the same for any given set of ghost positions and pacman pattern. This is easy to accomplish since it is reset at the beginning of every level or life.

Ms. Pac-man's randonimity comes from the R register, which is updated by the processor itself. The R register increments for every instruction executed, and for certain instructions increments by two, and for other instructions it is incremented by 2 times BC.

Suffice to say, if you phyiscally turn on the machine, insert a coin, and hit the start button within the same timeframe -- you could create a real, legitimate set of patterns for the entire game, since the R register would theoretically be at the same values at the same times.

In short, Pac-man affords us the opportunity to "synch" with the random seed multiple times per game. The only difference with Ms. Pac-man is that there is only one opportunity to "synch," and it is when the processor is reset and the game has not been played before you got there.

If the Pac-man seed were never reset, even between games, then it would be just as random as Ms. Pacman! The blue ghosts would be completely unpredictible if the game had been played before you got there.

I guess what I want people to get from this -- is that the level of randonimity is the same between games, and between the blue ghost behavior and "7 second random" behavior in Ms. Pac-man. It is simply an issue of when the seed is reset -- multiple times per game, or a single time per machine activation.

#45 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Tue May 22, 2007 3:12 PM

Ms. Pac-man's randonimity comes from the R register, which is updated by the processor itself. The R register increments for every instruction executed, and for certain instructions increments by two, and for other instructions it is incremented by 2 times BC.

Suffice to say, if you phyiscally turn on the machine, insert a coin, and hit the start button within the same timeframe -- you could create a real, legitimate set of patterns for the entire game, since the R register would theoretically be at the same values at the same times.


No, there's no comparison between the randomness of ms pac and pac. Since the R register incremented every instruction you have to run the exact same code. With variations of clock speed I'm not sure that's possible even if you initialized ram to be identical and rigged up some kind of robot to move the joystick at exactly the same time every time.

They've been argueing that point over on twin galaxies for as long as i can remember.

#46 Otoboke OFFLINE  

Otoboke

    Combat Commando

  • 4 posts

Posted Tue May 22, 2007 4:00 PM

I think there are some myths about the blue ghost behavior. It is random in that it uses a random seed generator that is called every time that a blue ghost needs to make a decision. The generator generates an address within 0x0000 and 0x1FFF to read the last few bits of. These bits are translated into the direction that the ghost must first try. If it is a wall, the ghost then just attempts through the remaining directions in sequence.

The only problem with this method is that the random seed is reset everytime you die, restart a level, etc.


Just for clarity, you're talking about the post-energizer blue ghosts as they flee from Pac-Man here, and not the non-energizer Blue ghost known as Inky, correct? Otherwise, my analysis of Inky's AI code was WAY off! I tested it by playing through a few games, pausing periodically, and making sure the technique mentioned earlier accurately predicted Inky's turns though. I was satisfied after 20 consecutive predictions.

Interesting analysis of the Ms. Pac "random home corner" trick, by the way. I haven't gotten around to looking at the Ms. Pac assembly yet. It does seem more like a thrown-together solution that happened to do the job, rather than a really elegant solution like what they were apparently trying for. Come to think of it, having every board start off with Blinky and Pinky running around like chickens with their heads cut off while the other two invariably go to the same corners is, almost literally, a half-assed solution. Too bad they were in such a hurry to get the Ms. Pac machines into the arcades.

#47 Shannon OFFLINE  

Shannon

    Born To Be Insane

  • 7,497 posts
  • Pac-man Fever
  • Location:Arcade

Posted Tue May 22, 2007 8:37 PM

Where's a ghost psychologist when you need one. :lol:

#48 JamieVegas OFFLINE  

JamieVegas

    Combat Commando

  • 9 posts

Posted Thu Jul 5, 2007 2:15 AM

Ms. Pac-man's randonimity comes from the R register, which is updated by the processor itself. The R register increments for every instruction executed, and for certain instructions increments by two, and for other instructions it is incremented by 2 times BC.

Suffice to say, if you phyiscally turn on the machine, insert a coin, and hit the start button within the same timeframe -- you could create a real, legitimate set of patterns for the entire game, since the R register would theoretically be at the same values at the same times.


No, there's no comparison between the randomness of ms pac and pac. Since the R register incremented every instruction you have to run the exact same code. With variations of clock speed I'm not sure that's possible even if you initialized ram to be identical and rigged up some kind of robot to move the joystick at exactly the same time every time.

They've been argueing that point over on twin galaxies for as long as i can remember.



I agree that slight variations in clock speed might exist across different machines. However, the scenario I describe above would indeed be possible if executed on one and only one machine. It is also possible, and much easier, to perform in an emulator. I have succeeded in doing it this way.

The machine needs to be reset from a known state, and the coin and start button triggers depressed at the exact same time. Since the R register value is determinisitc, so would be the outcome of the "randomization" functions, assuming all of the following game input remained the same.

This method has been used to cheat casinos using legitimate, hardware-based RNGs with high timer resolutions. [Since the Z80's R register is only 8-bit, the resolution is tiny (only 256 possible states.)] Once the randomization algorithm is known, and the machine is determined to be in a known state (i.e. in a machine where values of displayed cards in a video poker machine directly correspond to the state of the RNG,) an auxilliary computer is then manually synchronized with the gaming machine. It emits a sequence of beeps that a human operator observes in order to synchronize themselves with the timing rythm. At the exact monent that a pre-determined beep count has passed, the human operator depresses the approriate "stop" button. It sounds like a poorly hatched theory, but has been executed successfully in the real world. The human mind/muscle connection and timing/perception capacities are far more accurate than you would imagine. The margin for error for a trained operatior is within nanoseconds. Obviously, the system will not work every time. It does, however, succeed frequently enough to lay out the foundation for a "new way" of creating deterministic Ms. Pac-man patterns, as well as it has to bilk Nevada gaming establishments out of a couple hundred thousand dollars.

[This phenomenon was exploited in primitive gaming machines. Modern gaming machines now incorporate more than one RNG. The timing resolutions have been greatly increased, and the player-observable-outputs/RNG coupling has been purposely obfuscated.]

To conclude and to clarify, my observations apply to any single machine that one has the ability to reset at will, and to a player that has the dilligence to practice executing starting trigger sequences that are synchrnonized with attract mode screen output. I have had a 33% success rate with this method, every third reset being able to start the first rack with the exact same ghost movements.

#49 Dav OFFLINE  

Dav

    Moonsweeper

  • 353 posts

Posted Thu Jul 5, 2007 8:26 AM

Ms. Pac-man's randonimity comes from the R register, which is updated by the processor itself. The R register increments for every instruction executed, and for certain instructions increments by two, and for other instructions it is incremented by 2 times BC.

Suffice to say, if you phyiscally turn on the machine, insert a coin, and hit the start button within the same timeframe -- you could create a real, legitimate set of patterns for the entire game, since the R register would theoretically be at the same values at the same times.


No, there's no comparison between the randomness of ms pac and pac. Since the R register incremented every instruction you have to run the exact same code. With variations of clock speed I'm not sure that's possible even if you initialized ram to be identical and rigged up some kind of robot to move the joystick at exactly the same time every time.

They've been argueing that point over on twin galaxies for as long as i can remember.



I agree that slight variations in clock speed might exist across different machines. However, the scenario I describe above would indeed be possible if executed on one and only one machine. It is also possible, and much easier, to perform in an emulator. I have succeeded in doing it this way.

The machine needs to be reset from a known state, and the coin and start button triggers depressed at the exact same time. Since the R register value is determinisitc, so would be the outcome of the "randomization" functions, assuming all of the following game input remained the same.

This method has been used to cheat casinos using legitimate, hardware-based RNGs with high timer resolutions. [Since the Z80's R register is only 8-bit, the resolution is tiny (only 256 possible states.)] Once the randomization algorithm is known, and the machine is determined to be in a known state (i.e. in a machine where values of displayed cards in a video poker machine directly correspond to the state of the RNG,) an auxilliary computer is then manually synchronized with the gaming machine. It emits a sequence of beeps that a human operator observes in order to synchronize themselves with the timing rythm. At the exact monent that a pre-determined beep count has passed, the human operator depresses the approriate "stop" button. It sounds like a poorly hatched theory, but has been executed successfully in the real world. The human mind/muscle connection and timing/perception capacities are far more accurate than you would imagine. The margin for error for a trained operatior is within nanoseconds. Obviously, the system will not work every time. It does, however, succeed frequently enough to lay out the foundation for a "new way" of creating deterministic Ms. Pac-man patterns, as well as it has to bilk Nevada gaming establishments out of a couple hundred thousand dollars.

[This phenomenon was exploited in primitive gaming machines. Modern gaming machines now incorporate more than one RNG. The timing resolutions have been greatly increased, and the player-observable-outputs/RNG coupling has been purposely obfuscated.]

To conclude and to clarify, my observations apply to any single machine that one has the ability to reset at will, and to a player that has the dilligence to practice executing starting trigger sequences that are synchrnonized with attract mode screen output. I have had a 33% success rate with this method, every third reset being able to start the first rack with the exact same ghost movements.


In order to make this work on a slot machine you only have to hit it right once and if you miss you still have the regular odds of making a return. I can definitely see that working. In order to do this in ms pac you have to do it right every time you push the stick and every time you release the stick or it's useless, you've lost your sync with the R register. That's what, 100 times a level? Multiply that number by how many levels before it gets hard enough patterns will help you. I don't like those odds quite so much.

#50 kisrael OFFLINE  

kisrael

    HMBL 2600 coder

  • 3,970 posts
  • Location:Boston Burbs, MA

Posted Thu Jul 5, 2007 10:00 AM

I'd love to hear if they did an equally deep bit of ghost psychology for the recent Pac-Man CE on Xbox Live....




0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users