Evaluation functions. Why integer?

[Dann Corbit]

Source:
http://www.amd.com/us-en/assets/content ... ilkens.pdf

On Opteron, using SSE and 3DNow! you can get 3.4 FLOPS/Cycle
The integer operations are 1/Cycle, so floating point is {or can be} much faster than integer for 4 byte float and 4 byte integer.

[plattyaj]

Source:
http://www.amd.com/us-en/assets/content ... ilkens.pdf

On Opteron, using SSE and 3DNow! you can get 3.4 FLOPS/Cycle
The integer operations are 1/Cycle, so floating point is {or can be} much faster than integer for 4 byte float and 4 byte integer.

Presumably that's pipelined so you would have to keep the FLOPS coming to reach that - which, for the specific question, wouldn't happen since you have a lot of operations to do in between updates the the score even within the eval routine.

Andy.

[Guetti]

Another point to take into consideration (maybe it was already mentioned), why would you want floating point numbers? floats are there to measure something with enhanced precision. But that's not actually needed in chess programming.
As already mentioned, most use 1/100 pawns or one centipawn as a unit.
Now, if my evaluation functions gives me a score of 245 centipawns for white, but another move would give me a position with a score of 246 centipawns for white, can we say the second position would be better for white. My engine has to believe this, but is this really the case? I would say maybe in 50% of all the cases. The scoring of the evaluation function is so crude and lot's of the time plain wrong that the difference really doesn't matter. Even if the evaluation shows 300 for white it might still be a draw, so what does the difference of 0.01 pawns matter? Do I really want to compare position with 0.0000001 pawns difference and make a judgement about them? No.
As a scientist, one of the first things you learn in your studies is to never use more precision as is reasonable. I use to stick with that.

[michiguel]

I agree about point 1 but I disagree about 2.

You can represent every integer as double.
You even can have exactly the same evaluation when you replace integer by double and the only difference is that you are going to be slower.

Doubles can represent integers exactly, but that's not what we're doing. We're trying to represent fixed-point decimals of the form x.yy. You cannot represent 1/100 exactly in a double, as you must round at some point:

If you engine granularity is 1 cp you can do 1 cp = 1.000000
The whole program can be made to work the same. That is Uri's point and IMHO he is right. Of course the problem is if you use tricks using division of some sort, shifts, etc, but that is another issue. You do not need to equal 1.00000 to one pawn, you equal 1.00000 to the minimum unit you use, usually, a cp. In other words, I do not think you need to use fixed decimals. The pain is when you need to do ==. Since there is a big difference between units, establishing '==' as a function that returns TRUE when both numbers are "almost equal" should do it. This can be done based on the very small range of numbers that chess engines use in the evaluation.

Of course this is all clumsy but that is not Uri's point, I think.

Miguel

I don't think he has a point. Why would you use _slower_ math, and get nothing in return? The original poster was asking why no one uses IEEE variables when evaluations are displayed as if they are floating-point numbers. The answer is exactly what I responded. We could also use BCD math, as the X86 has always supported that as well. But we don't due to speed issues, same for FP.

So using CP = 1.000 would be completely pointless. You are not really using floating point to represent the actual scores, you would be doing exactly what we do in integers. Only slower, with a value that is at least 32 bits wide (no 16 bit FP values exist). Seems to add another reason to not use them "it is not a sane usage..."

Uri was disagreeing with this point from your post.

"(2) accuracy. You can't represent numbers like .1 .01, .001 exactly when converting to IEEE floating point. Just like we can't represent fractions like 1/3 exactly in decimal numbers. "

That is his point, which has nothing to do with the usefulness of floating points in CC.

Miguel

[michiguel]

Another point to take into consideration (maybe it was already mentioned), why would you want floating point numbers? floats are there to measure something with enhanced precision. But that's not actually needed in chess programming.
As already mentioned, most use 1/100 pawns or one centipawn as a unit.
Now, if my evaluation functions gives me a score of 245 centipawns for white, but another move would give me a position with a score of 246 centipawns for white, can we say the second position would be better for white. My engine has to believe this, but is this really the case? I would say maybe in 50% of all the cases. The scoring of the evaluation function is so crude and lot's of the time plain wrong that the difference really doesn't matter. Even if the evaluation shows 300 for white it might still be a draw, so what does the difference of 0.01 pawns matter? Do I really want to compare position with 0.0000001 pawns difference and make a judgement about them? No.
As a scientist, one of the first things you learn in your studies is to never use more precision as is reasonable. I use to stick with that.

If a good implementation with floating points is possible, it would be really useful for certain learning algorithms, because approximate derivatives of certain parameters can be calculated. You need much more accuracy to do that, and floats or doubles are more convenient.

Miguel

[bob]

I agree about point 1 but I disagree about 2.

You can represent every integer as double.
You even can have exactly the same evaluation when you replace integer by double and the only difference is that you are going to be slower.

Doubles can represent integers exactly, but that's not what we're doing. We're trying to represent fixed-point decimals of the form x.yy. You cannot represent 1/100 exactly in a double, as you must round at some point:

If you engine granularity is 1 cp you can do 1 cp = 1.000000
The whole program can be made to work the same. That is Uri's point and IMHO he is right. Of course the problem is if you use tricks using division of some sort, shifts, etc, but that is another issue. You do not need to equal 1.00000 to one pawn, you equal 1.00000 to the minimum unit you use, usually, a cp. In other words, I do not think you need to use fixed decimals. The pain is when you need to do ==. Since there is a big difference between units, establishing '==' as a function that returns TRUE when both numbers are "almost equal" should do it. This can be done based on the very small range of numbers that chess engines use in the evaluation.

Of course this is all clumsy but that is not Uri's point, I think.

Miguel

I don't think he has a point. Why would you use _slower_ math, and get nothing in return? The original poster was asking why no one uses IEEE variables when evaluations are displayed as if they are floating-point numbers. The answer is exactly what I responded. We could also use BCD math, as the X86 has always supported that as well. But we don't due to speed issues, same for FP.

So using CP = 1.000 would be completely pointless. You are not really using floating point to represent the actual scores, you would be doing exactly what we do in integers. Only slower, with a value that is at least 32 bits wide (no 16 bit FP values exist). Seems to add another reason to not use them "it is not a sane usage..."

Uri was disagreeing with this point from your post.

"(2) accuracy. You can't represent numbers like .1 .01, .001 exactly when converting to IEEE floating point. Just like we can't represent fractions like 1/3 exactly in decimal numbers. "

That is his point, which has nothing to do with the usefulness of floating points in CC.

Miguel

And that point is wrong. Might be functional in some cases, but whole numbers cut off 1/2 the exponent range that is possible. And again, might as well use BCD math which has no rounding/truncation issues at all. The point for using floating point numbers is to use actual floating point values. Otherwise why would you give up on the speed of integers which can do exactly the same thing, as we always have done, and not give up the speed?

Entire concept makes absolutely no sense to me. One could, using this logic, use character strings to represent the evaluation. One can put their foot under a running lawnmower. Question is, is it a reasonable action or not?

[Aleks Peshkov]

There are known publications about MTD-drivers that works nicely with float evaluation.

Floating unit speed is moot argument. Floating math can perform in parallel with unavoidable integer calculations (pointer arithmetic, loop indexes).

IMHO the only strong reason that floating math is unneeded complexity and a source of unexpected bugs.

[Uri Blass]

I agree about point 1 but I disagree about 2.

You can represent every integer as double.
You even can have exactly the same evaluation when you replace integer by double and the only difference is that you are going to be slower.

Doubles can represent integers exactly, but that's not what we're doing. We're trying to represent fixed-point decimals of the form x.yy. You cannot represent 1/100 exactly in a double, as you must round at some point:

Code: Select all

0.0100000000000000002081668171172168513294309377670288085937500000000000000000000000000000000000000000

And though there is a one-to-one correspondence between every centipawn evaluation to its double representation, the rounding will crop up. Notice how 1/100 is rounded so that the double representation is bigger than 1/100? Try running this program:

Code: Select all

#include <stdio.h>
main&#40;void&#41;&#123;
    double d = 0.01, s = 0;
    int i;
    for &#40;i = 0; i < 1000; i++)
        s += d;
    printf&#40;"%.100f\n", s&#41;;
&#125;

You would expect s to be either exactly 10, or maybe a bit bigger? Here's what it actually is:

Code: Select all

9.9999999999998312461002569762058556079864501953125000000000000000000000000000000000000000000000000000

Which is _less_ than 10.

Now if you wanted to use "binary" values, and have your base unit be 1/256 or whatever of a pawn, go ahead. Or you could also use doubles with each number scaled up by 100 or so, but then what's the point?

I get almost the same
I get
9.9999999999998312000000000000000000000000000000000000000000000000000000000000000000000000000000000000

I understand that 0.01 is binary approximation of 0.01 and it seems that the C is misleading.
I think that they simply should not allow me to write d=0.01 without warning by the compiler that d is not 0.01 but binary approximation of that value and double means
the finite set of non-zero values of the form s * m * 2e, where s is 1 or -1, and 0 < m < 253 and -1075 <= e <= 970.
.

I wonder why they do not do it.


I even could not see it based on clicking help on the word double and I had to search in google to find the following link that gives me the exact range of data

http://www.dotgnu.org/pnetlib-doc/System/Double.html

When I only click on help about double and later about data type range
I got simply that range of values of double is
1.7E +/- 308 (15 digits)

Clearly misleading.

Uri

[Tony]

I agree about point 1 but I disagree about 2.

You can represent every integer as double.
You even can have exactly the same evaluation when you replace integer by double and the only difference is that you are going to be slower.

Doubles can represent integers exactly, but that's not what we're doing. We're trying to represent fixed-point decimals of the form x.yy. You cannot represent 1/100 exactly in a double, as you must round at some point:

Code: Select all

0.0100000000000000002081668171172168513294309377670288085937500000000000000000000000000000000000000000

And though there is a one-to-one correspondence between every centipawn evaluation to its double representation, the rounding will crop up. Notice how 1/100 is rounded so that the double representation is bigger than 1/100? Try running this program:

Code: Select all

#include <stdio.h>
main&#40;void&#41;&#123;
    double d = 0.01, s = 0;
    int i;
    for &#40;i = 0; i < 1000; i++)
        s += d;
    printf&#40;"%.100f\n", s&#41;;
&#125;

You would expect s to be either exactly 10, or maybe a bit bigger? Here's what it actually is:

Code: Select all

9.9999999999998312461002569762058556079864501953125000000000000000000000000000000000000000000000000000

Which is _less_ than 10.

Now if you wanted to use "binary" values, and have your base unit be 1/256 or whatever of a pawn, go ahead. Or you could also use doubles with each number scaled up by 100 or so, but then what's the point?

I get almost the same
I get
9.9999999999998312000000000000000000000000000000000000000000000000000000000000000000000000000000000000

I understand that 0.01 is binary approximation of 0.01 and it seems that the C is misleading.

Uri

Nope, the problem is that most people don't know that every floating point is an approximation.

0.01 is just another way of writing: something between 0.095 and 0.0105

if you want it more precise: write 0.010 or 0.0100

But unless you write an infinite number of zeros, it wil always be an approximation. ( or rather, a limited precision )

The correct solution should actual have been 1*10^1 ( since you're not even allowed to write 10 wich implies 2 significant numbers)

There are exceptions. fe 5 apples. In this case the 5 has infinite precision.

Tony

[Tony]

Zero window searches have no problem with floating points.

A zero window means that the function returns either a score <= bestScore, or a score>bestScore. This only requires 1 parameter (and not 2 as most people do.) and it doesn't matter wether that's an integer or float.

Tony