TalkChess.com

Computer Chess Club
https://talkchess.com/

Move ordering

https://talkchess.com/viewtopic.php?t=65675

Page 1 of 2

Move ordering

Posted: Thu Nov 09, 2017 2:39 pm
by ZirconiumX
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?

Re: Move ordering

Posted: Thu Nov 09, 2017 3:44 pm
by elpapa
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 3:57 pm
by Ferdy
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;

Re: Move ordering

Posted: Thu Nov 09, 2017 4:06 pm
by ZirconiumX
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 4:19 pm
by ZirconiumX
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 4:40 pm
by hgm
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 4:42 pm
by jwes
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 4:59 pm
by asanjuan
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 5:48 pm
by elpapa
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.

Re: Move ordering

Posted: Thu Nov 09, 2017 7:49 pm
by ZirconiumX
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.
All times are UTC+02:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited