Author: Chris Whittington
Date: 07:20:58 10/23/97
Go up one level in this thread
On October 23, 1997 at 07:46:07, jean-christophe WEILL wrote: >On October 23, 1997 at 02:43:12, Reinhold Gellner wrote: > >>Doing a zero-window search, fail high moves have to be re-searched. >>Usually I do it with >> >>actual_value = -re_search( -beta, -actual_value ); >> >>However, as extensions or just move ordering changes, the re_search is >>not neccessarily the same and may result in a fail low! That is, >>actual_value is now below the former actual_value but >= alpha. >> >>I think this is a common problem. I have three solutions: >> >>1. ignore this fail low at all >>2. do another re_search: actual_value = -re_search( -actual_value, >>-alpha) >>3. do the initial re_search an open window: >> actual_value = - re_search( -beta, -alpha ); >> >>ad 1) this version may be dangerous in blitz games and of no importance >>in tournament games, resulting in a speed up. > >.Sometimes it may help you to lose games . Not only blitz one ! >if the fail low occurs just near the root. > This behaviour is described in my thesis and much of the time this >is a result of a heuristic cut-off(or extensions) which depends on the >alpha-beta values. Snap ! Any forward pruning, whether by knowledge, or null-move, either dependant on alpha and beta can cause this. We had this problem on CSTal last week. CSTal had an attack, had to choose between giving check (which lost) or running away with a knight (which was ok). The check move Ng2+was refuted by a particular king move Ke1e2, any other king move (Ke1d2 was available) lost. So the search went: Ng2+ Ke2 nullmove, expand nodes from here, and the effect was that the shallow nullmove search 'refuted' Ke2. Note Ke2 was objectively a refuting reply. Search then tried (after Ng2+), Kd2. Kd2 is a disaster. So search comes back from Ng2+ with a fail high, this move looks great because of the null move refuation of Ke2. Now we try again with a larger window. This time the null move doesn't get tried (the test shall_we_do_a_null_move comes back NO). And the search sees that Ng2+ Ke2 is bad for us, so we fail low :( CSTal then rejects Ng2+ and goes back to preferring some other earlier move. The next iteration it does the same thing. The next iteration the same thing again. The next iteration it is running out of time, does the same thing again, but the time controller decides to stop the search after the fai-high for Ng2+, but before the ensuing fail-low. So, because the search times out during a critical window, CSTal actually decides to play Ng2+ and loses of course :( Merde ! as they say in Paris :) Chris > > > >> >>ad 2) the second search may now fail high again, or even oscillate, >>resulting in an eternal loop. > >> >>ad 3) this safe approach seems to significantly increase the effective >>branching factor. >> > >When you extend the window, normally the transposition table value >should reduce it at the childs node ! Giving you no benefits for window >extension. But that is the good thing to do with some special flag >preventing the transposition table effect. This saves games even if >this also slow down your program a little bit. > >BTW in 1), everyone should check its code to know which of the move >is chosen as the best move, especially if you are at the root. > > >JC
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.