John L Jerz Website II Copyright (c) 2013
Chess-playing Programs and the Problem of Complexity (Newell, Shaw, Simon, 1958)
Home
Current Interest
Page Title

 
JLJ - We see here the continuing desire to reduce computer chess to analysis, and the "branching tree" seems to be the point where development stalls. How do we "decide" to expand a branch of the tree, versus not expanding it? It seems that we need an information model and a strategy - perhaps a plan will emerge from "groping" efforts which might be a necessity because the interlocking forces of the game pieces do not resolve in a clear, easy way to allow us to make definite predictions about future states of the gameboard. Dynamic complexity will stall all efforts to proceed in computer chess. A heuristic which acknowledges the complexity present on the gameboard and allows one to determine safe postponements of tree-branch expansion has promise, I feel. 
 
Let's see how very smart men Newell, Shaw and Simon visualize the problem in 1958 and what they offer as a solution to computer chess and the dynamic complexity present on the gameboard.
 
I feel that they lose sight of "joint action" when they simplify to "minimaxing" - structures are created by the (joint) activities of agents and (at the same time) the activities of human agents are constituted by existing structures. Chess is a social game - this is social science. Nothing is mentioned of the power of the pieces, or of constraints, or of global mobility, or of good and bad pieces. Sustainability is not addressed, neither is requisite variety. A strategy is not discussed for maneuver in the presence of uncertainty and resistance, adaptive capacity is apparently not a necessity, and diagnostic tests have no apparent usefulness. There is no need to stress-test the position to measure resilience. Where do we think, by questioning the predicted consequences? How is the actual thinking performed, or the machine-based substitute? Where is it that we actually "play" the game of chess? We simply have a procedure which is supposed to "work". Nothing is explained - we are no wiser.

p.1 Man can solve problems without knowing how he solves them.

[JLJ - Man determines how to "go on", which might involve just a reflex action.]

p.1 Chess is the intellectual game par excellence.
 
p.2 If one could devise a successful chess machine, one would seem to have penetrated to the core of human intellectual endeavor.
[JLJ - I disagree. There might be more than one way to "play" chess on a machine - perhaps a way duplicating the human method in addition to some other way which develops adaptive capacity, but which is more mechanical in nature and less strategic.]
p.2 Now there might have been a trick - one might have discovered some-thing... a device quite different from humans in its methods, but supremely effective in its way, and perhaps very simple. Such a device might play excellent chess, but would fail to further our understanding of human intellectual processes. Such a prize, of course, would be worthy of discovery in its own right, but there appears to be nothing of this sort in sight.
[JLJ - It is my opinion that "null move pruning" methods are this exact sort of example.]
p.4 How can we construct mechanisms that will show comparable complexity in their behavior?
 
p.7 chess is a finite game. There is only a finite number of positions, each of which admits a finite number of alternative moves. The rules of chess assure that any play will terminate: that eventually a position will be reached that is win, loss, or draw. Thus chess can be completely described as a branching tree
 
p.16 the best evidence suggests that a human player considers less than 100 positions in the analysis of a move
[JLJ - Perhaps humans have an inborn intuitive sense of sustainability.]
 p.16 In a sense, the machine barely glanced at each position it evaluated.
 
p.19 Any particular difficulty is removable
 
p.19 Every increase in sophistication of performance is paid for by an increase in the complexity of the program.
 
p.20 The point we wish to make is... that selectivity is a very powerful device and speed a very weak device for improving the performance of complex programs.
 
p.21 The significant feature of chess is the exponential growth of positions to be considered with depth of analysis... It is clear that we could afford to pay an apparently high computing cost per position to achieve this selectivity.
[JLJ - Perhaps we should think in terms of constructing scenarios. The future is uncertain and will likely remain so, whatever you do.]
 p.25 What kind of game the program will play clearly depends on what goals are available to it and chosen by it for any particular move.
 
p.26 A generator proposes; the analysis procedure disposes.
[JLJ - The analysis procedure should not dispose, but rather postpone until later - a line which is initially unpromising might reverse and become promising. Time constraints may allow such unpromising lines to be more thoroughly investigated, especially if there are signs of instability detected early. Perhaps our analysis procedure "supposes", and selects for further investigation the lines which catch our attention. ]
p.34 This analysis procedure is not a simple one, either conceptually or technically.
[JLJ - ...hinting that dynamic complexity is not easily reduced.]
 p.47 We wish not only to have the program make good moves, but to do so for the right reasons... The existing program is unable to balance material against positional advantage.
[JLJ - Well, maybe this indicates that your approach is not yet complete.]
 p.48 The program we have been describing is extremely complicated.
[JLJ - Well, that is because you don't have a strategy. Patch on top of patch on top of patch gets complicated.]
 p.51-52 We believe that any information processing system - a human, a computer, or any other - that plays chess successfully will use heuristics similar to those used by humans.
[JLJ - Not necessarily.]
 p.52 we are arguing that for tasks that could not be performed at all without very great selectivity - and chess is certainly one of these - the main goal of the program must be to achieve this selection.
[JLJ - ...yet Weick tells us that many of the positions we face are equivocal - they cannot be resolved into courses of action using the information we presently have - we must act and then interpret the results that emerge from that action.]