Board representation : 0x88 or 10x12 ??

[Philippe]

Hello,
I am in the first phase of a chess program. I was thinking about the 10x12 board, since it is very easy to know if you are out of the board. A single logical AND is enough. Basically, I store the content of a square in a INT : one bit for each type of piece, 1 bit for unused square, 1 bit for outboard square.
Then I read about the 0x88 representation. It seems rather easy to implement. But It seems that it is slower than the 10x12 board, because one has to make an extra test , just to know if the square is onboard or not.
Is it an illusion ? or is there others benefits of the 0x88 board ?

Thanks for information,

Philippe

[Alessandro Scotti]

IMO the real advantage of 0x88 is you can take any two squares and get their relative position (i.e. if on same diagonal, etc.) by simple lookup into a <256 elements table. This comes very useful in attack generation.
I'm currently using a 14x16 board, gives me the same feature without the 0x88 index "trick" that I don't like much.

[Reinhard Scharnagl]

I use a 15x12 board and am very satisfied with the performance it provides.

Reinhard.

http://www.chessbox.de/Compu/schachsmirf_e.html (Beta download)

[Alessandro Scotti]

I use a 15x12 board and am very satisfied with the performance it provides.

Actually I use a 16x12 board, I don't know why it often comes as 16x14 in my mind! I choose 16 over 15 because on paper it seems to offer faster indexing for just a very small space overhead. Never actually measured the performance of 15x12 though.

[Reinhard Scharnagl]

Never actually measured the performance of 15x12 though.

The 15 is very important. It has to do with special properties of the resulting nature of square coordinates. Without using such things, it would not matter if 10x12 or 16x12. But 15x12 enables SMIRF to see through lines, rows and diagonals.

Reinhard.

P.S.: Another implication of an odd structure size is to recognize dark squares simply by an odd coordinate.

[Alessandro Scotti]

The 15 is very important. It has to do with special properties of the resulting nature of square coordinates. Without using such things, it would not matter if 10x12 or 16x12. But 15x12 enables SMIRF to see through lines, rows and diagonals.

I only use the "delta" trick and that requires the board width to be >= 15, that's why I could not choose 10x12.

P.S. The square color idea is a nice one!

[Reinhard Scharnagl]

I only use the "delta" trick and that requires the board width to be >= 15, that's why I could not choose 10x12.

Probably I am not familiar with most of such tricks, because I do not use other chess program sources.

P.S. The square color idea is a nice one!

But still there hasn't been a need to use it in SMIRF's central routines, though I have some ideas for it.

Reinhard.

[Philippe]

Hi,

Thanks ! But Im afraid Im not very experienced in chess programming. I see indeed that the difference between 2 squares is a constant (in the 0x88 representation). But could you explain a little more this attack table ?

headache is coming quick !

Philippe

[Alessandro Scotti]

I only use the "delta" trick and that requires the board width to be >= 15, that's why I could not choose 10x12.

Probably I am not familiar with most of such tricks, because I do not use other chess program sources.

I don't think it would be easy to get the idea by only looking at source code. Fortunately, this method is very old and is mentioned almost everywhere. For example:

http://www.seanet.com/~brucemo/topics/0x88.htm

Yet, I've had to spend some time with pencil and paper to fully understand it and figure out the general rule.

[Alessandro Scotti]

Thanks ! But Im afraid Im not very experienced in chess programming. I see indeed that the difference between 2 squares is a constant (in the 0x88 representation). But could you explain a little more this attack table ?

Hi Philippe,
the method is explained in the link I posted above (see the "A bonus" paragraph). As I said, pencil and paper "simulations" with smaller boards (3x3 or 4x4) have been extremely helpful to me.

[Edit] In addition, I would say the same also for the other parts of my engine!

[H.G.Muller]

The difference between two squares for a certain type move is the same on any board. But to directly see from a small table if a move is possible from square x to square y the difference must also be unique. If you take a board with a guard band, moves that are different might yet have the same y-x, because they are the same if you interpret them as jumping over the guard band. E.g., if the width of your guard band is 2 (like in a 12x10 board), the Rook move a1-d1 has a difference +3. But if you jump from h1-a2, that is also a difference of +3, while the legal version of the move is a completely different one, that no FIDE piece can take. So a difference of +3 then does not automatically mean you have a Rook move.

To prevent this, you need a guard band of at least 7 wide. On the regular board there don't exist any moves that go far enough to jump over the guard band. Thus a 12x15 board suffices to make the square difference unique (15 = 8 + 7). A 0x88 board is 8x16, so the trick works there as well.

The idea then is that you can make a table where for each difference y-x you can immediately see which piece can make such a move (e.g. by setting one bit for each piece type). You can then very quickly check things like "does the piece the opponent just moved check my King?", by looking in the table for the difference of his to-square, and your King's position. If it says there that a Knight can do it, and the moved piece was a Knight, bingo!

If it says a Rook can do it, and the moved piece was a Rook (or Queen), you still have to check if there was nothing in between. To this end you make a similar table of the primitive step that would bring you from x to y, so that you can start tracing the ray starting at x, to see if the first non-empty square you encounter is indeed y.

[H.G.Muller]

Taking into account everything mentioned in this thread I build my new engine based on a 12 x 15 board. Due to the guard band it saves me from having to do a separate test for leaving the board, just test for occupancy of the target square by a friendly piece, and make sure the Guards test as belonging to both sides. It takes minimal space. (177 bytes, because the last row does not have to be complete to provide the 2-wide guard band. In fact you could make it 175 if you are not afraid for diagonal jumps of 2 from the corners.) The attack tables do not waste any space (15x15 = 225 entries each).

The first legal square, a1, is the 31st element of the board array, but I offset the indexing so that it is addressed as board[0x18]. (The first element of the board is thus board[-7].) That way I keep the advantage that the most-significant nybble of the index gives me the Rank number:
the first rank is 0x18-0x1F, the 8th rank 0x81-0x88. Having an easy test for the rank number comes in handy when generating Pawn moves (double move or promotion test).

I also use it to simplify e.p.-capture generation, I just pass along the to-square of any double move to the next ply, and the move generator there checks for Pawns (of the appropriate side) on the two squares next to it to generate the e.p.'s. If there was no double move I can pass zero, which is in the guard band of the board, and Guards don't test as Pawns, so I don't need a separate test to first determine if there was a double move.

The low-bit = square color I had not realized. Great trick! And yet another argument in favor of this representation.

[Reinhard Scharnagl]

My board has a skipped geometrie, thus also enabling to cover 8x8 and 10x8 boards. So black pawn move distance is -(white pawn move distance).

Code: Select all

     Dump of FeldInfo-Lo-2 (Koor=>Text):

x00: #0   #1   ??   ??   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##   ??
x0F: ??   ??   ??   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##
x1E: ??   ??   ??   ##   ##   a1   a2   a3   a4   a5   a6   a7   a8   ##   ##
x2D: ??   ??   ??   ##   ##   b1   b2   b3   b4   b5   b6   b7   b8   ##   ##
x3C: ??   ??   ??   ##   ##   c1   c2   c3   c4   c5   c6   c7   c8   ##   ##
x4B: ??   ??   ??   ##   ##   d1   d2   d3   d4   d5   d6   d7   d8   ##   ##
x5A: ??   ??   ??   ##   ##   e1   e2   e3   e4   e5   e6   e7   e8   ##   ##
x69: ??   ??   ??   ##   ##   f1   f2   f3   f4   f5   f6   f7   f8   ##   ##
x78: ??   ??   ??   ##   ##   g1   g2   g3   g4   g5   g6   g7   g8   ##   ##
x87: ??   ??   ??   ##   ##   h1   h2   h3   h4   h5   h6   h7   h8   ##   ##
x96: ??   ??   ??   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##
xA5: ??   ??   ??   ??   ##   ##   ##   ##   ##   ##   ##   ##   ##   ##   ??
xB4: ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??
xC3: ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??   ??

Reinhard.

[H.G.Muller]

OK, your board is rotated 90 degrees w.r.t. mine, and I can see why you do it that way: it allows you to expand the board to any number of files, without losing the possibility to use the difference between two squares as a unique identification of the move type. You will lose the easy test for the rank number, though, which is why I (lacking teh interest in larger boards) prefer the other representation. I do postulate Guards on the corners of the 12x12 used part as well, because for efficiency I sometimes trace slider rays in steps of 2, without taking the latency of waiting for the result of the first access to the board before testing the second.

In the skipped part between the guard bands I put frequently used global variables and temporaries.

[Reinhard Scharnagl]

OK, your board is rotated 90 degrees w.r.t. mine, and I can see why you do it that way

P.S..: Because that representation covers a lot of different board geometries, it proves to be the more genuine approach.

You will lose the easy test for the rank number

There is no need for that. As far as I have experienced, in performance relevant situations the rank number is not used alone, but additionally selected from a number range. Such questions could be handled much faster by simply fetching contents of a prepared seperated table, e.g. IsPromotionArea(coor).

Moreover the skipping leads to comparable procedures for white and black, only by negating move steps.

In the skipped part between the guard bands I put frequently used global variables and temporaries.

In ancient days, where memory had been expensive, I did it, too. Actually there are some castling relevant data fields to support e.g. Chess960. Also notice the two root fields for my two color specific double linked sorted piece lists consisting of the existing board pieces.

Reinhard.

[Alessandro Scotti]

The low-bit = square color I had not realized. Great trick! And yet another argument in favor of this representation.

As Reinhard said, it's not used very often though. In Kiwi (which has a standard 8x8 board for this stuff), I have this code:

Code: Select all

inline int color_of( int sq ) {
    return (sq + (sq >> 3)) & 1;
}


so it's not much more expensive. I use it only in the KBBK and KBNK recognizers so far.

[Reinhard Scharnagl]

... so it's not much more expensive.

well, I really doubt on that. ;-)

Reinhard.

[Alessandro Scotti]

... so it's not much more expensive.

well, I really doubt on that.

Reinhard.

How do you expect it to be? I think it will be 20-25% slower, with respect to a "return sq & 1;" implementation, with most time spent in accessing the "sq" variable. That's just a rough estimation of course.

[Reinhard Scharnagl]

How do you expect it to be?

Don't feel offended, that is not, what I intended. Be happy with your version! I already have uncovered too much of my not open source SMIRF project. I will no longer disturb your discussion on board representations within this thread.

Regards, Reinhard.

[Alessandro Scotti]

How do you expect it to be?

Don't feel offended, that is not, what I intended. Be happy with your version! I already have uncovered too much of my not open source SMIRF project. I will no longer disturb your discussion on board representations within this thread.

Regards, Reinhard.

Hi Reinhard,
absolutely no offense taken, just enjoying the discussion! As for uncovering SMIRF I am sure you have still many secrets to tell!