when to try zero window search

[AndrewShort]

I've never looked at any other source code before, but I broke down and fell to tempation to look at a modified Glaurung source, called StockFish. I chose stockfish arbitrarily because there was a recent post about it.

I have a fundamental question - why does it call search_pv() on the 1st move of every ply, but then it calls search (zero window) on the remaining moves? I thought the idea of PVS was that you only do so once you have found a move > Alpha, whereas this modified Glaurung seems to try zero window searches after the 1st move, even if the 1st move failed low...

[AndrewShort]

I guess another way of saying this is if the 1st move fails low, he goes ahead and tries a zero window search to prove that node in question is an ALL node.

interesting question - if your move ordering is really good, and the 1st move fails low, what % of the time will the remaining moves all fail low? that seems to be the gamble he's taking...

[Zach Wegner]

They're two different approaches that are basically equivalent. I think it's the difference between PVS and negascout, but I'm not sure which is which (nor do I care ). The advantage of Glaurung's method is that the node might actually be a fail low. If it is, then the >alpha method will search every move with an open window, which wastes time. For the moves>1 method, however, if the node is really a PV node and the best move is not the first, it will waste time researching that move.

Both methods end up searching just about the same amount of nodes. What you might try (though I haven't) is searching with a zero window if either moves>N or best_score>alpha.

[AndrewShort]

ok, that makes sense - thanks.

another thing i noticed in the source:

it only uses the hash to prune in non-pv nodes. why not also in pv nodes? I don't understand that. (It uses the hash in pv nodes for move ordering only)

[bob]

ok, that makes sense - thanks.

another thing i noticed in the source:

it only uses the hash to prune in non-pv nodes. why not also in pv nodes? I don't understand that. (It uses the hash in pv nodes for move ordering only)

Broken implementation. Just like the programs that do not store mate scores in the hash, but convert them to a "bound" instead.

[hgm]

it only uses the hash to prune in non-pv nodes. why not also in pv nodes? I don't understand that. (It uses the hash in pv nodes for move ordering only)

I thought that many programs do this, in order not to be fooled so easily into repetitions. What is in the hash, might no longer be valid, because some of the nodes later in the PV, or on a direct side branch, might now be repetitions because of the move just made at game level, while in the hash they still appear with a score like they occurred for the first time. And this wrong score can have penetrated to nodes closer to the root, which are not repetitions themselves, as well.

By forcing a search of the PV, at least you know for sure that you are not planning for a line that contains a repetition, or goes along a position from which the opponent could acheive a repetition in a single move (so that the score of that node should now be zero, in stead of what is stored in the hash).

[bob]

it only uses the hash to prune in non-pv nodes. why not also in pv nodes? I don't understand that. (It uses the hash in pv nodes for move ordering only)

I thought that many programs do this, in order not to be fooled so easily into repetitions. What is in the hash, might no longer be valid, because some of the nodes later in the PV, or on a direct side branch, might now be repetitions because of the move just made at game level, while in the hash they still appear with a score like they occurred for the first time. And this wrong score can have penetrated to nodes closer to the root, which are not repetitions themselves, as well.

By forcing a search of the PV, at least you know for sure that you are not planning for a line that contains a repetition, or goes along a position from which the opponent could acheive a repetition in a single move (so that the score of that node should now be zero, in stead of what is stored in the hash).

That seems broken to me. Why ignore exact scores in the PV, which is the biggest part of the search, and then use them in non-PV moves and prune away moves that might be better or worse because of the drawing potential? It doesn't make sense to ignore useful information like EXACT scores, IMHO. It sounds like a kludge someone tried that solved a specific problem. But I'll bet it hurts far more than it helps, overall...

[mcostalba]

That seems broken to me. Why ignore exact scores in the PV, which is the biggest part of the search, and then use them in non-PV moves and prune away moves that might be better or worse because of the drawing potential? It doesn't make sense to ignore useful information like EXACT scores, IMHO. It sounds like a kludge someone tried that solved a specific problem. But I'll bet it hurts far more than it helps, overall...

Thanks, I will try removing it and see what happens.

The only thing I'm sure is that Tord added this intentionally in Glaurung because this peculiarity is well commented, so I would suspect will not be a big gain (if any) removing it...

Marco

[gladius]

That seems broken to me. Why ignore exact scores in the PV, which is the biggest part of the search, and then use them in non-PV moves and prune away moves that might be better or worse because of the drawing potential? It doesn't make sense to ignore useful information like EXACT scores, IMHO. It sounds like a kludge someone tried that solved a specific problem. But I'll bet it hurts far more than it helps, overall...

It should add minimal overhead to the search if all of the non-PV nodes are already in the hash (which they hopefully are). It does seem more "correct" to not return the scores, as the hash key ignores repetitions.

I can see two things happening:
1. Believing the PV is a draw, when its actually not - this could be pretty bad.
2. Believing the PV is winning/losing when it's actually drawing - seems less bad, but could still cause problems.

Now, whether this is a good tradeoff or not is an excellent question. I'd be very interested if you tried this change on the cluster with Crafty .

[Eelco de Groot]

That seems broken to me. Why ignore exact scores in the PV, which is the biggest part of the search, and then use them in non-PV moves and prune away moves that might be better or worse because of the drawing potential? It doesn't make sense to ignore useful information like EXACT scores, IMHO. It sounds like a kludge someone tried that solved a specific problem. But I'll bet it hurts far more than it helps, overall...

It should add minimal overhead to the search if all of the non-PV nodes are already in the hash (which they hopefully are). It does seem more "correct" to not return the scores, as the hash key ignores repetitions.

I can see two things happening:
1. Believing the PV is a draw, when its actually not - this could be pretty bad.
2. Believing the PV is winning/losing when it's actually drawing - seems less bad, but could still cause problems.

Now, whether this is a good tradeoff or not is an excellent question. I'd be very interested if you tried this change on the cluster with Crafty .

I don't have any data about this but my interpretation of Tord's intention was something like:

Search is about getting new information, not about returning hash results, especially in the important PV nodes.

Furthermore I think Gary you are right that if there are results you can get for most of the non-PV sibling nodes the re-search of the PV node would not be very costly, the stored hash results can change the final result, and because of transpositions with these results along the PV as Bob has mentioned before you can get "grafted" results that now go deeper than the nominal search depth, at least that is how I understand Bob's posts. The second objective is to improve move ordering but I must admit I have not studied how Tord actually is doing that in Glaurung . But that was my interpretation of the design philosophy in search_pv (), I hadn't really thought about the draw by repetitions effects from the hashresults yet.

// Transposition table lookup. At PV nodes, we don't use the TT for
// pruning, but only for move ordering.

Regards, Eelco