Evaluation functions. Why integer?

[xsadar]

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(void){
    double d = 0.01, s = 0;
    int i;
    for (i = 0; i < 1000; i++)
        s += d;
    printf("%.100f\n", s);
}

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

Your compiler doesn't give you a warning when you write d = 0.01, because (1) when you use a feature it's expected that you already know how it works, and (2) it would have to give you an approximation warning (very nearly) every time you use a floating-point literal, which would be annoying to those who actually understand and need to use floating point arithmetic, not to mention that it would hide legitimate warnings.

However, it does appear that your documentation could have been a bit better. I'll have to admit though that I'm quite surprised that you didn't know floating-point values were binary approximations. I even thought it was implied in your response to Bob when I first read it.

[bob]

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.

It isn't so "moot" if you are updating the value everywhere. Now you end up stalling until the new value is ready, so it can be updated again. No way to pipeline multiple updates to the same value.

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

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(void){
    double d = 0.01, s = 0;
    int i;
    for (i = 0; i < 1000; i++)
        s += d;
    printf("%.100f\n", s);
}

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.

That would be insane. because it would lead to a false sense of security, where later you compute a value that just happens to end up at 1.0, and then you divide by 10 and get an inaccurate result with no warning at all. This is just a known issue with floating point math that is taught in every computer science curriculum around the world, with the express intent of making sure that students avoid the old "to a man who has a hammer, everything looks like a nail" approach to programming. Floating point math is used where you can have a _wide_ range of results, and can deal with some inaccuracy in the significant digits, integer math is used where you don't need a wide range of results and accuracy is paramount. You just don't use a hammer to drive a screw. That is what this is suggesting one should do...

.

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

Not to me. If you have 15 digits with an exponent range of that size, how can you not know that the lower digits will become inaccurate? This is what the subject of computational numerical analysis deals with in great detail...

[Gerd Isenberg]

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

That simple!
But it seems with float/double in standard PVS one is almost forced to use a separate zero window scout routine.

Gerd

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

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.

Even if no pipelining at all is possible the worst it can possibly do is exactly equal performance to integer. The cost per operation is one cycle either way, and the floating point unit has a better pipeline, so it will do as well or better.

So the old thinking of "integer for performance" should be rethought.

[bob]

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.

Even if no pipelining at all is possible the worst it can possibly do is exactly equal performance to integer. The cost per operation is one cycle either way, and the floating point unit has a better pipeline, so it will do as well or better.

So the old thinking of "integer for performance" should be rethought.

There are other issues. Do you know how you compare two floats? You do a FCOMP, then FSTSW ax and then do an int compare on ax to see what the result was. About as ugly as it can be. Integer math will always have a performance edge as there is no exponent to have to deal with when doing simple operations like add or subtract, which are way more common than multiplies/divides where the exponents are not quite as big a bother. But normalization is another time-waster to the integer programmer.

It should be easy enough to write a program to randomly FP add values, and do the same in integer math to see what the real difference is. I might tackle this once I get the testing back to running.

BTW better pipeline does not translate into better performance if you can't fill the pipeline. Hundreds of score += this_bonus and score -= that penalty preclude any pipelining. A longer and more efficient pipeline hurts latency unless data can be streamed thru (the classic arithmetic pipeline argument).

[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(void){
    double d = 0.01, s = 0;
    int i;
    for (i = 0; i < 1000; i++)
        s += d;
    printf("%.100f\n", s);
}

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

Your compiler doesn't give you a warning when you write d = 0.01, because (1) when you use a feature it's expected that you already know how it works, and (2) it would have to give you an approximation warning (very nearly) every time you use a floating-point literal, which would be annoying to those who actually understand and need to use floating point arithmetic, not to mention that it would hide legitimate warnings.

However, it does appear that your documentation could have been a bit better. I'll have to admit though that I'm quite surprised that you didn't know floating-point values were binary approximations. I even thought it was implied in your response to Bob when I first read it.

I disagree.
The compiler should allow the user to disable some type of warning but
I think that it should warn the user about something that is not correct.

Not everybody studied computer programming at university and know it and at least people who learn C by other ways may not know it.

It is obvious that the computer cannot calculate correctly every division because of finite memory but it is not obvious that the computer cannot calculate correctly numbers like 0.01 that are constants.

It is simply counter intuitive and if I want to have numbers in base 2 and I compose computer language then my first thought is simply not to allow expressions like 0.01 and I can allow instead of it
only numbers in base 2 or base 4 or base 8 or base 16.

Second thought is that maybe I want to allow 0.01 for people who prefer to use base 10 and do not care about the error
but if people want to use base that is not a power of 2 and if they do not disable warning they should get a warning by the compiler.

Note that in case that the compiler does not allow 0.1 but allow 1/10 I could probably guess without more hints that 1/10 is not an exact value for the same reason that I know that 1/3 is not an exact value.

Uri

[Gerd Isenberg]

There are other issues. Do you know how you compare two floats? You do a FCOMP, then FSTSW ax and then do an int compare on ax to see what the result was. About as ugly as it can be. Integer math will always have a performance edge as there is no exponent to have to deal with when doing simple operations like add or subtract, which are way more common than multiplies/divides where the exponents are not quite as big a bother. But normalization is another time-waster to the integer programmer.

It should be easy enough to write a program to randomly FP add values, and do the same in integer math to see what the real difference is. I might tackle this once I get the testing back to running.

BTW better pipeline does not translate into better performance if you can't fill the pipeline. Hundreds of score += this_bonus and score -= that penalty preclude any pipelining. A longer and more efficient pipeline hurts latency unless data can be streamed thru (the classic arithmetic pipeline argument).

Did you ever heard about SSE instructions and their double/float latency on x86-64? x87 is almost over in 64-bit mode. MSVC use SSE per default in 64-bit mode and I guess GCC and Intel-C per compiler switch.

Instead of

Code: Select all

if ( condA ) eval += wA;
if ( condB ) eval += wB;
if ( condC ) eval += wC;
if ( condD ) eval += wD;

one may use one dotproduct

Code: Select all

 eval += [c] * [w]; 

[bob]

There are other issues. Do you know how you compare two floats? You do a FCOMP, then FSTSW ax and then do an int compare on ax to see what the result was. About as ugly as it can be. Integer math will always have a performance edge as there is no exponent to have to deal with when doing simple operations like add or subtract, which are way more common than multiplies/divides where the exponents are not quite as big a bother. But normalization is another time-waster to the integer programmer.

It should be easy enough to write a program to randomly FP add values, and do the same in integer math to see what the real difference is. I might tackle this once I get the testing back to running.

BTW better pipeline does not translate into better performance if you can't fill the pipeline. Hundreds of score += this_bonus and score -= that penalty preclude any pipelining. A longer and more efficient pipeline hurts latency unless data can be streamed thru (the classic arithmetic pipeline argument).

Did you ever heard about SSE instructions and their double/float latency on x86-64? x87 is almost over in 64-bit mode. MSVC use SSE per default in 64-bit mode and I guess GCC and Intel-C per compiler switch.

Instead of

Code: Select all

if ( condA ) eval += wA;
if ( condB ) eval += wB;
if ( condC ) eval += wC;
if ( condD ) eval += wD;

one may use one dotproduct

Code: Select all

 eval += [c] * [w]; 

1. I have not considered SSE yet since we are talking both 32 and 64 bit architectures, rather than 64 bit exclusively.

2. That trick to get rid of the comparison sort of works. But then one has to have the zero/non-zero comparison weight to multiply by, something that is not defined as a floating-point operand. It is counter-intuitive, and also likely to be not accepted for years. I still don't do it, and I've been aware of the trick which has been used for 40 years now since the first vector architecture was described. But that is not how my eval is actually constructed.

I think the goal for a chess engine has to be to express ideas in the most direct, readable, and easy-to-follow way possible, staying within the guidelines for good performance when possible.

[Gerd Isenberg]

There are other issues. Do you know how you compare two floats? You do a FCOMP, then FSTSW ax and then do an int compare on ax to see what the result was. About as ugly as it can be. Integer math will always have a performance edge as there is no exponent to have to deal with when doing simple operations like add or subtract, which are way more common than multiplies/divides where the exponents are not quite as big a bother. But normalization is another time-waster to the integer programmer.

It should be easy enough to write a program to randomly FP add values, and do the same in integer math to see what the real difference is. I might tackle this once I get the testing back to running.

BTW better pipeline does not translate into better performance if you can't fill the pipeline. Hundreds of score += this_bonus and score -= that penalty preclude any pipelining. A longer and more efficient pipeline hurts latency unless data can be streamed thru (the classic arithmetic pipeline argument).

Did you ever heard about SSE instructions and their double/float latency on x86-64? x87 is almost over in 64-bit mode. MSVC use SSE per default in 64-bit mode and I guess GCC and Intel-C per compiler switch.

Instead of

Code: Select all

if ( condA ) eval += wA;
if ( condB ) eval += wB;
if ( condC ) eval += wC;
if ( condD ) eval += wD;

one may use one dotproduct

Code: Select all

 eval += [c] * [w]; 

1. I have not considered SSE yet since we are talking both 32 and 64 bit architectures, rather than 64 bit exclusively.

2. That trick to get rid of the comparison sort of works. But then one has to have the zero/non-zero comparison weight to multiply by, something that is not defined as a floating-point operand. It is counter-intuitive, and also likely to be not accepted for years. I still don't do it, and I've been aware of the trick which has been used for 40 years now since the first vector architecture was described. But that is not how my eval is actually constructed.

I think the goal for a chess engine has to be to express ideas in the most direct, readable, and easy-to-follow way possible, staying within the guidelines for good performance when possible.

May be compiler become (or some already are) smart enough for SIMD vectors:

Code: Select all

CMPPSL xmm0, xmm1 ; for (i=0; i<4; i++) xmm0[i] = xmm0[i] < xmm1[i] ? 0xffff : 0;
ANDPS  xmm0, xmm2 ; multiplication by and

with some final horizontal add.


AMD64 Architecture
Programmer’s Manual
Volume 4:
128-Bit Media Instructions

CMPPS

Compares each of the four packed single-precision floating-point values in the first source operand with the corresponding packed single-precision floating-point value in the second source operand and writes the result of each comparison in the corresponding 32 bits of the destination (first source). The type of comparison is specified by the three low-order bits of the immediate-byte operand, as shown in Table 1-1 on page 24. The result of each compare is a 32-bit value of all 1s (TRUE) or all 0s (FALSE). The first source/destination operand is an XMM register. The second source operand is another XMM register or 128-bit memory location.