Negascout & Threefold repetition

[andretaff]

Hello,

I'm working on my first engine, and it's two months old. It's slow, buggy, but it works.

I have two (noob) questions:

- Is negascout worth it? I read about it a lot but it seems everybody here still uses alpha-beta. Is this true? I implemented both but with my clumsy move ordering, alpha-beta is still better.

- I thought a lot about implementing threefold repetition but every solution that came to my mind was _very_ expensive in nodes/second. I thought about using the hash table, wich I already implemented, but it seems unreliable, since collisions can occur. Is there a simple, fast way to do this?

[Harald Johnsen]

Are you talking about that http://en.wikipedia.org/wiki/Negascout ?

Everybody is using that (or some variation, with ot without aspiration window), because it's worth it.

What you call alpha beta is the code posted above without the last line (b := α+1) ? What do you call 'better' ? Less nodes or correct results ?
I think the only overhead of using a null window lies in re-search that could fail low (ie useless re-search), but this should not happen often.


For 3fold detection you can use a simple stack of positions (not really positions but hash keys). You add the position to the stack when you play a move. Then you can scan this stack to check if the current position was allready seen.

HJ.

[andretaff]

Are you talking about that http://en.wikipedia.org/wiki/Negascout ?

yes!

What you call alpha beta is the code posted above without the last line (b := α+1) ?

Yes, pure alpha-beta pruning, without researches and no null-windows: http://en.wikipedia.org/wiki/Alpha-beta_pruning

What do you call 'better' ? Less nodes or correct results ?

They got the same results, but (and I really don't know why) pure alpha-beta was faster.

For 3fold detection you can use a simple stack of positions (not really positions but hash keys). You add the position to the stack when you play a move. Then you can scan this stack to check if the current position was allready seen.

Hm... I think I got the idea. Thanks!

[andretaff]

Maybe this answers my first question: "Hence, NegaScout works best when the move ordering is good. With a random move ordering, NegaScout will take more time than regular alpha-beta; although it will not explore any nodes alpha-beta did not, it will have to re-search many nodes."

I'm only ordering moves like this:
- Promotions
- Captures
- Everything else

[bob]

Hello,

I'm working on my first engine, and it's two months old. It's slow, buggy, but it works.

I have two (noob) questions:

- Is negascout worth it? I read about it a lot but it seems everybody here still uses alpha-beta. Is this true? I implemented both but with my clumsy move ordering, alpha-beta is still better.

- I thought a lot about implementing threefold repetition but every solution that came to my mind was _very_ expensive in nodes/second. I thought about using the hash table, wich I already implemented, but it seems unreliable, since collisions can occur. Is there a simple, fast way to do this?

Most today use plain alpha/beta in the PVS variant where you search most everything with a null-window and only research if something fails high at the wrong place.

The simplest repetition scheme is to store each new hash signature in an array, where each entry gets the hash signature for the next ply before a move is made. You can search thru this list when you add a new entry to the end, and if that end entry is found anywhere else in the list, you can call it a draw (2-fold) or you can go all the way and look for a third instance although that has a negative issue with missing lots of repetitions because they become too deep to see.

Once you get the above working, you can add a 50-move rule counter, and now you only need to search from the end of the list back for the number of entries specified by the 50-move counter, since once a capture is made or a pawn is pushed, repetitions are no longer possible with positions that occurred prior to that move...

It has a minimal performance cost and is extremely easy to implement...

[Harald Johnsen]

You must make a distinction between 'good' and 'bad' captures for your move ordering and search good captures first.
A queen capturing a defended pawn is not good, a pawn capturing a defended queen is good.

A simple thing to try is to score captures by attacker/victim value (score = victim - attacker see http://web.archive.org/web/200706072311 ... escent.htm) ; when the attacker value <= victim value your capture is good, the victim being defended or not.

A further step is then to score the captures where attacker > victim ; this is done with a SEE or swap routine.

HJ.

[andretaff]

Hello people,

Thanks for the help. I implemented the 2-fold version, but if I used it inside my main alpha-beta routine, the search became somewhat different. Either way, it works.

André

[hgm]

My experience with PVS in uMax was the same: plain alpha-beta was faster. You need to have a good move ordering before PVS pays off. But if you have perfect move ordering, there is also no point in using PVS, as they will again search the same tree.