killer move not working :)

[cyberfish]

I am trying out killer moves in my program, and it doesn't seem to give any improvement (average depth reached in 1s searches on 100 randomly-selected positions from the Encyclopedia of Chess Midgames), so I am wondering whether I got something conceptually wrong.

What I am doing now is something like this -

Code: Select all

killers[MAX_PLIES][2][2]; //[ply][first/second][src/dst]

negamax(a, b) {
    ...
    for (all moves) {
        ...
        if (eval >= beta && move is not a capture or promotion) {
            //add killer
            if (move == first killer) { nothing needs to be done }
            else if (move == second killer) { swap first and second; }
            else { second_killer = first_killer; first_killer = this move; }
        }
    }
    ...
}

In ordering moves, I am doing (for depth > 0)
1. hash move
2. all captures and promotions (cannot separate winning and losing captures because I am using MVV/LVA)
3. primary killer
4. secondary killer
5. other moves by history heuristics (slight speedup)

and for depth <= 0
1. hash move
2. winning and equal captures ordered by SEE and queen promotions

I am getting an average depth of ~10.35, and killers don't help at all.

Is there something wrong?

Many thanks

[bob]

Nothing jumps out except for the fact that you are not seeing any tree size reduction. Killer moves make a difference, although we are talking things like 10%, not 50%... Also in tactical problems they often don't work as well since there are "surprises" everywhere. You might want to try some normal positions to see what happens... positions chosen from some of your actual games...

[cyberfish]

Ah I see. Thanks.

we are talking things like 10%, not 50%

I think that's where my misunderstanding is. It sounded like a great idea and I thought it would give a huge speedup.

If it's on the order of 10%, I guess my testing method based on plies won't be so useful.

[AndrewShort]

my testing has always been to test certain positions at fixed depths, rather than at fixed times. So I might do a depth 9 search before killers, then a depth 9 search after killers, then compare the node counts and the time spent. With killers, you would expect the node count and the time to go down. That's how I quickly test virtually everything. Of course, I try many different positions, at different depths, but you get the idea...

[cyberfish]

my testing has always been to test certain positions at fixed depths, rather than at fixed times. So I might do a depth 9 search before killers, then a depth 9 search after killers, then compare the node counts and the time spent. With killers, you would expect the node count and the time to go down. That's how I quickly test virtually everything. Of course, I try many different positions, at different depths, but you get the idea...

Sounds like a good idea. Will do that.

[cyberfish]

I just tested it using the constant depth method, and killers cut down the search time from 43s to 30s (same 100 positions, 8 ply searches)... so I guess it's working well afterall

Thanks for the help.

[cyberfish]

Now that I am using this great testing method... I went on to test my other features one by one, and I noticed something strange with null-move prunning. Here are the results (100 random positions to depth 8) -

no null - 34.9s
R = 1 - 28.2s
R = 2 - 29.6s
R = 3 - 31.3s
R = 4 - 34.4s

Seems like my engine works the best with R = 1?

Also, the gain seems very small, compared to other people's reports (of how much they gain from null-move).

I suppose it would've been more accurate if I used real positions instead of from a test suite, but I didn't think the difference would be this large?

[Harald Johnsen]

no null - 34.9s
R = 1 - 28.2s
R = 2 - 29.6s
R = 3 - 31.3s
R = 4 - 34.4s

Seems like my engine works the best with R = 1?

Null move is bad for tactics and the 'solution' from tactical suits will be found one or more plies later. While using R=3 should give a smaller tree than with using R=1, finding a solution usually shrinks the tree more than using an optimal R.

You won't conclude anything when using tactical position for your tests.

HJ.

Code: Select all

killers[MAX_PLIES][2][2]; //[ply][first/second][src/dst]

Must be a typo, your last dimension is 2 ?

[cyberfish]

That makes sense. I think I should find some normal positions (btw, any automatic tools for that? I have the PGNs, but need positions in EPD).

Yes, the last dimension is 2 (source square and dst square).

[cyberfish]

Seems like pgn-extract will do (it can output to epd).