Fruit's Board Representation?

[Steve Maughan]

I think I recall that Fruit has a 16 x 16 board representation. And I think I remeber someone, probably Fabian, saying that this gives the benefits of post-box and x88. Having recently given this some thought I'm not sure how this can be the case. I cannot find a mask such that a simple '&' (or any other) operation will give a simple on/off board result (i.e. x88 approach), while still allowing [Square - 33] to be always a valid array index (i.e. postbox approach).

What am I missing? Can anyone explain the 16 x 16 approach?

Thanks,

Steve

[Michael Yee]

Not that this answers your question, but I seem to remember Tord saying that either gothmog or glaurung also used a 16x16 board...

[Igor Gorelikov]

If you have a certain bit set representing a piece on the board, you may use a board of any size for bitwise operation.
Just AND the board with the mask where those bits are set and you get what you want.

Igor

[Marcus Prewarski]

Diablo uses the same. I was planning on using just a mailbox style board until Tord explained the benefits of the 16x16 board. If you picture a 16x16 array, the actual board occupies the middle of the left half. In C the data structures could looks something like:

int all_squares[256];
int *squares;

squares = &all_squares[64];

You can now treat the data accessed by the squares pointer as if it points to an 8x16 arrary and thus do all the 0x88 tricks. And since you won't have the same bounds issues of a true 8x16 array you can still do all the same mailbox tricks.

[Tord Romstad]

I think I recall that Fruit has a 16 x 16 board representation. And I think I remeber someone, probably Fabian, saying that this gives the benefits of post-box and x88. Having recently given this some thought I'm not sure how this can be the case. I cannot find a mask such that a simple '&' (or any other) operation will give a simple on/off board result (i.e. x88 approach), while still allowing [Square - 33] to be always a valid array index (i.e. postbox approach).

What am I missing? Can anyone explain the 16 x 16 approach?

Hi Steve,

I am not sufficiently familiar with Fruit's source code to know exactly how the board representation works, but Glaurung also uses a 16 x 16 board. My position data structure looks like this (in reality there are several additional fields in the struct, but I omit them here because they have no relevance in the current discussion):

Code: Select all

typedef struct {
    uint8 board_[256];
    uint8 *board;
} position_t

I visualise the 256-byte board_[] array as a 16x16 matrix containing the "real" chess board on the left half of the middle eight ranks. The squares outside the real board are initialised to the constant value OUTSIDE. This enables me to do standard mailbox move generation and board scanning.

However, I almost never use the board_[] array directly. Instead, I do something similar to this when initialising the position data structure:

Code: Select all

void initialise_position(position_t *pos) {
   pos->board = pos->board_ + 64;  /* 64 = index of first square on the "real board" */
}

In the rest of my program, I always use the board pointer instead of the board_[] array. This has the neat consequence that the a1 square ends up at index 0, and I can choose whether I want to regard the position data structure as a mailbox representation or a 0x88 representation. There are two equivalent ways to test whether a square is outside the real board:

Code: Select all

if(pos->board[sq] == OUTSIDE) { ... }

or

Code: Select all

if(sq & 0x88) { ... }

In practice, I have found that the first method is almost always a tiny bit faster, therefore I only use the &0x88 trick in some initialisation code which has no effect on the program's performance. In addition to the higher speed, the mailbox method has the advantage that it works equally well in Scatha, my hexagonal chess program. I try to keep the source code for both engines almost identical.

You may ask why I use a 16-file board representation at all (rather than a 10x12 mailbox array), when I never use the &0x88 trick. The answer is that a 16-file board has a couple of other advantages: You can find the rank and file of a square by division by 16, which is probably faster than division by 10 or a table lookup. Lookup tables for things like the distance between two squares and whether a piece on square x can possibly attack square y can be made more compact (by using the well-known table[x-y] trick instead of table[x][y]).

As you may have noticed, I don't really need a 16x16 board in order to make this work. A 13x16 board would work equally well.

Tord

[Steve Maughan]

The "penny has dropped" (to use an English expression). Thanks chaps! I was missing the:

Code: Select all

typedef struct {
int board-[256];
int *board;
};


trick. Really cool trick!

Steve

[Anonymous]

Tord:

Code: Select all

typedef struct {
    uint8 board_[256];
    uint8 *board;
} position_t

>However, I almost never use the board_[] array directly. Instead, I do
> something similar to this when initialising the position data structure:

Code: Select all

void initialise_position(position_t *pos) {
   pos->board = pos->board_ + 64;  /* 64 = index of first square on the "real board" */
}

>In the rest of my program, I always use the board pointer instead of the >board_[] array.

This sounds a bit less efficient (on x86 hardware) than the functional equivilant

#define A1_OFFSET 64
#define BOARD(sq) board_[(sq) + A1_OFFSET]

Using the pointer needs one indirection more, to access the value. Constant offsets (almost) don't need any time. On x86 they will just change the used upcode. For offsets > 127 (or so, I don't remember the details), the upcode gets a bit longer, however - so the program may use a bit more of code space, and might be less cache friendly. Also, accessing data through a pointer can make things harder for the optimizer.

uint8 *bp;

bp[sq] = something;
some_global_value = something_else;
bp[sq+1] = bp[sq];

The optimizer now cannot produce

bp[sq+1] = something; // which still might be cached in one register

Of course, this small example is not really realistic, and one would code it a bit different from the beginning. But it may show the point.

>There are two equivalent ways to test whether a square is outside the real board:

Code: Select all

if(pos->board[sq] == OUTSIDE) { ... }

or

Code: Select all

if(sq & 0x88) { ... }

>In practice, I have found that the first method is almost always a tiny bit faster

A surprise to me. The 0x88 method is just one typical test upcode (which any machine will have, althoug some RISC type machines may need to put 0x88 into an register first - on x86 the constant is inside the upcode).

The mailbox methods needs a memory access (most probably from cache), which just sounds slower.

Not that I think, that the points I mentioned really matter. As I mentioned before, I had added debug code somewhere in the inner loop. Something like

if (hashkey == 123456)
printf("got you\n"); /* to convenietly set a debugging breakpoint */

and the code was reproducably faster.

Another time from a speed discussion in CCC - we wanted to benchmark several abs() macros. It turned out, that using the abs() of Omid produced faster code, than using an empty abs() ... I checked the produced assembler, and all looked correct - the empty abs version was just missing a few assembly statements compared to the real one.

Cheers,
Dieter

[Steve Maughan]

Dieter,

This sounds a bit less efficient (on x86 hardware) than the functional equivilant

#define A1_OFFSET 64
#define BOARD(sq) board_[(sq) + A1_OFFSET]

Using the pointer needs one indirection more, to access the value. Constant offsets (almost) don't need any time. On x86 they will just change the used upcode. For offsets > 127 (or so, I don't remember the details), the upcode gets a bit longer, however - so the program may use a bit more of code space, and might be less cache friendly. Also, accessing data through a pointer can make things harder for the optimizer.

Interesting! I'll try both.

Code: Select all

if(sq & 0x88) { ... }

>In practice, I have found that the first method is almost always a tiny bit faster

A surprise to me. The 0x88 method is just one typical test upcode (which any machine will have, althoug some RISC type machines may need to put 0x88 into an register first - on x86 the constant is inside the upcode).

The mailbox methods needs a memory access (most probably from cache), which just sounds slower.

I think the reason why it's faster is that in most cases you need to do the memory access anyway i.e. once you've establish that the square is on the board you then need to make sure it's not one of your pieces, which is a memory access. The 0x88 metthod is only faster if the square proves to be off the board.

Regards,

Steve

[Anonymous]

I think the reason why it's faster is that in most cases you need to do the memory access anyway i.e. once you've establish that the square is on the board you then need to make sure it's not one of your pieces, which is a memory access. The 0x88 metthod is only faster if the square proves to be off the board.

Thanks, Steve! Indeed a convincing explanation.

Cheers,
Dieter

[Sune Fischer]

This sounds a bit less efficient (on x86 hardware) than the functional equivilant

#define A1_OFFSET 64
#define BOARD(sq) board_[(sq) + A1_OFFSET]

Do you know if there Is a difference between the macro and a const declaration like:

Code: Select all

uint8 * const Board = &Board_[offset];


It looks like the compiler has the same information available at compile time, so it ought to result in the same code.

A surprise to me. The 0x88 method is just one typical test upcode (which any machine will have, althoug some RISC type machines may need to put 0x88 into an register first - on x86 the constant is inside the upcode).

The mailbox methods needs a memory access (most probably from cache), which just sounds slower.

Most of the time I think one is interested in more information than
wether the square is on or off the board.
That is where I think mailbox has an advantage over 0x88, because
several tests can be applied in one go by asking more direct questions, e.g.

Code: Select all

 if (board[sq] & IS_WHITE_PIECE) {...}


-S.

[Anonymous]

[quote="Sune FischerDo you know if there Is a difference between the macro and a const declaration like:

Code: Select all

uint8 * const Board = &Board_[offset];


[/quote]

Good question. In practice, there will most probably be a difference, in theory? Perhaps, in this context, it is also important to mention, if you use C or C++. For the practical side. You will have one header, that says

extern uint8 *const Board;

Now, in some module, where the compiler will not see the actual initialisation of this pointer (I am not even sure, if this is legal), you will use the pointer. In that stupid example I gave, it could still not do the optimization - the compiler only knows that the pointer is constant. It does not know, if the some_gloabal_var will not alias the object pointed to. At least not, when the compiler is not doing some "inter module optimization".

Try it out, and show the generated assembly for both methods - once with and once without const. some_global_var should be uint8 (otherwise the compiler might use strict aliasing rules, and decide that for example an int cannot alias the object pointed to by an uint8 *).

Regards,
Dieter

[Fabien Letouzey]

I think I recall that Fruit has a 16 x 16 board representation. And I think I remeber someone, probably Fabian, saying that this gives the benefits of post-box and x88. Having recently given this some thought I'm not sure how this can be the case. I cannot find a mask such that a simple '&' (or any other) operation will give a simple on/off board result (i.e. x88 approach), while still allowing [Square - 33] to be always a valid array index (i.e. postbox approach).

What am I missing? Can anyone explain the 16 x 16 approach?

Thanks,

Steve

There is a little confusion regarding 0x88 (due to imprecise vocabulary). 0x88 (which I call 16x8 board) really brings TWO different things: the AND test for in/out, and the vector attacks (compact tables).

I care only about the latter, and any board with at least 15 files will do (for 8x8 chess, that is).

For an old discussion about the AND test, search for CCC posts by Christophe Theron posts called "why 0x88 is not so smart".

I changed from 16x12 (Fruit 1.5) to 16x16 (2.0) only to have a symmetric treatment of files and ranks.

Fabien.

[Uri Blass]

I wonder if the board representation is very important.

I simply use info[64] as the board representation when
0=a1,1=b1,...7=h1,...63=h8

info[x]=0(8) means white(black) pawn at square x respectively.
info[x]=1(9) means white(black) knight at square x.
...
info[x]=5(13) means white king at square x.
info[x]=22 means empty square.


Did someone try that method and how much faster are the alternatives?

[Steve Maughan]

Uri,

I wonder if the board representation is very important.

I doubt it makes too much difference +/- 10% maybe.

I simply use info[64] as the board representation when
0=a1,1=b1,...7=h1,...63=h8

info[x]=0(8) means white(black) pawn at square x respectively.
info[x]=1(9) means white(black) knight at square x.
...
info[x]=5(13) means white king at square x.
info[x]=22 means empty square.


Did someone try that method and how much faster are the alternatives?

Monarch uses this approach i.e. array of 64 squares. Monarch also uses the list of possible moves approach which is similar to Gnu 4 and Ferrett. The only real issue is how to detect the edge of the board and generate moves. How does Movie generate moves?

Steve

[Uri Blass]

1)practically info has more than 64 squares but I can usually think about it as array with 64 squares(originally it had 64 squares and I changed it after getting advice to do it and I think that it helped to do it slightly faster but there was not a big difference).

Here is the exact definition of it.

int PADDED_info[80];
int * const info = PADDED_info+8;

I have also the following code when I initialize info
for (i=64;i<72;i++)
info[i]=-1;
for (i=-8;i<0;i++)
info[i]=-1;

2)Maybe there is a more efficient way to do it with my structure but here are example functions that show how I do it(I show only one direction of rook and one direction of bishop but other directions are done in a similiar way)


I have an array that tells me the square that is in direction leftup to another square and in case that there is no square the array has -1

for rook moves I do not need special arrays
Note that I use the constant EMPTA and not EMPTY because EMPTY is used for another purpose and when I want to get the piece in square i piece(i) that is defined as info[i]&7

Note that I could use
while (info[target]==EMPTA) instead of while ((target!=-1)&&(info[target]==EMPTA)) but in my move generator I do not do it because I found that doing it did not make the program faster(often target=-1 so it is faster to calculate the long expression)

In other places in Movei I use the trick of not checking if the square is out of the board thanks to the extension of info.




static void generate7(int square)
{
int target;
target=leftup[square];
while ((target!=-1)&&(info[target]==EMPTA))
{
gen_quietnopawns(square,target);
target=leftup[target];
}
if ((target!=-1)&& (color(target)!=side))
gen_push(square,target);
target=rightdown[square];
while ((target!=-1)&&(info[target]==EMPTA))
{
gen_quietnopawns(square,target);
target=rightdown[target];
}
if ((target!=-1)&& (color(target)!=side))
gen_push(square,target);

}

static void generate1(int square)
{
int target=square+1;
while ((fil0(target)!=0)&&(info[target]==EMPTA))
{
gen_quietnopawns(square,target);
target+=1;
}
if ((fil0(target)!=0)&&(color(target)!=side))
gen_push(square,target);
target=square-1;
while ((fil0(target)!=7)&&(info[target]==EMPTA))
{
gen_quietnopawns(square,target);
target-=1;
}
if ((fil0(target)!=7)&&(color(target)!=side))
gen_push(square,target);

}

static void generatesimpleknights(int square)
{
int i,target;
for (i=0;i<knightnumber[square];i++)
{
target=knightmove[square][i];
if (info[target]==EMPTA)
gen_quietnopawns(square,target);
else
if (color(target)!=side)
gen_push(square,target);
}
}

[Steve Maughan]

[quote="Fabien LetouzeyI changed from 16x12 (Fruit 1.5) to 16x16 (2.0) only to have a symmetric treatment of files and ranks.
[/quote]

May I ask why you're interested in treating files and ranks symmetrically?

Steve

[Tord Romstad]

This sounds a bit less efficient (on x86 hardware) than the functional equivilant

Code: Select all

#define A1_OFFSET 64
#define BOARD(sq) board_[(sq) + A1_OFFSET]

My hardware is not 0x86, but the above code looks like it should run a tiny bit faster on other processors as well. Perhaps it is worth a try. Thanks for the suggestion!

Tord

[Ross Boyd]

Steve,

quote="Fabien LetouzeyI changed from 16x12 (Fruit 1.5) to 16x16 (2.0) only to have a symmetric treatment of files and ranks.


May I ask why you're interested in treating files and ranks symmetrically?

I believe it allows Fabien to use simple XORs to reflect the board left-to-right or top-to-bottom, to simplify evaluation of certain piece endings.
But I could be wrong.

Ross

[Fabien Letouzey]

May I ask why you're interested in treating files and ranks symmetrically?
Steve

For symmetries in simple endgames.
E.g. rank symmetry is simpler with 16x16.

Fabien.

[Daniel Shawul]

quote]This sounds a bit less efficient (on x86 hardware) than the functional equivilant

#define A1_OFFSET 64
#define BOARD(sq) board_[(sq) + A1_OFFSET] [/quote]

i use the pointer technique. how much is this slower?
I woder how deep i have to know c in order to program chess efficiently,cause everytime i think i improved there is something else that is better. May be it is better to study assembly and get it over with.
cheers
daniel