Fail-soft search but Fail-hard transposition table look up?

[kubpica]

Hi, I noticed you are using the Fail-soft version of Alpha-beta algorithm.
In search.go there is this comment:

// Return the best score, which is alpha.
  return bestScore

But I think that "bestScore" is not always alpha here, in Fail-soft Alpha-beta it can be lower than alpha (for so called "All-Nodes" where every move fails-low). Fail-soft is supposed to be optimization of alphabeta, in fail-soft version you don't clamp returned values to alpha/beta. But I noticed that you do clamp values returned from transposition table to alpha/beta in case of AlphaFlag/BetaFlag:

if entry.Flag == ExactFlag {
  adjustedScore = score
}
if entry.Flag == AlphaFlag && score <= alpha {
  adjustedScore = alpha
}
if entry.Flag == BetaFlag && score >= beta {
  adjustedScore = beta
}

Shoudn't you just always do adjustedScore = score ? I checked source code of Stockfish and I think they don't clamp values returned from tt.

Another interesting topic is whether we should store "bestMove" for "All-Nodes" (AlphaFlag) or not. I noticed that you do store it, but Stockfish don't (they store "MOVE_NONE" in case of AlphaFlag).
For more details look here: https://stackoverflow.com/questions/72252975/transposition-table-look-up-for-fail-hard-vs-fail-soft-alpha-beta-how-do-they-d

I am new to this stuff so I may be wrong, but it's very interesting, what you think?

[deanmchris]

Hi @kubpica,

You're correct; I am using the fail soft version of the alpha-beta algorithm. That comment should be corrected; thanks for the heads-up! For the rest of your questions I'm going to try to answer as best I can although I have to be honest that it's been a while since I looked at my own code, so my analysis will be going off of quickly scanning back through things.

As for the transposition table, I believe I'm using alpha and beta instead of score because I found through testing that that approach worked best. I have to confess I don't remember why though. I'd have to spend some time going back through my notes to see if I could find anything. I imagine Stockfish is doing the same because they found, as you noted, that not clamping values worked best. As nice as it would be if chess programming was an exact science, that isn't always the case, and often times what works best for one engine might not work well at all in another. That's why always testing things yourself and not just copying-and-pasting is so important!

As for storing a best move, scanning back through my code and if I remember correctly, although I'm storing a best move at fail-low nodes, it's never actually used. If you look back at the search code, whenever I stored a best-move at a fail-low node, the score for that TT entry will also be lower than alpha. And in the transposition table code, if we ever visit this entry again, it's stored score will be less than alpha, and since it is an alpha node we're going to be ending the search early, returning that score and never using the best move.

It's been a while since I've worked with the code as I've said, but in hindsight right now, I don't think I had a good reason for doing things the way I described above, and I should be explicit in my code about not storing best moves for nodes that failed low, since clearly no move searched was good enough to raise alpha.

I appreciate your comment a lot! In the coming months I'm hopefully going to get back in the mood to re-write Blunder from scratch, improving upon some past mistakes, so whenever I revisit this particular section of and if you're still interested, I'll be sure to try to give a better answer!

[kubpica]

@algerbrex
Okay that makes sense that for some engines fail-soft look up may work better while for others it will be fail-hard (clamping stored values to alpha/beta). I was trying to understand transposition tables (instead of just copying-and-pasting ;) ) and I was confused when I saw different implementations of tt look up method. At first I tought the difference depends on whether we are using fail-soft or fail-hard alpha-beta but then I was even more confused when I saw implementations that used "fail-hard search" but "fail-soft transposition table" and vice versa.

As for storing a best move, correct me if I'm wrong, but I think alpha and beta may be different when we encounter the same position (but maybe in different way), so it's not guaranteed that stored score will always be less than alpha. So I think that it may happen that storedScore will be bigger than new-alpha and then ttMove ("bestMove") will be used. If alpha was always the same for the same entry why would we need to check score <= alpha in tt look up? Also using your logic why would we store "bestMove" for BetaFlag, if you assume we would always end search early? I found some old discussion about this: https://groups.google.com/g/rec.games.chess.computer/c/p8GbiiLjp0o They claim there that storing "bestMove" for "All-Nodes" (AlphaFlag) resulted in faster search but it may not necessery mean stronger play because they where woried about search instability.

Thank you very much for your response! I am eager to hear your conclusions as you redo this part of engine. I will check what works best in my draughts engine so I can also share if I find anything interesting ;)

[tissatussa]

hi, maybe i can inspire.

i follow this Issue with interest .. i'm a programmer myself, but not yet of any engine .. i'm a bit familiar with the terms you use here, like alpha beta TT etc .. overall i like the way you help eachother by describing technical issues in detail by clear wording ! While reading this Issue i have these thoughts :

• keep things simple.
• use special chess positions to test any new code ? = design / find such positions for any case ?
• one thing i learned at school : always write comments in your code, also mentioning things that did NOT work and why, because later you might see that code again and think "something was wrong .. i found info on it and did tests, but i don't remember .."
• rewriting things from scratch may seem unnecessary, but indeed useful and often the only way to correct code parts.