Zobrist Collisions?

[Desperado]

ok, let us have a closer look to the triangular approach.
How do you make sure that your array is free of trash ?

Here is what i mean (2 options):

Code: Select all

void search(...)
{  
 option1: triangular[rd2][rd2].move = moveNone

 while(moves)
 {
  ...
  option2:
  triangular[rd2+1][rd2+1].move = moveNone 
  moveDo()
  value=-search()
  moveUndo()
  if(value>alpha) collectPv()
  ...
 } 

 ...
}

if you do not cleanup your array, you may collect moves that
doesnt belong to the current line. Imagine you
deepen move1(rd2) which leads to pv.Now move2(rd2) will get a transScore leading to a new pv (but,you dont have a continuation).
Does your triangularArray still contains the subsequent moves of move1 ??! And will they be added to move2 as newPv ??

i dont use the triangular approach, so i am not sure at the moment
if it is enough to clean up the _next_ entry only !? However, when returning a score which leads to a newPv make sure that the triangular array is cleaned up, or includes the moves _really_ belonging to the current bestmove.

That problem is not only given by using early return by trans, but a general issue to handle if you return scores which may lead to a new
pv and dont include a move.

[stevemulligan]

I should have specified that I was only using the triangular approach when I had the TT disabled, and the PV was ok in that case.

It was only when I tried to retrieve the PV from the TT that I was getting a strange line that included a blunder, and a different move.

For some reason the bug seems to be gone and I'm not sure exactly what changed. Right now the TT search matches the results of the plain search for the board I posted.

I have a question about using the PV for move ordering:

Right now when I sort moves, the previous depth is always factored in. Should I stop including the previous iteration in move ordering once I reach a ply where the moves stop matching?

eg:

Code: Select all

depth 4 pv d6h2 g1h1 h2f4 h1g1
depth 5 pv d8f6 f2f3 d6c5 d2e3 d5d4

ie, when searching line for d8f6 on my 5th iteration, should I stop using the PV from the previous iteration in move ordering when I get to f2f3?[/url]

[Desperado]

I should have specified that I was only using the triangular approach when I had the TT disabled, and the PV was ok in that case.

It was only when I tried to retrieve the PV from the TT that I was getting a strange line that included a blunder, and a different move.

For some reason the bug seems to be gone and I'm not sure exactly what changed. Right now the TT search matches the results of the plain search for the board I posted.

I have a question about using the PV for move ordering:

Right now when I sort moves, the previous depth is always factored in. Should I stop including the previous iteration in move ordering once I reach a ply where the moves stop matching?

eg:

Code: Select all

depth 4 pv d6h2 g1h1 h2f4 h1g1
depth 5 pv d8f6 f2f3 d6c5 d2e3 d5d4

ie, when searching line for d8f6 on my 5th iteration, should I stop using the PV from the previous iteration in move ordering when I get to f2f3?[/url]

Normally after each iteration which has finished, the pv is restored into TT.
So the complete line will be used for move ordering on the next iteration.
Assuming you use transmove in your movepicker scheme.
Restoring maybe necessary because during the search process the slots
including the pv info are overwritten.

[Sven]

I have a question about using the PV for move ordering:

Right now when I sort moves, the previous depth is always factored in. Should I stop including the previous iteration in move ordering once I reach a ply where the moves stop matching?

eg:

Code: Select all

depth 4 pv d6h2 g1h1 h2f4 h1g1
depth 5 pv d8f6 f2f3 d6c5 d2e3 d5d4

ie, when searching line for d8f6 on my 5th iteration, should I stop using the PV from the previous iteration in move ordering when I get to f2f3?

Yes, you should, otherwise you would use a special kind of "killer heuristic" (the "PV killer"?) with a much too high priority, higher than captures. When using the PV of the previous iteration for move ordering (not talking about "PV from hash" at this point yet but about something like the triangular PV), you should track whether you are still "within the PV", i.e. whether the whole current line from the root node to the current node is identical to the old PV. Example: your PV above was "d6h2 g1h1 h2f4 h1g1" after iteration 4, and now you are in iteration 5 and

a) you are at ply 2 at the node after "d6h2 g1h1" => still within the PV, so search "h2f4" first;

b) you are at ply 3 at the node after "d6h2 g1h1 h2e5" => out of PV, "h1g1" is irrelevant for move ordering (it is a move from a different position);

c) you are at ply 1 at the node after "d8f6" => out of PV, "f2f3" is irrelevant for move ordering (a move from a different position).


Please note: when using hash table moves for move ordering and ensuring that the previous PV is fully stored in the hash table (maybe also in a separate hash table for that purpose, as Bob does it) then the whole checking whether you are "still within the PV" becomes redundant (usually you would not get a hash table move from a position different from the current one).

Sven

[Desperado]

... otherwise you would use a special kind of "killer heuristic" (the "PV killer"?) with a much too high priority...

, didnt thought of that case. Indeed, to avoid such a
behaviour the moves should be cleared after they were used once.

@Steve
a bit more elegant would be, if you keep your triangular for collecting
the pv, and as i already mentioned, put the pv from triangular into TT
after the iteration is done. Doing so you are always able to try the
transposition table move as first, which implies to examine the last pv
as first line on the next iteration.

Michael

[Sven]

... otherwise you would use a special kind of "killer heuristic" (the "PV killer"?) with a much too high priority...

, didnt thought of that case. Indeed, to avoid such a
behaviour the moves should be cleared after they were used once.

That is another possible way of solving it. If I understood you correctly you want to clear the move of the stored previous PV as soon as you use it for move ordering, i.e. you "consume" the previous PV move by move when descending the tree for the first time in the new iteration. I was only thinking about the (IMO) most logical approach: have a boolean flag "isInPV" as an additional argument of the search function that is used for full-width search, and set it to true exactly in these cases:
a) at the root node,
b) at each node where the "isInPV" flag was set for the parent node and the move leading to the current node is identical to the corresponding move of the stored previous PV.

Your approach may be a tiny bit faster; if each bit of speed is very important and the much more elegant way of storing the previous PV in the TT is not going to be used, for any reason, then perhaps your approach should be used. From a design viewpoint, though, I would prefer the "isInPV" solution over yours to avoid having to modify the previous PV, and to let the implementation reflect explicitly what is happening.

Another (small) drawback of your approach is that, when using aspiration windows, you might need to maintain a second copy of the previous PV, just in case your new iteration fails low or high so you have to repeat it with a different window but your previous PV has already been destroyed partially.

Sven

[Desperado]

Hello Sven,

yes, that is what i had in mind, but it was just a first idea how to do it.

The most intuitive (for me) way to implement,
would be to use (pv)killer slots filled up from triangular before starting next iteration.
(so instead copying into the TT, just copying into these slots, where they can be _consumed_ so to say).
If required the slots can be refilled anytime for any reason
from triangular.(eg researches with different bounds and so on ...).

cheers

[Sven]

If required the slots can be refilled anytime for any reason from triangular.(eg researches with different bounds and so on ...).

Yes, but not "from triangular" since that can be overwritten resp. cleared already by the new iteration attempt which failed high or low. When you fail high or fail low then you actually don't have a meaningful PV so the best PV you could use for move ordering in a research is the PV of the previous iteration which you had already used (but "consumed" in your case). And for that reason you would need another copy of that PV which you don't touch.

Sven