After a few years of complete disregard, I have been looking at game tree search algorithms recently. More specifically Tree Search in Two-Player, Zero-Sum, Deterministic, Finite State Games of Perfect Information such as Chess, Go, Checkers, Othello and Hex. And the most astonishing new development in this period I missed was that Jonathan Schaeffer, a legendary name in the obscure area of game tree search algorithms, managed to find the Min-Max value of the standard Checkers game tree.
Obviously this is of more interest to people with interest in practical ideas than airy-fairy theory because
1. It has been solved only for the 8×8 board with 12 pieces. The generalized game for a NxN board is an EXPTIME complete problem – meaning a Turing Machine has a time complexity of O(2^Polynomial(N)) to solve the min-max value for any arbitrary position. Even if the Polynomial function for Checkers happens to be the identity function, Polynomial(N) = N, its twice as hard to solve the 9×9 version than the 8×8 version and so on …
2. Several ultra-intelligent cut-offs have been applied to prune the game tree. So there is no gigantic lookup table containing all possible board states (which is estimated to be ~ 10^31). Only those branches that lead to perfect game play have been evaluated. But nothing revolutionarily better than existing cut-off algorithms has been discovered.
Among the games I am interested in – Chess and Go, the smallest one – Chess, has a state space that is ~10^9 times larger than Checkers. Not much of the Checkers brute forcing is going to be very useful there, even if Google donated all their computers to me. Its far more exciting if a pruning technique that is asymptotically better than Alpha-Beta is found than if we solved all 10-piece endgames and put in on a DVD [ To My Prof: No, that is NOT a dig at Ken Thompson Maam, he is a Googler 
]
And just in case you were wondering, the min-max value of the 8×8 Checkers tree happens to be a draw. So, the next time you are at the doleful end of a checkers game, don’t blame it on the imperfect branch, you loser.
Filed under: Computer Science, Mathematics
Ananth, there is a good IEEE paper which had an elaborate comparative analysis on various pruning methodologies – both non-heuristic and heuristic. It was published in two parts in IEEE proceeding for an international conference on Machine Learning. I stumbled upon it when I was working on improving extended Kalman Filter (which actually is a non-heuristic pruning methodology). The main focus of that analysis was on recurrent neural network, not on game trees, however. Try to get hands on that paper either in Google library or Trinity library. A search for comparative analysis of pruning techniques in the library software can help you find the exact paper.
state space larger than Chess’ state space?
One curious question: how much is Go’s (assume 8 X
@ Sundar,
Found the paper, but it talks about Pruning Algorithms for Decision Trees. Decision Trees model Boolean Functions and are simpler to deal with than Game Trees. But I can see that some of the pruning techniques discussed in the paper sound like MTD(f) or NegaScout used in classic game tree search.
> “One curious question: how much is Go’s ( assume 8 X 8 ) state space larger than Chess’ state space?”
Go is usually played on much larger sizes – 17×17 or 19×19 by humans. Chess has a branching factor of ~35 moves and average game length of ~60. Go has a branching factor of ~250 moves and average game length of ~150.
So we are talking about a state space of 10^50 (chess) versus 10^170 (19×19 Go).
For now, Go and Kickboxing are the two main sports where we can beat the shit out of the electronic monster
Go and Kickboxing … Couldn’t stop laughing (-:
Hey dude by the way……… tell me is there a flow-based scheduler algorithm implemented in a OS?? As in the process will be estimated for the runtime and memory it might take… and the algorithm will schedule the processes based on the required/average interaction required by the user from the system at that time??? Can’t get clearer than this….. was reading “Goal” and thought of this………….
P.S: Sorry for the irrelevance to the post but did not want to go through all the posts….. to find a better place..