AI Follies: Interesting Behavior

By Shamus Posted Tuesday Aug 18, 2009

Filed under: Programming 32 comments

Here are some thoughts on the goals of an AI programmer, which should have gone at the beginning of this series. Let me put them up now before we go any further.

My first computer (which you can read about here) was the Tandy MC-10. 4k of memory. Less than a single megahertz of speed. Once I got my programming legs under me, the first thing I tried to do was make a game clone Pac-Man. For reference, here is what the original looked like:

wakka wakka wakka!
The original.

As a programmer, displaying something like that on the Tandy was about as likely as getting Crysis running on a 486. If I’d wanted to display my ghosts with the same level of detail, they would have needed to take up most of the screen. On the MC-10 the screen was 40 characters wide by 20 lines tall. It had a fixed character set. Character codes 0 through 127 were standard ASCII. 128 through 255 were a bunch of stupid shapes that were, in theory, for doing graphics but which didn’t really look very interesting and were more hassle than they were worth.

So my Pac-Maze ended up being made mostly of ASCII characters. Periods for dots. Asterisks for power pills. A solid block of pixels for the walls. I’ll bet a lot of thirty and forty-somethings out there authored something very, very similar. Here is a very close re-creation of what it looked like, according to my memories:

wakka wakka wakka!
The difference in maze layout is due to the fact that the original Pac-Maze can’t actually exist on a 40×20 grid. This was as close as I could come.

Well, that was the platonic ideal anyway. In reality, the computer was hooked up to a television, and ended up looking more or less like this:

wakka wakka wakka!

All those hours spent looking at my TV from sixteen inches away. Ouch.

Anyway, this was my first attempt at AI pathfinding. It ended in disaster, but I think it was an admirable effort for a junior-high school kid. I can still remember the rules that the ghosts used:

Each ghost can move in one of four directions. Note that “moving” here is not a smooth thing. The ghosts did not slide smoothly around the board like they did in the arcade. They could only occupy one of the given character positions. And so they blinked around, hopping from one dot to the next like pieces on a chess board. A single turn would take a full second. Imagine counting one Mississippi, two Mississippi, etc. That’s how long it took poor Pac-man to jump from one dot to the next. (The game ran much smoother without the dot-eating sound effect, but I couldn’t give that up!)

Originally, they all ranked each direction the same. (That is, they would consider moving up before they considered moving left.) But this uniformity of rules led to uniformity of behavior. If two ghosts ever got close to each other, they would keep making the same decisions and thus move together. Eventually the whole gang would pile up and it was pretty much like running from one ghost for the rest of the board.

If I wanted different behavior, I needed different rules for each ghost. I made it so that each had their own order in which they “preferred” each of these directions. So, ghost #1 might rank the four directions:

1) Up
2) Down
3) Left
4) Right

That is, if given a choice between going down or left, it will prefer down more than left, left more than right, etc. Another might prefer:

1) Right
2) Left
3) Up
4) Down

Two ghosts preferred vertical movement first, the other two preferred horizontal movement first. The rules they used were:

1) Can’t pass through walls.
2) You may NEVER reverse direction.
3) You MUST move.
4) Check your direction priority, and see if you can move TOWARDS the player without violating rules 1 through 3.
5) If you can’t move towards the player, just select the highest-rated direction that doesn’t violate rule 1 through 3.

The upshot of these rules was that if you removed the player from the game entirely, the ghosts would fan out, each heading to a different corner. They would then run in circles around the wall in that corner forever. Two would go clockwise around their little wall, the other two would go un-clockwise. This was really cool. Diverse behavior! I was so proud of myself.

But if the player was in the game, the ghosts would fan out and envelop poor Pac-Man from all sides within seconds. The game was essentially impossible. I discovered that “interesting” behavior was not the same thing as “efficient” behavior, and that “interesting” was way harder.

My solution was to slow them down. Ghosts only got to move half as often as the player, which meant you could escape their grasp. It was still much harder than the arcade, and a lot less interesting. You could stay alive if you stayed near the middle of the board where you had lots of options, but it was fatal to go after the dots in the corners because they would manage to cover all of your escape routes before you could get back out. If I made them move one-third the speed of the player, it became too easy. You could ditch them on one side of the board and go work on the other. They were a constant nuisance, but they weren’t a threat and they were always moving towards you. (They sort of “camped” the middle, which made dots close to the center almost impossible to grab. Not that “camping” was part of anyone’s gaming vocabulary yet.) I began to gain an appreciation for just how much thought had gone into the original game. It was easy to make the game either effortless or impossible, and the designer managed to find the precise balance between the two, a narrow band of behaviors that could be labeled as “fun”.

Sometimes AI is used to make the game seem less smart by making it miss more, ignore you at the right time, or as with my example above, chase you less efficiently. Sometimes AI is used to make the game “smarter”. So the goal of AI is not to simply increase intelligence. And it’s not to make the computer opponents more efficient. The goal of AI is to make the computer an interesting opponent.

It turns out that this is a complete pain in the ass.

 


From The Archives:
 

32 thoughts on “AI Follies: Interesting Behavior

  1. Benjamin Orchard says:

    The goal of AI is to make the computer an interesting opponent.

    It turns out that this is a complete pain in the ass.

    Which is why I really, really, really appreciate a good AI when I see it in effect. I’ve always appreciated the work that Blizzard does in their games. It’s far from ‘perfect’, but it IS about 20000000% better than what I would end up with.

  2. DaveMc says:

    Just to confirm, as a late thirty-something: yes, I did something similar, back on my Commodore P.E.T. (Personal Electronic Transactor, I think). And probably again on the immensely powerful (by comparison) Commodore 64. (That’s 64K of RAM, you whippersnappers. And we were glad to have it, what with all the walking to school barefoot in the snow, and so forth.)

  3. Nevermind says:

    By the way, the original PacMan AI was just a little bit more comlicated than yours. You can read about it here: http://home.comcast.net/~jpittman2/pacman/pacmandossier.html

    It’s really fascinating how they managed to create such interesting behaviour with such simple rules.

  4. Didn’t the original pacman ghosts just wander aimlessly until they see the player? At least it seems more logical that way.

  5. JohnW says:

    A single turn would take a full second. Imagine counting one Mississippi, two Mississippi, etc. That's how long it took poor Pac-man to jump from one dot to the next. (The game ran much smoother without the dot-eating sound effect, but I couldn't give that up!)

    So instead of wackawackawackawacka your Pacman went wacka…wacka…wacka…wacka?

    1. Shamus says:

      JohnW: Sort of. My PacMan went:

      BffT… BffT… BffT…

      It was sort of like the sound you get when interleaving two halves of a deck of playing cards. I don’t know what you call that move, but it you took a quarter-second of that sound, that was my “Wakka”.

  6. Peter H. Coffin says:

    And probably again on the immensely powerful (by comparison) Commodore 64. (That's 64K of RAM, you whippersnappers. And we were glad to have it, what with all the walking to school barefoot in the snow, and so forth.)

    And that’s pretty much where the gaming state of the art sat for the next decade or so. There were lots of things with more memory or horsepower, or even direct successors, but none of them stretched and used to the point of “used up” the way that the C64 did. That’s high praise from an Apple ][ owner.

    I did a couple of experiments in a more abstract way that Shamus, mostly in BASIC, sometimes with a game called (IIRC) Robot War. In the BASIC stuff I remember almost fixated on using proximity as a tool for credible behavior. Something being just close enough turning on the “aware of player” flag made it seem a LOT better than trying to figure sight lines or predictive behavior, and varying the awareness area inversely to the speed of the critter helped make them very interesting very cheaply, because they’d “see” you, speed up to come after you and lose perception, maybe move in the wrong direction, slow down and spot you again…

  7. UTAlan says:

    It seems counter-intuitive that AI has to be “dumbed down” for us. It’s almost discouraging that, although I beat Call of Duty on Veteran difficulty, even that wasn’t as hard as they could have made it. (Not that I’m upset that they didn’t make it harder!)

  8. Tommi says:

    The rule of needing to gimp the AI to make play fun seems to break down in (real time) strategy games and, say, Go.

  9. Deoxy says:

    It seems counter-intuitive that AI has to be “dumbed down” for us. It's almost discouraging that, although I beat Call of Duty on Veteran difficulty, even that wasn't as hard as they could have made it.

    Games can be infinitely hard – that is to say, they can be made literally impossible. “Dumbing down” the AI is not about making it dumb because we are too dumb to beat it, it is about making it not auto-kill us when it has enormous advantages.

    Imagine that you were clairvoyant, knowing everything going on on the entire planet all at once, and you had an army of robots that obeyed your thoughts. How would any conventional army have the slightest chance against you, much less a small group or even one person (no matter how much of a bullet-sponge they were)? That’s the situation here.

    AI is about taking a situation like that and trying to get the computer to act as though that WEREN’T the situation. It’s not about “dumbing down” (though, to a certain extent, that is required). It’s about trying to simulate something playable instead of “march of the auto-killing-you stupidity that no one will buy because it’s dumb”.

    To put it another way, in the real world, we are all “dumb” in that well, we don’t automatically know almost everything in the known universe. In a game, the program does. Making a game that is playable by us limited mortals involves levelling the playing field, at least somewhat.

  10. Blurr says:

    Actually, the ghosts in the actual pac-man games work on very different principles from the ones that you’ve described:

    Red – Blinky: Oikake – “Akabei” (oikake-ru = to run down/to pursue/to chase down). Or of course the english “Shadow”.. the guy is literally on your tail and can be thought of as your shadow

    Pink – Pinky: Machibuse (machibuse = performing an ambush). Or in the english “speedy”. He is indeed just as fast as Blinky and works with him to ambush and cut you off.

    Blue – Inky: Kimagure – “Aosuke” (kimagure = fickle/moody/uneven temper). Or in english “Bashful”. He is unpredictable. Sometimes he follows you, sometimes he goes away from you.

    Orange – Clyde: Otoboke – “Guzuta” (Otoboke = Pretending Ignorance). The nick “Guzuta” means someone who lags behind). Or of course “pokey” in english. The guy is slow. He’s always going somewhere on his own. But he does sometimes successfully cut you off, but almost never outright chases you.

    1. Shamus says:

      Blurr: I think Nevermind was referring to this:

      http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#CH3%20-%20Intersections

      and this:

      http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#CH3%20-%20Scatter%20Targets

      Wow. It is sort of neat that my cobbled-together logic had so many things in common with the real deal.

  11. Zel says:

    Don’t worry, us younger folks made the same programs on our fancy graphic calculators (mine was a TI-83) in high school, including variants of PacMan, Space Invaders and Scud Attack. It was a great way to pass time during boring classes.

  12. Lochiel says:

    @UTAlan: Remember, in most games the AI has better (read: perfect) information than you do. And even in games where the Player has the same information the AI does (like PacMan), their are more of them than there are of us.

    When there is only one AI, and the moves and information are equal (board games and RTS’s) then it is difficult to get an AI to match a human opponent.

    1. WJS says:

      Are any RTSes actually what we’d call fair? I’m pretty sure all the ones I’ve played cheat to some extent. It doesn’t matter what kind of units I build, the AI always has the right units to counter them. It always knows what units you have built, even if it isn’t allowed to know where they are and head straight to you. Then of course there’s the more blatant, like how AI in Warcraft and Starcraft get to build units for free while you have to pay for them, or Dawn of War where the enemy get two or three times the unit cap you do.

  13. Al Shiney says:

    Shamus, this post brought back fond memories of my own first exposure to a computer in high school … a TRS-80 Model II. I’ve never done any AI coding, but reading your algorithms brought a smile to my face as I tried to remember how to write in BASIC. Man, that was really only 30 years ago but it now seems like the dark ages.

  14. Ah, yes, TRS-80. That thing of yours actually looks way more fun than anything I could do on mine when it was just 4K. At 16K, mind you, there were these text adventure games . . .
    Those blocky graphics! The blocks weren’t actually pixels though, obviously, or periods and stuff couldn’t be smaller. I actually knew a couple of people who knew how to force the machine to show actual pixels.

    One thing, though–the old TRS-80 model 1 came with something no computer I’ve ever had since came with: A manual that was readable and useful. As in, I actually ended up reading the whole thing. Learned simple BASIC programming from it, liked its little stylized-computer cartoonish character. I can still remember the appendix at the back, with the cartoon character wearing a stethoscope etc. saying “If you don’t like this part, we can take it out!”
    The original Trash-80 was also unusual in that when you got the thing, the procedure for getting it to work was
    1. Plug it in
    2. Turn it on
    3. Wait 1/10th of a second

    Badabing! DOS prompt. At that point it was as useful as it was going to be.

    1. WJS says:

      I don’t know if expecting a modern computer to come with a manual is all that realistic. I’m pretty sure I have hundreds of manuals for mine.

  15. pwiggi says:

    @Tommi: Whether or not you have to dumb down AI for strategy games (I’ll stick to Chess and Go, and ignore RTSes and the like) depends on who the AI is for.

    If you want professional-level AI that can defeat a chess champion, then sure, make the best chess-playing algorithm you can.

    However, if you want a go bot that a 20 kyu player can play against to sharpen their game, and have a chance in hell of defeating, then you have to be careful. For example, I can’t beat gnugo on its lowest difficulty setting (yeah, yeah, laugh it up, I suck at go). So, if you want scalable difficulty, you still need algorithms that can be challenging without being impossible for newer players. You still have to find the spot on the difficulty curve that the individual player thinks is fun. And the wide disparity of skill levels in abstract strategy games means that this may be even harder than for other games.

    Also go is a notoriously hard game to program AI for. The absolute best go AI could only defeat a 9 dan player with a 9 stone handicap. The player estimated that the AI probably played at about a 2 dan level.

    And this AI required 500 machines parallel-processing data. That’s not AI so much as brute-force game tree analysis.

    Also also, there’s a big difference between chess/go and, say, pac-man or FPS-of-the-week. In the latter games, the AI is capable of summarily defeating the player by programmer fiat. The pac-man ghosts could move faster than you can input instructions to pac-man. The FPS AI could shoot you from across the map, flawlessly, because he has access to all of the game state data, and knows your exact location at all times.

    AI for chess or go, on the other hand, is constrained by the same rules as the player; the AI can’t ‘cheat’.

    1. WJS says:

      Obligatory “time marches on” link. I remember being dutifully impressed at that. Chess was cracked back in the 90s, but Go was always out of reach. For a time.

  16. Doug Sundseth says:

    Yeah, the C-64 was definitely a hot gaming computer for its time, not least because it had three different processors. The CPU was responsible only for computation and calls to the other processors. Graphics were handled by a graphics co-processor, which had the capability to handle smooth movement of sprites and do collision detection. Sound was handled by a sound co-processor.

    Plus, screen addresses were assigned in a logical manner, which was a significant advantage for the programmer over the Apple II.

  17. Pops says:

    Herein lies our mysterious pull towards games, even when we can “code” other things, perhaps even more useful things, we just have to attempt a game. My first was on a DEC machine at the local university while in high school. No monitors, just tractor feed continuous form paper. Wrote a “sink the submarine” game. I took a really long time to reprint the “screen” after each move. Killed quite a few trees…

  18. Adamantyr says:

    I’ve done simple AI programming myself on my TI-99/4a… sadly in my BASIC days. TI-BASIC was renowned for it’s slowness… put it this way, more than 2 moving enemies as well as a player seriously cramped gameplay speed.

    The first chase routine I ever used was the simplest; subtracting a target position’s coordinates from present coordinates to determine a movement vector. I usually called it the SGN method because using the sign function to return 1,0, or -1 was the quickest way to get the results.

    Of course, this method involves no pathfinding around things, it’s just a direct move at (or away) method. So usually with any walls your enemy objects would just stop and run continuously into the wall.

    I’d have worked on improving the algorithm, adding some additional logic so it could slip around a corner, but TI-BASIC’s speed was so limited it wasn’t really worth pursuing.

  19. I’ve been programming on my TI-83 Plus, teaching myself from the manual. I haven’t made anything with motion, but I did make a workable Hangman and Battleship, and Tic-Tac-Toe that works fine until it suddenly has a memory error. Still not sure how to fix that.

  20. Scott M says:

    It’s probably worth differentiating between an AI that is effectively replacing a human opponent (as in Chess, Go, or, to some degree, RTS games) and an AI that is in a clearly superior position (such as Pac-Man or numerous single player games). I find the former more interesting because the AI has the same goal as the player and is competing with them over it, and they are confined by the same rules as the player. In this case the challenge really is to make the AI as good as possible, because that tends to be equivalent to making it interesting.

    1. WJS says:

      I don’t think that “replacing a human player” is a useful category, since it would include bots for deathmatch shooters. Obviously you don’t want to make them “as good as possible”, since that would be exactly the kind of cheating murderbot that prompted this series of articles.

  21. Carra says:

    Never got to programming any moving game.

    Did have some fun programming an advanced minesweeper. Or monopoly :)

  22. Tolmar says:

    The original Pacman’s ghosts all had different AIs. Part of what was so hard about finding an AI for your clone might have been that you constrained yourself to having similar AIs on all the ghosts.

    The ghosts are usually described as one that seeks you directly, one that seeks you in a roundabout manner, one that roams the board but seeks you if you’re nearby, and one that moves entirely randomly.

    I’d try two seekers, with tiebreakers similar to the ones in your version, but with one of the two preferring to seek the short axis first and the other to prefer the long axis first. That is, they’d look at the difference in x and y positions, and one would fix the small distance first, the other the long. Then two random ones, with one attempting to seek if pacman is in the same row or column.

    (Well, actually, I’d give them all entirely different movement rules from one another, but that’s hardly Pacman anymore.)

  23. Dan says:

    I made a similar ASCII Pac-man clone in QBasic 4.5 (following a tutorial) when I was about 12, but I’m only 22 and this was on a 386.

  24. Greg says:

    Hi Shamus,

    I’m another TRS-80 TANDY MC-10 guy, and yes, it was my first computer, and yes, I made a crude port PAC-MAN work on an MC-10 so I feel your pain (and I think my text mode was just 32×16, so I’m drooling right now if somehow you got a 40×20 version).

    Years later, I punted the text version and tried writing in assembly to use some of the higher-resolution modes that the MC-10 had.

    Here’s a picture of the result:

    http://2.bp.blogspot.com/_C9La3rNXj8M/RYJcc2seC1I/AAAAAAAAAAM/qzZNVUHqJg8/s320/mc10_pac-man.jpg

    The rules for the NAMCO pac-man I was able to get from an abandoned Ms Pac-Man machine (I could decode the ROM).

    Monsters have three modes:
    – flight: move randomly
    – corner: go to their respective corners (red: up-right, blue lower-right, orange: lower left, pink upper-left)
    – pursuit:
    red – tracks you where you are.
    pink – tracks four dots in the direction you are heading
    blue – tracks the point that puts the spot two dots in front of you directly between it and red (the idea is to keep you between itself and red, but in reality blue can’t move fast enough for this to work very well, especially when you turn a corner).
    orange – tracks you where you are but runs back to his corner if you’re within eight dots of him.

    There are a bunch of us still active on yahoo’s MC-10 users group. Come and check us out for old time’s sake.

    http://tech.groups.yahoo.com/group/TRS80MC10Club

  25. Sylocat says:

    Did you consider having a “proximity” rule for whether they would move towards you? Say, they would follow the rule that would get them to fan out and stick in the corners, unless you were within a certain distance from them?

    This way, you could vary the strategy, making it a little game to have to “lure” each ghost out of the corner it got stuck in, so you could pick up the dots in the corner.

  26. WJS says:

    Wow, 40×20. And here I am thinking that 80×24 is fairly small.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to WJS Cancel reply

Your email address will not be published.