Rounding

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.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Rounding

Post by Don » Fri Jan 20, 2012 11:19 pm

Zach Wegner wrote:
Don wrote:I think it's difficult to change the scale one you have committed to one.
I imagine this is true for most people, but IMO this is because most people use inferior programming languages/development strategies.

I prefer to have all tuned values in floating point, and have the actual fixed-point integer arithmetic generated for some arbitrary precision as a compilation step. In my code this can be adjusted per evaluation module, so e.g. you can switch to higher precision for evaluating king safety, and it rounds at the end.
I did once try using floating point for the primary calculation and it was not that long ago, it was on a dual core modern chip. I had heard that on modern chips this might even benefit the speed since we have a separate floating point execution unit that can do this in parallel. However it was not the case, I saw a noticeable slowdown.

I think I made the right decision - to use 1000 as that allows me to use any lower resolution. If I experiment with the "final" resolution that the search uses I will lay it out in such a way that I can easily experiment with other resolutions with no further pain. It's probably only a 2 hour job even if I do it the hard way and we will probably see if 200 for a pawn is an improvement at some point but it's certainly not very high on our list of priorities.

User avatar
Rebel
Posts: 4788
Joined: Thu Aug 18, 2011 10:04 am

Re: Rounding

Post by Rebel » Sat Jan 21, 2012 12:01 am

lkaufman wrote: I'm surprised to see Crafty and Fruit in the list. Fruit, because Rybka is supposed to have used the Fruit eval; when I started work on Rybka (2.2) it used millipawn eval (or 1/1024 perhaps). Do you happen to know about Rybka 1? As for Crafty, I thought it does fairly fancy stuff with mobility, which would seem to be impossible with 1 cp resolution. Any comment?
Your former pupil :wink: used 3200 as a base, at least in R1. Then at the end of eval score is divided by 32 back to centipawn. I think the goal of this odd process to have more equal scores but better rounded -> more beta-cutoffs -> (somewhat) faster search.

User avatar
lucasart
Posts: 3046
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Rounding

Post by lucasart » Sat Jan 21, 2012 2:39 am

lkaufman wrote:Some top programs round off the score to achieve greater speed at some cost in quality, namely Rybka, SF, and Komodo. Others do not, namely (I believe) Ivanhoe, Critter, and (probably) Houdini.
The question is, once you have decided on the scoring resolution you actually want the search to use, is it better to have the eval also use that resolution or should it use finer resolution and round off? In other words, which is more logical:
1.Rybka - eval terms in millipawns, final score for search rounded to centipawns.
or
2. Ivanhoe - eval terms in centipawns, no rounding.

Any opinions?
I don't understand why rounding eval scores would make the search faster. In fact, I would intuitively want to think the opposite. Care to explain ?

CRoberson
Posts: 2005
Joined: Mon Mar 13, 2006 1:31 am
Location: North Carolina, USA
Contact:

Re: Rounding

Post by CRoberson » Sat Jan 21, 2012 4:13 am

In the 1990's, I used millipawns for NoonianChess and I still use it for Telepath and Ares. In 2006, I tried truncating the millipawn eval to the lowest centipawn. When tested against benchmarks, it cut the time to ply. Pruning was increased and move choices didn't change.

I never tested it in matches to see if it plays better. Not only that, I should probably test to see if rounding is better than truncating. At the time, I thought rounding vs truncating from millipawns to centipawns wouldn't matter.

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

Re: Rounding

Post by Don » Sat Jan 21, 2012 5:14 am

lucasart wrote:
lkaufman wrote:Some top programs round off the score to achieve greater speed at some cost in quality, namely Rybka, SF, and Komodo. Others do not, namely (I believe) Ivanhoe, Critter, and (probably) Houdini.
The question is, once you have decided on the scoring resolution you actually want the search to use, is it better to have the eval also use that resolution or should it use finer resolution and round off? In other words, which is more logical:
1.Rybka - eval terms in millipawns, final score for search rounded to centipawns.
or
2. Ivanhoe - eval terms in centipawns, no rounding.

Any opinions?
I don't understand why rounding eval scores would make the search faster. In fact, I would intuitively want to think the opposite. Care to explain ?
Because you are using a lower resolution score.

With higher resolution there are many more scores in the tree and very few scores that are exactly the same. Therefore the search must be more precise. Example:

These scores all round to 17 cp:

16.5, 16.6 16.7 16.8 16.9 17.0, 17.1, 17.2 17.3 17.4

I used a decimal point here but these could be millipawns if you remove the decimal point.

If you are using centipawn resolution and beta is 17, any score >= 17 gives you a cutoff.

With millipawn resolution you have 10 different scores instead of 1 that would round to 17. So if these 10 different score were expressed in centipawns they could all give a cutoff, but not so in millipawns.

User avatar
lucasart
Posts: 3046
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Rounding

Post by lucasart » Sat Jan 21, 2012 5:31 am

Don wrote:
lucasart wrote:
lkaufman wrote:Some top programs round off the score to achieve greater speed at some cost in quality, namely Rybka, SF, and Komodo. Others do not, namely (I believe) Ivanhoe, Critter, and (probably) Houdini.
The question is, once you have decided on the scoring resolution you actually want the search to use, is it better to have the eval also use that resolution or should it use finer resolution and round off? In other words, which is more logical:
1.Rybka - eval terms in millipawns, final score for search rounded to centipawns.
or
2. Ivanhoe - eval terms in centipawns, no rounding.

Any opinions?
I don't understand why rounding eval scores would make the search faster. In fact, I would intuitively want to think the opposite. Care to explain ?
Because you are using a lower resolution score.

With higher resolution there are many more scores in the tree and very few scores that are exactly the same. Therefore the search must be more precise. Example:

These scores all round to 17 cp:

16.5, 16.6 16.7 16.8 16.9 17.0, 17.1, 17.2 17.3 17.4

I used a decimal point here but these could be millipawns if you remove the decimal point.

If you are using centipawn resolution and beta is 17, any score >= 17 gives you a cutoff.

With millipawn resolution you have 10 different scores instead of 1 that would round to 17. So if these 10 different score were expressed in centipawns they could all give a cutoff, but not so in millipawns.
ah, ok thanks. i still use the old centipawn scale in my program. anyway there are more things to improve before i reach that stage ;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: Rounding

Post by Harald » Sat Jan 21, 2012 8:43 am

Here is a reason why centi pawns and milli pawns are ok but a finer resolution is not:

If you sum up the score af all pieces that are allowed for one side
then you get something like
9Q + 2R + 2B + 2N +K vs k or
9*1000 + 2*600 + 2*400 + 2*400 + 0 == 11800 milli pawns.
You can even add big positional evaluation terms.
Together with mate values between 15000 and 16000 or between 32000 and 32767
this score fits nicely in a 16 bit signed short integer.
And this short integer does not waste space in the hash table or in any other struct.
Therefore you can have a big hash table with many entries and the program will not
crash from score overflows anywhere.
A finer resolution than a half millipawn needs a 32 bit integer
or at least another byte for each score.

Harald

User avatar
marcelk
Posts: 348
Joined: Fri Feb 26, 2010 11:21 pm
Contact:

Re: Rounding

Post by marcelk » Sat Jan 21, 2012 9:35 am

Harald wrote: A finer resolution than a half millipawn needs a 32 bit integer
or at least another byte for each score.
Either that, or map the value back into a 16 bit range, for example with a sigmoid-like function. Not hard to do when the largest component (material balance) comes from a pre-calculated table. It suffices to map only that into a -15...15 range and keep the rest as-is.

elpapa
Posts: 203
Joined: Sun Jan 18, 2009 10:27 pm
Location: Sweden
Full name: Patrik Karlsson

Re: Rounding

Post by elpapa » Sat Jan 21, 2012 9:45 am

Harald wrote:Here is a reason why centi pawns and milli pawns are ok but a finer resolution is not:

If you sum up the score af all pieces that are allowed for one side
then you get something like
9Q + 2R + 2B + 2N +K vs k or
9*1000 + 2*600 + 2*400 + 2*400 + 0 == 11800 milli pawns.
You can even add big positional evaluation terms.
Together with mate values between 15000 and 16000 or between 32000 and 32767
this score fits nicely in a 16 bit signed short integer.
And this short integer does not waste space in the hash table or in any other struct.
Therefore you can have a big hash table with many entries and the program will not
crash from score overflows anywhere.
A finer resolution than a half millipawn needs a 32 bit integer
or at least another byte for each score.

Harald
But those numbers you call millipawns are actually centipawns.

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: Rounding

Post by Harald » Sat Jan 21, 2012 2:49 pm

elpapa wrote:
Harald wrote:Here is a reason why centi pawns and milli pawns are ok but a finer resolution is not:

If you sum up the score af all pieces that are allowed for one side
then you get something like
9Q + 2R + 2B + 2N +K vs k or
9*1000 + 2*600 + 2*400 + 2*400 + 0 == 11800 milli pawns.
You can even add big positional evaluation terms.
Together with mate values between 15000 and 16000 or between 32000 and 32767
this score fits nicely in a 16 bit signed short integer.
And this short integer does not waste space in the hash table or in any other struct.
Therefore you can have a big hash table with many entries and the program will not
crash from score overflows anywhere.
A finer resolution than a half millipawn needs a 32 bit integer
or at least another byte for each score.

Harald
But those numbers you call millipawns are actually centipawns.
You are right. Sorry for the misinformation.
9Q + 2R + 2B + 2N +K vs k or
9*1000 + 2*600 + 2*400 + 2*400 + 0 == 11800 centi pawns.
And now? Is this an argument for centi pawns?
Or for the unit of 1/256 pawn? In that case the range would be +- 30208.

Harald

Post Reply