Effect of MVV/LVA

[Sven]

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.

Hi Mathieu,

taking your words exactly as you have written them, the main reason for your disappointment is probably your wrong measurement, and that seems to be what most other posters in this thread have missed.

Change your measurement such that you search to a fixed depth, not a fixed total time, and then you should get what you expected. Your current measurement is "nodes per second" which should be quite independent from the method of move ordering. What you want to measure is that you need less nodes for the same number of search iterations, i.e. that your search skips more subtrees due to better ordering.

Of course it is true that you will also need a QSearch to reach some minimum level of acceptance in playing strength for your engine. But that should not affect your "benchmark" too much, as also a "bad search" (without QSearch) to fixed depth N with better move ordering will need less nodes than the same "bad search" to same depth with worse move ordering. QSearch improves by minimizing the horizon effect but there are usually enough bad captures close to the root of the full search that can be rejected much faster with reasonable ordering of the opponent's capture moves than with random ordering, often enough independent from what will happen at the horizon.

It would be nice if you could confirm all this with results of your measurements after switching to "fixed depth".

Sven

[mathmoi]

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

Hi Marco, you are absolutely right.

What I did not say in my original post, that I should have, is that the searchs were to a fixed depth. In that case I expect to need less nodes to complete the search with MVV/LVA.

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

Hi Mathieu,

taking your words exactly as you have written them, the main reason for your disappointment is probably your wrong measurement, and that seems to be what most other posters in this thread have missed.

Change your measurement such that you search to a fixed depth, not a fixed total time, and then you should get what you expected. Your current measurement is "nodes per second" which should be quite independent from the method of move ordering. What you want to measure is that you need less nodes for the same number of search iterations, i.e. that your search skips more subtrees due to better ordering.

Of course it is true that you will also need a QSearch to reach some minimum level of acceptance in playing strength for your engine. But that should not affect your "benchmark" too much, as also a "bad search" (without QSearch) to fixed depth N with better move ordering will need less nodes than the same "bad search" to same depth with worse move ordering. QSearch improves by minimizing the horizon effect but there are usually enough bad captures close to the root of the full search that can be rejected much faster with reasonable ordering of the opponent's capture moves than with random ordering, often enough independent from what will happen at the horizon.

It would be nice if you could confirm all this with results of your measurements after switching to "fixed depth".

Sven

Hi Sven,

I'm sorry, I did not express myself clearly. The test I did were indeed fixed depth searches. What I meant is that they need about 1 minutes to complete.

Thanks for your help

[mcostalba]

It would be nice if you could confirm all this with results of your measurements after switching to "fixed depth".

Sven

Hi Sven,

I'm sorry, I did not express myself clearly. The test I did were indeed fixed depth searches. What I meant is that they need about 1 minutes to complete.

Sorry, but I ask again, it helps me to understand.

If you search at fixed depth IMHO what counts is the time it takes to finish at a given depth, not the node count, becuase you can have lower node count with MVV/LVA simply because your implementation of ordering is very slow compared to the original code, so that node crunching speed is lower.

A fair comparison could be IMHO "How much time it takes to complete a search to a given depth with and without the ordering"

This test wheigth the two conditions "togheter": MVV/LVA is slower but this is more then compensated by more cutoffs achiavable.

Or "MVV/LVA is slower AND this is NOT enough compensated by more cut/off achivable"

Is it wrong?

Thanks
Marco

[mathmoi]

It would be nice if you could confirm all this with results of your measurements after switching to "fixed depth".

Sven

Hi Sven,

I'm sorry, I did not express myself clearly. The test I did were indeed fixed depth searches. What I meant is that they need about 1 minutes to complete.

Sorry, but I ask again, it helps me to understand.

If you search at fixed depth IMHO what counts is the time it takes to finish at a given depth, not the node count, becuase you can have lower node count with MVV/LVA simply because your implementation of ordering is very slow compared to the original code, so that node crunching speed is lower.

A fair comparison could be IMHO "How much time it takes to complete a search to a given depth with and without the ordering"

This test wheigth the two conditions "togheter": MVV/LVA is slower but this is more then compensated by more cutoffs achiavable.

Or "MVV/LVA is slower AND this is NOT enough compensated by more cut/off achivable"

Is it wrong?

Thanks
Marco

Hi Marco,

You're still right.

However, the improvment in "time it takes to complete a search to a given depth" was as low as the improvment in nodes required. The improvment in time was about 1-2%.

[CThinker]

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,

My experience is that, more complex move ordering slows down the search. However, it leads to a smaller search tree (assuming that the move ordering is actually sound).

[Sven]

Hi Mathieu,

I have to correct my last posting regarding the influence of QSearch on MVV/LVA. I checked with my current engine code and found that MVV/LVA indeed seems to help a bit more when you have a QSearch. My results look like this (initial chess position):

Code: Select all

MVV_LVA QSEARCH depth sec   nodes      %nodes
no      no      8     28,86 19.551.005 100%
no      yes     8     18,79 11.729.256 100%
yes     no      8     27,74 19.021.764  97%
yes     yes     8     15,06  9.102.224  78%

The current development version of my new engine (which is far from being released) has 0x88 board, nullmove, no TT yet, and for this test I switched off killer move and history heuristic to have similar conditions like you have. In the non-MVV/LVA version all captures and promotions are tried prior to all other moves, in the order they are generated.

My node counts are ridicolous without TT, of course.

In your case the presence of a hash table might result in even less improvement by MVV/LVA since the original ordering is already quite good when trying the hash move first.

Sorry if I had confused you a bit.

Sven

[mathmoi]

Hi Mathieu,

I have to correct my last posting regarding the influence of QSearch on MVV/LVA. I checked with my current engine code and found that MVV/LVA indeed seems to help a bit more when you have a QSearch. My results look like this (initial chess position):

Code: Select all

MVV_LVA QSEARCH depth sec   nodes      %nodes
no      no      8     28,86 19.551.005 100%
no      yes     8     18,79 11.729.256 100%
yes     no      8     27,74 19.021.764  97%
yes     yes     8     15,06  9.102.224  78%

The current development version of my new engine (which is far from being released) has 0x88 board, nullmove, no TT yet, and for this test I switched off killer move and history heuristic to have similar conditions like you have. In the non-MVV/LVA version all captures and promotions are tried prior to all other moves, in the order they are generated.

My node counts are ridicolous without TT, of course.

In your case the presence of a hash table might result in even less improvement by MVV/LVA since the original ordering is already quite good when trying the hash move first.

Sorry if I had confused you a bit.

Sven

Hi Sven,

Theses numbers seems to confirm that MVV/LVA only improve the "time to depth" slighly when a QSearch is not present. In this case you get an improvment of about 4%. So my implementation is probably correct.

Thanks for your help and for taking the time to run thoses tests.