0x88 with pointers

[Robert Pope]

I decided to start from scratch again and try to write an 0x88 style program, but instead of using an array of integers for the board, I wanted to try an idea from one of Bob's old papers on chessboard representations: a piece_list array, and then have the 0x88 board be an array of pointers, each pointing to the appropriate element of the piece_list.

So, at first, when I initialized the empty squares of piece_entry *board[128] I set them equal to '\0'. But then when I wrote a little loop to print the pieces on the board, it crashed on
printf("%c ",bd[120]->piece); which is the first square that is off-board.

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

[bob]

I decided to start from scratch again and try to write an 0x88 style program, but instead of using an array of integers for the board, I wanted to try an idea from one of Bob's old papers on chessboard representations: a piece_list array, and then have the 0x88 board be an array of pointers, each pointing to the appropriate element of the piece_list.

So, at first, when I initialized the empty squares of piece_entry *board[128] I set them equal to '\0'. But then when I wrote a little loop to print the pieces on the board, it crashed on
printf("%c ",bd[120]->piece); which is the first square that is off-board.

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

The normal way is to simply check for a null value before de-referencing the pointer.

if (p)
*p=something:

for example...

[Sven]

I decided to start from scratch again and try to write an 0x88 style program, but instead of using an array of integers for the board, I wanted to try an idea from one of Bob's old papers on chessboard representations: a piece_list array, and then have the 0x88 board be an array of pointers, each pointing to the appropriate element of the piece_list.

So, at first, when I initialized the empty squares of piece_entry *board[128] I set them equal to '\0'. But then when I wrote a little loop to print the pieces on the board, it crashed on
printf("%c ",bd[120]->piece); which is the first square that is off-board.

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

If you represent empty squares (or off-board squares) by a NULL pointer then you need to check each time when accessing a particular square whether the pointer is NULL, since dereferencing a NULL pointer will let your program crash. If you represent them by a pointer to a constant "No Piece" entry which you use for all empty (or off-board) squares then you avoid that.

But the question is whether this difference is relevant for your program. For the off-board squares you will need the 0x88 test anyway when generating moves or attacks, so you would probably never access any element of your board[128] array that belongs to an off-board square. Regarding the empty "real" squares, it might be possible that you frequently need some kind of "isEmpty" condition for a square. In that case the NULL pointer might pay off since comparing a pointer to zero might be slightly cheaper than dereferencing a pointer and comparing one of the struct members to zero. You would have to always test for "isEmpty" before accessing a non-empty square, though.

I have never tested this pointer approach. I am pretty sure that Bob has tested it prior to mentioning it in his paper back then. Actually I don't believe it makes much of a difference to the traditional approach that stores piece types directly in the board array, assuming of course that both approaches are implemented correctly. If measurable at all, I would guess that the pointer approach may turn out as slightly better. Updating the board (i.e. makeMove()) will most probably be cheaper with the pointer approach since you only change two pointers for most moves, and save the pointer to the captured piece. Reading the board might be slightly less efficient with the pointer approach but the evaluation function will also use the piece list itself a lot.

Btw: '\0' is not the typical way of representing a null pointer. '\0' is a constant that is typically used to represent a null byte which is just one character. The compiler will convert it to a null pointer if you assign '\0' to a pointer variable, but it might also print a warning while doing so. Better use a simple 0 for a null pointer instead of '\0'. For some people NULL seems to look better than 0 so they use that instead.

I also do not know why your loop that prints the pieces on the board wants to print anything for the square no. 120. As you wrote it is off-board, so why printing it?

Code: Select all

int r;
int f;
for (r = 7; r >= 0; r--) {
    for &#40;f = 0; f <= 7; f++) &#123;
        int sq = &#40;r << 4&#41; | f;
        assert&#40;!&#40;sq & 0x88&#41;);
        assert&#40;board&#91;sq&#93; != 0&#41;;
        printf&#40;"%c ", board&#91;sq&#93;->piece&#41;;
    &#125;
    printf&#40;"\n");
&#125;

will never attempt to visit an off-board square, and assumes that you use a constant piece entry for all empty on-board squares.

Sven

[Robert Pope]

Ok, I'll try that. I thought that needing if() statements all the time would be an expensive operation.

[bob]

Ok, I'll try that. I thought that needing if() statements all the time would be an expensive operation.

Depends on what you are doing. If a pointer is null most of the time, or non-null most of the time, the branch will be predicted correctly most of the time and there is no cost. If not, then you might do something like what we did in Cray Blitz and attempt to collect all the non-zero pointers together so that you can avoid stepping over all the null pointers. This is pretty common for board representations since at least 1/2 of the squares are always empty and stepping over them is fairly costly.

[hgm]

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

It is usually not competitive to store the complete pointer, which is unnecessary bulky (it could be 64 bit), and thus wastes lots of cache space. A better approach is therefore to store the piece-list index of pieces in the board array. So you would write list[bd[120]].piece rather than bd[120]->piece. On modern CPUs there is no speed penalty for this; adding the start address of the list[] array to the index is done in the addressing mode of the instruction that loads the item from the array. So it does not require a separate instruction, and is executed in parallel with other instructions, by one of the CPU's address-generation units, and thus also not competing for arithmetic/logic units executing other instructions.

Apart from that, you are right. To make this efficient you will need an extra element in the piece list for empty squares. By giving this dummy piece a value of 0, a PST and Zobrist tables containing all zeros, etc., you don't need to make any distinction between captures and non-captures in the MakeMove() code.

[Robert Pope]

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

It is usually not competitive to store the complete pointer, which is unnecessary bulky (it could be 64 bit), and thus wastes lots of cache space. A better approach is therefore to store the piece-list index of pieces in the board array. So you would write list[bd[120]].piece rather than bd[120]->piece. On modern CPUs there is no speed penalty for this; adding the start address of the list[] array to the index is done in the addressing mode of the instruction that loads the item from the array. So it does not require a separate instruction, and is executed in parallel with other instructions, by one of the CPU's address-generation units, and thus also not competing for arithmetic/logic units executing other instructions.

Apart from that, you are right. To make this efficient you will need an extra element in the piece list for empty squares. By giving this dummy piece a value of 0, a PST and Zobrist tables containing all zeros, etc., you don't need to make any distinction between captures and non-captures in the MakeMove() code.

If list(bd(120)) is just as fast or faster, it is certainly more intuitive to me. At least I am early enough in that I can play around some. I just wish I understood what was efficient/inefficient better than I do.

And my android phone doesn't have brackets. Go figure.

[Robert Pope]

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

It is usually not competitive to store the complete pointer, which is unnecessary bulky (it could be 64 bit), and thus wastes lots of cache space. A better approach is therefore to store the piece-list index of pieces in the board array. So you would write list[bd[120]].piece rather than bd[120]->piece. On modern CPUs there is no speed penalty for this; adding the start address of the list[] array to the index is done in the addressing mode of the instruction that loads the item from the array. So it does not require a separate instruction, and is executed in parallel with other instructions, by one of the CPU's address-generation units, and thus also not competing for arithmetic/logic units executing other instructions.

Apart from that, you are right. To make this efficient you will need an extra element in the piece list for empty squares. By giving this dummy piece a value of 0, a PST and Zobrist tables containing all zeros, etc., you don't need to make any distinction between captures and non-captures in the MakeMove() code.

If list(bd(120)) is just as fast or faster, it is certainly more intuitive to me. At least I am early enough in that I can play around some. I just wish I understood what was efficient/inefficient better than I do.

And my android phone doesn't have brackets. Go figure.

[Robert Pope]

I guess that is because bd[120]=='\0', so bd[120]->piece is undefined. I can get around it by adding a 33rd entry to the piece_list table for all empty squares and point to that. But I wanted a little feedback on whether that was a good approach, or if there were advantages to setting the empty squares to NULL pointers.

It is usually not competitive to store the complete pointer, which is unnecessary bulky (it could be 64 bit), and thus wastes lots of cache space. A better approach is therefore to store the piece-list index of pieces in the board array. So you would write list[bd[120]].piece rather than bd[120]->piece. On modern CPUs there is no speed penalty for this; adding the start address of the list[] array to the index is done in the addressing mode of the instruction that loads the item from the array. So it does not require a separate instruction, and is executed in parallel with other instructions, by one of the CPU's address-generation units, and thus also not competing for arithmetic/logic units executing other instructions.

Apart from that, you are right. To make this efficient you will need an extra element in the piece list for empty squares. By giving this dummy piece a value of 0, a PST and Zobrist tables containing all zeros, etc., you don't need to make any distinction between captures and non-captures in the MakeMove() code.

If list(bd(120)) is just as fast or faster, it is certainly more intuitive to me. At least I am early enough in that I can play around some. I just wish I understood what was efficient/inefficient better than I do.

And my android phone doesn't have brackets. Go figure.