How much improvement from PVS?

[xsadar]

Roughly, what's the range of Elo improvement I should get after changing from alpha-beta to PVS? I finally got around to implementing PVS, but see no Elo difference after testing. (My old version actually performed ever so slightly better.) I ran an engine vs world test with 480 games games each with no measurable difference. So I'm wondering if my implementation is buggy, my testing is flawed, or maybe I'm expecting too much improvement, in which case I need more games. Or perhaps even some combination of the above problems.

Here are the results from ELOstat:

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 Matheus-2.3                    :  180   58  56   160    76.9 %    -28   15.0 %
  2 BikJump v1.8 (64-bit)          :  119   53  52   160    70.0 %    -28   17.5 %
  3 umax4.8                        :   70   50  50   160    63.7 %    -28   20.0 %
  4 Heracles 0.6.16                :  -22   49  49   160    50.9 %    -28   18.1 %
  5 zilch-0.0.0.3a                 :  -25   28  28   480    43.0 %     24   20.2 %
  6 zilch-0.0.0.4                  :  -27   28  28   480    42.8 %     24   21.0 %
  7 Smash 1.0.3                    :  -74   50  50   160    43.4 %    -28   15.6 %
  8 cilian-x86_64                  : -117   43  44   160    37.5 %    -28   37.5 %

Edit: zilch-0.0.0.3a is my engine with alpha-beta zilch-0.0.0.4 is with PVS.

[Dann Corbit]

Roughly, what's the range of Elo improvement I should get after changing from alpha-beta to PVS? I finally got around to implementing PVS, but see no Elo difference after testing. (My old version actually performed ever so slightly better.) I ran an engine vs world test with 480 games games each with no measurable difference. So I'm wondering if my implementation is buggy, my testing is flawed, or maybe I'm expecting too much improvement, in which case I need more games. Or perhaps even some combination of the above problems.

Here are the results from ELOstat:

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 Matheus-2.3                    :  180   58  56   160    76.9 %    -28   15.0 %
  2 BikJump v1.8 (64-bit)          :  119   53  52   160    70.0 %    -28   17.5 %
  3 umax4.8                        :   70   50  50   160    63.7 %    -28   20.0 %
  4 Heracles 0.6.16                :  -22   49  49   160    50.9 %    -28   18.1 %
  5 zilch-0.0.0.3a                 :  -25   28  28   480    43.0 %     24   20.2 %
  6 zilch-0.0.0.4                  :  -27   28  28   480    42.8 %     24   21.0 %
  7 Smash 1.0.3                    :  -74   50  50   160    43.4 %    -28   15.6 %
  8 cilian-x86_64                  : -117   43  44   160    37.5 %    -28   37.5 %

If you don't get a big improvement (I guess you should expect about 50 Elo) then your move ordering is bad. Find out what your pv node fail high rate is on average. It should be over 90%. If you do not usually fail high on the pv nodes, then you will waste lots of time with re-searching.

PVS gains its boost from the zero window searches, but that advantage vanishes if the zero window searches fail high.

What are you currently doing for move ordering?

[BubbaTough]

I guess you should expect about 50 Elo

I expect it will be less than this if you are using aspiration windows.

-Sam

[xsadar]

Roughly, what's the range of Elo improvement I should get after changing from alpha-beta to PVS? I finally got around to implementing PVS, but see no Elo difference after testing. (My old version actually performed ever so slightly better.) I ran an engine vs world test with 480 games games each with no measurable difference. So I'm wondering if my implementation is buggy, my testing is flawed, or maybe I'm expecting too much improvement, in which case I need more games. Or perhaps even some combination of the above problems.

Here are the results from ELOstat:

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 Matheus-2.3                    :  180   58  56   160    76.9 %    -28   15.0 %
  2 BikJump v1.8 (64-bit)          :  119   53  52   160    70.0 %    -28   17.5 %
  3 umax4.8                        :   70   50  50   160    63.7 %    -28   20.0 %
  4 Heracles 0.6.16                :  -22   49  49   160    50.9 %    -28   18.1 %
  5 zilch-0.0.0.3a                 :  -25   28  28   480    43.0 %     24   20.2 %
  6 zilch-0.0.0.4                  :  -27   28  28   480    42.8 %     24   21.0 %
  7 Smash 1.0.3                    :  -74   50  50   160    43.4 %    -28   15.6 %
  8 cilian-x86_64                  : -117   43  44   160    37.5 %    -28   37.5 %

If you don't get a big improvement (I guess you should expect about 50 Elo) then your move ordering is bad. Find out what your pv node fail high rate is on average. It should be over 90%. If you do not usually fail high on the pv nodes, then you will waste lots of time with re-searching.

PVS gains its boost from the zero window searches, but that advantage vanishes if the zero window searches fail high.

What are you currently doing for move ordering?

Thanks for the suggestion. I'll have to check my pv-node fail-high percentage. I would think my move ordering should be good enough to get a decent improvement, but I could be wrong.

My move ordering is currently:
1. Hash move
2. All captures and promotions ordered by MVV/LVA
3. All other moves

[xsadar]

I guess you should expect about 50 Elo

I expect it will be less than this if you are using aspiration windows.

-Sam

No aspiration windows yet.

[hgm]

In fact, if your move ordering is very good, you will also get no improvement from PVS.

I think your estimate of 50 Elo is very optimitic. IIRC Bob once wrote here that Crafty is ~10% faster because of PVS. (But this was long ago, so I might have it wrong.) That would mean only 10 Elo.

My engines did not benefit from PVS, last time I tried. I admit that in combination with LMR, PVS is the most natural thing to do. You will do a re-search anywy at unreduced depth for any score above alpha, so there would not be any benefit from doing the pilot search with an open window. It seems also logical to do that re-search immediately with an open window, as you already have an indication that the search will not fail low. There is no general reason why scores should get lower on deeper search.

[xsadar]

In fact, if your move ordering is very good, you will also get no improvement from PVS.

I think your estimate of 50 Elo is very optimitic. IIRC Bob once wrote here that Crafty is ~10% faster because of PVS. (But this was long ago, so I might have it wrong.) That would mean only 10 Elo.

If that's the case, I'll definitely need more games. Hopefully I can get a response from Bob.

My engines did not benefit from PVS, last time I tried. I admit that in combination with LMR, PVS is the most natural thing to do. You will do a re-search anywy at unreduced depth for any score above alpha, so there would not be any benefit from doing the pilot search with an open window. It seems also logical to do that re-search immediately with an open window, as you already have an indication that the search will not fail low. There is no general reason why scores should get lower on deeper search.

[Dann Corbit]

In fact, if your move ordering is very good, you will also get no improvement from PVS.

I think your estimate of 50 Elo is very optimitic. IIRC Bob once wrote here that Crafty is ~10% faster because of PVS. (But this was long ago, so I might have it wrong.) That would mean only 10 Elo.

If that's the case, I'll definitely need more games. Hopefully I can get a response from Bob.

My engines did not benefit from PVS, last time I tried. I admit that in combination with LMR, PVS is the most natural thing to do. You will do a re-search anywy at unreduced depth for any score above alpha, so there would not be any benefit from doing the pilot search with an open window. It seems also logical to do that re-search immediately with an open window, as you already have an indication that the search will not fail low. There is no general reason why scores should get lower on deeper search.

I guess the most important missing piece of data is what your current "pv node is correct" rate is.

[bob]

Roughly, what's the range of Elo improvement I should get after changing from alpha-beta to PVS? I finally got around to implementing PVS, but see no Elo difference after testing. (My old version actually performed ever so slightly better.) I ran an engine vs world test with 480 games games each with no measurable difference. So I'm wondering if my implementation is buggy, my testing is flawed, or maybe I'm expecting too much improvement, in which case I need more games. Or perhaps even some combination of the above problems.

Here are the results from ELOstat:

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 Matheus-2.3                    :  180   58  56   160    76.9 %    -28   15.0 %
  2 BikJump v1.8 (64-bit)          :  119   53  52   160    70.0 %    -28   17.5 %
  3 umax4.8                        :   70   50  50   160    63.7 %    -28   20.0 %
  4 Heracles 0.6.16                :  -22   49  49   160    50.9 %    -28   18.1 %
  5 zilch-0.0.0.3a                 :  -25   28  28   480    43.0 %     24   20.2 %
  6 zilch-0.0.0.4                  :  -27   28  28   480    42.8 %     24   21.0 %
  7 Smash 1.0.3                    :  -74   50  50   160    43.4 %    -28   15.6 %
  8 cilian-x86_64                  : -117   43  44   160    37.5 %    -28   37.5 %

Edit: zilch-0.0.0.3a is my engine with alpha-beta zilch-0.0.0.4 is with PVS.

PVS is a nominal change. It searches slightly faster, but then has to occasionally re-search to get a true score where normal alpha/beta does not. The advantage is that you will "sniff" out a good move quicker, and if that happens just prior to time running out, PVS will fail high while normal alpha/beta would time out and not play the actual best move. I doubt it is worth more than 10 Elo or something, which means you are going to need 20,000+ games to be able to measure the improvement...

[xsadar]

Roughly, what's the range of Elo improvement I should get after changing from alpha-beta to PVS? I finally got around to implementing PVS, but see no Elo difference after testing. (My old version actually performed ever so slightly better.) I ran an engine vs world test with 480 games games each with no measurable difference. So I'm wondering if my implementation is buggy, my testing is flawed, or maybe I'm expecting too much improvement, in which case I need more games. Or perhaps even some combination of the above problems.

Here are the results from ELOstat:

Code: Select all

    Program                          Elo    +   -   Games   Score   Av.Op.  Draws

  1 Matheus-2.3                    :  180   58  56   160    76.9 %    -28   15.0 %
  2 BikJump v1.8 (64-bit)          :  119   53  52   160    70.0 %    -28   17.5 %
  3 umax4.8                        :   70   50  50   160    63.7 %    -28   20.0 %
  4 Heracles 0.6.16                :  -22   49  49   160    50.9 %    -28   18.1 %
  5 zilch-0.0.0.3a                 :  -25   28  28   480    43.0 %     24   20.2 %
  6 zilch-0.0.0.4                  :  -27   28  28   480    42.8 %     24   21.0 %
  7 Smash 1.0.3                    :  -74   50  50   160    43.4 %    -28   15.6 %
  8 cilian-x86_64                  : -117   43  44   160    37.5 %    -28   37.5 %

Edit: zilch-0.0.0.3a is my engine with alpha-beta zilch-0.0.0.4 is with PVS.

PVS is a nominal change. It searches slightly faster, but then has to occasionally re-search to get a true score where normal alpha/beta does not. The advantage is that you will "sniff" out a good move quicker, and if that happens just prior to time running out, PVS will fail high while normal alpha/beta would time out and not play the actual best move. I doubt it is worth more than 10 Elo or something, which means you are going to need 20,000+ games to be able to measure the improvement...

Hmm... The way people talk about PVS I thought (and hoped) it would be more of an improvement than that. So, since around 20,000 games is generally impractical, is it best to just assume that if you're not getting too many re-searches and the average time to depth decreases, that it's probably implemented properly and is thus an improvement? Or how is the best way to verify your implementation?