mtd(f) idea

[jwes]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

[bob]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

It is not so simple. You start off by proving that the "best move" is inside some relatively wide window. But you are not sure which is actually the best move. As you raise alpha, fewer and fewer moves are good enough to become "best" until you hit just one, if you are lucky. In reality you will jump alpha over the true score and now all moves fail low. How narrow must the window be before you decide that you are willing to accept the best move returned by the search, even though others might actually be slightly better (by whatever amount you are under the true lower bound)???

I'm not willing to accept even 5 centipawns worse, because if I let my score drop by 5 centipawns every move, after only 20 moves, I have given up a whole pawn (I will say more on this in a week or two after crafty 23.1 is released, as I found an interesting change in the time overflow code that is directly related to this idea). In any case, it is almost as hard to get within 5 as it is to get within 1, and I'm not willing to give up 5.

[jwes]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

It is not so simple. You start off by proving that the "best move" is inside some relatively wide window. But you are not sure which is actually the best move. As you raise alpha, fewer and fewer moves are good enough to become "best" until you hit just one, if you are lucky.

If one move is significdantly better than all the others, won't it be likely to go very quickly, e.g. what crafty calls an "easy move" should take only one zero-window search per iteration.

In reality you will jump alpha over the true score and now all moves fail low. How narrow must the window be before you decide that you are willing to accept the best move returned by the search, even though others might actually be slightly better (by whatever amount you are under the true lower bound)???

That depends on your evaluation. How different do two scores need to be befor you can say they are significantly different? Or how much score would you be willing to give up for an extra ply of depth?

I'm not willing to accept even 5 centipawns worse, because if I let my score drop by 5 centipawns every move, after only 20 moves, I have given up a whole pawn (I will say more on this in a week or two after crafty 23.1 is released, as I found an interesting change in the time overflow code that is directly related to this idea). In any case, it is almost as hard to get within 5 as it is to get within 1, and I'm not willing to give up 5.

[bob]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

It is not so simple. You start off by proving that the "best move" is inside some relatively wide window. But you are not sure which is actually the best move. As you raise alpha, fewer and fewer moves are good enough to become "best" until you hit just one, if you are lucky.

If one move is significdantly better than all the others, won't it be likely to go very quickly, e.g. what crafty calls an "easy move" should take only one zero-window search per iteration.

It is still not so simple, as I said. An "easy move" can still see a significant score drop, where you first think you are winning a piece, but later realize the score is worse than that, but the move still has to be played. There is no way to know one move is significantly better without doing the search. And with MTD(f), you have to do several. You could try searching all but the "best" move to a lowered window and they all fail low, you now have a measurable "gap" between the "best" and the "rest". But you still need a PV. And that still requires searching until the exact path is found by failing low on N, N+1, and then failing high on N-1, N.

In reality you will jump alpha over the true score and now all moves fail low. How narrow must the window be before you decide that you are willing to accept the best move returned by the search, even though others might actually be slightly better (by whatever amount you are under the true lower bound)???

That depends on your evaluation. How different do two scores need to be befor you can say they are significantly different? Or how much score would you be willing to give up for an extra ply of depth?

I am not willing to give up any actual score to go deeper. That is exactly the opposite of what I want to do, because if you give up that simply .05, it only takes 20 iterations for that to turn into a whole pawn you gave up. I don't need to do an extra ply just to lose a pawn.

I'm not willing to accept even 5 centipawns worse, because if I let my score drop by 5 centipawns every move, after only 20 moves, I have given up a whole pawn (I will say more on this in a week or two after crafty 23.1 is released, as I found an interesting change in the time overflow code that is directly related to this idea). In any case, it is almost as hard to get within 5 as it is to get within 1, and I'm not willing to give up 5.

[jwes]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

It is not so simple. You start off by proving that the "best move" is inside some relatively wide window. But you are not sure which is actually the best move. As you raise alpha, fewer and fewer moves are good enough to become "best" until you hit just one, if you are lucky.

If one move is significdantly better than all the others, won't it be likely to go very quickly, e.g. what crafty calls an "easy move" should take only one zero-window search per iteration.

It is still not so simple, as I said. An "easy move" can still see a significant score drop, where you first think you are winning a piece, but later realize the score is worse than that, but the move still has to be played. There is no way to know one move is significantly better without doing the search. And with MTD(f), you have to do several. You could try searching all but the "best" move to a lowered window and they all fail low, you now have a measurable "gap" between the "best" and the "rest". But you still need a PV. And that still requires searching until the exact path is found by failing low on N, N+1, and then failing high on N-1, N.

If you need a PV, then you can't use my idea, but you don't need a PV to determine the best move.

In reality you will jump alpha over the true score and now all moves fail low. How narrow must the window be before you decide that you are willing to accept the best move returned by the search, even though others might actually be slightly better (by whatever amount you are under the true lower bound)???

That depends on your evaluation. How different do two scores need to be befor you can say they are significantly different? Or how much score would you be willing to give up for an extra ply of depth?

I am not willing to give up any actual score to go deeper. That is exactly the opposite of what I want to do, because if you give up that simply .05, it only takes 20 iterations for that to turn into a whole pawn you gave up. I don't need to do an extra ply just to lose a pawn.

I'm not willing to accept even 5 centipawns worse, because if I let my score drop by 5 centipawns every move, after only 20 moves, I have given up a whole pawn (I will say more on this in a week or two after crafty 23.1 is released, as I found an interesting change in the time overflow code that is directly related to this idea). In any case, it is almost as hard to get within 5 as it is to get within 1, and I'm not willing to give up 5.

How much do you give up by not searching a ply deeper? I ran some old log files through a script and the standard deviation between scores at ply n and ply n+1 was 30 centipawns.

[bob]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

It is not so simple. You start off by proving that the "best move" is inside some relatively wide window. But you are not sure which is actually the best move. As you raise alpha, fewer and fewer moves are good enough to become "best" until you hit just one, if you are lucky.

If one move is significdantly better than all the others, won't it be likely to go very quickly, e.g. what crafty calls an "easy move" should take only one zero-window search per iteration.

It is still not so simple, as I said. An "easy move" can still see a significant score drop, where you first think you are winning a piece, but later realize the score is worse than that, but the move still has to be played. There is no way to know one move is significantly better without doing the search. And with MTD(f), you have to do several. You could try searching all but the "best" move to a lowered window and they all fail low, you now have a measurable "gap" between the "best" and the "rest". But you still need a PV. And that still requires searching until the exact path is found by failing low on N, N+1, and then failing high on N-1, N.

If you need a PV, then you can't use my idea, but you don't need a PV to determine the best move.

In reality you will jump alpha over the true score and now all moves fail low. How narrow must the window be before you decide that you are willing to accept the best move returned by the search, even though others might actually be slightly better (by whatever amount you are under the true lower bound)???

That depends on your evaluation. How different do two scores need to be befor you can say they are significantly different? Or how much score would you be willing to give up for an extra ply of depth?

I am not willing to give up any actual score to go deeper. That is exactly the opposite of what I want to do, because if you give up that simply .05, it only takes 20 iterations for that to turn into a whole pawn you gave up. I don't need to do an extra ply just to lose a pawn.

I'm not willing to accept even 5 centipawns worse, because if I let my score drop by 5 centipawns every move, after only 20 moves, I have given up a whole pawn (I will say more on this in a week or two after crafty 23.1 is released, as I found an interesting change in the time overflow code that is directly related to this idea). In any case, it is almost as hard to get within 5 as it is to get within 1, and I'm not willing to give up 5.

How much do you give up by not searching a ply deeper? I ran some old log files through a script and the standard deviation between scores at ply n and ply n+1 was 30 centipawns.

I don't see numbers that large, but in any case, your idea is going to stretch this out, not narrow it... Since you never get to the exact score. As far as needing the PV goes, that is essential for debugging.

[jwes]

It occurred to me that if you gave up returning a score and always choosing the best move if it is not significantly better than other moves, you could make mtd(f) significantly faster. The idea is that you terminate each iteration of the search if either there is only root move that fails high, or if there are moves in a range of n centipawns, where n is the minimum difference of evaluations that you consider statistically significant. If there are more than one move returned, you could use chess knowledge or pick one randomly.

It is not so simple. You start off by proving that the "best move" is inside some relatively wide window. But you are not sure which is actually the best move. As you raise alpha, fewer and fewer moves are good enough to become "best" until you hit just one, if you are lucky.

If one move is significdantly better than all the others, won't it be likely to go very quickly, e.g. what crafty calls an "easy move" should take only one zero-window search per iteration.

It is still not so simple, as I said. An "easy move" can still see a significant score drop, where you first think you are winning a piece, but later realize the score is worse than that, but the move still has to be played. There is no way to know one move is significantly better without doing the search. And with MTD(f), you have to do several. You could try searching all but the "best" move to a lowered window and they all fail low, you now have a measurable "gap" between the "best" and the "rest". But you still need a PV. And that still requires searching until the exact path is found by failing low on N, N+1, and then failing high on N-1, N.

If you need a PV, then you can't use my idea, but you don't need a PV to determine the best move.

In reality you will jump alpha over the true score and now all moves fail low. How narrow must the window be before you decide that you are willing to accept the best move returned by the search, even though others might actually be slightly better (by whatever amount you are under the true lower bound)???

That depends on your evaluation. How different do two scores need to be befor you can say they are significantly different? Or how much score would you be willing to give up for an extra ply of depth?

I am not willing to give up any actual score to go deeper. That is exactly the opposite of what I want to do, because if you give up that simply .05, it only takes 20 iterations for that to turn into a whole pawn you gave up. I don't need to do an extra ply just to lose a pawn.

I'm not willing to accept even 5 centipawns worse, because if I let my score drop by 5 centipawns every move, after only 20 moves, I have given up a whole pawn (I will say more on this in a week or two after crafty 23.1 is released, as I found an interesting change in the time overflow code that is directly related to this idea). In any case, it is almost as hard to get within 5 as it is to get within 1, and I'm not willing to give up 5.

How much do you give up by not searching a ply deeper? I ran some old log files through a script and the standard deviation between scores at ply n and ply n+1 was 30 centipawns.

I don't see numbers that large, but in any case, your idea is going to stretch this out, not narrow it... Since you never get to the exact score.

Except in the case where the best move changes and is significantly better. Whether searching somewhat deeper is worth more than not always picking the move with the highest evaluation would have to be settled by testing.

[rjgibert]

This reminds me a bit of MTD(best) with a coarse eval. MTD(best) is a little faster, but supposedly it is not worth what you give up for the bump in speed.