double memory of data in fruit

[Uri Blass]

I see the following code in Fruit2.1 in board_is_ok function.
I wonder what is the reason for memoryzing the same data twice.

if (board->number[WhitePawn12] != board->pawn_size[White]) return false;
if (board->number[BlackPawn12] != board->pawn_size[Black]) return false;
if (board->number[WhiteKing12] != 1) return false;
if (board->number[BlackKing12] != 1) return false;

[Sven Schüle]

Hi Uri,

although the 'pawn_size[]' array appears to be redundant because its usage might always be replaced by using 'number[WhitePawn12]' and 'number[BlackPawn12]', I think the solution with the additional 'pawn_size[]' array is cleaner and better for two reasons:

- When given a colour as a variable, you would have to transform it into the appropriate constant 'WhitePawn12' or 'BlackPawn12' when accessing 'number[]', using either a ?: operation, another small array with two entries or (worst solution) an ugly cast, using knowledge that White == WhitePawn12 and Black == BlackPawn12.

- The 'piece[][]' array has 'piece_size[]' to maintain list sizes, and it is obvious to have the same for the 'pawn[][]' array, 'pawn_size[]'.

The runtime overhead seems to be small for me.

I hope my interpretation of Fabien's code is right, of course I might have missed some important detail.

Sven

[Fabien Letouzey]

Hi Sven,

I hope my interpretation of Fabien's code is right, of course I might have missed some important detail.

Your interpretation is right.

Fabien.

[Uri Blass]

Thanks for the information

Note only that if I do not miss something
board->number[WhiteKing12] is always 1 so I do not understand why
to include it(maybe it was done only to detect bugs)

I tried to figure out when board->number[piece_type] is used because
I have not it in Movei and I always use expressions like
numpawns[side] or numknights[side]

I see in move_do.cpp

ASSERT(board->number[piece_12]<9);
board->number[piece_12]++;

I think that it is wrong because there may be 10 rooks or 10 knights or 10 bishops in chess.

Uri

[Sven Schüle]

I see in move_do.cpp

Code: Select all

ASSERT(board->number[piece_12]<9);
board->number[piece_12]++;

I think that it is wrong because there may be 10 rooks or 10 knights or 10 bishops in chess.

The ASSERT seems to wrong, should perhaps be something like this:

Code: Select all

int max_number[] = { 8, 8, 10, 10, 10, 10, 10, 10, 9, 9, 1, 1 };
...
ASSERT(board->number[piece_12] < max_number[piece_12]);

Sven

[Dann Corbit]

I see in move_do.cpp

Code: Select all

ASSERT(board->number[piece_12]<9);
board->number[piece_12]++;

I think that it is wrong because there may be 10 rooks or 10 knights or 10 bishops in chess.

The ASSERT seems to wrong, should perhaps be something like this:

Code: Select all

int max_number[] = { 8, 8, 10, 10, 10, 10, 10, 10, 9, 9, 1, 1 };
...
ASSERT(board->number[piece_12] < max_number[piece_12]);

Sven

I think it is an array bounds check.
If the index is 8 or less then you can increment it.
If the index is 9, when incremented it will become 10.
That would indicate 11 chessmen and is too large.

So I think that the assert is correct.

The suggestion to use an array to check for smaller bounds for a given type is a good one, but Fabien is checking pre-increment and the numbers provided are post-increment. Also, it is a big mistake to ever increment (or decrement) the king count.

IMO-YMMV.

[Uri Blass]

I see in move_do.cpp

Code: Select all

ASSERT(board->number[piece_12]<9);
board->number[piece_12]++;

I think that it is wrong because there may be 10 rooks or 10 knights or 10 bishops in chess.

The ASSERT seems to wrong, should perhaps be something like this:

Code: Select all

int max_number[] = { 8, 8, 10, 10, 10, 10, 10, 10, 9, 9, 1, 1 };
...
ASSERT(board->number[piece_12] < max_number[piece_12]);

Sven

I think it is an array bounds check.
If the index is 8 or less then you can increment it.
If the index is 9, when incremented it will become 10.
That would indicate 11 chessmen and is too large.

So I think that the assert is correct.

The suggestion to use an array to check for smaller bounds for a given type is a good one, but Fabien is checking pre-increment and the numbers provided are post-increment. Also, it is a big mistake to ever increment (or decrement) the king count.

IMO-YMMV.

You say:
"If the index is 9, when incremented it will become 10.
That would indicate 11 chessmen and is too large."

I do not think that it is right
I do not see how 10 means 11 chessmen.

It is clear that 1 means 1 king by that code:
if (board->number[WhiteKing12] != 1) return false;

It means that 10 means 10 pieces of that type.

Uri

[Sven Schüle]

If the index is 9, when incremented it will become 10.
That would indicate 11 chessmen and is too large.

As Uri wrote in parallel to me: 10 means 10.

The suggestion to use an array to check for smaller bounds for a given type is a good one, but Fabien is checking pre-increment and the numbers provided are post-increment.

No problem with pre-increment check if the check is "xxx < max_number".

Also, it is a big mistake to ever increment (or decrement) the king count.

I think we can be pretty sure that Fruit never plays with zero or more than two kings Besides, the code being discussed belongs to a function square_set() which is used for promotions and restoring captured pieces, as far as I can see. This will never touch the king count, provided no king capture occurs.

Sven

[Dann Corbit]

int foo[10];

int index = 10;

foo[index] = 5; /* This overwrites memory because 10 is too large. */

[Sven Schüle]

int foo[10];

int index = 10;

foo[index] = 5; /* This overwrites memory because 10 is too large. */

Dann,

I know this but my code proposal does not compare an array index with a max number but a number of pieces of given type. 'board->number[...]' is checked against an allowed maximum.

Sven

[Chan Rasjid]

Uri,

After I decided on paying attention to nps, I goggle for "tips tricks C C++
optimization" and I found some good articles and I almost broke every basic rule. One good article is this:-
http://www.npac.syr.edu/nse/hpccsurvey/ ... ntley.html

from another article on optimization:-

LOCALITY OF REFERENCE

The FOREMOST consideration when optimizing memory access, whether for virtual memory or cache considerations, is locality of reference. That is the property of a program to use addresses which are near (in both time and location) other recent references to memory. The main difference between optimizing for VM and optimizing for cache is scale: VM pages can be anywhere from 0.5kb to 8kb and beyond and can take tens of milliseconds to read in from disk. Cache blocks typically range from 16 bytes to 256 bytes and get read in in the tens of microseconds. A program which forces many VM pages or cache lines to load in quick succession is said to be "thrashing."

You can affect locality of reference by changing the order in which you access and allocate things and by splitting your data structures into "frequently used" and "infrequently used" segments and allocating all the "frequently used" stuff together. (But don't fool yourself into thinking that malloc always allocates adjacent chunks of memory on each successive call. You have to allocate one giant chunk and dole it out yourself to be certain. But this can lead to other problems.)

Fabien almost followed the above to the letter.

1) I had silly things like int fn(char a, char b);
2) Gian mentioned not to pass pointers(to var ?) as function parameters
but did not expained fully. Consider:-

int AA, b, c;

//at this point optimization may want AA in register
b = fn(&AA);
with the fn() call, AA must be pushed back to stack as &register is invalid.
Of course it becomes an issue only if the codes are critically active.
So the rule is only to pass only int(never char/short) or pointer to struct as function arguments.

3) Fruit has int opening,endgame. I only know they are for incremental
PST scores.I don't check the details but guess the meaning. Probably
the reason to updates 2 sets is cheap as all relevant references should be within 128 byte same cache line, one var after the next,etc..
With either open/endgame stage we may need to re-compute for all pieces when stage changes(which is often as captures are ordered high).
So just keep 2 sets and take either opening or endgame PST score on eval() depending on the actual stage.So again Fruit makes 2 copies ready even though only 1 is finally used(My guess).

4) Fruit pays attention to the magic numbers 256,128, 64, 32.

Rasjid

[Uri Blass]

Rasjid,
Your guess in 3 is not correct.
Based on my understanding
Fruit always calculate both opening evaluation and endgame evaluation
and calculate average of them based on the value of pieces.

There may be parts that are identical both in the opening and the endgame but I think that it is a mistake to care about speed in early stage and fruit is still only in early stage.

My guess is that Fruit is going to get more than 100 elo improvement in the next year not thanks to speed improvement when speed improvement that may make fruit 10% faster may help it to get less than 1/10 of it so it is clear that it is a bad idea for fabien to invest time on nodes per second today.

Uri

[Dann Corbit]

{snip}
1) I had silly things like int fn(char a, char b);
2) Gian mentioned not to pass pointers(to var ?) as function parameters
but did not expained fully. Consider:-

int AA, b, c;

//at this point optimization may want AA in register
b = fn(&AA);
with the fn() call, AA must be pushed back to stack as &register is invalid.
Of course it becomes an issue only if the codes are critically active.
So the rule is only to pass only int(never char/short) or pointer to struct as function arguments.
{snip}
Rasjid

That rule is simply wrong. If you pass a struct by value instead of by pointer or by reference, then it will push a copy of the entire structure onto the stack. That is so bad that it deserves no further mention. The only time you should pass a struct by value is if it must not be changed, and even then you could pass pointer to const or rerference to const which would be much better.

As far as passing objects on a stack instead of pointers to objects -- in the first place, you are only pushing at most sizeof(address) when you pass a pointer. On a 32 bit system (or a 64 bit system with 32 bit addressing) you are pushing one 4 byte value. The cost for that is very small.

Now, passing by register is faster than passing by value for a calling convention. But we are talking about 1% or 2% at most for a program speed to improve by this change.

Those rules are silly rules and wrong rules. By far, far, far write code that is clear and expresses your meaning in the best way. Any savings you might hope for from passing a value verses passing an address are going to be marginal or even negative.

Don't do that. I do not see places in Fabien's code where he abuses those sorts of rules. I think it is imagination.

[diepeveen]

Dann,

If you can save 1% somewhere with just a week work, you must do it. I would never ignore a hint of GCP in that respect.

Good programmers don't only write the right code, they also optimize it utmost.

Vincent

{snip}
1) I had silly things like int fn(char a, char b);
2) Gian mentioned not to pass pointers(to var ?) as function parameters
but did not expained fully. Consider:-

int AA, b, c;

//at this point optimization may want AA in register
b = fn(&AA);
with the fn() call, AA must be pushed back to stack as &register is invalid.
Of course it becomes an issue only if the codes are critically active.
So the rule is only to pass only int(never char/short) or pointer to struct as function arguments.
{snip}
Rasjid

That rule is simply wrong. If you pass a struct by value instead of by pointer or by reference, then it will push a copy of the entire structure onto the stack. That is so bad that it deserves no further mention. The only time you should pass a struct by value is if it must not be changed, and even then you could pass pointer to const or rerference to const which would be much better.

As far as passing objects on a stack instead of pointers to objects -- in the first place, you are only pushing at most sizeof(address) when you pass a pointer. On a 32 bit system (or a 64 bit system with 32 bit addressing) you are pushing one 4 byte value. The cost for that is very small.

Now, passing by register is faster than passing by value for a calling convention. But we are talking about 1% or 2% at most for a program speed to improve by this change.

Those rules are silly rules and wrong rules. By far, far, far write code that is clear and expresses your meaning in the best way. Any savings you might hope for from passing a value verses passing an address are going to be marginal or even negative.

Don't do that. I do not see places in Fabien's code where he abuses those sorts of rules. I think it is imagination.

[Uri Blass]

Dann,

If you can save 1% somewhere with just a week work, you must do it. I would never ignore a hint of GCP in that respect.

Good programmers don't only write the right code, they also optimize it utmost.

Vincent

1% speed improvement for week of work could give fabien not more than 1 elo per week

Fabien does a lot better than it so I do not think that good programmers spend a lot of time in optimizing their code to be faster.

Uri

[mridul]

There is a difference between writing a program from scratch and a program which has already matured and optimised.

When progress becomes tougher , when you have eliminated all bugs you can find and cant find any new ones , when adding a new "feature" becomes more expensive than the benifits ... you can keep expirimenting with new ideas , but anything which gives you 1% improvement will be very carefully pursued.
This is common not just to chess but to most other s/w & h/w projects.

And dont take anything and everything stated in context of Fruit and Fabien.

[Uri Blass]

There is a difference between writing a program from scratch and a program which has already matured and optimised.

When progress becomes tougher , when you have eliminated all bugs you can find and cant find any new ones , when adding a new "feature" becomes more expensive than the benifits ... you can keep expirimenting with new ideas , but anything which gives you 1% improvement will be very carefully pursued.
This is common not just to chess but to most other s/w & h/w projects.

And dont take anything and everything stated in context of Fruit and Fabien.

I think that working a week for 1% improvement is not good idea even for Fruit WCCC

If you think that working a week for 1% improvement is the best thing that you can do and your program is not significantly better than Fruit WCCC then I think that it is probably not written well and it may be a better idea to start from scrartch.

Uri

[mridul]

The very reason different programs have different styles is because the underlying ideas are different , the assumptions made and the problems being solved are different - all attempting to play chess , but in different ways.

Just 'cos one specific impl does well does not imply that all others are thrash and should start from scratch.
Tommorrow if SMK is to opensource shredder , you will say the same thing about any other program (including fruit) I guess ?

And , please dont forget that lot of us (ok , atleast some of us like me ) do chess programming to relax after a days/weeks tough work : to chat , think and unwind - you dont want to take that away do you ?

The original comment would be relevent to professionals I guess ... not to me for sure !
If something I work on at office requires improvement and I have to work for weeks for 1 - 5 % improvement , I would - I get paid for that work : not for a chess program I do for fun and am not very serious about (yet).
For a professional - chess is their bread , so they work for 1 - 5 % improvements for weeks on end.


Now , if we are to talk technical merits , let us analyse fruit:

From what I have last seen , the important points will be (I am not doing an exhaustive analysis here) :
1) Data organisation and use - to maximise cache coherence.
2) Simple and tight loops - reduce branch mispredictions.
3) Nothing agressive - no dubious ideas that I can find offhand.
4) Essentially bugfree to a large extent (dont underestimate this fact).
5) Well tuned params (just from a cursory look) - nothing which were conflicting each other (this can be a major problem).
6) I did not see anything speculative in eval , but then I did not find it sufficiently sophisticated.
Does not need to be - the search takes it deep enough to play positionally sound chess : so lot of things I always toy around with are essentially absent.
7) this space for rent.

So you see , just that your code has bugs - get a decent search going , simple and yet essentially bugfree eval and qsearch and you will be strong engine.
Only difference is that I dont want a super strong engine - I want to write something which entertains me while writing it : I like to see my engine's eval rise because of its qsearch 4 moves before crafty sees danger.
I want to be able to play with ideas in kingsafety , make the static eval "understand" the position , etc.
All these are buggy if not done well (including tuning bugs).
Different people get different kicks

Crafty and fruit from what I have seen rarely understand the static nature of a position well enough - but their search depth is their strength.

Please note , my whole point is that , you can make movei superstrong by just making it bugfree , implementing a good eval and removing dubious things from search/eval (definition of dubious is upto you to define !).
You do not have to rewrite it to use ideas from fruit - what works for fruit maynot work for you and viceversa.


- Mridul

[Uri Blass]

I certainly need to implement ideas from fruit because my code is too ugly and writing good code with one of the ideas from fruit.

I do not have in Movei a lot of knowledge that fruit has both in evaluation and search(it is a common knowledge but Movei does not have it and I did not do the effort to add it because I hate my ugly code).

My division of the code to files is not good and I think that how to divide code to files is the first thing that I can learn from fruit(I may work slightly more about movei of today because I started to work on a function to generate only checks and did not finish it but basically I plan to start a new project when I may copy and paste part from the old project but the organization of files will be different) .

Uri

[Dann Corbit]

{snip}
My division of the code to files is not good and I think that how to divide code to files is the first thing that I can learn from fruit(I may work slightly more about movei of today because I started to work on a function to generate only checks and did not finish it but basically I plan to start a new project when I may copy and paste part from the old project but the organization of files will be different) .

Uri

Your code is ugly, but for a person learning to program it is really quite amazing.

The division of files is not so important. The division of tasks into functions is pretty important and you do well enough there.

It might be worthwhile to start from scratch, and move your good movei ideas from the old program to the new one, one at a time.

You can look at really well written things (like Fruit) to get an outline of how to do it.

Just a thought.

But it will be really dissapointing for two or three months.