Author: Dann Corbit
Date: 13:15:47 01/05/99
Go up one level in this thread
On January 05, 1999 at 15:20:02, Jay Scott wrote:> >On January 04, 1999 at 18:32:24, Dann Corbit wrote: >>Since this analysis is clearly fairly superficial, the most interesting part >>will be in the large ce evaluations. For instance, gambit openings are quite >>likely to show a score of +/- 100 centipawns for obvious reasons. For openings >>like this, I would not be nearly as concerned about the centipawn score as the >>win/loss percentage and how some of the greats have played it. But for >>positions which have a ce greater than 2 the results are quite interesting. >>After enough data is gathered, I will be able to perform simulated annealing on >>the database. At that time, I expect the value of analysis to improve >>exponentially. > >I assume the "simulated annealing" is some algorithm which attempts to >back up scores from leaves up through intermediate nodes without totally >obliterating the scores calculated at higher levels. How does that work? > >To me, the obvious way to analyze an opening tree is from the leaves up. >When all positions below a given node have been analyzed, you stash their >scores into a persistent hash table. Then when you analyze this node, the >search is essentially looking to see whether there's a superior alternative >to the book moves that are already analyzed. The search can take advantage >of transpositions into the already-analyzed portion of the book to return a >more knowledgable evaluation of those alternatives. > >The last search is of the root position, and it discovers, "hmm, 1. f3 is >not as strong as 1. d4." :-) When that's finished you have a fully-scored >tree, probably with many alternate suggestions that you can wade through >for interesting TN's. If you later go back and analyze some leaf node more >deeply, you may have reanalyze higher nodes as well to back the score up the >tree. > >Obviously this method is a lot harder to coordinate if you have lots of >volunteers doing the searches! What I mean by simulated annealing is very different from what most people probably imagine. First of all, it requires a tremendous number of precomputed points to even think about attempting it (otherwise, it is simply too slow). Imagine a man standing on a globe. If he jumps, he can see farther (a more distant horizon). If he jumps higher, he can see still farther. But jumping more than seven or eight feet is pretty difficult for humans. To jump 30 feet straight up without a pole may well be impossible. Chess programs face a similar difficulty. From a given position, they can only see a small sphere around the current location. It takes incredible effort to increase the size of the sphere. At some point, it becomes useless even to try because of the exponential nature of the process. But imagine a plane covered with millions of spheres. We can look at the next sphere, which can look at the next sphere, which can look at the next sphere. How might this work in a database? Suppose I have a few million analyzed points. I can look at some point, and suppose it wants to move g4. Then I can move to g4. Hopefully, g4 is already there and analyzed. If not, I can generate and analyze it. Now, I can take the new information and update our first position. Maybe from here, the analysis suggests bxh6 for the opponent. So at the same time, we extend the opponents view from that position, using the same methods. We continue this process until we reach termination (win/loss/draw). Now that we have done this, we repeat the process for every point in the database (not yet analyzed). After we have done so, it turns out that our first move, g4 was wrong! So instead we take the new suggestion and analyze that. This process can be repeated as many times as desired. Each time, we make a linear path, choosing only what appears to be the best choice. The reason I call this process simulated annealing is because of the similarity to the physical process. We start out with a large number of small crystals, and then melt them together until they become very large.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.