JamieVegas

One would think they'd at least include a "classic AI" mode. The differences in the "maze architecture" suggest that they've "revamped" the AI. Some of the more interesting "faux AI" tricks wouldn't work correctly in a huge 16:9 maze, nor would they work with mazes that greatly deviate from the interlocking architecture ("'T', 'L', and '+' based," for want of a better phrase.) Not to mention, "home corner mode" might not bode as well on maps that large.

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.

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.

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.

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?

Dav, You did Ms. Pacman as well? What did they do to the ghost logic, exactly? Are they still using the same algorithm to get a direction based on a source and destination grid point? Where exactly does the randomness come into play? What about the "personalities"? How much different are they from the original Pacman?

Dav, I wish I'd known you'd disassembled all of it! I might have just wasted a ton of time. It seemed like from the last post about the blue ghost in this thread that there was at least still some confusion about the exact math and logic taking place. Anyway, yes, I did get around to the blue time -- today, actually. I found the same thing -- it reads anywhere from 0000 to 1FFF in the ROM. Very strange. I assume that if you got the wandering ghost path routine analyized that you got the best-direction function analyzed, too. Did you find the AI for the attract mode demo Pacman? I found that today, as well. He is simply headed towards the destination point that is directly opposite the midpoint between the pink ghost and pacman. The demo seemed pre-recorded to me. It just goes to show how something simple can create the illusion of intelligence. I've dissassembled them all before years ago. I don't know if I kept it around. Yes it is extemely simple compared to how complex the results seem. I'll be interested in seeing your webpage. If you haven't gotten around to doing the blue time it's just a psuedo random number generator using the program code to generate random bits, I always thought that was pretty neat.

Breakthrough! I've just disassembled and completely documented the entirety of the ghost AI. It's incredibly simple, guys! I'll post a link to the website I'm preparing as soon as it is ready.

I have documented exactly what they do, except the blue ghost! I've been fascinated by the AI for a while. Nearly the all of the information you find on the web is entirely wrong. It's all deceptively simple, and I'm very happy that Dav provided some assembly to make the solution definitive. I knew the blue ghost was seeking a destination two spaces ahead of Pacman, but it was also clear that the red ghost proximity was having some effect. Exactly what the effect was, I couldn't tell for sure. From the code, it appears that the blue ghost is always finding away to be nearer to two spaces ahead of Pacman, plus the difference between the red ghost and that spot. That is to say, if the red ghost is getting closer, so is the blue. This sort of makes sense along with the "personality" which is supposed to be exhibited by the blue ghost, which is that he is "bashful" and only directly attacks if the red ghost is around. If you're going towards him while the red ghost is far away, his destination is way ahead of you, and that's why he seems to "go in the opposite direction" sometimes. If anyone wants to discuss disassembly or ghost AI information, please e-mail me!