Author: Dieter Buerssner
Date: 12:48:26 09/02/01
Go up one level in this thread
On September 02, 2001 at 12:52:21, Georg v. Zimmermann wrote: >How do you prune window dependent ? Isn't (almost) all pruning window dependent? With null move, you compare with beta. With futility pruning you compare with alpha. >>Also, when adjusting alpha to a lower bound value, this value is >>actually outside of the window. So, say the value was actually exact, one ends >>up without a PV. Also, it is not really clear, what sort of node this is. It was >>a lower bound earlier, now it an upper bound that is inside of the original >>search window, but outside of the window with the adjusted bounds. >> > >I don't follow. >Only if the score was from a fail high I adjust alpha to be at least as good as >the hashscore. It must be within the window since if it was > beta the hash >lookup would have even produced a fail high. You have a lower bound score in the hash with enough depth. Say the score is +10 (which means it was shown to be >= +10 in the earlier search). If you adjust alpha to 10, and the exact score of this node would actually be +10 (the "=" in ">="), this score will not be inside the new (adjusted) alpha-beta window, because the bounds are not inside the window (at least with the normal formulation of alpha-beta search, that I am used to). That a lower bound score is actually an exact score (but not proved yet to be one) can happen quite easily due to transpositions. Say a capture sequence, where it does not matter with which piece you capture first. What I mean about the additional inconsistencies added by adjusting the bounds due to window dependent pruning may be depicted by the following example: A position was searched to depth 10 with beta=0. The null move fails high. It can happen, that if you would search this with no null move, that it really would not fail high. It might be a score of -30 or something. But you don't know this yet. You store 0 as lower bound score in the hash table. You revisit this node at depth 10. Say this time with a window of (-50,50); so beta is 50. Now you adjust alpha to 0. Because of the higher beta, the null move shall not give a cutoff this time. You search all moves with the window (0,50). And you can get a fail low, because the former null move score was wrong. Without adjusting the bound you may get a perfect exact score (-30) and a PV. With adjusting, you can end up with a too high score, that may find its way back to the root, and perhaps a real problem is only seen at one higher depth. All this said, I adjust the bounds. But I don't see a big difference by this. Regards, Dieter
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.