Effectiveness of killer moves

[pkumar]

How does the lazy approach fare?

I had a similar bug some time ago, I found the commit but I think it had no impact on strength. I kept the fix where no move is generated twice.

Then why call it a bug? The way I see it, all sibling moves are at the same depth as the failed killer move(s) and have also failed if we have to play the killer(s) a second time. So the killer results are very likely to remain available - especially if the TT has multiple buckets. The only question is which approach is costlier. You have tried both and did not see any difference in strength. Did you notice any difference in NPS?

[mar]

Then why call it a bug? The way I see it, all sibling moves are at the same depth as the failed killer move(s) and have also failed if we have to play the killer(s) a second time. So the killer results are very likely to remain available - especially if the TT has multiple buckets. The only question is which approach is costlier. You have tried both and did not see any difference in strength. Did you notice any difference in NPS?

As I said I don't remember, of course entering a node has some cost, so has examining hash, killers (noncaptures only) already generated.
Question is how often you get that far in staged move generation anyway.
I didn't do an in-depth extensive examination as I prefer a consistent move generator that only outputs each move once but YMMV.

[pkumar]

I prefer a consistent move generator that only outputs each move once

Agreed it is at least aesthetically pleasing.

[bob]

Hi everyone,

I'm putting move ordering into my chess engine and I have a few questions. I currently am using: hash move, good captures sorted by MVV/LVA, promotions/promotion captures, killers, losing captures sorted by MVV/LVA.

I put in this position:

position fen r1b1k2r/ppppnppp/2n2q2/2b5/3NP3/2P1B3/PP3PPP/RN1QKB1R w KQkq - 0 1

Without the killers I get:
info score cp -110 depth 8 nodes 4674058

When I added the killer I get:
info score cp -110 depth 8 nodes 4499666

It seems that at best, adding killers is only making a slight impact. In some cases, the nodes searched is actually slightly more.

My questions are:

1) Does anybody else have this problem? Are killers supposed to result in a dramatic reduction in the node count?

2) What is the typical node count for a middlegame position? I increment the node count every time I call the make move method. I searched the above position at depth 9 and I got:

info score cp 74 depth 9 nodes 11,201,963

Thanks in advance.

Here's some numbers from current Crafty that won't be very helpful, since it is a forward-pruner/LMR program...

Code: Select all

depth=8

          8     0.02/35.68    0.09   1. Bc4 O-O 2. O-O d6 3. Nxc6 Nxc6 4. Bxc5
                                     dxc5
          8->   0.03/32.02    0.09   1. Bc4 O-O 2. O-O d6 3. Nxc6 Nxc6 4. Bxc5
                                     dxc5
        time=0.03(100%)  n=107662(107.7K)  fh1=91%  50move=0  nps=3.6M
        ext=319  pruned=28.3K  qchks=1.2K  predicted=1
        LMReductions: 0/12.1K  1/3.0K  2/1.7K  3/316  
        null searches (R): 3/2.2K  


depth=9

          9->   0.06/28.20    0.41   1. Bc4 O-O 2. O-O d6 3. Nxc6 Nxc6 4. Bxc5
                                     dxc5 5. Qh5
        time=0.06(100%)  n=178566(178.6K)  fh1=92%  50move=0  nps=3.0M
        ext=598  pruned=50.7K  qchks=1.7K  predicted=0
        LMReductions: 0/20.1K  1/4.6K  2/3.0K  3/714  4/1  
        null searches (R): 3/4.2K  

Node counts are almost like "fingerprints" here.

[tpetzke]

I haven't ever used the lazy approach. I just remove the killers from the generated quiet moves.

If I left them in I would get a TT hit but also experience some side effects, e.g.

The history counter for the failed killers would be decremented (which is currently not the case)

The killers would probably show up in one of the first spots so LMR and LMP will not effect them a lot but it will effect later moves heavier than before because potentially 2 killers + 1 counter move sneaked in.

Searching the killer move a 2nd time has probably no impact but those side effects can very easily have.