| Games, Puzzles, and Computation |
|
Author: Robert A. Hearn & Erik D. Demaine Author: Robert A. Hearn & Erik D. Demaine This is a book that you might buy by mistake because it seems to be about games and puzzles - it is but not in the way that you might think. It puts forward a way of approaching the analysis of games that was invented by the authors as part of a PhD thesis. The idea is that you can formulate any game in terms of a new computational framework called constraint logic. This is an unfortunate choice of names because there already is a standard and different interpretation of "constraint logic" in computer science and this might well add to the confusion. The point of formulating games in this new way is to more easily prove the computational class that the game falls into. The book and the book jacket makes this seem an appealing task by describing it as a way of discovering which games are hard and why. The book doesn't really deliver on this level because the results aren't informal but very formal. You don't discover what makes a particular game good to play or have any real idea as to what is going on. 
As this approach originates with the authors, and it hasn't as yet exactly become mainstream, you would think that this was their big chance to communicate their ideas to a wider audience. Sadly in this the book fails. The authors spend a great deal of time discussing what is to come and their intentions. So much so that you eventually start to really want them to just get on with it. However, when they do get on with it they fail to explain the ideas clearly. The idea of a constraint graph seems fairly easy at first - it's a directed graph with a minimum inflow value specified on each node. Each arc carries a flow of 1 or 2 and the inward directed arcs have to sum to more than the minimum inflow value. This restricts the directions that the arcs can be set if you want to satisfy the constraint. With this description you should now be able to understand the definitions and examples given in the book. Without it you will have to work quite hard. The connection between a constraint graph and computation is that it isn't difficult to show that some node configurations behave like "and" gates and some like "or" gates. You can then put these together to build more complex "gadgets" and these can be assembled into more complex systems. You can then go on to prove the computational class of each type of graph produced using different gadgets. What has this got to do with games? The answer is that you can represent most of the standard zero. one, two and more person games as constraint graphs. The problem is that how this is done isn't actually made clear. The idea seems to be that you have to identify sequences of moves that have the same properties as the basic gadgets and, or and so on in a given class of graph. This is explained, not very well, by a set of examples. At the end of the day the reader really has no choice but to invent the method for themselves. I gave up at this point with more questions about the validity of the methodology then answers. For example, once you have demonstrated a that some moves correspond to a few gadgets you can conclude that the game needs at least these gadgets. From here you can argue that the complexity is at least the complexity of the corresponding constraint graph, but you have not proved that there are no more complex gadgets present in the game and so the complexity might be greater. Clearly there is some reason why identifying a particular set of basis gadgets is sufficient but I didn't have the time nor inclination to work through the ideas any further. This book simply doesn't explain the ideas it contains. They might be useful or they might not. The only thing that is obvious is that constraint graphs are an interesting and fun way of describing computation. If the authors really expect their idea to have some influence then they need to find a better way of explaining their new ideas - this book just doesn't deliver on the promise.
|
|||
| Last Updated ( Monday, 23 May 2011 ) |