two values in one integer

[Sven]

So is it worth doing at all? If so, only for code cleanliness reasons (thinking of a "Score Pair" for MG/EG and always updating both at the same time)

I fully second this. When we moved to Score Pair we measured around 1% speed up (in line with Don's measurements) but we removed more than 80 lines of code and overall evaluation (that is where this is used most) was more readable. So we kept it.

But removing more than 80 lines was not necessarily related to the introduction of the "packed" solution itself, only to maintaining a "Score Pair" and providing an abstraction that makes the code more readable while the underlying implementation could be "packed in one integer", "struct", or even "two global variables accessed through one function [or macro ]".

Sven

[Rebel]

So is it worth doing at all? If so, only for code cleanliness reasons (thinking of a "Score Pair" for MG/EG and always updating both at the same time)

I fully second this. When we moved to Score Pair we measured around 1% speed up (in line with Don's measurements) but we removed more than 80 lines of code and overall evaluation (that is where this is used most) was more readable. So we kept it.

32 bit or 64 bit ?

[Rebel]

32-bit registers would be fine, but a minor issue is to have two 16-bit short ints. Working with 16-bit registers/instructions has penalties and weak compiler/optimizer support on x86 or x86-64.

Yep. That's what I remember from the Pentium days. Apparently nowadays it seems nothing has changed. 16 bit is (still) bad news.

Code: Select all

struct Score {
    int16_t mgPart;
    int16_t egPart;
};

; to avoid on x86
mov	 r8w, WORD PTR  [...]
mov	 r9w, WORD PTR  [... + 2]
add	 r8w, 100
add	 r9w, 50

add	 r8w, WORD PTR  [...]
add	 r9w, WORD PTR  [... + 2]...
...
mov	 WORD PTR  [...], r8w
mov	 WORD PTR  [... + 2], r9w

Actually, any math you do on 16-bit quantities will probably be done in a 32-bit register because of the penalties that 16-bit instructions have (partial register stalls or false dependencies on previous contents, etc.) What x86 chips do have is excellent support for zero- or sign-extension into 32- or 64-bits while loading from an 8- or 16-bit memory value. So you can expect the compiler to do a movzx or movsx to load it into a 32-bit register, do 32-bit math on it, and then store back the 16 bits when done. Occasionally it will have to insert extra instructions to preserve the semantics of the 16-bit type (truncation before multiplying, or something like that?). Its still a good idea to declare temporary variables as a 32-bit type and just truncate it back to 8- or 16-bits when you store it in a data structure.

But the "two scores in one register" trick: Does it save instructions? Yes. Will it execute any faster? Maybe a cycle faster here or there, but probably you won't notice any difference. So is it worth doing at all? If so, only for code cleanliness reasons (thinking of a "Score Pair" for MG/EG and always updating both at the same time)

I am taking code from R1-x64

Code: Select all

0x401b62: test   %r15,%rax                        if on full-open file (bP)
0x401b65: jne    0x401b73
0x401b67: add    $0x3cb,%esi                      add 971 in MG
0x401b6d: add    $0xac,%edi                       add 172 in EG

There is no loading from nor storage to memory in this process. The compiler keeps both EDI and ESI. And the 2 x add are executed simultaneously. All in one processor cycle. Nothing can beat this IMO.

[mcostalba]

32 bit or 64 bit ?

I have tested in 32 bits. My guess is that even if the speed is the double, given that we are talking of just an extra "add" each time a score is added, also if we use say 50 score pairs in evaluation, the total count goes up of 50 add instructions every time evaluation is called and this is really barely measurable. I am even surprised that is measurable at all.

[Pierre Bokma]

Thanks for all the valuable input. I have implemented the Stockfish version, I cannot say if this a speed improvement (my engine is in the early stages) but it sure makes coding a lot easier. The gain in clearness of the code is a hudge advantage in my opinion.

[Evert]

not some completely unnecessary mg&eg score combination. Say I decided to have three game states

I agree.

On some level, it doesn't make sense to me that the current evaluation should be some linear interpolation between a "middle game" evaluation and an "end game" evaluation. What does make sense to me is that the evaluation of any piece should have two components: how much it's worth in the current position and its future potential. As the future potential of some evaluation terms decreases (knights in the end game, king safety when there are fewer pieces on the board) their evaluation is scaled down while other terms (like passed pawns) become more important.

Modelling that as some interpolation between middle game and end-game evaluation is clearly the simplest way to do it, but it's not at all clear that it's the best way. For instance, not all evaluation terms need to scale in the same way. Some might not scale with the value of pieces still on the board, but rather some other metric.

It would be far more interesting if people experimented with this rather than all doing the same type of middle-end game interpolation. Of course the number of parameters that can be tuned would explode...

[wgarvin]

not some completely unnecessary mg&eg score combination. Say I decided to have three game states

I agree.

On some level, it doesn't make sense to me that the current evaluation should be some linear interpolation between a "middle game" evaluation and an "end game" evaluation. What does make sense to me is that the evaluation of any piece should have two components: how much it's worth in the current position and its future potential. As the future potential of some evaluation terms decreases (knights in the end game, king safety when there are fewer pieces on the board) their evaluation is scaled down while other terms (like passed pawns) become more important.

Modelling that as some interpolation between middle game and end-game evaluation is clearly the simplest way to do it, but it's not at all clear that it's the best way. For instance, not all evaluation terms need to scale in the same way. Some might not scale with the value of pieces still on the board, but rather some other metric.

It would be far more interesting if people experimented with this rather than all doing the same type of middle-end game interpolation. Of course the number of parameters that can be tuned would explode...

Assume that you encapsulate this stuff as some sort of "ScorePair" object, and do updates to it with adds and small-factor multiplies. (It doesn't much matter whether you implement the "ScorePair" as a struct with two ints, or with the two-values-packed-in-one-int trick.) Then you could easily change later to three or even four different values, just by (1) changing the implementation of the ScorePair type, and (2) fixing each table of ScorePair constants, or other defined ScorePair constants, so they contain three or four values.

At the end of the eval when you want to interpolate between the three or four values, it doesn't have to be a simple linear interpolation between two numbers. Anything that gives weights that sum up to 1 could be used to linearly combine them (e.g. normalized barycentric coordinates). So for example, you could have three score slots, corresponding to "early middlegame", "late middlegame" and "endgame". And it could combine them with something like

Code: Select all

(EMG*(1-t1)+LMG*t1)*(1-t2) + (EG*t2)

where t1 blends between early and late middlegame phases, and t2 blends from middlegame to endgame. Non-linear combinations might also work, who knows.

The nice thing is that, to try out a scheme like this, you would not have to edit the code of every eval feature. You'd just edit "ScorePair" and replace all of your tables and constant-generating macros etc.

[Don]

not some completely unnecessary mg&eg score combination. Say I decided to have three game states

I agree.

On some level, it doesn't make sense to me that the current evaluation should be some linear interpolation between a "middle game" evaluation and an "end game" evaluation. What does make sense to me is that the evaluation of any piece should have two components: how much it's worth in the current position and its future potential. As the future potential of some evaluation terms decreases (knights in the end game, king safety when there are fewer pieces on the board) their evaluation is scaled down while other terms (like passed pawns) become more important.

The idea of interpolating between 2 evaluation functions makes developing an evaluation function far easier, but I'm with you on this, I don't think it's ideal.

Each position has different considerations and the "stage" of the game is only one of many of those considerations. It turns out that it is one of the more relevant things and so it is an easy way to proceed.

A simple test case to focus on is where to put the king? There is an awkward stage between opening an middle game where we are not completely satisfied with Komodo. The interpolation of the two tables does not make that much sense to us.

What to do with the king is a precarious balance between how safe it is and how useful it can be as a fighting piece and it highly correlated to how many pieces are on the board and what they are.

Modelling that as some interpolation between middle game and end-game evaluation is clearly the simplest way to do it, but it's not at all clear that it's the best way. For instance, not all evaluation terms need to scale in the same way. Some might not scale with the value of pieces still on the board, but rather some other metric.

Of course if they don't scale you can simply give them the same or close to the same values. But the problem is that they don't phase from one to the other exactly the same, it's not necessarily linear. You can have significantly different values for a single opening and middle-game term but the middle-game value may be dominant until we are almost in a king and pawn ending for example and then the transition should be sudden.

A way to deal with that (which adds a lot of complexity) is to pick a center point for the interpolation, one for each eval term. If your stages range from 0 to 100 for the middlegame the center point does not have to 50, it could be some other value. But that is only one kind of curve and may not be the most appropriate one for every evaluation feature.

I fear at this point in time the knowledge engineering aspect of chess is complicated and we have such a long way to go that even though the interpolation idea is probably not ideal, it's not our biggest problem. .

It would be far more interesting if people experimented with this rather than all doing the same type of middle-end game interpolation. Of course the number of parameters that can be tuned would explode...

[BubbaTough]

OK,

I was looking at stockfish, and it looks like the following is true in their implementation.

1. multiplication / division is not truly supported (they might define functions that fake it, but they just extract the values, do operations, and reinsert making it slower than keeping things in two different variables).

2. negative values...I am not sure if these are gracefully handled during addition/subtraction. It seems maybe not? If not there is great risk for causing problems (such as calculating the net gain / loss of a PST entry from a move).

Is this correct (particularly the negative value thing, I must admit I am too lazy to work through the twos complement thing carefully myself)?

-Sam

[rvida]

1. multiplication / division is not truly supported (they might define functions that fake it, but they just extract the values, do operations, and reinsert making it slower than keeping things in two different variables).

Multiplication is supported and safe (as long as you do not cause an overflow). Division does not work.

2. negative values...I am not sure if these are gracefully handled during addition/subtraction. It seems maybe not? If not there is great risk for causing problems (such as calculating the net gain / loss of a PST entry from a move).

Addition/subtraction handles signed arithmetic correctly. Negative values are overflow-corrected when extracting individual (eg/mg) values.