Move ordering

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

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

Move ordering

Post by ZirconiumX » Thu Nov 09, 2017 1:39 pm

Manik is convinced that there is a bug in the move ordering code of Dorpsgek due to having a comparatively low fail-high on first move rate (I ran a self-play game to depth 8 and got an average of 84.8%), and after a couple of months of not being motivated, I thought I'd ask the CCC.

My move ordering at a high level looks like this:
- TT moves. (dynamically scored within search)
- Capture-promotions, ordered by MVV/LVA and promotion piece.
- All captures, ordered by MVV/LVA. (Manik thinks I should search LxH, then ExE, then HxL, but he only judged this by piece value since I don't have a SEE)
- Killer moves - first the killers from this ply, then the killers from 2 plies ago (dynamically updated in search).
- Promotions, ordered by promotion piece.
- The rest of the quiet moves, ordered by the relative history heuristic.

My static move ordering code (MVV/LVA, history heuristic, promotion scoring) can be found here. The dynamic search update code (TT move, killers) can be found here.

Can anybody spot any bugs that I might have missed?
Some believe in the almighty dollar.

I believe in the almighty printf statement.

elpapa
Posts: 184
Joined: Sun Jan 18, 2009 10:27 pm
Location: Sweden

Re: Move ordering

Post by elpapa » Thu Nov 09, 2017 2:44 pm

I use the following formula for MVV/LVA:

Code: Select all

score += pieceval[captured_piece] * 8 - pieceval[own_piece]
Or maybe * 16, I don't remember, but I think * 8 is enough using traditional piece values.

Looking at your code it seems you just subtract one value from the other which must be wrong.

Ferdy
Posts: 3571
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Move ordering

Post by Ferdy » Thu Nov 09, 2017 2:57 pm

ZirconiumX wrote:Manik is convinced that there is a bug in the move ordering code of Dorpsgek due to having a comparatively low fail-high on first move rate (I ran a self-play game to depth 8 and got an average of 84.8%), and after a couple of months of not being motivated, I thought I'd ask the CCC.

My move ordering at a high level looks like this:
- TT moves. (dynamically scored within search)
- Capture-promotions, ordered by MVV/LVA and promotion piece.
- All captures, ordered by MVV/LVA. (Manik thinks I should search LxH, then ExE, then HxL, but he only judged this by piece value since I don't have a SEE)
- Killer moves - first the killers from this ply, then the killers from 2 plies ago (dynamically updated in search).
- Promotions, ordered by promotion piece.
- The rest of the quiet moves, ordered by the relative history heuristic.

My static move ordering code (MVV/LVA, history heuristic, promotion scoring) can be found here. The dynamic search update code (TT move, killers) can be found here.

Can anybody spot any bugs that I might have missed?
Try to check the max score of history.

Code: Select all

} else {
	value += HistoryScore(b, m);
	assert&#40;HistoryScore&#40;b, m&#41; < 20000&#41;;
	return value;
&#125;

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

Re: Move ordering

Post by ZirconiumX » Thu Nov 09, 2017 3:06 pm

elpapa wrote:I use the following formula for MVV/LVA:

Code: Select all

score += pieceval&#91;captured_piece&#93; * 8 - pieceval&#91;own_piece&#93;
Or maybe * 16, I don't remember, but I think * 8 is enough using traditional piece values.

Looking at your code it seems you just subtract one value from the other which must be wrong.
The actual code for MVV/LVA I have is this:

Code: Select all

        value += piecevals&#91;GetPieceByBit&#40;b, Bitlist&#123;b->index&#91;m.dest&#93;&#125;)&#93; -
&#40;6 - GetPieceByBit&#40;b, Bitlist&#123;b->index&#91;m.from&#93;&#125;));
The 6 - piece_type is because a King = 0 and a Pawn = 5 in my engine. I'm reasonably sure that's okay.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

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

Re: Move ordering

Post by ZirconiumX » Thu Nov 09, 2017 3:19 pm

Ferdy wrote:
ZirconiumX wrote:Manik is convinced that there is a bug in the move ordering code of Dorpsgek due to having a comparatively low fail-high on first move rate (I ran a self-play game to depth 8 and got an average of 84.8%), and after a couple of months of not being motivated, I thought I'd ask the CCC.

My move ordering at a high level looks like this:
- TT moves. (dynamically scored within search)
- Capture-promotions, ordered by MVV/LVA and promotion piece.
- All captures, ordered by MVV/LVA. (Manik thinks I should search LxH, then ExE, then HxL, but he only judged this by piece value since I don't have a SEE)
- Killer moves - first the killers from this ply, then the killers from 2 plies ago (dynamically updated in search).
- Promotions, ordered by promotion piece.
- The rest of the quiet moves, ordered by the relative history heuristic.

My static move ordering code (MVV/LVA, history heuristic, promotion scoring) can be found here. The dynamic search update code (TT move, killers) can be found here.

Can anybody spot any bugs that I might have missed?
Try to check the max score of history.

Code: Select all

&#125; else &#123;
	value += HistoryScore&#40;b, m&#41;;
	assert&#40;HistoryScore&#40;b, m&#41; < 20000&#41;;
	return value;
&#125;
I ran a quick depth-8 self-play, recording the maximum history score encountered and printing it after every search. I got a peak of 1,515, which is well within the boundaries of the search (the second killer move from two plies ago gets a score of 15,500, for example).

However, I'm still going to add a check for individual table overflow, just to be sure.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
hgm
Posts: 22082
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: Move ordering

Post by hgm » Thu Nov 09, 2017 3:40 pm

The sensible approach would be to make some sampling of cut moves that were not tried first, and investigate why it was that they were not tried first, and if this could have been foreseen.

jwes
Posts: 772
Joined: Sat Jul 01, 2006 5:11 am

Re: Move ordering

Post by jwes » Thu Nov 09, 2017 3:42 pm

ZirconiumX wrote:Manik is convinced that there is a bug in the move ordering code of Dorpsgek due to having a comparatively low fail-high on first move rate (I ran a self-play game to depth 8 and got an average of 84.8%), and after a couple of months of not being motivated, I thought I'd ask the CCC.

My move ordering at a high level looks like this:
- TT moves. (dynamically scored within search)
- Capture-promotions, ordered by MVV/LVA and promotion piece.
- All captures, ordered by MVV/LVA. (Manik thinks I should search LxH, then ExE, then HxL, but he only judged this by piece value since I don't have a SEE)
- Killer moves - first the killers from this ply, then the killers from 2 plies ago (dynamically updated in search).
- Promotions, ordered by promotion piece.
- The rest of the quiet moves, ordered by the relative history heuristic.

My static move ordering code (MVV/LVA, history heuristic, promotion scoring) can be found here. The dynamic search update code (TT move, killers) can be found here.

Can anybody spot any bugs that I might have missed?
You don't appear to distinguish between winning and losing captures. If you move losing captures to the end, it should help greatly. If you don't have SEE, even something simple like captures of unprotected pieces or pieces of higher or equal value first would help. Promotion to a queen should be in with winning captures, but that won't matter much.

User avatar
asanjuan
Posts: 206
Joined: Thu Sep 01, 2011 3:38 pm
Location: Seville, Spain

Re: Move ordering

Post by asanjuan » Thu Nov 09, 2017 3:59 pm

ZirconiumX wrote:Manik is convinced that there is a bug in the move ordering code of Dorpsgek due to having a comparatively low fail-high on first move rate (I ran a self-play game to depth 8 and got an average of 84.8%), and after a couple of months of not being motivated, I thought I'd ask the CCC.

My move ordering at a high level looks like this:
- TT moves. (dynamically scored within search)
- Capture-promotions, ordered by MVV/LVA and promotion piece.
- All captures, ordered by MVV/LVA. (Manik thinks I should search LxH, then ExE, then HxL, but he only judged this by piece value since I don't have a SEE)
- Killer moves - first the killers from this ply, then the killers from 2 plies ago (dynamically updated in search).
- Promotions, ordered by promotion piece.
- The rest of the quiet moves, ordered by the relative history heuristic.

My static move ordering code (MVV/LVA, history heuristic, promotion scoring) can be found here. The dynamic search update code (TT move, killers) can be found here.

Can anybody spot any bugs that I might have missed?
I consider promotions AND captures in the same stage.
Even if the promotion doesn't capture anything. Also, I set a MVV/LVA for them as ([promotion_type_value] - [pawn_value] + ([captured_piece_value]-1)).

So every promotion is considered before killers.

Also, i'm using SEE to set the losing captures at the end of the list as long as they are being processed in the move list.

Works well.

elpapa
Posts: 184
Joined: Sun Jan 18, 2009 10:27 pm
Location: Sweden

Re: Move ordering

Post by elpapa » Thu Nov 09, 2017 4:48 pm

ZirconiumX wrote:The actual code for MVV/LVA I have is this:

Code: Select all

        value += piecevals&#91;GetPieceByBit&#40;b, Bitlist&#123;b->index&#91;m.dest&#93;&#125;)&#93; -
&#40;6 - GetPieceByBit&#40;b, Bitlist&#123;b->index&#91;m.from&#93;&#125;));
The 6 - piece_type is because a King = 0 and a Pawn = 5 in my engine. I'm reasonably sure that's okay.
Agreed. I misread the code. I don't really like it, but functionally it's correct.

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

Re: Move ordering

Post by ZirconiumX » Thu Nov 09, 2017 6:49 pm

jwes wrote:
ZirconiumX wrote:Manik is convinced that there is a bug in the move ordering code of Dorpsgek due to having a comparatively low fail-high on first move rate (I ran a self-play game to depth 8 and got an average of 84.8%), and after a couple of months of not being motivated, I thought I'd ask the CCC.

My move ordering at a high level looks like this:
- TT moves. (dynamically scored within search)
- Capture-promotions, ordered by MVV/LVA and promotion piece.
- All captures, ordered by MVV/LVA. (Manik thinks I should search LxH, then ExE, then HxL, but he only judged this by piece value since I don't have a SEE)
- Killer moves - first the killers from this ply, then the killers from 2 plies ago (dynamically updated in search).
- Promotions, ordered by promotion piece.
- The rest of the quiet moves, ordered by the relative history heuristic.

My static move ordering code (MVV/LVA, history heuristic, promotion scoring) can be found here. The dynamic search update code (TT move, killers) can be found here.

Can anybody spot any bugs that I might have missed?
You don't appear to distinguish between winning and losing captures. If you move losing captures to the end, it should help greatly. If you don't have SEE, even something simple like captures of unprotected pieces or pieces of higher or equal value first would help. Promotion to a queen should be in with winning captures, but that won't matter much.
Deferring captures of lower-valued pieces was a loss of about 25 elo +/- 37:

Code: Select all

Score of New vs Old&#58; 84 - 103 - 63  &#91;0.462&#93; 250
Deferring captures of defended squares was a loss of about 50 elo +/- 37:

Code: Select all

Score of New vs Old&#58; 73 - 108 - 69  &#91;0.430&#93; 250
The two together is a small gain of 10 elo +/- 24:

Code: Select all

Score of New vs Old&#58; 230 - 213 - 138  &#91;0.515&#93; 581
I think you're definitely right, but I haven't found the combination just yet.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Post Reply