Authors: Danny Kopec, Shweta Shetty and Christopher Pileggi
Audience: People interested in puzzles and AI.
Reviewer: Mike James
A book with companion CD-ROM that solves AI problems - sounds just what the AI expert ordered!
But not quite.
You knew there would be a catch, didn't you?
This is a book about "toy" problems, mostly logic or combinatorial problems. The authors explain the problem and then explain the solution in fine detail. The idea is that the solutions to the problem should some how illuminate the task that AI has to solve. The solutions given are rated in terms of how close to a good human approach they are and the standard AI approach is outlined. The AI approach generally isn't described in sufficient detail. If you don't know what a depth first search or an A* algorithm is then you probably aren't going to get much out of the explanations of the AI approach.
The first chapter is a discussion about what the book is all about and what it hopes to achieve. This gives the book the feel of ongoing research rather than anything finished and authoritative.
Chapter 2 explains the idea of problems solving and uses Polya's suggested five steps for problem solving. While I am a great fan George Polya's book "How To Solve It" I have always found the heuristics more useful to humans trying to solve a problem rather than humans trying to invent an AI to solve the problem. The main reason for this is that the heuristics are generally expressed in very high level human terms - understand the problem, make a plan, carryout the plan and look back at your work. These are good ways to organize and motivate a human but very tough to translate into algorithms. If you already have intelligence then Polya's heuristics help guide its use but if you don't have intelligence then basically they don't help get you some.
In Chapter 2 we also meet the Human Window criteria which is a characterisation of how "human friendly" a solution method is. It has to fit into the capabilities of human memory and comprehension. It is an interesting idea but it is difficult to see what bearing it has on AI. An artificial intelligence need not use a human friendly algorithm. You could say that a human chess player uses a human friendly algorithm but a computer chess program doesn't. Perhaps one day AI systems will work in the same way that humans do, but for the moment the only thing a human friendly algorithm has to offer is an example of how different humans and AI systems are.
From this point the book moves on to consider ten problems in turn. The problems are:
- The Missionaries and Cannibals Problem
- The 12 Coins Problem
- The Red Donkey Puzzle
- The 15 Puzzle
- The Knight's Tour Problem
- The Monty Hall Problem
- Rubik's Cube
- The Prisoner's Dilemma
Some of these problems are well known and have been the subject of simple AI approaches usually involving search with a heuristic to speed things up and perhaps some automated logic and planning. In each case the problem is described and some sort of graphical representation is presented. Then the possible approaches are discuses and the best human solution found. This is then evaluated in terms of the human window idea. The best machine solution is then described in very high level terms with no attempt to explain how the machine algorithm works. You also are given references to places where you can try the puzzles out on line.
The descriptions of how to solve the problems are fairly clear and if you work though the problem with the descriptions you should see how they work. What is lacking, however, is any "meta" analysis of what is going on. For example, in the solution of the 15 puzzle, the one where you have some jumbled tiles with numbers on them that you have to slide around to get them back in order, the description of the solution fails to mention that what you are looking for are a set of operators that decouple the tile movement. If you can find such a set of operators then you can move each tile into position without messing up the positions of the ones you have already put into place. There is no real attempt to see any "bigger frameworks" in operation that the solutions are special cases of.
There is no real code given in the book but there is a CDROM bound into the back that contains the code for programs that solve the problems. These are in a range of languages - Python, Prolog, Java and Picat.
The selection of problems is interesting but what the Monty Hall problem is doing in the list is a mystery as it isn't so much a problem as applied probability theory. The same is true of the prisoner's dilemma which is applied game theory. These two chapters seem to be just about explaining the theory of the situation than being about problem solving.
The book closes with some miscellaneous problems and a final chapter on the possibility of a theory of problem solving.
Overall this book reads more like a cross between a puzzle solving book, a work of philosophy and something on psychology. There is some AI in it but this is mostly on the CD-ROM.
If you are setting out to build programs to solve any of the problems discussed in the book then you might find it useful to give you an insight into it and some solutions. If you were hoping for something that would teach you about AI then you need to find a different book.