A Very Short Introduction

Artificial Intelligence

By Margaret A. Boden

The Missionaries and Cannibals Problem

The M&C problem is a classic puzzle in Artificial Intelligence. The puzzles goes that:

On one bank of a river are three missionaries and three cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.
How can the boat be used to safely carry all the missionaries and cannibals across the river?

Wikipedia describes how AI could understand the problem stated.

A system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector ⟨m, c, b⟩. The vector’s elements represent the number of missionaries, cannibals, and whether the boat is on the wrong side, respectively. Since the boat and all of the missionaries and cannibals start on the wrong side, the vector is initialized to ⟨3,3,1⟩. Actions are represented using vector subtraction/addition to manipulate the state vector. For instance, if a lone cannibal crossed the river, the vector ⟨0,1,1⟩ would be subtracted from the state to yield ⟨3,2,0⟩. The state would reflect that there are still three missionaries and two cannibals on the wrong side, and that the boat is now on the opposite bank. To fully solve the problem, a simple tree is formed with the initial state as the root. The five possible actions (⟨1,0,1⟩, ⟨2,0,1⟩, ⟨0,1,1⟩, ⟨0,2,1⟩, and ⟨1,1,1⟩) are then subtracted from the initial state, with the result forming children nodes of the root. Any node that has more cannibals than missionaries on either bank is in an invalid state, and is therefore removed from further consideration. The valid children nodes generated would be ⟨3,2,0⟩, ⟨3,1,0⟩, and ⟨2,2,0⟩. For each of these remaining nodes, children nodes are generated by adding each of the possible action vectors. The algorithm continues alternating subtraction and addition for each level of the tree until a node is generated with the vector ⟨0,0,0⟩ as its value. This is the goal state, and the path from the root of the tree to this node represents a sequence of actions that solves the problem.

The Frame Problem

Boden describes how “finding an appropriate knowledge representation, in whatever domain, is difficult partly because of the need to avoid the frame problem.”

As originally defined by McCarthy and Hayes, the frame problem involves assuming that an action will cause only these changes, whereas it may cause those too. More generally, the frame problem arises whenever implications tacitly assumed by human thinkers are ignored by the computer because they haven’t been made explicitly.

Machine Learning’s Three Types

Boden articulates how there are three general types of learning styles:

• Supervised — “the programmer ‘trains’ the system by defining a set of desired outcomes for a range of inputs, and providing continuous feedback about whether it has achieved them.”
• Unsupervised — “the user provides no desired outcomes or error messages. Learning is driven by the principle that co-occurring features engender expectations that they will co-occur in the future. Unsupervised learning can be used to discover knowledge@
• Reinforcement — “Reinforcement learning is driven by analogues of reward and punishment: feedback messages telling the system that what it just did was good or bad.”

Human Creativity

AI helps us explain human creativity distinguishing it within three types:

• Combinational — “Familiar ideas are combined in unfamiliar ways. Examples include visual collage and scientific analogies (the heart is a pump)”
• Exploratory — “Exploits some culturally valued way of thinking…The stylistic rules are used to produce the new idea — much as English grammar generates new sentences.”
• Transformational — “A successor of exploratory creativity, usually triggered by frustration at the limits of existing style…These new ideas are deeply surprising, because they’re seemingly impossible. They’re often initially unintelligible, for they can’t be fully understood in terms of the previously accepted way of thinking.”