Last time we built a problem solver that was capable of finding a solution to the fox, chicken and grain puzzle. This was generic inasmuch as it can solve other logic puzzles such as the 3 bulbs in the attic problem:

There are three switches downstairs. Each corresponds to one of the three light bulbs in the attic. You can turn the switches on and off and leave them in any position.
How would you identify which switch corresponds to which light bulb, if you are only allowed one trip upstairs?

(source: http://brainden.com/logic-puzzles.htm)

Although, it has to be said that the key bit of lateral thinking required for this one is in framing the problem for the model. That is, the intuition that in addition to the two states of on/off, a third state can be generated (off but still hot).

There are other problems that cannot be solved using the set based model. Take, for example, the classic problem of the man in the elevator:

A man who lives on the tenth floor takes the elevator down to the first floor every morning and goes to work. In the evening, when he comes back; on a rainy day, or if there are other people in the elevator, he goes to his floor directly. Otherwise, he goes to the seventh floor and walks up three flights of stairs to his apartment.
Can you explain why?

(source: http://brainden.com/logic-puzzles.htm)

To solve this problem we need a spacial model. We also need some knowledge of the differences in the expected or stereotypical composition of elements in the model under the stated cases (rainy day, not rainy day), which are implicit - e.g. it's not stated that he has an umbrella when it rains. Finally, we need to compose elements in such a way that the two outcomes are produced (go to 10th floor, go to 7th floor) and infer the implied characteristics that are relevant to the question posed. In short, this is a complex problem - even the human brain can take some time to seek out the solution.

Spacial model

What would a suitable spacial model look like? We need to be able to position objects in space based on their relationships (e.g. the buttons on the elevator are placed in a vertical line). We probably also need to model the dimensions and orientation of objects for more realistic placement.

How many dimensions do we need? We see in 2D (the 3D world is projected on our 2D retinas). The model in our heads includes some depth information but we're not maintaining a full 3D model as otherwise we could see through walls. Also, we do a great deal of problem solving on paper, which is a 2D space so it looks like we can go a long way with 2D. It will be computationally much less intensive to avoid higher dimensions.

To solve a problem with a spacial model we'll want to do something similar to the set-based approach:

  • Define the start state in the model
  • Define the win state in the model
  • Find a sequence of moves from start state to win state

However, there are some additional complexities that come with the freedom of the spacial model:

  • There are infinite possibilities to set up the start state and win state
  • There's an infinite number of possible moves

This is because we have gone from a discrete model with a small number of possible states to a continuous model with infinite possible positions, orientations etc. We need some strategies to collapse down the possibilities back to a manageable number.

As with the set based example we're not going to concern ourselves with translating the natural language problem into model-space just yet. Let's assume we have our start state and win state defined along with the possible actions and consequences.

We can apply the same monte-carlo tree search algorithm as before. The only difference is the state has become more complex, including position information rather than just set membership.

It's easy to see how this would work for the fox, chicken and grain problem but what about the man in the elevator? In that case, in addition to moves such as pressing an elevator button, there are also parameters that can be changed such as the height of the man.

Next time

We'll implement this in python to solve the man in the elevator problem.