Update Best Score and Best Move

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Update Best Score and Best Move

Post by tomitank » Wed May 10, 2017 8: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

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

Re: Update Best Score and Best Move

Post by hgm » Wed May 10, 2017 10:04 am

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: 3948
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Update Best Score and Best Move

Post by Sven » Wed May 10, 2017 10:44 am

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: 2298
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Update Best Score and Best Move

Post by mar » Wed May 10, 2017 10:53 am

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: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Update Best Score and Best Move

Post by tomitank » Mon May 15, 2017 2: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

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

Re: Update Best Score and Best Move

Post by hgm » Mon May 15, 2017 3: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: 927
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Update Best Score and Best Move

Post by AlvaroBegue » Mon May 15, 2017 4: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;
    }

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

Re: Update Best Score and Best Move

Post by hgm » Mon May 15, 2017 5: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: 927
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Update Best Score and Best Move

Post by AlvaroBegue » Mon May 15, 2017 5: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: 3948
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Update Best Score and Best Move

Post by Sven » Mon May 15, 2017 7: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.

Post Reply