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.
Effectiveness of killer moves
Moderators: hgm, Rebel, chrisw
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Effectiveness of killer moves
Welcome to the forum!raccoon wrote: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.
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
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 6
- Joined: Sat Jul 26, 2014 9:53 am
Re: Effectiveness of killer moves
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.
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.
Last edited by raccoon on Sun Aug 17, 2014 2:18 pm, edited 1 time in total.
-
- Posts: 2556
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Effectiveness of killer moves
Killers improve ordering, that's what you got so why complain?raccoon wrote: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
Btw. nice to see that you quit football for computer chess!
-
- Posts: 6
- Joined: Sat Jul 26, 2014 9:53 am
Re: Effectiveness of killer moves
Well sometimes killers actually make things worse.mar wrote:Killers improve ordering, that's what you got so why complain?raccoon wrote: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
Btw. nice to see that you quit football for computer chess!
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
-
- Posts: 2556
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Effectiveness of killer moves
Well, usually killers are good and you don't reduce them or prune them.raccoon wrote:Well sometimes killers actually make things worse.
The only objective measure to see if an idea helps or not is to play (lots of) games.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Effectiveness of killer moves
In QSearch, you can prune losing captures safely, which gives a nice speed boost.raccoon wrote: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.
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
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: Effectiveness of killer moves
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.
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
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.
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.What is the typical node count for a middlegame position?
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
-
- Posts: 100
- Joined: Tue Oct 15, 2013 5:45 pm
Re: Effectiveness of killer moves
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?tpetzke wrote: 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.
-
- Posts: 2556
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Effectiveness of killer moves
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.pkumar wrote:How does the lazy approach fare?