Discussion of chess software programming and technical issues.
Moderators: hgm , Rebel , chrisw
tomitank
Posts: 276 Joined: Sat Mar 04, 2017 12:24 pm
Location: Hungary
Post
by tomitank » Wed May 10, 2017 10:57 am
Hi all!
I write from Hungary, therefore sorry for my english.
I'd like to know, what's the best way to update in PVS the best score and best move?
Sample 1.
Code: Select all
if (Score > BestScore) {
if (Score > alpha) {
if (Score >= beta) {
return Score;
}
alpha = Score;
}
BestScore = Score;
BestMove = move;
}
Sample 2.
Code: Select all
if (Score > BestScore) {
BestScore = Score;
BestMove = move;
if (Score > alpha) {
if (Score >= beta) {
return Score;
}
alpha = Score;
}
}
Sample 3.
Code: Select all
if (Score > BestScore) {
BestScore = Score;
BestMove = move;
if (Score > alpha) {
alpha = Score;
if (Score >= beta) {
return Score;
}
}
}
Or another idea?
Thanks, Tamas
hgm
Posts: 27807 Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller
Post
by hgm » Wed May 10, 2017 12:04 pm
Sample 1 seems to do the least superfluous work. The difference could be immeasurably small, though.
For the benefit of multi-PV I often use this:
Code: Select all
if(score > bestScore) bestScore = score, bestMove = move;
if(score > alpha) {
if(score >= beta) return score;
alpha = bestScore;
UpdatePV(move);
if(ply == ROOT) {
PrintPV();
alpha -= multiPvMargin;
}
}
This tests for score > alpha on every move, while normally (i.e. in every node except in the root when running multi-PV) this should not be possible without increasing bestScore. (Which only very few moves do.)
Sven
Posts: 4052 Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Post
by Sven » Wed May 10, 2017 12:44 pm
tomitank wrote: Or another idea?
Sample 4
Code: Select all
if (score >= beta) {
return score;
}
if (score > bestScore) {
bestScore = score;
if (score > alpha) {
UpdatePV(move);
// bestMove is first entry of current PV
// updating alpha is not really necessary, simply pass something like Max(alpha, bestScore) to the recursive call
if (ply == 0) {
// root
PrintPV();
}
}
}
mar
Posts: 2559 Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak
Post
by mar » Wed May 10, 2017 12:53 pm
All fail soft variants are functionally equivalent, so I'm not sure what you're asking about.
Naturally you may want to exit as soon as possible, however you'll most likely do some extra work later, like
- extracting PV in PV nodes if score > alpha
- updating killers/history/TT on beta cutoff
tomitank
Posts: 276 Joined: Sat Mar 04, 2017 12:24 pm
Location: Hungary
Post
by tomitank » Mon May 15, 2017 4:52 pm
Hi!
Currently i extract PV (and the UCI best move) from the Hash.
I tried many more variation, but [Sample 1.] work for me better.
I tried this avoiding the hash bug, but it's not so good for me:
Code: Select all
if (Score > BestScore) {
if (Score > alpha) {
if (Score >= beta) {
return Score;
}
alpha = Score;
if (ply == 0) UCIBestMove = move; // best root move
}
BestScore = Score;
BestMove = move;
}
I do not know why?
I do something wrong?
With Hash Update (currently version):
Code: Select all
moves loop {
.......
if (Score > BestScore) {
if (Score > alpha) {
if (Score >= beta) {
Update Killer, History
StoreHashMove(currentMove, Score, FLAG_BETA, Depth);
return Score;
}
alpha = Score;
}
BestScore = Score;
currBestMove = currentMove;
}
}
if (alpha != OldAlpha) {
StoreHashMove(currBestMove, BestScore, FLAG_EXACT, Depth);
} else {
StoreHashMove(currBestMove, BestScore, FLAG_ALPHA, Depth);
}
Thanks, Tamas
hgm
Posts: 27807 Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller
Post
by hgm » Mon May 15, 2017 5:32 pm
I usually assign a hash slot and store the entry at the end of the node (just before Search() returns). Nothing should be probing for it in the mean time anyway. Only in the root I store after every iteration. Because in analysis mode the root never returns normally; it is always aborted, returning without hash store.
AlvaroBegue
Posts: 931 Joined: Tue Mar 09, 2010 3:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)
Post
by AlvaroBegue » Mon May 15, 2017 6:55 pm
What's the point of keeping both BestScore and alpha? In my code I only have alpha and this doesn't seem to be a problem.
Code: Select all
if (score > alpha) {
best_move = move;
alpha = score;
if (alpha >= beta)
break;
}
hgm
Posts: 27807 Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller
Post
by hgm » Mon May 15, 2017 7:17 pm
It is the difference between fail hard and fail soft. In fail soft you return bestScore, which can stay below alpha.
AlvaroBegue
Posts: 931 Joined: Tue Mar 09, 2010 3:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)
Post
by AlvaroBegue » Mon May 15, 2017 7:51 pm
hgm wrote: It is the difference between fail hard and fail soft. In fail soft you return bestScore, which can stay below alpha.
Oh, that makes sense. Thanks.
Sven
Posts: 4052 Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Post
by Sven » Mon May 15, 2017 9:05 pm
tomitank wrote: Hi!
Currently i extract PV (and the UCI best move) from the Hash.
I tried many more variation, but [Sample 1.] work for me better.
I tried this avoiding the hash bug, but it's not so good for me:
Code: Select all
if (Score > BestScore) {
if (Score > alpha) {
if (Score >= beta) {
return Score;
}
alpha = Score;
if (ply == 0) UCIBestMove = move; // best root move
}
BestScore = Score;
BestMove = move;
}
I do not know why?
I do something wrong?
Updating the best move should only happen if the new score is inside the window, i.e. alpha < Score < beta. When failing low or high there is no best move.