Geeky Games...
Trudy's Wumpus World, Behind the Scenes

Last updated October 20, 2008

Okay, you've played the game. Now you want to know how it works? Are you people ever satisfied? Seriously, this game was quite an interesting self-study in artificial intelligence for me, and I thought you might enjoy it as much as I did. Well, I'm pretty geeky, so you might not enjoy it as much as me, but you might find it at least remotely fascinating. If you don't, you can always go play some other games.

Presenting... the World!

The Wumpus world, in this case, is a 5 by 5 grid of "cubicles" or cells, similar to this:


You begin in the upper left corner of the grid; the computer player starts at the bottom right. Each cell has a numeric value, which describes its contents: 0 is empty, 1 is a "pit" (black hole), 2 is the "gold" (paycheck), and 4 is the "Wumpus" (Trudy). These values can be added together such that you can tell exactly what's in the cell (7 means the Wumpus, the gold, and a pit are all in the same cell). The two start positions are always empty, to prevent you from being automatically killed at start up and to keep you from winning right off the bat because the gold is in the same cell as you.

Take Good Notes, Students...

In order to effectively explore the world, it is necessary for the computer to remember where it has been, and what it deduces is in each cell. To do this, the computer player maintains two arrays, the memory and move_history arrays. (An array, for the computer-illiterate people out there, is a grouping of similar values that is addressed by a single name. It eases algorithmic processes to use them.) The memory array stories a value for each and every cell in the world, initialized to "unknown." Whenever the computer player enters a new cell, it will analyze its situation, deduce what may be in the adjacent cells (up, down, left, and right), and stores these values into its memory. It will then use its memory to decide which way to go.

The move_history array is used to keep track of where the computer has been. The computer uses this to help determine where it wants to go next. As a general rule, the computer will prefer to go to a cell it has deduced is "clear" (i.e., empty of pits and Wumpuses (or is it Wumpi?)) before it will backtrack to somewhere it has already been.

This process is very similar to what you might do when you draw a map of the Wumpus world as you go. You will probably try and keep track of the path you took and maybe take notes of where you felt a breeze or smelled the Wumpus. That way, you can easy go back a safe route if you had to, or deduce whether or not a suspected "bad" cell really does contain a pit or Wumpus.

Not So Fast, Sherlock...

How does the computer go about "deducing" what is or isn't inside an adjacent cell? That's a very good question, since every decision the computer must make depends on what it "knows" about its surroundings. The computer does pretty much the same thing you do when you play. If it feels a breeze, it knows that a pit must be in a nearby cell. It can narrow down the location somewhat by taking note of where it has been. If it's already been in the cell to the left, it knows that cell is "clear," because it would have died there if it wasn't. That eliminates that cell as a possible location for the pit.

It can also examine the same cell more than once, coming from different directions. If one cell has already been suspected of containing a Wumpus, but another cell adjacent to it does not contain a smell, then that cell probably doesn't contain a Wumpus. That means it is clear and free to explore. But if it does smell a Wumpus, then that's a good indicator that we've found where he's hiding (especially since there's only one Wumpus).

The computer is really no match for a human opponent, mostly because we are much more powerful in our deductive reasoning skills. The computer can only run a series of tests, seeing if a condition is met or not, and then acting on the results. Don't get me wrong; the computer rarely makes a mistake!

Eenie, Meenie, Minie, Moe...

Once the computer has analyzed the world, it then decides what it must do. Should it move to another cell? Should it pick up the gold? Will it be eaten by a Wumpus?

Again, this process is merely a series of tests on memory, based on its precepts. If the gold is present in the current cell (it sees a glitter), it will pick the gold up and hold onto it. If it has walked into a cell with a pit or a Wumpus, it will "die" and stop moving. Otherwise, it will have to decide a direction to travel, and once it has picked one, move into a new cell.

To do this, the computer ranks each possible move with an "optimal value" or "priority." The higher the priority, the "better" the choice. It will then compare the priorities of each move, pick the highest one, then move in the direction of that priority. If more than one move has the same priority, it will randomly pick a direction and follow it.

How does it assign priorities? That's where the different player characters come in. Each computer player, whether it is Nick, Ki, or Fooker, assigns these priorities differently. As an example, we'll look at Nick. Nick plays very conservatively, meaning he will take the "safest" route whenever possible. What constitutes safe? Any cell known to be clear is safe, either because he's been there or because he's deduced that it is. Of these, he will choose a cell he's never been to first, because it will better his chances to explore. If a cell is not safe, he will then decide how risky it is. Does it possibly contain a pit, or does it definitely contain a pit? Nick usually assigns the following priorities to the following situations:

  1. Clear, not visited
  2. Clear, already visited
  3. May have pit or Wumpus
  4. Definitely has pit or Wumpus
  5. Invalid move

(An invalid move would move him out of the room and off the grid.) In this way, he will almost always travel places he knows are safe, and should never make an invalid move. Indeed, if you play him often enough, you will notice that Nick very rarely will fall into a black hole or get caught by Trudy. Ki and Fooker play in a similar manner, only they assign their priorities slightly differently. Ki will take an occasional risk if need be, while Fooker will take wild risks if it means beating you to the paycheck (he's always been pretty competitive :) ).

Well, there you have it, boys and girls. Even if the computer seems to make intelligent decisions, it is really just a matter of testing conditions and setting priorities, actions we do instinctively, without really thinking about them. So, next time you think Fooker is cheating, just remember: he's just a machine....

Return to GPF Geeky Games