Multi-cut and fail-soft

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
ZirconiumX
Posts: 1334
Joined: Sun Jul 17, 2011 9:14 am

Multi-cut and fail-soft

Post by ZirconiumX » Thu Jun 30, 2016 5:48 pm

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.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
hgm
Posts: 26538
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Multi-cut and fail-soft

Post by hgm » Fri Jul 01, 2016 9:52 am

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
Posts: 347
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Multi-cut and fail-soft

Post by Karlo Bala » Fri Jul 01, 2016 4:21 pm

ZirconiumX wrote: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.
Best Regards,
Karlo Balla Jr.

zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Multi-cut and fail-soft

Post by zd3nik » Sun Jul 03, 2016 6:45 pm

Karlo Bala wrote:
ZirconiumX wrote: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.

User avatar
hgm
Posts: 26538
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Multi-cut and fail-soft

Post by hgm » Sun Jul 03, 2016 8:59 pm

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
Posts: 347
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Multi-cut and fail-soft

Post by Karlo Bala » Mon Jul 04, 2016 7:34 am

hgm wrote: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.
Best Regards,
Karlo Balla Jr.

User avatar
hgm
Posts: 26538
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Multi-cut and fail-soft

Post by hgm » Mon Jul 04, 2016 8:23 am

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
Posts: 1334
Joined: Sun Jul 17, 2011 9:14 am

Re: Multi-cut and fail-soft

Post by ZirconiumX » Mon Jul 04, 2016 12:03 pm

hgm wrote: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.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Karlo Bala
Posts: 347
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Multi-cut and fail-soft

Post by Karlo Bala » Mon Jul 04, 2016 12:19 pm

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.
Best Regards,
Karlo Balla Jr.

User avatar
hgm
Posts: 26538
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Multi-cut and fail-soft

Post by hgm » Mon Jul 04, 2016 10:55 pm

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.

Post Reply