Effect of MVV/LVA

[mathmoi]

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,

[sje]

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?

1) Transposition
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.

[Michael Sherwin]

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,

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!! JMO

[mathmoi]

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.

[mathmoi]

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?

1) Transposition
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.

Hi Steven,

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.

[xsadar]

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.

[bob]

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?

1) Transposition
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.

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...

[mcostalba]

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.

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.

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

[Aleks Peshkov]

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.

[hgm]

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.