Devising algorithm for an A.I. to solve the Wumpus game

Question

Background

I am currently coding an AI in C++ to solve a game called Hunt the Wumpus. You can try the game out here. My implementation of the game is based on a Graph template which I use to model the caves and the AI's "memory".

Rules

• The start position for the player, the Wumpus and the hazards (pits or bats) is randomized, one of the 20 caves.
• You can move from cave to cave freely and each cave will warn you if it has dangerous neighbors.
• You can shoot one of your 5 arrows to a cave adjacent to yours. The arrow will fly randomly for up to three caves. If it comes in contact with you or the Wumpus, the arrow will kill it.
• When shoting an arrow, if it's a misfire, then the Wumpus wakes up and each turn it will move randomly.
• You die either when one of the following happens:
  • Falling into a pit
  • Walking into the Wumpus' cave (it devours you)
  • Losing all of your arrows
  • An arrow which you shot randomly flies back into your cave and kills you.

AI Rules

• The AI marks each cave it visits as safe. If it enters a cave which has a threatful neighbor, it makrs the cave with TN (Threat Neighbor) and it marks each neighbor as a possible threat (PT).
• The AI has a "memory" which is a copy of the graph, but it is incomplete. The AI fills it as it travels through the graph.
• Based on the information stored in said memory, the AI decides to move or shoot.

Problem

I'm having trouble with the algorithm that I'm trying to implement "to hunt the Wumpus". My algorithm searches for the non-dangerous caves, each turn analysing the current memory and deducing which caves are optimal to move.

I think my algorithm cannot solve this problem, since it might get stuck. This is because I instructed to back off when there is a TN flag and the algorithm will not be able to deduce if there are safe caves remaining within reach.

I read up this paper [1] which explains an approach to solving the problem but does not describe the algorithm in detail. The section I'm trying to base my algotrithm off is section 4.2 and following of [1].

The algorithm

Suppose $G=(\lbrace v_0,...,v_{19}\rbrace, E)$ is the graph we are working on and let $N_i = \lbrace u\in G: \lbrace u,v_i\rbrace\in E\rbrace$ represent the neighborhood of vertex $v_i$. Suppose $M$ is the graph which represents the A.I.'s memory. $M$ is constructed step by step, for each turn that passes, each vertex $m_i\in M$ stores the following data: vertex number in $G$, indications (room is safe/dangerous, neighborhood has pit/bat/wumpus), and times A.I. has been here.

• For the first cave $v_i$, $m_0$ stores the information for this cave. Even if it is dangerous we have to move to a random neighbor in $N_i$. We store the room number, the indications it gives in memory for future reference and mark this room as safe.
• When we enter the next room $v_j$, if we didn't die we mark it as safe. We recieve the indications from the neighbors, store them in $m_1$ and we decide what to do next.
  • If there were no threats coming from the neighbors, we move once again to a random neighbor in $N_j$ except the previous one.
  • If there was a threat flag, then we only store the information of the room and backtrack to the last threatless room we were in.
• If we find the Wumpus-Is-Neighbor (W) flag in vertex $v_k$ then we mark the neighbors $N_k$ as possible hosts for the wumpus. Because there are no 4-cycles in the graph, once we hit with the W flag again in, say vertex $v_l$, we will know certainly that the Wumpus is in $N_l$.

• When we find the W flag again we will search inside $N_k\cap N_l$ for the only vertex inside

• Each turn when we move or shoot, the A.I. reads all of $M$ and adds flags, then we deduce information.

• Once the A.I. evaluates this, the A.I. decides to move or shoot. It will only shoot once we have found two instances of the W flag in two non-adjacent rooms.

As an example: Suppose that the A.I. walks into $v_i$, $m_i$ corresponding to $v_i$ has a TN flag, and $v_j\in N_i$. Then $m_j$ corresponding to $v_j$ will have a PT flag.
Now suppose the A.I. arrives at $v_k$, there is no TN flag in $m_k$, and $v_j\in N_k$. This means that the PT flag in $m_j$ is not true, and therefore $v_j$ is a safe room.

A more detailed example

• Step 1: The A.I. starts the game at $v_i$. It stores information in $m_0$, the $i$ index of $v_i$, the flags from this room (either safe or non safe). Then it moves randomly as it cannot backtrack.
• Step 2: The A.I. walks into $u\in N_i$, once again storing the information in $m_1$. Suppose $u$ has a TN flag, then all of $v\in N(u)$ has a PT flag except for $v_i$. The A.I. decides to backtrack to the previous cave (if it wasn't dangerous). Else, the A.I. has to choose to move randomly between $N(u)$.

For the following steps the A.I. covers all of the area it can reach and it deduces that there are safe rooms which it hasn't gone to.

Here I face one of the problems: I feel the A.I. isn't taking enough risks and therefore it might reach a stalemate where there are no more safe rooms to explore and it won't be able to deduce that there exist more of such rooms.

• Step $i$: Essentially the A.I. arrives at this room, records the information in a new vertex in $M$ and decides whether to explore this room's neighborhood or backtrack.

Another problem I have is that I am not sure whether the A.I. will reach the Wumpus' room.

Also when the A.I. at a room with bats, I'm not sure how to handle the $M$ graph, since what I'm doing is adding a $m_i$ vertex one by one. I think that it shouldn't generate a problem, but I'm not sure.

---

1. Hunt the Wumpus: an Empirical Approach by Graeme Cole (2005)

Answer 1

If you have explored all edges out of all safe rooms, and you don't have enough information to identify the location of the Wumpus, then you can pick an unsafe room randomly and randomly explore an edge out of it. That prevents you from getting stuck if you've explored all safe rooms. (There are other possible strategies, but this is a simple one that's probably reasonable and easy to program.)

Rather than backtracking, I would suggest the following strategy: if the current room $r$ is not safe, pick a random safe room $r'$ that has an unexplored edge out of it, move from $r$ to $r'$, and then explore the unexplored edge out of $r'$. Since you've built up the graph in memory, you can easily find a path from $r$ to $r'$ (e.g., via BFS). In this way, you're not restricted to rooms $r'$ and paths that take the form of "backtracking", but you can go to anywhere known and reachable. In this way, if there is any safe place you can explore, the algorithm will explore that before trying anything unsafe.

In this way, you won't get stuck.

Bats should be straightforward to handle. Suppose the bat takes you to a room $r$ that you haven't previously been in. Then you add a new vertex for $r$ to the graph, that's disconnected from all other vertices.

Those simple tweaks should take care of all of the problems/concerns you listed in the question.

Answer 2

This game is mentioned in Peter Norvig's lovely textbook "Artificial Intelligence: A Modern Approach". A pdf can be found online quite easily.

Are you familiar with how to model this problem as a search problem?

The issue with the algorithm getting 'stuck' is a basic feature in search algorithms like depth first search and breadth first search, in that once the algorithm can not make any more legal moves it should return to an un-explored branch of the search space and explore that until it reaches a goal state.