I’ve just completed my first coding project in my Master’s pursuit. It was to write an artificial intelligence agent that could solve the ‘Sheep and Wolves’ problem. For those unfamiliar, this problem goes like this:

A farmer has some number of sheep and wolves. He also has a boat. He needs to get these animals across a river, but can only take 2 at a time. Now, he can never leave more wolves than sheep on either side of the river, or the wolves will eat the sheep. He also cannot cross with less than 1 animal either direction (he gets lonely).

So, we had discussed several problem solving methodologies in class. The goal of this course in particular is to solve these AI problems taking a more human/cognitive approach (as opposed to purely optimal solutions as seen in Machine Learning). I ended up using a model called “Generate and Test” which is a fancy way to say, take an informed guess, and see if it is correct.

I accomplished this through building a state tree of the problem and all its possible “move”. For example, the farmer can only take:

- 1 sheep
- 1 wolf
- 1 sheep and 1 wolf
- 2 sheep
- 2 wolves

So, we build a state to represent the starting condition, then update it based on these 5 possible outcomes. Then these 5 possibilities again branch out into 5 more possible outcomes each, and so on until a tree of every conceivable (and valid) possibility is complete. This is a lot of compute! So, I came up with a couple of heuristics to limit the state space a bit.

First, there are tight limitations on which states can be created and added to the tree. No illegal moves based on the problem rules, no bringing 2 animals back from the starting side of the river, this sort of thing.

Secondly, a simple boolean to check and see if the “success” state was ever achieved. This check was performed against a Set structure with constant time lookups (very efficient) in which I placed every state as it was generated. If we ever see the success state, we stop generating immediately.

Finally, a BFS through the tree looking for this success state completes the solution, and a tree walk back to the root node of the state tree delivers the list of moves needed to arrive at the solution. Very cool stuff.