NegaC*

[ZirconiumX]

I wonder how an implementation of NegaC* would fair in comparison to a modern aspiration window search. Would it be faster (all searches in a zero window) or slower (requires at least 2 searches per iteration)?

For anyone who does not know what NegaC* is - it's essentially a binary search using zero-window fail-soft alpha-beta to extract values.

Matthew:out

[rreagan]

How is it different from MTD(f)?

[Henk]

How is it different from MTD(f)?

What I know about MTD(f) is that you can't do futility pruning. Other reductions may not be applicable too I guess. It's just a total different approach.

[ZirconiumX]

How is it different from MTD(f)?

MTD(f) requires a first guess to be accurate, NegaC* does not, but they are otherwise highly related.

I'm only asking this out of curiosity.

Matthew:out

[ZirconiumX]

How is it different from MTD(f)?

What I know about MTD(f) is that you can't do futility pruning. Other reductions may not be applicable too I guess. It's just a total different approach.

Not sure if this is correct. Stockfish applies futility pruning in zero-window searches, and since in MTD(f) the entire search is zero-window, I think it's OK to do futility pruning.

I do know that Principal Variation Search is pointless in MTD(f), though (first move: search with full window, which is a zero-window, all others, search with a zero window, which is the same as what we currently have).

Matthew:out

[Henk]

How is it different from MTD(f)?

MTD(f) requires a first guess to be accurate, NegaC* does not, but they are otherwise highly related.

I'm only asking this out of curiosity.

Matthew:out

An advantage is that you get more hash table hits. When I implemented it my hash table was not working correctly. Also I remember stop criterium gave problems. Flipping from guess to guess + delta and back. But my implementation was not good.

[ZirconiumX]

How is it different from MTD(f)?

MTD(f) requires a first guess to be accurate, NegaC* does not, but they are otherwise highly related.

I'm only asking this out of curiosity.

Matthew:out

An advantage is that you get more hash table hits. When I implemented it my hash table was not working correctly. Also I remember stop criterium gave problems. Flipping from guess to guess + delta and back. But my implementation was not good.

Since MTD(f) is incredibly slow without a TT (Aske Plaat explicitly stated it had to have a TT in his thesis).

I have yet to see NegaC* bound bounce, like MTD(f) does.

I suppose we have to wait until someone with more experience chips in.

Matthew:out

[Henk]

How is it different from MTD(f)?

MTD(f) requires a first guess to be accurate, NegaC* does not, but they are otherwise highly related.

I'm only asking this out of curiosity.

Matthew:out

An advantage is that you get more hash table hits. When I implemented it my hash table was not working correctly. Also I remember stop criterium gave problems. Flipping from guess to guess + delta and back. But my implementation was not good.

Since MTD(f) is incredibly slow without a TT (Aske Plaat explicitly stated it had to have a TT in his thesis).

I have yet to see NegaC* bound bounce, like MTD(f) does.

I suppose we have to wait until someone with more experience chips in.

Matthew:out

With MTD(f) you have no alpha or beta but only one gamma. So it's quite different. But it's too long ago. I can't remember.

[bob]

How is it different from MTD(f)?

MTD(f) requires a first guess to be accurate, NegaC* does not, but they are otherwise highly related.

I'm only asking this out of curiosity.

Matthew:out

Either has to be accurate. Otherwise you require more iterations. I gave up on mtd(f) after several months of effort many years ago when Don Daily was touting its benefits. If a new iteration significantly changes the score, it does not work well.