Effectiveness of killer moves

[raccoon]

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.

[ZirconiumX]

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.

Welcome to the forum!

Personally I would have put promotions above good captures, because an extra queen usually swings things to your favour.

What's the PV given, or haven't you implemented that yet?

4% less nodes from killer moves shows that they are having an effect. Aside from transposition tables, null-move, and alpha beta, there is no silver bullet that gives a massive Elo boost once the basics are out of the way.

Possibly try SEE sorting moves. And also make sure quiet moves are well sorted, they matter too.

Matthew:out

Matthew:out

[raccoon]

Thanks for your reply.

The PV is this:

info score cp -110 depth 8 nodes 4499666 pv f1b5 c6d4 e3d4 f6g5 d4c5 g5c5 b5d3 c5c3

I am using SEE to sort good and bad captures. Should I use SEE to prune losing quiet moves as well? It seems kind of costly.

[mar]

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

Killers improve ordering, that's what you got so why complain?
Btw. nice to see that you quit football for computer chess!

[raccoon]

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

Killers improve ordering, that's what you got so why complain?
Btw. nice to see that you quit football for computer chess!

Well sometimes killers actually make things worse.

At the start position without killers:
info score cp 91 depth 9 nodes 33165712 pv b1c3 b8c6 e2e3 e7e6 d1g4 f7f5 g4h5 g7g6 h5f5

At the start position with killers:
info score cp 91 depth 9 nodes 42463746 pv b1c3 e7e6 e2e3 b8c6 d1g4 f7f5 g4h5 g7g6 h5f5

[mar]

Well sometimes killers actually make things worse.

Well, usually killers are good and you don't reduce them or prune them.
The only objective measure to see if an idea helps or not is to play (lots of) games.

[ZirconiumX]

Thanks for your reply.

The PV is this:

info score cp -110 depth 8 nodes 4499666 pv f1b5 c6d4 e3d4 f6g5 d4c5 g5c5 b5d3 c5c3

I am using SEE to sort good and bad captures. Should I use SEE to prune losing quiet moves as well? It seems kind of costly.

In QSearch, you can prune losing captures safely, which gives a nice speed boost.

Pruning losing quiet moves in search is a bad idea, but you could test if reducing moves like that is an Elo gain.

Matthew:out

[tpetzke]

Welcome to the club.

You should not judge any improvement based on the behavior on a single position, you should at least use a whole bunch of positions. Test suites are not necessarily good because they contain usually a best move found by a deeper search which is not necessarily the most common case if an engine searches in a game. Best is playing games.

When you add killers to the captures don't forget to remove them from the quiet moves generated later if you have staged move generation.

What is the typical node count for a middlegame position?

There is no typical general node count for a mid game position. This number will vary a lot between engines and positions. Mature engines will use a lot of selectivity within the search so they will show a node count that will seem ridiculously low to someone that just started with its engine.

For the position you posted iCE needs 50k nodes for depth 8 and 83k nodes for depth 9. Stronger engines will most likely use even less nodes.

Don't let that confuse you, over time you will add the techniques that bring your node count down. In order to work properly they need a decent eval and a stable search framework.

Good luck with your project

[pkumar]

When you add killers to the captures don't forget to remove them from the quiet moves generated later if you have staged move generation.

If we try to remove then every noncapture move has to be checked against the killers. If we don't then we are likely to return quickly with a TT hit when the killer is played the second time (if at all). How does the lazy approach fare?

[mar]

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.