Confusion in the Wumpus World model?

Question

The Wumpus World is an example for Knowledge Representation, Reasoning, and Planning- in which an agent had to explore a cave made up from a series of interconnected rooms. In one of the rooms in the cave, there was a Wumpus which would kill the agent if it entered that room. Some rooms contained pits, and the agent would die if it entered any of those rooms too. The agent had one arrow with which it could kill the Wumpus. The goal was to locate the gold that was hidden somewhere in the cave and return to the start without getting killed.

http://www.cis.temple.edu/~giorgio/cis587/readings/wumpus.shtml

There is exactly one Wumpus. Hence W1,1 ∨ W1,2 ∨ ... W4,3 ∨ W4,4

One way to say that there is at most one wumpus is that for any 2 squares, one of them must be wumpus-free. With n squares, we get n(n-1)/2 sentences such as ¬W1,1 ∨ ¬W1,2 .For a 4*4 world we begin with a total of 155 sentences containing 64 distinct symbols.

---

I'm not able to understand how we get n(n-1)/2 sentences. And also- how do we know that in a 4*4 world we have a total of 155 sentences? Can someone please explain this concept to me. Thanks.

Answer 1

In a 4*4 world, you have 16 total squares. We are creating a sentence for every pair of states. Without loss of generality, we can convert every two-dimensional index (r,c) to a one-dimensional index (r*4 +c). That is just a simplifying step.Algorithmically, you can write the creation of those sentences as:

for(i = 0; i < 16; ++i)
  for(j = i+1; j < 16; ++j)
    print ~Wi v ~Wj

We can then analyze the number of print statements made for each iteration of the i loop.

i = 0: 15 sentences

i = 1: 14 sentences

...

i = 15: 1 sentence

So in this case, the number of sentences the summation of the numbers 1 to 15. The well known formula for this is n(n-1) / 2, giving an answer of 105. This is different than your stated answer of 155, so I do not know where you got that number from. 155 is not a number that can be found by that formula.

Also, note that the n I am using is different than the number of squares; it is one less than the number of squares. The reason is that you do not want statements that compare the same square like ~W1,1 v ~W1,1.