Move ordering

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jdart
Posts: 3510
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Move ordering

Post by jdart » Thu Nov 09, 2017 8:08 pm

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

User avatar
hgm
Posts: 22332
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering

Post by hgm » Thu Nov 09, 2017 8:33 pm

Actually that is theoretically worse.

Sven
Posts: 3578
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Move ordering

Post by Sven » Fri Nov 10, 2017 12:23 am

ZirconiumX wrote:
jwes wrote:Deferring captures of lower-valued pieces was a loss of about 25 elo +/- 37:

Code: Select all

Score of New vs Old: 84 - 103 - 63  [0.462] 250
Deferring captures of defended squares was a loss of about 50 elo +/- 37:

Code: Select all

Score of New vs Old: 73 - 108 - 69  [0.430] 250
The two together is a small gain of 10 elo +/- 24:

Code: Select all

Score of New vs Old: 230 - 213 - 138  [0.515] 581
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 ...)

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.
ZirconiumX wrote:[...] I haven't found the combination just yet.
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:
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.

Dann Corbit
Posts: 8672
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Move ordering

Post by Dann Corbit » Fri Nov 10, 2017 1:28 am

Sven wrote:
ZirconiumX wrote:
jwes wrote:Deferring captures of lower-valued pieces was a loss of about 25 elo +/- 37:

Code: Select all

Score of New vs Old: 84 - 103 - 63  [0.462] 250
Deferring captures of defended squares was a loss of about 50 elo +/- 37:

Code: Select all

Score of New vs Old: 73 - 108 - 69  [0.430] 250
The two together is a small gain of 10 elo +/- 24:

Code: Select all

Score of New vs Old: 230 - 213 - 138  [0.515] 581
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 ...)

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.
ZirconiumX wrote:[...] I haven't found the combination just yet.
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:
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.
But be careful about positions like this, where there is a sequence of captures, especially in qs:
[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.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Move ordering

Post by ZirconiumX » Fri Nov 10, 2017 7:00 pm

Sven wrote:[lots of useful information I probably should have thought about earlier, as Sven is very good at doing]
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.

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
I'll now go and test the patches individually.

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.

Sven
Posts: 3578
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Move ordering

Post by Sven » Sat Nov 11, 2017 11:40 am

Dann Corbit wrote:
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.
But be careful about positions like this, where there is a sequence of captures, especially in qs:
[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.
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
Posts: 8672
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Move ordering

Post by Dann Corbit » Sat Nov 11, 2017 9:07 pm

Sven wrote:
Dann Corbit wrote:
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.
But be careful about positions like this, where there is a sequence of captures, especially in qs:
[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.
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.
After exf3, BxQ
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.

Sven
Posts: 3578
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Move ordering

Post by Sven » Sun Nov 12, 2017 11:10 am

Dann Corbit wrote:
Sven wrote:
Dann Corbit wrote:
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.
But be careful about positions like this, where there is a sequence of captures, especially in qs:
[...]

I guess that skipping the qs and reducing the depth cause problems in positions like the above.
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.
After exf3, BxQ
Losing captures, in the context we are discussing here, can only be "high takes low" captures.

Post Reply