Probcut

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
gladius
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Probcut

Post by gladius » Fri May 24, 2013 5:15 am

I'm trying an experiment with Probcut http://chessprogramming.wikispaces.com/ProbCut on Stockfish. I took 55000 positions from games, and tried depth 15 searches, recording the scores at each move. Then did a least squares fit, predicting how well the scores of the low depth search predicts the high depth searches.

SF uses a depth reduction of 4 for probcut, and the fitted values are below. I used a simple formula, instead of the static reduction that SF currently uses. Should be interesting to see how it goes!

https://github.com/glinscott/Stockfish/ ... ...46b0441

Code: Select all

lo hi   slope  off  stdev
 1  5 -   0.9 -11.3  62.2
 2  6 -   0.9  -3.2  57.8
 3  7 -   0.9  -5.4  56.3
 4  8 -   0.9  -1.0  62.4
 5  9 -   1.0  -3.6  44.3
 6 10 -   1.0  -1.1  64.0
 7 11 -   1.0  -1.1  83.7
 8 12 -   1.1  -0.8 110.9
 9 13 -   1.2  -0.1 136.0
10 14 -   1.2  -0.1 166.3
11 15 -   1.2   0.3 177.6
The code (a giant mess!) is here https://gist.github.com/glinscott/5641353.

Here is the output for all depth pairs up to 15.

Code: Select all

lo hi   slope  off  stdev
 1  2 -   0.9 -11.1  34.8
 1  3 -   0.9  -8.6  42.6
 1  4 -   0.9 -13.1  61.0
 1  5 -   0.9 -11.3  62.2
 1  6 -   0.9 -13.5  65.6
 1  7 -   0.9 -13.6  69.1
 1  8 -   0.9 -14.2  72.3
 1  9 -   0.9 -14.8  76.1
 1 10 -   0.9 -14.8  92.5
 1 11 -   0.9 -15.1 112.4
 1 12 -   0.9 -15.8 138.8
 1 13 -   1.0 -15.9 170.2
 1 14 -   1.0 -16.5 201.5
 1 15 -   1.0 -16.7 223.8
 2  3 -   1.0   2.3  31.4
 2  4 -   0.9  -2.6  51.6
 2  5 -   0.9  -0.8  54.7
 2  6 -   0.9  -3.2  57.8
 2  7 -   0.9  -3.3  62.0
 2  8 -   0.9  -3.9  65.3
 2  9 -   0.9  -4.4  69.3
 2 10 -   0.9  -4.3  86.8
 2 11 -   1.0  -4.5 107.5
 2 12 -   1.0  -4.9 134.5
 2 13 -   1.0  -4.6 166.3
 2 14 -   1.1  -4.8 198.0
 2 15 -   1.1  -4.7 220.3
 3  4 -   1.0  -4.7  45.3
 3  5 -   1.0  -3.0  47.6
 3  6 -   1.0  -5.3  52.2
 3  7 -   0.9  -5.4  56.3
 3  8 -   1.0  -6.0  59.9
 3  9 -   1.0  -6.6  63.9
 3 10 -   1.0  -6.5  82.5
 3 11 -   1.0  -6.7 103.6
 3 12 -   1.0  -7.2 131.1
 3 13 -   1.1  -7.1 162.7
 3 14 -   1.1  -7.4 194.6
 3 15 -   1.1  -7.4 217.2
 4  5 -   0.9   2.1  51.6
 4  6 -   0.9  -0.3  55.0
 4  7 -   0.9  -0.4  59.3
 4  8 -   0.9  -1.0  62.4
 4  9 -   0.9  -1.5  66.2
 4 10 -   0.9  -1.4  84.1
 4 11 -   0.9  -1.5 104.7
 4 12 -   1.0  -1.8 131.9
 4 13 -   1.0  -1.6 162.8
 4 14 -   1.1  -1.6 194.8
 4 15 -   1.1  -1.4 217.2
 5  6 -   1.0  -2.3  26.1
 5  7 -   1.0  -2.5  34.0
 5  8 -   1.0  -3.1  39.2
 5  9 -   1.0  -3.6  44.3
 5 10 -   1.0  -3.5  67.9
 5 11 -   1.0  -3.7  91.6
 5 12 -   1.1  -4.1 121.0
 5 13 -   1.1  -3.9 153.3
 5 14 -   1.1  -4.0 186.4
 5 15 -   1.2  -4.0 208.5
 6  7 -   1.0  -0.1  26.3
 6  8 -   1.0  -0.7  32.6
 6  9 -   1.0  -1.2  38.8
 6 10 -   1.0  -1.1  64.0
 6 11 -   1.0  -1.2  88.4
 6 12 -   1.1  -1.5 118.2
 6 13 -   1.1  -1.2 150.7
 6 14 -   1.2  -1.3 184.0
 6 15 -   1.2  -1.1 206.2
 7  8 -   1.0  -0.5  22.9
 7  9 -   1.0  -1.1  31.2
 7 10 -   1.0  -1.0  59.3
 7 11 -   1.0  -1.1  83.7
 7 12 -   1.1  -1.4 114.3
 7 13 -   1.1  -1.2 146.1
 7 14 -   1.2  -1.2 179.7
 7 15 -   1.2  -1.1 201.9
 8  9 -   1.0  -0.5  22.4
 8 10 -   1.0  -0.4  54.1
 8 11 -   1.1  -0.5  79.7
 8 12 -   1.1  -0.8 110.9
 8 13 -   1.2  -0.6 142.1
 8 14 -   1.2  -0.6 176.1
 8 15 -   1.3  -0.5 198.2
 9 10 -   1.0   0.1  46.8
 9 11 -   1.1  -0.0  74.1
 9 12 -   1.1  -0.3 105.8
 9 13 -   1.2  -0.1 136.0
 9 14 -   1.2  -0.1 171.3
 9 15 -   1.3   0.1 193.4
10 11 -   1.0  -0.1  55.1
10 12 -   1.1  -0.5  90.2
10 13 -   1.2  -0.2 123.7
10 14 -   1.2  -0.1 166.3
10 15 -   1.2   0.1 188.6
11 12 -   1.0  -0.3  70.3
11 13 -   1.1  -0.1 109.3
11 14 -   1.1   0.0 154.5
11 15 -   1.2   0.3 177.6
12 13 -   1.1   0.3  80.8
12 14 -   1.1   0.4 131.5
12 15 -   1.1   0.6 156.0
13 14 -   1.0   0.0  98.8
13 15 -   1.1   0.2 126.1
14 15 -   1.0   0.2  75.6

User avatar
Ajedrecista
Posts: 1398
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Probcut.

Post by Ajedrecista » Fri May 24, 2013 7:01 pm

Hello Gary:

I am sorry to see that your two attempts of probcut failed at Stage I:

https://github.com/glinscott/Stockfish/ ... ...46b0441

https://github.com/glinscott/Stockfish/ ... ...7d784a0

I do not know anything about C++ and also I do not know anything about chess programming, so I do not know what probcut is (I read a little about it on CPW).

But just taking a look to these pieces of code:

Code: Select all

double slope = 0.9 + &#40;static_cast<double>&#40;depth&#41; / 66.0&#41;;  
double stdev = 20.0 + depth * 5;  
Value rbeta = Value&#40;&#40;static_cast<double>&#40;beta&#41; + stdev * 1.5&#41; / slope&#41;;  
Depth rdepth = depth - 4 * ONE_PLY;

Code: Select all

double slope = 0.9 + &#40;static_cast<double>&#40;depth&#41; / 66.0&#41;;  
double stdev = 50.0 + depth * 6;  
Value rbeta = Value&#40;&#40;static_cast<double>&#40;beta&#41; + stdev&#41; / slope&#41;;  
Depth rdepth = depth - 4 * ONE_PLY;
I see something like rbeta = (beta + T*stdev)/(slope). If I take three or more different values of depth and I force rbeta values to be equal two to two (rbeta(depth=X) = rbeta(depth=Y), rbeta(depth=X) = rbeta(depth=Z), rbeta(depth=Y) = rbeta(depth=Z)...), I am surprised that the three (or more) values of beta are always the same, and are dependent of T*stdev = c1 + c2*depth.

Taking the value of slope, I reached the equation of beta = 59.4 * c2 - c1 in those cases when rbeta is constant and independent of depth. I guess that those cases are irrelevant for tuning, but I write it just in case. What I really want to say is that if by any chance those values were not irrelevant, is there a known good value of beta, so you can adjust c1 and c2? The same applies to rbeta: if there is a known good value of rbeta in those special cases, you will know beta and therefore c1 and c2.

Code: Select all

First attempt&#58; &#123;c1 = 1.5 * 20 = 30; c2 = 1.5 * 5 = 7.5&#125; ===> beta = 415.5
Second attempt&#58; &#123;c1 = 50; c2 = 6&#125; ===> beta = 306.4
It is surely a waste of time (I think that if two values of beta and/or rbeta are the same at different depths, then it is a coincidence), but who knows? I am glad to see the fast improvement of SF. :)

Regards from Spain.

Ajedrecista.

gladius
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Re: Probcut.

Post by gladius » Fri May 24, 2013 11:35 pm

Ajedrecista wrote:I am sorry to see that your two attempts of probcut failed at Stage I:
Yes, it has not been successful yet, but I have some ideas for how to improve things. I think my numbers may be skewed, as I was searching positions from the same games. A more random selection of positions could help.

I think chess programmers need to be able to forget about failures quickly, otherwise you would become very depressed :).

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Probcut.

Post by Don » Sat May 25, 2013 5:32 pm

gladius wrote:
Ajedrecista wrote:I am sorry to see that your two attempts of probcut failed at Stage I:
Yes, it has not been successful yet, but I have some ideas for how to improve things. I think my numbers may be skewed, as I was searching positions from the same games. A more random selection of positions could help.

I think chess programmers need to be able to forget about failures quickly, otherwise you would become very depressed :).
I have a different view here. When you experiment with an idea you should be learning something. So even the so-called failures are not true failures unless they don't teach you anything but they serve to train your intuition a bit more, to teach you what is possible, what is not, what works and what doesn't. In fact I have constructed tests designed to fail simply for the information return. A lot of times you need to know if this or that is really a big deal, so doing it wrong can help you understand the nature of the idea. Here is an example: we have this rather complicated check and out of check extension system - we know it works but is it really a big deal or would something really simple be almost as good? That can be tested very easily and it gives you some sense of how much time to spend on further refinements.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

gladius
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Re: Probcut.

Post by gladius » Sat May 25, 2013 8:20 pm

Don wrote:
gladius wrote:
Ajedrecista wrote:I am sorry to see that your two attempts of probcut failed at Stage I:
Yes, it has not been successful yet, but I have some ideas for how to improve things. I think my numbers may be skewed, as I was searching positions from the same games. A more random selection of positions could help.

I think chess programmers need to be able to forget about failures quickly, otherwise you would become very depressed :).
I have a different view here. When you experiment with an idea you should be learning something. So even the so-called failures are not true failures unless they don't teach you anything but they serve to train your intuition a bit more, to teach you what is possible, what is not, what works and what doesn't. In fact I have constructed tests designed to fail simply for the information return. A lot of times you need to know if this or that is really a big deal, so doing it wrong can help you understand the nature of the idea. Here is an example: we have this rather complicated check and out of check extension system - we know it works but is it really a big deal or would something really simple be almost as good? That can be tested very easily and it gives you some sense of how much time to spend on further refinements.
Yes - I agree, forget was not the best term to describe this. Better might be, you can not get depressed about tests that fail, but as you say, use them to improve your next try.

Post Reply