At each node in the tree, you should be doing a probe into your hash (transposition/refutation) table. Sometimes the draft of that position is sufficient, and the bound is usable, so that you can terminate the search immediately. At other times, the draft is insufficient, or the stored bound doesn't help you, but you may well have a "best move" stored in that entry (you would normally have a best move if you search a node and either return a real score (score > alpha && score < beta) or a lower bound (score >= beta). In either of those cases, you have a best move you can store in the table. This is what I call a "hash move". Since it was best in a previous search from this same position, you should try it first in this position as well...Martin Brown wrote:I expect the problem here is my lack of understanding of the right way to do things. Thanks for your patience if this is a really dumb question. I am not sure what you mean here by hash move (lookup into the hash table of previous results for the position or PV from a shallower search?).bob wrote:I don't quite follow. Here's my move ordering and an explanation of why this is:Martin Brown wrote:This seems like a good time to ask why there isn't some advantage to storing any killer move (including captures) and trying out the killer with a slightly more complex test for legality before move generation at that ply.
I presume that in general this approach must be slower and that sorted favourable captures are so effective in their own right as to be not worth storing. Although in the toy program I have written it seems to be faster when the killer is tried before full move generation. My move generator is old and slow, but it is terminal node evaluations that dominate runtime.
Thanks for any enlightenment.
(1) hash move (always). This move was proved best in a previous search, it should be tried first here. I do this without generating any moves at all.
(2) captures with SEE >= 0. I only generate captures here and try the ones that appear to not be bad.
(3) killer moves (2). I do this before generating any additional moves (I have already generated captures, I still have to generate non-captures).
(4) The rest of the moves. Here I have to generate the non-captures and search them in the order generated.
So back to the original question. Killers should not be captures, because we will try the good captures _before_ we try any killers at all. We would not want to search the same capture again (we should get an instant hash fail low if we did) which would simply waste that killer.
Good captures first. Why? Most moves in a full width search hang something, and the quickest way to refute a move that hangs material is to capture the thing instantly. If that doesn't work, then you try moves that were good in previous searches (killer moves). Of course the hash move still comes first and it _may_ be a capture, it is simply whatever was best the last time this exact position was searched.The code I am resurrecting dates from the 1980's. The way it was done then was very crude:
Generate all moves
Try killer(s) {any move allowed as a killer}
Try sorted list of moves {excluding killers}
I changed it to apply the killers with a test for legality before move generation. So it is now
Test killer legal - try killer
Generate all moves
Try list of sorted moves excluding killers.
I can see that allowing captures as killers pollutes the killer line with responses to daft opponent moves that leave pieces en prise. But isn't that issue taken care of by having two killers and a usage heuristic?
And if a superficially bad capture that is tried after all other moves causes a beta cutoff why should it not enter the killer line ?
I am sure your way is better since that is how everybody seems to do it now, but I am curious to better understand why... Thanks again.
