Hi,
My chess engine used a simple AlphaBeta search without QSearch. It used to search the TT move, followed by captures (in no particular order) and finnaly the remainings moves.
Now I added MVV/LVA (the captures are now ordered) and I'm disapointed of the result. When I run a benchmark on 5 differents positions for about 1 minute, the MVV/LVA version does search 381.3M nodes while the non-MVV/LVA version searches 383.5M nodes. That's only a reduction of 0.6% of the nodes.
I think there is something wrong with what I'm doing. Or is MVV/LVA that innefective?
If i'm doing something wrong, how much of an improvment should I get?
Thanks for your help,
Effect of MVV/LVA
Moderators: hgm, Rebel, chrisw
-
- Posts: 290
- Joined: Mon Mar 13, 2006 5:23 pm
- Location: Québec
Effect of MVV/LVA
Mathieu Pagé
mathieu@mathieupage.com
mathieu@mathieupage.com
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Effect of MVV/LVA
1) Transpositionmathmoi wrote:When I run a benchmark on 5 differents positions for about 1 minute, the MVV/LVA version does search 381.3M nodes while the non-MVV/LVA version searches 383.5M nodes. That's only a reduction of 0.6% of the nodes.
I think there is something wrong with what I'm doing. Or is MVV/LVA that innefective?
If i'm doing something wrong, how much of an improvment should I get?
2) MVV/LVA for expected gain >= 0
3) Killer moves
4) Non gaining moves by history heuristic
5) MVV/LVA for negative expected gain
The above ordering should give you a significant improvement in time to depth. But it doesn't reduce the node count; it just makes the program stronger because less nodes are needed to reach a given depth.
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: Effect of MVV/LVA
Because, you do not have a qsearch I assume that your engine does not search very deep in a reasonable aount of time. The values backed up in the search tree when there is no qsearch tend to be very inaccurate and therefore alpha-beta does not work very well. First, write a qsearch! Then worry about better move ordering!! JMOmathmoi wrote:Hi,
My chess engine used a simple AlphaBeta search without QSearch. It used to search the TT move, followed by captures (in no particular order) and finnaly the remainings moves.
Now I added MVV/LVA (the captures are now ordered) and I'm disapointed of the result. When I run a benchmark on 5 differents positions for about 1 minute, the MVV/LVA version does search 381.3M nodes while the non-MVV/LVA version searches 383.5M nodes. That's only a reduction of 0.6% of the nodes.
I think there is something wrong with what I'm doing. Or is MVV/LVA that innefective?
If i'm doing something wrong, how much of an improvment should I get?
Thanks for your help,
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 290
- Joined: Mon Mar 13, 2006 5:23 pm
- Location: Québec
Re: Effect of MVV/LVA
Hi Michael,
I was suspecting that. I was not sure though.
I'll implement my QSearch next before I revisit my MVV/LVA effiency.
Thanks.
I was suspecting that. I was not sure though.
I'll implement my QSearch next before I revisit my MVV/LVA effiency.
Thanks.
Mathieu Pagé
mathieu@mathieupage.com
mathieu@mathieupage.com
-
- Posts: 290
- Joined: Mon Mar 13, 2006 5:23 pm
- Location: Québec
Re: Effect of MVV/LVA
Hi Steven,sje wrote:1) Transpositionmathmoi wrote:When I run a benchmark on 5 differents positions for about 1 minute, the MVV/LVA version does search 381.3M nodes while the non-MVV/LVA version searches 383.5M nodes. That's only a reduction of 0.6% of the nodes.
I think there is something wrong with what I'm doing. Or is MVV/LVA that innefective?
If i'm doing something wrong, how much of an improvment should I get?
2) MVV/LVA for expected gain >= 0
3) Killer moves
4) Non gaining moves by history heuristic
5) MVV/LVA for negative expected gain
The above ordering should give you a significant improvement in time to depth. But it doesn't reduce the node count; it just makes the program stronger because less nodes are needed to reach a given depth.
I don't have killer and history heuristic implemented yet. However I'll try to follow you advice on ordering "MVV/LVA for negative expected gain" after the normals moves.
Thanks for your help.
Mathieu Pagé
mathieu@mathieupage.com
mathieu@mathieupage.com
-
- Posts: 147
- Joined: Wed Jun 06, 2007 10:01 am
- Location: United States
- Full name: Mike Leany
Re: Effect of MVV/LVA
Also, qsearch is, of course, where you will get the most direct benefit from capture move ordering, since all moves in qsearch are captures and most moves in main search are not.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Effect of MVV/LVA
MVV/LVA doesn't give you an "expected gain". It takes the most valuable piece that can be captured, which might be a rook, and then captures it with the least valuable attacker, which might be a queen. But you have no idea whether you are winning a rook, or losing the queen for a rook...sje wrote:1) Transpositionmathmoi wrote:When I run a benchmark on 5 differents positions for about 1 minute, the MVV/LVA version does search 381.3M nodes while the non-MVV/LVA version searches 383.5M nodes. That's only a reduction of 0.6% of the nodes.
I think there is something wrong with what I'm doing. Or is MVV/LVA that innefective?
If i'm doing something wrong, how much of an improvment should I get?
2) MVV/LVA for expected gain >= 0
3) Killer moves
4) Non gaining moves by history heuristic
5) MVV/LVA for negative expected gain
The above ordering should give you a significant improvement in time to depth. But it doesn't reduce the node count; it just makes the program stronger because less nodes are needed to reach a given depth.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Effect of MVV/LVA
I am new to chess programming so probably my question is very silly, but I imagine that adding some more computation, as is MVV/LVA, lowers the searched nodes, not increment them.mathmoi wrote:Hi,
Now I added MVV/LVA (the captures are now ordered) and I'm disapointed of the result. When I run a benchmark on 5 differents positions for about 1 minute, the MVV/LVA version does search 381.3M nodes while the non-MVV/LVA version searches 383.5M nodes. That's only a reduction of 0.6% of the nodes.
What it counts is that, although node searched are less search depth is higher due to a higher number of cut-offs because of the cleaverer search.
So I would expect that introducing MVV/LVA lowers the node count but gives a better maximum searched depth.
Am I missing something obvious ?
Thanks
Marco
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: Effect of MVV/LVA
I am thinking for a long time about trying something better then plain MVV/LVA, but without SSE pseudo-search.
For example, captures of last moved piece is probably worse to try first, before any other victims.
Thinking further, I am about reshuffling piece-lists each node (because I generate captures incrementally in piece-list order). Piece-list reordering is a heuristic similar but different from killer and history.
For example, captures of last moved piece is probably worse to try first, before any other victims.
Thinking further, I am about reshuffling piece-lists each node (because I generate captures incrementally in piece-list order). Piece-list reordering is a heuristic similar but different from killer and history.
-
- Posts: 27848
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Effect of MVV/LVA
Without QS, you basiclly have a fixed-depth search, and there is little to be gained by ordering the moves. MVV/LVA gives a huge improvement over random ordering, because it tends to reduce the number of captures in the end leaves, by quickly eliminating any Queens that start on a rampage in enemy territory.
Without QS you would not benifit from that. You would not benifit from putting the best move first anyway, as on the next iteration this 'best' move is usually very bad: it was specfically designed to make it impossible for the opponent to avoid you initiating a piece trade at the horizon, which he was then not allowed to recapture. But one ply deeper he can recapture, and all the goals you have been striving for (usually QxB or QxN captures, as those are almost impossible to avoid) suddenly are heavily losing, as he will have tht extra move to recapture the Queen.
Without QS you would not benifit from that. You would not benifit from putting the best move first anyway, as on the next iteration this 'best' move is usually very bad: it was specfically designed to make it impossible for the opponent to avoid you initiating a piece trade at the horizon, which he was then not allowed to recapture. But one ply deeper he can recapture, and all the goals you have been striving for (usually QxB or QxN captures, as those are almost impossible to avoid) suddenly are heavily losing, as he will have tht extra move to recapture the Queen.