Exact TT scores and alpha/beta

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4470
Joined: Tue Feb 28, 2012 10:56 pm

Re: Exact TT scores and alpha/beta

Post by syzygy » Fri Nov 03, 2017 6:33 pm

AlvaroBegue wrote:
op12no2 wrote:But I notice that that seems to be wrong - and at a PV node one should only return an exact score if it lies within the current alpha/beta window.
No, the logic is not quite that. The implication goes only one way: If he minimax score of the node lies within the current alpha/beta window, then the function must return it. Otherwise, it only needs to return something beta or above if the minimax score is beta or above, and something alpha or lower if the minimax score is alpha or lower.
I don't think the last sentence is fully accurate. If the minimax score is >= beta, then the value returned must indeed be >= beta, but it should also be <= minimax_score. This is because the value returned will normally be stored in the TT as an upper or lower bound for the parent node. To replace alpha or beta as a valid bound on minimax_score, the value returned should lie between alpha or beta and minimax_score.

AlvaroBegue
Posts: 922
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Exact TT scores and alpha/beta

Post by AlvaroBegue » Fri Nov 03, 2017 7:38 pm

syzygy wrote:
AlvaroBegue wrote:
op12no2 wrote:But I notice that that seems to be wrong - and at a PV node one should only return an exact score if it lies within the current alpha/beta window.
No, the logic is not quite that. The implication goes only one way: If he minimax score of the node lies within the current alpha/beta window, then the function must return it. Otherwise, it only needs to return something beta or above if the minimax score is beta or above, and something alpha or lower if the minimax score is alpha or lower.
I don't think the last sentence is fully accurate. If the minimax score is >= beta, then the value returned must indeed be >= beta, but it should also be <= minimax_score. This is because the value returned will normally be stored in the TT as an upper or lower bound for the parent node. To replace alpha or beta as a valid bound on minimax_score, the value returned should lie between alpha or beta and minimax_score.
Correct. Sorry for my imprecise language (or my sloppy thinking).

op12no2
Posts: 349
Joined: Tue Feb 04, 2014 11:25 am
Location: Mumbles, Wales, UK.
Full name: Colin Jenkins
Contact:

Re: Exact TT scores and alpha/beta

Post by op12no2 » Sat Nov 04, 2017 9:40 am

Yes, sorry chaps, ignore me, >= beta makes sense and that's what I do - no idea what went on in my mind for that message yesterday :)

voyagerOne
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: Exact TT scores and alpha/beta

Post by voyagerOne » Sun Nov 05, 2017 6:11 pm

Strangely doing PV TT-cutoffs in Stockfish causes a huge regression.

User avatar
Evert
Posts: 2924
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Exact TT scores and alpha/beta

Post by Evert » Sun Nov 05, 2017 8:36 pm

voyagerOne wrote:Strangely doing PV TT-cutoffs in Stockfish causes a huge regression.
You make the cut-off under the assumption that searching the node again would give you the same result as you found before, thus wasting time. Stockfish makes pruning decisions based on more than just alpha-beta bounds and depth, so you need to test more than just alpha-beta bounds and depth to decide to accept a cut-off or not. Or you just don't accept it and avoid the complication.

voyagerOne
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: Exact TT scores and alpha/beta

Post by voyagerOne » Sun Nov 05, 2017 8:55 pm

Evert wrote:
voyagerOne wrote:Strangely doing PV TT-cutoffs in Stockfish causes a huge regression.
You make the cut-off under the assumption that searching the node again would give you the same result as you found before, thus wasting time. Stockfish makes pruning decisions based on more than just alpha-beta bounds and depth, so you need to test more than just alpha-beta bounds and depth to decide to accept a cut-off or not. Or you just don't accept it and avoid the complication.
Well said!

User avatar
hgm
Posts: 23991
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Exact TT scores and alpha/beta

Post by hgm » Sun Nov 05, 2017 8:58 pm

What else is there, other than the search window and the depth? How wide the window is?

Henk
Posts: 5883
Joined: Mon May 27, 2013 8:31 am

Re: Exact TT scores and alpha/beta

Post by Henk » Sun Nov 05, 2017 9:17 pm

Lazy evaluation. Adding random values to insure it is not playing same game.

voyagerOne
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: Exact TT scores and alpha/beta

Post by voyagerOne » Sun Nov 05, 2017 9:21 pm

Another test I did was to see if we can safely do an exact TT-Cutoff in QS-Search.

Again it regressed pretty bad..

Stan Arts
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: Exact TT scores and alpha/beta

Post by Stan Arts » Sun Nov 05, 2017 9:27 pm

hgm wrote:What else is there, other than the search window and the depth? How wide the window is?
One issue of search with agressive reductions and such is that score becomes more accurate the more often you research a node. For example because hashtable moves are not reduced.

In Nemeton I deliberately close down the root window completely after the first move was searched. I used to have it open 1/6th pawn or so to avoid annoying researches when flipflopping between close moves but the annoying research on any fail high actually increases quality of play.. And Nemeton barely even reduces. I'm sure this effect is much worse in other engines.

Post Reply