hgm wrote:It all depends on what 'level_below_best' is, and how you update it. As I pointed out, the very deep line you showed is definitely searching a branch that is totally irrelevant for the root score, and thus should have been pruned by alpha-beta. So either your alpha-beta is not correctly implemeted (e.g. alpha and beta wrongly updated), or your eval scores must be very wrong (which I don't expect). Normally gaining Knight for Pawn should be sufficient to cause a beta cutoff, but it obviously doesn't.
As long as you don't fix that, none of the refinements suggested in the above posts will have much impact. Move ordering is only helpful when alpha-beta works properly...
This is a better description of my main search function and I hope it describes what I mean by the best score at the level below. It shows what variables I have to play with ie score and BestScore. It doesn't include the stand pat score as we're trying to decide if my alpha beta stuff is ok - I think it is but this should explain it.
findBestMove( level, max_level ) {
bestScore[level] = whites_turn ? -2000000 : 2000000
get moves in MVV/LVA order ie captures first
// leaf node
if level > max_level and no_captures_available
return evaluateBoard();
// try each move
for each move
if level <= max_level or capture_move
// try move
putOnMove()
swapSides()
score = findBestMove( level+1, max_level )
swapSides()
takeOffMove()
// minmax
if whites_turn and score>bestScore[level] or blacks_turn and score<bestScore[level]
bestScore[level] = score
bestMove[level] = move
// alpha beta cut
if whites_turn and score>=bestScore[level -1] or blacks_turn and score<=bestScore[level -1]
return score
return bestScore[level]
Does this look right?
What score is returned if there are no captures? It looks like you only return -INF in that case unless it happens to reach the maximum level. That is wrong too.
I also see that if all captures are losing, you have not choice but to return a losing score which is also wrong.
You can correct some of this by first setting the bestScore at the new level to the same score as the evaluation, not -INF. So if all captures are losing this would become the default score (which is how all modern programs do it) and if there are NO captures this would be returned.
I'm not positive, but I think the final fix to your code is to set bestScore not to -INF but to the the current evaluation OR the bestScore from 2 levels previously, whichever is better.
This does not apply to the main search however which is no doubt also wrong. In the main search set the bestScore for this level to the -INF or the best from level-2 which is the same as the best score from level-2 i.e. :
bestScore[level] = bestScore[level-2]
Watch out for level < 0, in which case you should use -INF (-200000 for you.)
hgm wrote:This is no good. For one, it only allows stand pat when there are no captures, so it would not even return the correct score. Because if there are only losing captures it would think it has to play the least bad of those.
I am not used to alpha-beta in another formulation than negamax, but what you show here looks fishy. I don't see how it would realize deep cutoffs, because the score t the current level gets better than that at level-3, level-5 etc. To avoid having to test for those explicitly, one normally initializes what you call bestScore[level] to bestScore[level-2] rather than -INF.
He is using a very non-standard alpha/beta framework here. The negamax framework confuses some people even though I think it's a major simplification because it avoid having to constantly test for who is the max and who is the min and what alpha and beta really mean. I think it's the -search( -beta, -alpha) stuff that confuses people, all of those negatives as well as reversing the position of alpha and beta is confusing at first when first trying to wrap your head around alpha/beta, but it's even more confusing trying to deal with it inside the search routine by having 2 cases for everything.
Don wrote:What score is returned if there are no captures? It looks like you only return -INF in that case unless it happens to reach the maximum level. That is wrong too.
If the level is > max_level and there are no captures then it will just treat that as a leaf node, evaluate the board and return that score. If the level is <= max_level then it should just put on every move and recurse up a level and eventually return a score from the recursive call.
The idea of initialising bestScore[level] = bestScore[level-2] is much better than my approach. I'll do this right now guys.
if level > max_level
score = evaluateBoard();
// minmax
if whites_turn and score>bestScore[level] or blacks_turn and score<bestScore[level]
bestScore[level] = score
bestMove[level] = move
// alpha beta cut
if whites_turn and score>=bestScore[level -1] or blacks_turn and score<=bestScore[level -1]
return score
Don wrote:It does not look right to me. You are are looking at previous levels to get the equivalent of beta which is ok to do, but it's like you are resetting alpha to -INF at each level. So your program is going to be orders of magnitude slower. Assuming I read this right.
I understand alpha beta cut off as a process but I have no idea what you mean when you refer to alpha and beta as variables. What is -INF? is this the initial value I'm setting it to. Is there a simple explanation of these variables ie is alpha just the current score and beta the current best score. Can I change this code to use your alpha and beta values or do I need to completely rewrite. I have tried reading the chessprogramming wiki pages but they tend to explain each complex process by using other complex processes and I soon give up
I have no doubt that my process can be sped up but is it actually wrong?
Alpha is our best score, beta is the opponents best score.
If a value is higher than alpha, this that move was a good move for us, better than our last best move.
If a value is higher than beta, then that move was brilliant. In fact, so brilliant that it has exceeded the opponents best score. We might as well return beta so that we can prove to our opponent this was a brilliant move for us. However, this value is negated, so that a high value for us is a low value for them, so that move does not improve alpha.
bob wrote:(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.
That's interesting ! I naively used SEE ordering for captures and promotions, whether in the search or in the qsearch. Does it really make a big difference on the qsearch ?
Use see() for move ordering is perfectly legit, but if your tree is exploding I would suspect that it is wrong.
I think most program uses see only for pruning bad moves and it's understood that MVVLVA is slightly superior to see() for move ordering, not by much but by a little. This is definitely counter-intuitive. But it's a huge win to pruning losing captures in quies.
So you're saying that MVV/LVA sort is better than SEE sort, for the purpose of sorting captures and promotions, in the qsearch *and* in the search ?
That's one thing to test on my todo list !
This discussion brings to mind my memories from nearly forty years ago when I first started some serious thinking about coding a chess program. At that time, long before the Internet, the only source I had for writing a search came from old textbooks which always talked about viewing all evaluations and scores solely from White's point of view. This was confusing to me and I think that's also the cause of some of your difficulties.
The much better approach is to interpret all scores form the point of view of the player on the move. In my code, the structure describing a position has two components of type Color; these are good (for the player on the move) and evil (for the other player). When going up or down a ply, the values of the two are interchanged.
This really simplifies things when compared with the old, old textbook presentations of two player search!
bob wrote:(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.
That's interesting ! I naively used SEE ordering for captures and promotions, whether in the search or in the qsearch. Does it really make a big difference on the qsearch ?
Use see() for move ordering is perfectly legit, but if your tree is exploding I would suspect that it is wrong.
I think most program uses see only for pruning bad moves and it's understood that MVVLVA is slightly superior to see() for move ordering, not by much but by a little. This is definitely counter-intuitive. But it's a huge win to pruning losing captures in quies.
So you're saying that MVV/LVA sort is better than SEE sort, for the purpose of sorting captures and promotions, in the qsearch *and* in the search ?
That's one thing to test on my todo list !
Yes, but the difference is small. Same for main search and quies. In the main search you want to put losing captures at least after killers, and some put them even later.
sje wrote:
The much better approach is to interpret all scores form the point of view of the player on the move. In my code, the structure describing a position has two components of type Color; these are good (for the player on the move) and evil (for the other player). When going up or down a ply, the values of the two are interchanged.
This really simplifies things when compared with the old, old textbook presentations of two player search!
I actually found it much cleaner, in the evaluation, to do the evaluation entirely from white's point of view. Then, in the end, flip the sign if it is on fact black to move.
I originally wrote Jazz' evaluation entirely side-to-move neutral, and I liked it at first. But then I started adding things like king-safety and passer evaluation, and then you're dealing with pawns and suddenly you're not looking at "side to move" and "other side", but "white" and "black". It became very cumbersome, and I decided to save myself further headaches by going for "always from white's point of view" inside the evaluation.
There is an exception though: end-game evaluation functions internally score things from the point of view of the "attacker" and then flip the sign before returning if white is the "defender" (and then the sign gets flipped again later when it's black to move).
It's probably not the most efficient, but being able to read my own code is an important consideration too.
