Multi-cut and fail-soft

[ZirconiumX]

I'm experimenting with multi-cut, and it seems to be fairly effective (though I have no testing to prove this as of yet).

Since my search is fail-soft, but MC uses multiple searches, I'm wondering what I should return from a theoretical standpoint. I'm currently returning beta, but returning the score of the search that causes the cutoff is another possibility.

[hgm]

This is hard to say without testing. My first intuition would be to return the lowest of the score of the moves that you did search.

[Karlo Bala]

I'm experimenting with multi-cut, and it seems to be fairly effective (though I have no testing to prove this as of yet).

Since my search is fail-soft, but MC uses multiple searches, I'm wondering what I should return from a theoretical standpoint. I'm currently returning beta, but returning the score of the search that causes the cutoff is another possibility.

Just return alpha or beta (depending on the result; alpha mean return nothing). In a deep search, a fail soft PVS behave like a fail hard PVS.

[zd3nik]

I'm experimenting with multi-cut, and it seems to be fairly effective (though I have no testing to prove this as of yet).

Since my search is fail-soft, but MC uses multiple searches, I'm wondering what I should return from a theoretical standpoint. I'm currently returning beta, but returning the score of the search that causes the cutoff is another possibility.

Just return alpha or beta (depending on the result; alpha mean return nothing). In a deep search, a fail soft PVS behave like a fail hard PVS.

Agreed. Use a hard alpha/beta value whenever the result is nebulous. Only use soft returns (above beta, below alpha) with more reliable values. My 1.5 cents.

[hgm]

The point is that if you visit the node the next time with a larger value of beta, the value stored in the hash table would not be high enough for a cutoff. So you would redo the search, and eventually you would find the same three moves above beta (perhaps after searching a lot of others, as you do not store three hash moves,so you have no idea which moves caused the multi-cut) if the worst of the three was also above the new beta. So basically you have been wasting time by redoing what you already knew. That applies to all new beta below the score of the worst multi-cut move, and by storing this lowest score instead of the beta you had at the time,y you would have exactly prevented that.

Note that the difference between fail-soft and fail-hard only affects TT probing; the search would never notice whether you return beta or something higher.

[Karlo Bala]

The point is that if you visit the node the next time with a larger value of beta, the value stored in the hash table would not be high enough for a cutoff. So you would redo the search, and eventually you would find the same three moves above beta (perhaps after searching a lot of others, as you do not store three hash moves,so you have no idea which moves caused the multi-cut) if the worst of the three was also above the new beta. So basically you have been wasting time by redoing what you already knew. That applies to all new beta below the score of the worst multi-cut move, and by storing this lowest score instead of the beta you had at the time,y you would have exactly prevented that.

Note that the difference between fail-soft and fail-hard only affects TT probing; the search would never notice whether you return beta or something higher.

I see, you are talking about the original implementation from literature. That is IMO not a very efficient implementation exactly because the reasons you gave. Anyhow, even in the original idea, it is proposed to return beta.

[hgm]

I suppose that is what "multi-cut" means: taking a beta cut when several reduced searches (usually 3) score above beta, in the hope this will be cheaper than doing a single full-depth search to score above beta. If it can mean something else, I have no idea what, and it becomes difficult to answer any questions about it.

But the general idea of fail soft is that you try to figure out for every search of a sub-tree for which more-demanding situations than the original request it would also be valid, and set the bound as sharp as possible. Whether this helps much in practice is a good question. Alpha-beta search is rather lazy, and often does not return scores above beta or below alpha even in a fail-soft framework.

[ZirconiumX]

I suppose that is what "multi-cut" means: taking a beta cut when several reduced searches (usually 3) score above beta, in the hope this will be cheaper than doing a single full-depth search to score above beta. If it can mean something else, I have no idea what, and it becomes difficult to answer any questions about it.

But the general idea of fail soft is that you try to figure out for every search of a sub-tree for which more-demanding situations than the original request it would also be valid, and set the bound as sharp as possible. Whether this helps much in practice is a good question. Alpha-beta search is rather lazy, and often does not return scores above beta or below alpha even in a fail-soft framework.

One MC idea I've seen proposed is to attempt it when a TT probe fails high with not enough depth to cut off. It seems like a better idea than always trying at predicted cut nodes, though I suspect it will be essentially equivalent to trying null move pruning when the static evaluation fails high.

Another one attempts to order the nodes that cut off first if there aren't enough cuts to confirm. The paper does point out that this doesn't have all that much effect though, since with good move ordering you will likely have ordered the cuts first anyway.

[Karlo Bala]

You are right, of course, yet sometimes one can relax conditions a bit. For example, search first move with the largest depth, and the last (third or fourth) with the smallest. The question is which result to return? Best? Deepest? Or, search first move against beta, second against beta-delta1, and third against beta-delta2.

[hgm]

It depends on what these searches of the cut moves return. Not on the reductionthey got, or what window they were searched with. What matters is for which depth and beta of the node you are searching them from you would accept those returned scores as sufficient for a cutoff. That is the depth and score you should store for that node.

This is really not different from null-move pruning. If you are in a d=6 node, and search a null move with reply depth d=2 (i.e.R=3) and get a cutoff, you store that node in the hash with d=6. Not with d=3. With a lower score bound equal to that returned by the null-move search when you always do null move, or with the static eval if you only do null moves when eval >= beta.