Mult-cut, SE and ETC

[rjgibert]

What's the matter with using multi-cut in chess?

It is somewhat similar to SE in effect and seems more efficient. It can also be optimized to work perhaps even better by hybridising it with ETC--Enhanced Transposition table Cut-offs.

Multi-cut doesn't seem at all a popular idea for chess. What is the reason for this?

[zamar]

What's the matter with using multi-cut in chess?

It is somewhat similar to SE in effect and seems more efficient. It can also be optimized to work perhaps even better by hybridising it with ETC--Enhanced Transposition table Cut-offs.

Multi-cut doesn't seem at all a popular idea for chess. What is the reason for this?

Tried this with Stockfish. Couldn't make it work. I don't know why. (I also like the idea)

[rjgibert]

What's the matter with using multi-cut in chess?

It is somewhat similar to SE in effect and seems more efficient. It can also be optimized to work perhaps even better by hybridising it with ETC--Enhanced Transposition table Cut-offs.

Multi-cut doesn't seem at all a popular idea for chess. What is the reason for this?

Tried this with Stockfish. Couldn't make it work. I don't know why. (I also like the idea)

The only thing I can think of that could be wrong with it is: all the reduced depth fail highs could be trivial transpositions of each other. This might happen too often in chess for MC to work, but perhaps this is some how fixable?

[grzegorzs]

Multi-cut doesn't seem at all a popular idea for chess. What is the reason for this?

I know that author of nanoSzachy played a lot with it and his conclusion was that it just doesn't work with null move prunning. However he told me once that it is possible it works better in endings. When I removed from my program null move and added Multi-cut it played better but worse than with null-move. With both, program played the same or worse. Now I can't tell you detail statistics but it was measured on little number of games - 200 probably.

[grzegorzs]

According to ETC I have to confess that it never worked for me. However one day I decided to use it to quick repetition detection. You know if 0> alpha and some move give you repetition you can very easy improve alpha.
It seemed so obvious that I was sure it must work. It didn't. On any level of tree it didn't. In tests a little in practice not at all.

But you know I am great bug creator
Try yourself

[Mincho Georgiev]

I couldn't get anything from Multi-cut. Probably if one doesn't use nullmove at the late endgame could squeeze some benefit though. Same for ETC, it was just too expensive in my implementation and it was not working as advertised. For the SE, I will wait for the Robert Hyatt's results, since I've never tried it so far.

[Andres Valverde]

What's the matter with using multi-cut in chess?

It is somewhat similar to SE in effect and seems more efficient. It can also be optimized to work perhaps even better by hybridising it with ETC--Enhanced Transposition table Cut-offs.

Multi-cut doesn't seem at all a popular idea for chess. What is the reason for this?

IIRC some versions of Homer (not sure about the latest release) did use MC.

[diep]

As i have told one of the publicists on it: Yngvi Bjornsson,

multicut is a real invention. a great invention.

Doesn't work for Diep regrettably.

Problem is similar to Zugzwang's Fail High reductions and the ProbCut.

Also it tries to compete with nullmove.

What do you try first, multicut or nullmove?
Nullmove is simply a safer assumption than multicut.

Still i like the idea. It searches 1 ply deeper for Diep when i use it.

Not counting reductions/LMR or whatever similar in search depth:

When diep doesn't manage to get 12 ply, then multicut works elowise.
When diep gets above 12 ply, say 14 ply,
then multicut no longer helps; it does search 1 ply deeper,
yet loses elo. Significant elo. Realize i didn't have much testing hardware at the time, so only real significant changes i could see.

Like a 100 elopoints or so diep lost at bigger search depths.

I used it with 3 moves needed to give a fail high to decide to give a cutoff and R=2 and R=3. R=2 in general doesn't work with it very well,
as that hardly saves out nodes. Using 2 moves giving a fail high
really was too dubious.

What i concluded is that it is a very interesting algorithm to further investigate. Maybe with some changes or additions to it, it can work.

The real problem it has, is of course transpositions.

There is methods to avoid this; yet if you do that your hashtable gives worse performance and in todays chessprograms one of the most important things is the hashtable.

Multicut is a typical algorithm that might work much better in games like go than it does in chess/checkers, thanks to the importance of the hashtable in chess, not to mention checkers (all forms of checkers, so also the more complicated 10x10 international one).

A big problem of course of multicut is that with bigger reduction factor you create with it your own horizon effect.

For example suppose we have a position P where white can still optimize its a1 rook to e1 (open file) and where it can improve its night from b3 to d4,
and where there is a potential improvement possible moving to a local maxima of evaluation of moving the king from g1 to h1 (better pawn shelter).

So now it's not surprising if our multicut algorithm will find the 3 cutoffs:

Kg1h1
Ra1e1
Nb3d4

And in every variation it plays its piece to that square in a different order.

You can of course demand: "let's get 10 moves that give a cutoff".

Well i can assure you then that nullmove already works genius.

Basically we must look to the positions: "where can multicut work where nullmove cannot".

That's in positions where the opponent has a shit position, yet is threatening something that you can avoid in a bunch of manners.

In case of the game of chess the real question is whether you want to reduce that, as that's rather tricky. Just SUPPOSE it is a real problem...

Vincent

[bob]

I couldn't get anything from Multi-cut. Probably if one doesn't use nullmove at the late endgame could squeeze some benefit though. Same for ETC, it was just too expensive in my implementation and it was not working as advertised. For the SE, I will wait for the Robert Hyatt's results, since I've never tried it so far.

For me, ETC was another break-even. At any ply in the tree, after you get a hash miss, you rip thru the move list, and update the hash sig for each move and see if that will produce a hash hit that leads to a cutoff. If so, you can either search that move first, or just bail out right now since you already know the result.

It takes time to cycle thru the move list and update the hash signature. In return you get a few more quick cutoffs without searching. For me, this was simply a "wash" with no upside nor downside, since there was no gain or loss. And my philosophy has always been to toss things that offer nothing yet add complexity.

[Mincho Georgiev]

Thanks, I'm glad to know that I'm not alone on this. How about Multi-cut. I couldn't get nothing from it either. I remember, somebody tried it with Crafty couple of years ago (I cannot recall who it was though, sorry), do you know something about the results. I may still have the code, I think.