An interesting(?) new(?) search algorithm

[Michael Sherwin]

It is sort of a cross between PVS-null-window, MTD(f), a high jump competition and a bubble sort.

The following describes what happens at the root only.

1.) The most basic idea is to search at each new iteration the previous iterations best move with a null window to make sure that it is no worse and to search the rest of the moves to make sure that they are no better. If this condition is satisfied then the current iteration is finished.

2.) If the previous iterations best move is worse than it was previously then it is searched again with a null window to see if it is still better than 2nd place. If so, then it is awarded 1 point above second place. If not better, it is awarded 1 point less than second place. This process continues until a move manages to maintain the first position. Then the rest of the moves are searched as in 1.) above.

3.) All remaining moves that are not better are discarded. Each better move that is found sets the bar a little higher (a new higher score) and only moves that make it over the bar keep competing.

The idea behind this algorithm is that in normal alpha-beta or MTD(f) it waste much time to find exact scores and it should be much quicker to just determine which move is better!

[rjgibert]

It is sort of a cross between PVS-null-window, MTD(f), a high jump competition and a bubble sort.

The following describes what happens at the root only.

1.) The most basic idea is to search at each new iteration the previous iterations best move with a null window to make sure that it is no worse and to search the rest of the moves to make sure that they are no better. If this condition is satisfied then the current iteration is finished.

2.) If the previous iterations best move is worse than it was previously then it is searched again with a null window to see if it is still better than 2nd place. If so, then it is awarded 1 point above second place. If not better, it is awarded 1 point less than second place. This process continues until a move manages to maintain the first position. Then the rest of the moves are searched as in 1.) above.

The trouble is, you don't always know what the 2nd best move is e.g. any previous iteration completing by 1.) above

3.) All remaining moves that are not better are discarded. Each better move that is found sets the bar a little higher (a new higher score) and only moves that make it over the bar keep competing.

The idea behind this algorithm is that in normal alpha-beta or MTD(f) it waste much time to find exact scores and it should be much quicker to just determine which move is better!

MTD(f) is one member of a family of variants. Another one is MTD(best), which seems to be the one you are striving for. The improvement is small enough to be deemed not worth giving up having an exact score. What's so great about an exact score? Beats me.

[bob]

It is sort of a cross between PVS-null-window, MTD(f), a high jump competition and a bubble sort.

The following describes what happens at the root only.

1.) The most basic idea is to search at each new iteration the previous iterations best move with a null window to make sure that it is no worse and to search the rest of the moves to make sure that they are no better. If this condition is satisfied then the current iteration is finished.

2.) If the previous iterations best move is worse than it was previously then it is searched again with a null window to see if it is still better than 2nd place. If so, then it is awarded 1 point above second place. If not better, it is awarded 1 point less than second place. This process continues until a move manages to maintain the first position. Then the rest of the moves are searched as in 1.) above.

3.) All remaining moves that are not better are discarded. Each better move that is found sets the bar a little higher (a new higher score) and only moves that make it over the bar keep competing.

The idea behind this algorithm is that in normal alpha-beta or MTD(f) it waste much time to find exact scores and it should be much quicker to just determine which move is better!

That is old, and it has one major problem. The first quick search does not fail low, so the previous best move is not bad. But a new move later fails high and now you know nothing about what is best. The original best move or one in the remaining list. If you don't change your mind often, this might work OK. But for Crafty, no. Ken Thompson used another variant of the current PVS algorithm:

search the first move and then search the remainder of the root moves with a null-window. If one fails high, it is best. no need to re-search it to find out how much better. If a second fails high, you have to re-search the first to get a score, then the second with a null-window to see if it fails high.

But once the iteration ends, you can be screwed. Suppose the root move at the previous iteration was not best, and you had a single fail-high. With no PV, no best move (since ply 2 is an ALL node if ply-1 fails high) you start a deeper search with no ordering help and it takes forever.