Recommended board representation for a rookie

[Fguy64]

Greetings...

I'm throwing out my first attempt at an engine and starting again from scratch. I'll be using C language, and I'd like to take a stab at creating my own GUI using GTK+

What board representation would you suggest for a rookie. I'm tempted to go with 0x88 because Bruce Moreland features a full page of documentation on his site, where he offers the following endorsement...

It's acceptably fast.
The code is small and not complex.
You get a good in-check routine as a side-effect.

http://web.archive.org/web/200707070125 ... /index.htm

[ZirconiumX]

Greetings...

I'm throwing out my first attempt at an engine and starting again from scratch. I'll be using C language, and I'd like to take a stab at creating my own GUI using GTK+

What board representation would you suggest for a rookie. I'm tempted to go with 0x88 because Bruce Moreland features a full page of documentation on his site, where he offers the following endorsement...

It's acceptably fast.
The code is small and not complex.
You get a good in-check routine as a side-effect.

http://web.archive.org/web/200707070125 ... /index.htm

You'll find the GUI significantly harder than any engine you write. Ultimately, my advice is to find something you're reasonably comfortable with and use that.

I initially worked with the 8x8 FirstChess code when I was a kid. Four years later, it's still the beating heart of my chess program.

[Fguy64]

You'll find the GUI significantly harder than any engine you write...

That's ok I've got plenty of time for learning, which is the main goal of this project.

[hgm]

0x88 board layout is very convenient, because square-number difference can be used to unambiguously find the board step. And it is space efficient, because you can use the 'unphysical' part of the board in board-size tables (like piece-square or Zobrist tables) for other board-size tables.

For the board itself the code simplifies a bit if you surround the actual playing area by a guard band of squares that are marked inaccessible, by placing something there that is distinguishable from both white and black pieces. You then only have to test whether moves land on empty or enemy piece to see if they are pseudo-legal, and when they land on own piece or boundary guard they are not pseudo-legal. There would be no need to check if the square number itself is valid.

[Fguy64]

0x88 board layout is very convenient, because square-number difference can be used to unambiguously find the board step. And it is space efficient, because you can use the 'unphysical' part of the board in board-size tables (like piece-square or Zobrist tables) for other board-size tables.

For the board itself the code simplifies a bit if you surround the actual playing area by a guard band of squares that are marked inaccessible, by placing something there that is distinguishable from both white and black pieces. You then only have to test whether moves land on empty or enemy piece to see if they are pseudo-legal, and when they land on own piece or boundary guard they are not pseudo-legal. There would be no need to check if the square number itself is valid.

in your second paragraph, are you describing 0x88 or are you describing something else? My understanding of 0x88 is that it is a 16 x 8 board, and how is it possible to surround the actual playing area by a guard band of squares and at the same time have a 16 x 8 board?

[Sven]

0x88 board layout is very convenient, because square-number difference can be used to unambiguously find the board step. And it is space efficient, because you can use the 'unphysical' part of the board in board-size tables (like piece-square or Zobrist tables) for other board-size tables.

For the board itself the code simplifies a bit if you surround the actual playing area by a guard band of squares that are marked inaccessible, by placing something there that is distinguishable from both white and black pieces. You then only have to test whether moves land on empty or enemy piece to see if they are pseudo-legal, and when they land on own piece or boundary guard they are not pseudo-legal. There would be no need to check if the square number itself is valid.

in your second paragraph, are you describing 0x88 or are you describing something else? My understanding of 0x88 is that it is a 16 x 8 board, and how is it possible to surround the actual playing area by a guard band of squares and at the same time have a 16 x 8 board?

His second paragraph is about 10x12 or something similar.

[hgm]

in your second paragraph, are you describing 0x88 or are you describing something else? My understanding of 0x88 is that it is a 16 x 8 board, and how is it possible to surround the actual playing area by a guard band of squares and at the same time have a 16 x 8 board?

You can embed the 16x8 board in a larger array. The crux of the 0x88 layout is that you leave a space as large as a rank (8 squares) between the storage cells of different ranks. So I am not talking about 10x12, but 16x12: for 10x12 you would not know if a step of +3 is a Rook move from (say) d4 to g4 or an impossible move from h4 to a5. So it would just be a 0x88 board with two ranks above and below it, all filled, just as the unused area of the 0x88 board, with border guards that make it obvious the square is off board to anything trying to go there.

Code: Select all

* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* 0 0 0 0 0 0 0 0 * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * *

[Sven]

So it would just be a 0x88 board with two ranks above and below it, all filled, just as the unused area of the 0x88 board, with border guards that make it obvious the square is off board to anything trying to go there.

With 0x88 I don't fill the unused area with border guards since I would need two tests, one for "0 <= square <= 127" and one for the presence of the border guard. Instead of that I only use the "is valid square" test ((square & 0x88) != 0).

[Gerd Isenberg]

So it would just be a 0x88 board with two ranks above and below it, all filled, just as the unused area of the 0x88 board, with border guards that make it obvious the square is off board to anything trying to go there.

With 0x88 I don't fill the unused area with border guards since I would need two tests, one for "0 <= square <= 127" and one for the presence of the border guard. Instead of that I only use the "is valid square" test ((square & 0x88) != 0).

For move generation purposes, you don't need to test for valid indices (beside assert of a debug version), since by design, the surrounded squares ensure a valid array index for all move direction increments starting from a valid on-the board index. While the ((square & 0x88) != 0) looks cheap, it is a somehow redundant, since you have to access the board if the 0x88 test passes a valid index in most cases anyway. So it seems smarter to sacrifice the 0x88 property and to add one additional off-the board case beside piece codes and empty square. See also the old posting 0x88 is not so smart by Christophe Théron. 16x16 is fine, 15x15 has the advantage that lsb of square index determines the square color

[hgm]

With 0x88 I don't fill the unused area with border guards since I would need two tests, one for "0 <= square <= 127" and one for the presence of the border guard.

This is why I put two extra ranks above and below the board. There is no need to test for 0 <= square <= 127, because squares < 0 and > 127 will hit a border guard on those extra ranks. The border has to be wide enough to catch the piece with the largest stride, which in Chess is a Knight. So two ranks suffice.

Usually my piece encoding uses a WHITE bit or a BLACK bit (e.g. 32 and 64) set on the pieces, and then set both bits on the border guards. When the move generator calculates a target square to = from + step, and examines the board through victim = board[to], it just has to test the bit for the stm (if(victim & stm)...) to know if it hit a friendly piece or strayed off board, which are exactly the cases where the move is invalid.

Although a width of 15 is in principle enough to make the square-number difference unambiguous, it is very costly in terms of memory efficiency, as the unused 7 board files are just to small to do anything useful with them. Only the actual board needs boundary guards, all other board-size tables (PST, Zobrist keys) will only be accessed for on-board squares. So with 16x8 you could store a white PST in the left half, and the corresponding black PST in the right half, for perfect memory filling, rather than using only 8/15 of the memory. If you really want to use the lowest bit for easy square shade, it would be better to use 17x8. So that you can use 16/17 of the memory.

Having a unused part as least as large as the used part is also very useful for move encoding; you can use the square numbers in the unused part (the 'shadow board') to code for a move to the corresponding square of the real board together with some special effect (like promotion).