Evaluation functions. Why integer?

[Gerd Isenberg]

Hi,

I've started to browse a lot of computer chess code from several different engines. What puzzles me a bit is that "all" engines uses an evaluation function that returns an integer value.

From my ignorant point of view: Would it be more natural to return a floating point value?

Since the answer to the above question is probably "No", can someone explain "why not" ?

-Øystein

I'll add mine without worrying about duplication:

(1) speed. floating point is slower than integer.

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

(3) comparisons are a pain. == is a no-no in floating point operations because of the inaccuracy mentioned, and the existence of extra precision in the floating point stack that you can't store, so comparisons become problematic and most use a "fuzzy comparison". rather than if (a == b) we would use if (abs(a-b) < .000001) (use whatever precision you want.

4. All bits are significant so you can't just store the lower order N bits in a hash entry, you will have to reserve a full 32 or 64 bits.

5. null-window searches would be problematic in that "what is a null-window"? And before you start trying to play game with scoring increments so that you are sure that nobody changes the score by as little as .0001, go back to the accuracy point and re-read. This would be interesting as well

Integers avoid all of that, and have no down-side, so why would one want to use something that introduces quirks left and right and get nothing in return?

That is all true - but I think there are applications nowadays related to eval, where you may have huge simd wise SSE dot-products of feature vectors with (learned) 32-bit float or even 64-bit double weights, to implement tapered eval more smoothly with various sigmoid characteristics without to worry about overflows. Once per eval to convert a final double/float to a centipawn integer in a short range for comparison and alpha-beta backup is not critical at all.

Anyway, out of interest related to the null-window issue, I am interested how to calculate the smallest possible increment 'I' of an IEEE 754-1985 64-bit double or 32-bit float F, so that

Code: Select all

F + I > F

is true. Most efficiently. I guess to treat the float as 32-bit integer and to perform some bit-twiddling on it.

[Uri Blass]

Hi,

I've started to browse a lot of computer chess code from several different engines. What puzzles me a bit is that "all" engines uses an evaluation function that returns an integer value.

From my ignorant point of view: Would it be more natural to return a floating point value?

Since the answer to the above question is probably "No", can someone explain "why not" ?

-Øystein

I'll add mine without worrying about duplication:

(1) speed. floating point is slower than integer.

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

(3) comparisons are a pain. == is a no-no in floating point operations because of the inaccuracy mentioned, and the existence of extra precision in the floating point stack that you can't store, so comparisons become problematic and most use a "fuzzy comparison". rather than if (a == b) we would use if (abs(a-b) < .000001) (use whatever precision you want.

4. All bits are significant so you can't just store the lower order N bits in a hash entry, you will have to reserve a full 32 or 64 bits.

5. null-window searches would be problematic in that "what is a null-window"? And before you start trying to play game with scoring increments so that you are sure that nobody changes the score by as little as .0001, go back to the accuracy point and re-read. This would be interesting as well

Integers avoid all of that, and have no down-side, so why would one want to use something that introduces quirks left and right and get nothing in return?

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.

I also see no problem with null move searches.

You can decide for example that your scores are only x.y when y has 2 digits and in this case the difference for null is exactly 0.01

double allow you range of 1.7E +/- 308 (15 digits)

You can clearly get accuracy if all you numbers are n+m/100 when -10^12<n<10^12 and 0<=m<100 because in this case all the scores have at most 14 digits and double can give them exact value.

If you use 32 bit integer you can only get scores that are in the range
–2,147,483,648 to 2,147,483,647 and it is clearly smaller number of values.

Note that 64 bit integers can give you bigger accuracy relative to double but I know nobody who use 64 bit integer for evaluation and I suspect that most use only 16 bit numbers for evaluation so even 32 bit numbers are not used.

Basically every number in the computer can be translated to some integer so there is no point in the question why integer for the evaluation function and the only question is what range to use.

Every range of values has finite number of values so is similiar to integer.
You need more bits if you want bigger accuracy but people did not find accuracy of 1/10000 of pawn instead of 1/100 pawn productive so they have no reason to use more than 16 bits.

Uri

[Dann Corbit]

Hi,

I've started to browse a lot of computer chess code from several different engines. What puzzles me a bit is that "all" engines uses an evaluation function that returns an integer value.

From my ignorant point of view: Would it be more natural to return a floating point value?

Since the answer to the above question is probably "No", can someone explain "why not" ?

-Øystein

Some people do use float.
It would be a bad idea for MTD(f) but works OK for PVS search.

[Tord Romstad]

Programming in integers forces sharper thoughts, it keeps you more alert, ergo--it's good for your (programmer's) brain.

This is entirely backwards -- are you sure you don't mean "floats" rather than integers in the above sentence?

Integers are easy. All schoolchildren have a crude understanding of their basic properties. Machine integers are only slightly more complex; they are nothing more than integers modulo some power of 2. I could teach my 8 year old niece how they work in an hour or two.

Floating point numbers, on the other hand, are terrifyingly difficult, and should be used with very great care unless you have a few university level courses in numerical analysis under your belt.

The set of real numbers is a very complicated mathematical object (we don't even know how many they are!), and are very poorly understood by virtually all non-mathematicians. People tend to think they understand them, probably because they have seen them so often that they begin to feel familiar, but if you ask them a few simple technical questions, you'll find out that they are almost completely clueless. This isn't because people are stupid, but because real numbers are hard, and usually aren't explained in detail in undergraduate mathematics courses.

Floating point numbers are an attempt to emulate real numbers on a computer. The problem is that they emulate real numbers extremely poorly: They share almost no properties with the real numbers, and don't obey even the most basic laws of arithmetic. For instance, it is not generally true that a+(b+c) equals (a+b)+c, nor that a*(b+c) equals a*b + b*c. Comparing floating point numbers is very error-prone. Equality is meaningless, and if you replace equality by approximate equality (by defining to numbers to be "equal" if they differ by less than some small epsilon) you end up with a non-transitive equality operator. The "greater than" and "smaller than" operators are also dangerous; because two computations which should be mathematically equivalent can often give different results. For instance, the result of the comparison x < y may depend on whether the variable x was computed as a+(b+c) or as (a+b)+c.

Morover, the vast majority of programmers (at least those I have met) know hardly anything about real numbers, and have no idea how floating point numbers are represented in the computer, or how basic arithmetic operations on floating point numbers work. Their attempts to use floating point numbers for non-trivial practical problems are doomed to fail. Without very deep knowledge, sound use of floating point numbers for difficult problems is impossible. In the best case, you will end up with a program which works most of the time, but which fails spectacularly for a few border cases which are bound to turn up somewhere in a sufficiently big data set. With expert knowledge, sound use of floating point numbers isn't entirely impossible, but merely extremely difficult.

Writing completely robust and bug free software with floating point numbers is at least an order of magnitude more difficult than writing a strong chess program (I know, as I have tried to do both). Whenever I can, I stay away from them. Fortunately, for most of the difficult problems I have worked with, it has been possible to use rational numbers, finite fields, or finite algebraic extensions of one of these fields, all of which are far easier to work with on a computer than the floating point numbers. The only big advantage of floating point numbers is that they are implemented in hardware, and that computations with floating point numbers are therefore insanely fast. I wish my computer had an RNU ("rational number unit") rather than an FPU.

Tord

[Zach Wegner]

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?

[bob]

Hi,

I've started to browse a lot of computer chess code from several different engines. What puzzles me a bit is that "all" engines uses an evaluation function that returns an integer value.

From my ignorant point of view: Would it be more natural to return a floating point value?

Since the answer to the above question is probably "No", can someone explain "why not" ?

-Øystein

I'll add mine without worrying about duplication:

(1) speed. floating point is slower than integer.

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

(3) comparisons are a pain. == is a no-no in floating point operations because of the inaccuracy mentioned, and the existence of extra precision in the floating point stack that you can't store, so comparisons become problematic and most use a "fuzzy comparison". rather than if (a == b) we would use if (abs(a-b) < .000001) (use whatever precision you want.

4. All bits are significant so you can't just store the lower order N bits in a hash entry, you will have to reserve a full 32 or 64 bits.

5. null-window searches would be problematic in that "what is a null-window"? And before you start trying to play game with scoring increments so that you are sure that nobody changes the score by as little as .0001, go back to the accuracy point and re-read. This would be interesting as well

Integers avoid all of that, and have no down-side, so why would one want to use something that introduces quirks left and right and get nothing in return?

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.

And exactly who was talking about using whole numbers? The original poster _clearly_ said "From my ignorant point of view: Would it be more natural to return a floating point value? " If he was talking about whole numbers he would not have phrased the question like that...

I also see no problem with null move searches.

You can decide for example that your scores are only x.y when y has 2 digits and in this case the difference for null is exactly 0.01

Shows you don't understand floating point math. You can't guarantee that at all once you do the first floating point operation on a number, since most have a divide somewhere in the evaluation. And humans have an ugly tendency to use .1 or .01 or any of _many_ decimal constants that don't convert to IEEE exactly, leaving you stuck on the null-window issue.

double allow you range of 1.7E +/- 308 (15 digits)

You can clearly get accuracy if all you numbers are n+m/100 when -10^12<n<10^12 and 0<=m<100 because in this case all the scores have at most 14 digits and double can give them exact value.

Please compute m/100 where m = 1 and tell me how accurate the answer is. Or where M=10.

If you use 32 bit integer you can only get scores that are in the range
–2,147,483,648 to 2,147,483,647 and it is clearly smaller number of values.

But with _zero_ inaccuracies caused by the inability to represent small values accurately.

Note that 64 bit integers can give you bigger accuracy relative to double but I know nobody who use 64 bit integer for evaluation and I suspect that most use only 16 bit numbers for evaluation so even 32 bit numbers are not used.

I know a few that use 64 bit values. Those that use 64 bit architectures. Not that the values will ever get that big, but nothing prevents it. Steven said he uses micropawn evaluations so his get close to 32 bits.

Basically every number in the computer can be translated to some integer so there is no point in the question why integer for the evaluation function and the only question is what range to use.

Unless we are talking about floating point values, which means a decimal point with one or more digits to the right. we are not talking about integers. For example, integer values have more significant digits than corresponding floating point values. But the point of floating point numbers is extreme range, which is where integers fail. But if you use the current type of evaluation, whether it be centipawns or millipawns, and you store those as true floating point values, then the problem is as we have described it.

Every range of values has finite number of values so is similiar to integer.
You need more bits if you want bigger accuracy but people did not find accuracy of 1/10000 of pawn instead of 1/100 pawn productive so they have no reason to use more than 16 bits.

Uri

None of that is significant in this context. He asked "why not use floating point values" which appear to be a sane alternative since we all give evaluations in terms of x.xx or x.xxx numbers... Any of the above represents an issue with doing that. Floating point has been around for a long time. And on some matchines it was even faster than integer math. Yet we stuck with integers. there's a reason. Or actually several, as given above.

[CThinker]

Hi,

I've started to browse a lot of computer chess code from several different engines. What puzzles me a bit is that "all" engines uses an evaluation function that returns an integer value.

From my ignorant point of view: Would it be more natural to return a floating point value?

Since the answer to the above question is probably "No", can someone explain "why not" ?

-Øystein

Actually, what you see in most chess code is "fixed point" real.

Normally, a basic value is considered as 1.00, and in code, it is represented as 100 (there is an invisible decimal point after the two zeros; like in Crafty) or 1000 (like in Amy).

The only benefit that you get from floating point real is the wide range of values. But this is not useful in computer chess. Even if you have 10 queens on the board, with 10.0 points each, the score would only be 100.0. When represended as fixed point real in a 32-bit signed integer, you are still left with 7 decimal places (that is, 1.0 is represented as 10000000, so, 100.0 is just 1000000000).

Fixed point real is way, way, way faster than floating point real.

In commercial applications (like games, CAD, audio DSP, etc) use of fixed point real is more common than floating point real.

[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

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

[Dann Corbit]

Hi,

I've started to browse a lot of computer chess code from several different engines. What puzzles me a bit is that "all" engines uses an evaluation function that returns an integer value.

From my ignorant point of view: Would it be more natural to return a floating point value?

Since the answer to the above question is probably "No", can someone explain "why not" ?

-Øystein

Actually, what you see in most chess code is "fixed point" real.

Normally, a basic value is considered as 1.00, and in code, it is represented as 100 (there is an invisible decimal point after the two zeros; like in Crafty) or 1000 (like in Amy).

The only benefit that you get from floating point real is the wide range of values. But this is not useful in computer chess. Even if you have 10 queens on the board, with 10.0 points each, the score would only be 100.0. When represended as fixed point real in a 32-bit signed integer, you are still left with 7 decimal places (that is, 1.0 is represented as 10000000, so, 100.0 is just 1000000000).

Fixed point real is way, way, way faster than floating point real.

That used to be true.
I guess that 4 byte float calculations are indistinguishable in speed from 4 byte integer calculations. At least the difference will be so small that you will have a hard time measuring it.
Adding two floats on AMD Athlon is one cycle.
Multiplying two floats on AMD Athlon is one cycle.
You can do even better (several instructions/cycle) due to pipelining by using 3DNow!.

In commercial applications (like games, CAD, audio DSP, etc) use of fixed point real is more common than floating point real.