It is not that hard to do SEE.
If you have that, you can still order by MVV/LVA and then when you get to a capture move, run it through SEE. Then if the eval is negative, move the capture to the end of the move list and try the next capture. (This saves having to generate all captures, do SEE on all, then sort, which might be theoretically better ordering but is time-consuming).
--Jon
Move ordering
Moderators: hgm, Rebel, chrisw
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering
Actually that is theoretically worse.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering
ZirconiumX wrote:None of these results is surprising (Except that I hope that you play at least 1000 games per test run next time to increase significance ...)jwes wrote:Deferring captures of lower-valued pieces was a loss of about 25 elo +/- 37:
Deferring captures of defended squares was a loss of about 50 elo +/- 37:Code: Select all
Score of New vs Old: 84 - 103 - 63 [0.462] 250
The two together is a small gain of 10 elo +/- 24:Code: Select all
Score of New vs Old: 73 - 108 - 69 [0.430] 250
Code: Select all
Score of New vs Old: 230 - 213 - 138 [0.515] 581
Capturing lower-valued pieces includes capturing undefended pieces so deferring these is suboptimal. Capturing defended pieces in general also includes moves like PxQ where the queen is defended by a piece lower than a queen, so this is even more suboptimal. Even the combination of both is insufficient since the defender could be a queen (for instance) and you might have a second attacker of the target piece so that you could capture the queen afterwards, which does not classify the first capture as a losing capture.
There is no perfect combination but if you have not implemented SEE yet and still want to decide whether a capture most probably is a losing capture then you need a combination of criteria like this:ZirconiumX wrote:[...] I haven't found the combination just yet.
a) higher piece takes lower piece (viewing bishop and knight as equal), and
b) captured piece is defended, and
c) the least-valued defender has a value that is low enough to be sure that you would lose material even if you had a second attacker that could capture the least-valued defender afterwards.
Jumbo has no SEE yet. For b) and c) it does the following:
- target is defended by a pawn => losing capture
- (rook or queen captures pawn, or queen captures minor piece) and target is defended by a minor piece => losing capture
This leaves the following cases "undecided" so they are currently not classified as a losing capture:
- queen takes rook which is defended by a minor
- queen takes minor which is defended by a rook
- queen takes pawn which is defended by a rook
I should probably add support for these cases as well.
Please don't forget that you can also make use of the losing captures concept in QS: you can simply skip them there to avoid wasting time.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move ordering
Sven wrote:But be careful about positions like this, where there is a sequence of captures, especially in qs:ZirconiumX wrote:None of these results is surprising (Except that I hope that you play at least 1000 games per test run next time to increase significance ...)jwes wrote:Deferring captures of lower-valued pieces was a loss of about 25 elo +/- 37:
Deferring captures of defended squares was a loss of about 50 elo +/- 37:Code: Select all
Score of New vs Old: 84 - 103 - 63 [0.462] 250
The two together is a small gain of 10 elo +/- 24:Code: Select all
Score of New vs Old: 73 - 108 - 69 [0.430] 250
Code: Select all
Score of New vs Old: 230 - 213 - 138 [0.515] 581
Capturing lower-valued pieces includes capturing undefended pieces so deferring these is suboptimal. Capturing defended pieces in general also includes moves like PxQ where the queen is defended by a piece lower than a queen, so this is even more suboptimal. Even the combination of both is insufficient since the defender could be a queen (for instance) and you might have a second attacker of the target piece so that you could capture the queen afterwards, which does not classify the first capture as a losing capture.
There is no perfect combination but if you have not implemented SEE yet and still want to decide whether a capture most probably is a losing capture then you need a combination of criteria like this:ZirconiumX wrote:[...] I haven't found the combination just yet.
a) higher piece takes lower piece (viewing bishop and knight as equal), and
b) captured piece is defended, and
c) the least-valued defender has a value that is low enough to be sure that you would lose material even if you had a second attacker that could capture the least-valued defender afterwards.
Jumbo has no SEE yet. For b) and c) it does the following:
- target is defended by a pawn => losing capture
- (rook or queen captures pawn, or queen captures minor piece) and target is defended by a minor piece => losing capture
This leaves the following cases "undecided" so they are currently not classified as a losing capture:
- queen takes rook which is defended by a minor
- queen takes minor which is defended by a rook
- queen takes pawn which is defended by a rook
I should probably add support for these cases as well.
Please don't forget that you can also make use of the losing captures concept in QS: you can simply skip them there to avoid wasting time.
[d]rnbq1rk1/pp4pp/2pbp3/5pB1/2PPp3/5NP1/PPQ1PPBP/R4RK1 b - - bm exf3; c0 "give up the queen for Halloween.";
I guess that skipping the qs and reducing the depth cause problems in positions like the above.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Move ordering
So, like an idiot I accidentally tested both the move ordering changes you suggested and the QS move skipping at the same time, and only realised 2 hours and 800 games into the test. (I think most people have done that at some point, however.) I put the code here.Sven wrote:[lots of useful information I probably should have thought about earlier, as Sven is very good at doing]
Anyway, the two together give a modest gain of 24 elo +/- 15, passing SPRT(0,10) at 10+0.1.
Code: Select all
Score of New vs Old: 466 - 379 - 422 [0.534] 1267
Regarding SEE, I've tried many different variants and couldn't get an elo gain out of any of them, even with an attack table engine. But I'm going to put that aside for now, and maybe I'll open another topic about it later.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering
I see no losing capture involved here. exf3 is lower takes higher and is not a candidate to be skipped in QS, and the same for fxg2 after Bxd8.Dann Corbit wrote:But be careful about positions like this, where there is a sequence of captures, especially in qs:Sven wrote:Please don't forget that you can also make use of the losing captures concept in QS: you can simply skip them there to avoid wasting time.
[d]rnbq1rk1/pp4pp/2pbp3/5pB1/2PPp3/5NP1/PPQ1PPBP/R4RK1 b - - bm exf3; c0 "give up the queen for Halloween.";
I guess that skipping the qs and reducing the depth cause problems in positions like the above.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move ordering
After exf3, BxQSven wrote:I see no losing capture involved here. exf3 is lower takes higher and is not a candidate to be skipped in QS, and the same for fxg2 after Bxd8.Dann Corbit wrote:But be careful about positions like this, where there is a sequence of captures, especially in qs:Sven wrote:Please don't forget that you can also make use of the losing captures concept in QS: you can simply skip them there to avoid wasting time.
[d]rnbq1rk1/pp4pp/2pbp3/5pB1/2PPp3/5NP1/PPQ1PPBP/R4RK1 b - - bm exf3; c0 "give up the queen for Halloween.";
I guess that skipping the qs and reducing the depth cause problems in positions like the above.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering
Losing captures, in the context we are discussing here, can only be "high takes low" captures.Dann Corbit wrote:After exf3, BxQSven wrote:I see no losing capture involved here. exf3 is lower takes higher and is not a candidate to be skipped in QS, and the same for fxg2 after Bxd8.Dann Corbit wrote:But be careful about positions like this, where there is a sequence of captures, especially in qs:Sven wrote:Please don't forget that you can also make use of the losing captures concept in QS: you can simply skip them there to avoid wasting time.
[...]
I guess that skipping the qs and reducing the depth cause problems in positions like the above.