Negascout questions

[MattieShoes]

I've implemented A/B searches before but never used Negascout, so what I know of it is mostly theoretical. I am only an egg

Negascout searches all moves after the first one with a zero window to confirm they all fail low. Normally that's turned off for the last couple ply, presumably because move ordering at the tips is bound to be poor, and the cost of re-searching is greater than the the savings of shallow zero window searches... right?

The on->off thing seems odd to me. Has anybody experimented with gradually relaxing the number of moves before resorting to a zero window search as one approaches the tips? Perhaps throwing in winning captures at some point, then killers at another, or some such?

Also, why does it always search the first move at full width? It makes perfect sense at PV nodes but the majority of your nodes are either expected alpha or beta nodes, which you can guess from the hash entry if nothing else. If it's an expected alpha node, why not search the first move with a zero window search? Or if it's an expected beta node, why not start with a zero window search on beta rather than alpha?

My own engine's move ordering is still too poor for negascout but I did see gains from a sort of gradually relaxing scheme...

Code: Select all

if(num>ply)
    localBeta = localAlpha+1;

[Aleks Peshkov]

I am not an expert, just some quick remarks.
1) What you talk about is not Negascout or any other known search method.
2) All subtrees above zero-window node are zero-window searches. You can pass only zero alpha-beta window to all descendants of a zero-window node recursively, because you do not know any other alpha and beta beside numbers you got from parent node. Sorry for my bad explanation. Think about it.
3) There are very few wide window nodes in Negascout. They are PV-nodes (and some PV-candidates that somehow failed-high in zero-windows search, but failed low in alpha-beta research).

[MattieShoes]

I realize now that the questions don't really make sense in the context of negascout -- all non-PV nodes will automatically have a zero window search everywhere, including the first move. I was visualizing something different because when I was toying with it, I was using regular A/B searching at the root node and negascout in the rest of the tree.

I read somewhere that engines commonly turn off negascout near the tips though now I can't find that. If they do, then I think the first question still makes sense...

[Gian-Carlo Pascutto]

This thread could be useful

http://talkchess.com/forum/viewtopic.php?t=26974

[Gerd Isenberg]

I've implemented A/B searches before but never used Negascout, so what I know of it is mostly theoretical. I am only an egg

Negascout searches all moves after the first one with a zero window to confirm they all fail low. Normally that's turned off for the last couple ply, presumably because move ordering at the tips is bound to be poor, and the cost of re-searching is greater than the the savings of shallow zero window searches... right?

The on->off thing seems odd to me. Has anybody experimented with gradually relaxing the number of moves before resorting to a zero window search as one approaches the tips? Perhaps throwing in winning captures at some point, then killers at another, or some such?

Also, why does it always search the first move at full width? It makes perfect sense at PV nodes but the majority of your nodes are either expected alpha or beta nodes, which you can guess from the hash entry if nothing else. If it's an expected alpha node, why not search the first move with a zero window search? Or if it's an expected beta node, why not start with a zero window search on beta rather than alpha?

My own engine's move ordering is still too poor for negascout but I did see gains from a sort of gradually relaxing scheme...

Code: Select all

if(num>ply)
    localBeta = localAlpha+1;

If you already search expected Cut- or All-Nodes in PVS/NegaScout, that is beta is already alpha+1, there is no difference between calling Alpha-Beta or NegaScout, since the window is already null and the PVS re-search condition (score > alpha && score < beta) is a contradiction.

For PV-Nodes, the point of fail-soft NegaScout near the tips or in quiscence - there are no savings compared to fail-soft Alpha-Beta. Or the other way around, fail-soft NegaScout always returns correct minimax scores at the two lowest levels, under the assumption that all horizon nodes would have the same score for the (in that case redundant) re-search from PV-Nodes.

That is why one can use alpha-beta near the tips or in qsearch, for a simpler control structure (no re-search condition), and to avoid the potential problem with a possible re-search - because the assumption all leaves have same fail-soft score independent from the window does not always hold.

[bob]

I've implemented A/B searches before but never used Negascout, so what I know of it is mostly theoretical. I am only an egg

Negascout searches all moves after the first one with a zero window to confirm they all fail low. Normally that's turned off for the last couple ply, presumably because move ordering at the tips is bound to be poor, and the cost of re-searching is greater than the the savings of shallow zero window searches... right?

I don't. I do scout searches everywhere, although you should notice that below a node that is "scouting" no further scout searches are possible because you already pass in a null-window to start a search with...

The on->off thing seems odd to me. Has anybody experimented with gradually relaxing the number of moves before resorting to a zero window search as one approaches the tips? Perhaps throwing in winning captures at some point, then killers at another, or some such?

Also, why does it always search the first move at full width? It makes perfect sense at PV nodes but the majority of your nodes are either expected alpha or beta nodes, which you can guess from the hash entry if nothing else. If it's an expected alpha node, why not search the first move with a zero window search? Or if it's an expected beta node, why not start with a zero window search on beta rather than alpha?

It really doesn't do that. Think of it this way. At ply=N, you search the first move at normal {alpha,beta} window. Which means at ply=N+1, you also search the first move with {alpha,beta}. For any node, however, once you search the first move with normal {alpha,beta} bounds, you search the rest with {alpha, alpha+1} bounds.

Back to ply=N, you have now searched the first move normally, so you search 2-M with {alpha,alpha+1}. Which means that when you get to ply N+1, your original window will be {x,x+1). So you can't do the normal scout/pvs approach here since you can only search with the window you are passed in. In effect, almost all nodes are not really "scout searched" because they are already null-window searches...

My own engine's move ordering is still too poor for negascout but I did see gains from a sort of gradually relaxing scheme...

Code: Select all

if(num>ply)
    localBeta = localAlpha+1;

[MattieShoes]

Okay, I think I'm all straightened out now My weird implementation when I was toying with it was causing me to think of the tree wrong

Besides, it looks like I have bigger problems. I was just restructuring some big things in my program and it announced 1. Nc3#

[sje]

Besides, it looks like I have bigger problems. I was just restructuring some big things in my program and it announced 1. Nc3#

Perhaps someone should put up a web page that showcases amusing chess programming errors. I'm sure that everyone would have something to contribute.

One of my recent coding blunders involve a too-clever board initialization routine. Instead of setting up the pieces on the first two and last two ranks, the initializer used the first two and last two files. You can see how the rest of the code just might have a little problem with this.

[MattieShoes]

Haha, did it crash due to pawns on illegal ranks or did it actually try and play like that? I wonder what the eval penalty for octupled isolated pawns is...

I've done lots of bonehead movegen stuff, like pawns moving the wrong direction or allowing pieces to capture their side's pieces. In combination, that becomes exciting

1.e4 cxb8=Q!!

My move struct stores a piecelist index rather than the from square, so if one attempts to make a move that was generated for the other side, one can get 1. e2f6 for example.

There was a computer on FICS that would occasionally crash and tell you a message like "Missing white king -- please message xxx".

And null move while in check can have exciting results

[bob]

Besides, it looks like I have bigger problems. I was just restructuring some big things in my program and it announced 1. Nc3#

Perhaps someone should put up a web page that showcases amusing chess programming errors. I'm sure that everyone would have something to contribute.

One of my recent coding blunders involve a too-clever board initialization routine. Instead of setting up the pieces on the first two and last two ranks, the initializer used the first two and last two files. You can see how the rest of the code just might have a little problem with this.

My favorite goes back to 1984. We won the 1983 WCCC with the Cray-XMP 2 processor system, and the "split-at-the-root" algorithm discussed here a couple of times. Early in 1984 one of my Cray friends told me they would have a prototype of the Cray XMP-4 (4 cpus) ready to test in the Summer, and we obviously wanted to use it at the 1984 ACM computer chess tournament in Los Angeles. I spent a good bit of time re-writing the parallel search to use what was at the time called "PVS" (not to be confused with the PVS search of today) which stood for "principal variation split". The idea was we went to the bottom of the tree down the left-hand edge and split there, then backed up one ply and split there, until we backed up to the root where we split there. A 10 ply search therefore did 10 splits.

I had been invited to play in a human chess tournament in Mobile, and we were paired against a player I won't name. Our first game against a player over 2300 with this version that had never played even part of a real game (we were using this human event as a test/tune opportunity to get ready for the ACM event in October of that year). We reached an interesting position and out of the clear blue, Cray Blitz played BxP mate. I looked at this, puzzled, and the opponent played PxB and there was no mate. We went back to Hattiesburg that night, as the next rounds were the next day, and some late-night testing showed a cute timing bug. After the move BxP, there were exactly three legal moves, two king moves and capturing the bishop. I had four processors, and the timing just lucked out that the first three moves were searched very quickly (this BxP was a 2 ply instant search). The last processor to report back in was the one with no legal moves to search and it simply returned "I am mated".

Never had a mate bug any worse than that. Of course I did watch the famous Coko vs Genie game in 1970 where Cooper and Kozdrowicki used a single mate score that was not relative to the depth where it was found, and they kept threatening mate in 2 until they lost the game...