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?
Move ordering
Moderators: hgm, Rebel, chrisw
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Move ordering
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 211
- Joined: Sun Jan 18, 2009 11:27 pm
- Location: Sweden
- Full name: Patrik Karlsson
Re: Move ordering
I use the following formula for MVV/LVA:
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.
Code: Select all
score += pieceval[captured_piece] * 8 - pieceval[own_piece]
Looking at your code it seems you just subtract one value from the other which must be wrong.
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Move ordering
Try to check the max score of history.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?
Code: Select all
} else {
value += HistoryScore(b, m);
assert(HistoryScore(b, m) < 20000);
return value;
}
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Move ordering
The actual code for MVV/LVA I have is this:elpapa wrote:I use the following formula for MVV/LVA:
Or maybe * 16, I don't remember, but I think * 8 is enough using traditional piece values.Code: Select all
score += pieceval[captured_piece] * 8 - pieceval[own_piece]
Looking at your code it seems you just subtract one value from the other which must be wrong.
Code: Select all
value += piecevals[GetPieceByBit(b, Bitlist{b->index[m.dest]})] -
(6 - GetPieceByBit(b, Bitlist{b->index[m.from]}));
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Move ordering
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).Ferdy wrote:Try to check the max score of history.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?
Code: Select all
} else { value += HistoryScore(b, m); assert(HistoryScore(b, m) < 20000); return value; }
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.
I believe in the almighty printf statement.
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering
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.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Move ordering
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.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?
-
- Posts: 214
- Joined: Thu Sep 01, 2011 5:38 pm
- Location: Seville, Spain
Re: Move ordering
I consider promotions AND captures in the same stage.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?
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.
Still learning how to play chess...
knigths move in "L" shape ¿right?
knigths move in "L" shape ¿right?
-
- Posts: 211
- Joined: Sun Jan 18, 2009 11:27 pm
- Location: Sweden
- Full name: Patrik Karlsson
Re: Move ordering
Agreed. I misread the code. I don't really like it, but functionally it's correct.ZirconiumX wrote:The actual code for MVV/LVA I have is this:The 6 - piece_type is because a King = 0 and a Pawn = 5 in my engine. I'm reasonably sure that's okay.Code: Select all
value += piecevals[GetPieceByBit(b, Bitlist{b->index[m.dest]})] - (6 - GetPieceByBit(b, Bitlist{b->index[m.from]}));
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Move ordering
Deferring captures of lower-valued pieces was a loss of about 25 elo +/- 37:jwes wrote: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.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?
Code: Select all
Score of New vs Old: 84 - 103 - 63 [0.462] 250
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
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.