Author: Robert Hyatt
Date: 06:59:58 04/21/01
Go up one level in this thread
On April 20, 2001 at 06:44:09, David Rasmussen wrote: >On April 19, 2001 at 10:22:12, Uri Blass wrote: > >>> >>>What is the Enhanced Tranposition Cutoff algorithm? >>> > >Sorry, I didn't see that before. >ETC is a technique where you look at _all_ the successors of a node, to see if >it is in the hashtable. If some are, you then choose then one that tightens the >alpha-beta window the most. In most normal chess programs, you can't do this, >because you don't generate all the moves at once, but instead generate only some >moves at a time, in the hope that you will get a cutoff, before you have >generate all the moves. This too is of course only a constant time improvement, >but this constant time improvement, and the constant extra time it takes to >generate all successor hash keys at every node, makes ETC not feasible for >todays systems. Testing shows that you save 10% on average on the treesize using >ETC. The treesize grows exponentially, thus the 10% savings will also. But on >"short" timecontrols, coupled with todays "slow" hardware, which gives us >"small" trees, it isn't worth doing, in most programs. Still, an exponential >saving _will_ beat constant time savings if we think long enough. > >>>Uri >>I see that you said in a previous post: >>"For example, we would use Enhanced >>Transposition Cutoff at all nodes." >> >>You also talked about heinz scalable search so maybe I should look at his book >>to understand what you mean. >> > >I haven't read his book. But I have read all of the article preprints that I >understand the book is based on. > >>I believe that there are good ideas that can be used to get exponential >>improvement but I doubt if these ideas cannot be used for today's hardware if >>you use it in the right way. >> > >ETC is one example. There might be several others, that we don't look into, >given the hardware constraints that we are used to. > >>If you can use an idea for all the nodes then using it only for part of them in >>the right way is something to think about >> > >People that use ETC in practice, only use it at the first n plies, where the >tree is "small" so the penalty will be small. Unfortunately, so will the gain. This is backward. Screw up the move ordering at the root and see what happens to the size of the tree. Then screw it up 2-3 plies from the tips and see what happens. I'll bet you will prefer to screw it up near the tips after you run the experiment. :) Which is the point of trying ETC early in the search where the overhead is low and the potential gain is maximized...
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.