Author: Heiner Marxen
Date: 14:51:21 01/22/02
Go up one level in this thread
On January 22, 2002 at 17:02:00, Russell Reagan wrote:
>When I first began my chess programming, I chose to go with a 64-byte array. It
>seemed logical and simple. After learning about other methods of representing
>the board, I began to think that other board representations were superior
>because they allowed for shortcuts here and there. To preface my question, here
>is a short trip through what I have thought about.
>
>Padding a 64-byte array with a 1 square border would allow for simple edge
>detection for sliding pieces, but not for the knight.
>
>Padding a 64-byte (either 120-byte 10x12 or 144-byte 12x12 arrays) array with a
>1 or 2 square border for the left and right hand sides with a 2 square border
>for the top and bottom allow for simple edge detection including the knight.
>
>Improving upon that you can use a 256-byte array (16x16) to avoid a multiply and
>use a shift instead, with the simple edge detection that the 120-byte and
>144-byte arrays have.
>
>Now a brief tangent about 0x88. This doesn't seem to work for all squares.
>Perhaps someone can explain this to me. If you go to square 112 (A8 I belive),
>and you want to generate the rook's legal moves, so you test 112+16 to see if
>the rook can move up one square on the board, but 112+16=128, which is out of
>bounds of the 8x16 array, so detecting the edge for the top row doesn't work. I
It does work: index 128 == 0x80 and therefore (index & 0x88) is non-zero.
Thus, this index is not ok.
>suppose you could simply add rows to the top and bottom and have a 11x16 array
>to handle this case, but I've always heard people using 8x16. So I either don't
>understand something or something doesn't work right. I'm betting on me not
>understanding something :)
>
>Then we have bitboards.
>
>Now, originally I was under the assumption that the reason for using a 16x16
>array or 0x88 was that edge detection on a 64-byte array was less efficient than
>testing the bordering squares, as is done in the 16x16 implementation.
The main advantage of 0x88 is that there is an efficient test on the _index_
as opposed to fetch a square and then detect some special border code. IMO.
This easy to see if we look at the board index in binary:
column x and row y has index 0yyy0xxx
Those two zero bits are the trick, since they can be used to detect
arithmetic overflow and underflow within the 3-bit xxx and yyy.
>Now my question...
>
>Let's take the example of generating legal rook moves. You're rook is on g6, and
>you start testing if the rook can move to h6. Everything checks out, so you
>increment the value for the square h6 and you get a7. You can test to see if
>this next square is ok for the rook to move to by doing something like
>
>if(row(i) != row(i+1)) break;
>
>or use a while loop or whatever, with the row comparison being the test. Since
>you can compute the row with a macro that does a binary shift, computing the row
>is a 1-cycle instruction, so in all you use maybe 3-cycles for the test (2
>shifts and an addition?). I'm not very good with ASM so correct me if I'm wrong,
>and this may be where I'm confusing myself.
>
>In the 16x16 array method, you'd have to do something like
>
>if(squares[i+offset] == 0) break;
>
>so you'd use 2-cycles for this (addition for i+offset, and another for the
>offset of squares), saving 1-cycle, which would add up after looking at millions
>of positions.
>
>0x88 would seem to simplify the problem even furth to a 1-cycle AND operation on
>the index of the square.
Sounds like you know already how 0x88 works :-)
>These speedups seem great, but will there be any speed loss for having to
>compute an offset (since there are extra squares in 16x16 or 0x88 methods)? In a
>64-byte array, there is no need to compute an offset, just keep on incrementing
>in a for loop. So you save a few cycles with 16x16 or 0x88 but do you lose a few
>back from computing the offset?
I do not follow. What offset is to be computed? Look at this:
int rook_steps[4] ={ 1, -1, 16, -16 };
gen_rook_moves(int from)
{
int dir, to, step;
for( dir=0 ; dir<4 ; ++dir ) {
step = rook_steps[dir];
to = from;
while( 0 == (0x88 & (to += step)) ) {
...check board[to] to be empty or enemy...
}
}
}
>Then there are bitboards, and they seem to save tons of time in some aspects, so
>it seems easy to be sold on them. For example to compute whether the king is in
>check, just do a 1-cycle AND operation on two bitboards (more in reality since
>most users are on 32-bit machines) and you've got your answer. No tracing along
>rays searching for attacking pieces.
Sounds interesting. Could you elaborate, what bitboards are to be used, here?
> Same thing for computing legal moves. You
>can do a lookup and an AND operation and get a bitboard with legal destination
>squares, but then you have to give some speed back and go looking through the
>resulting bitboard, so you might as well have searched through a 64-byte array
>in the first place right?
>
>Basically in thinking about all of these methods there seem to be speedups in
>one area, only to realize that you have to take a speed hit in another.
Sure.
There is no single overall best board representation.
> I'm
>trying to sort out all of the pros and cons and figure out what I'm missing in
>regards to the supposed "advantages" of using a 16x16 board, 0x88, or bitboards
>over a simple 64-byte array. It seems like the extra cycle you'd take to compute
>an offset for 16x16 or 0x88 would outweigh the edge detection cycles that are
>saved, since there will be more times you are computing offsets than doing edge
>detection. And with bitboards, if you have to search not 1, but several
>bitboards taking a hit of 64 cycles each, then the gains there seem to diminish
>rapidly.
>
>So what am I missing? Why am I not seeing how these other methods are better
>than a simple 64-byte array?
The gains of 0x88 are not exactly overwhelming. A simple 64-byte array
is not _that_ bad, after all. And bitboards are not going to give you
much speedup in the move generator, but can help a lot in evaluation.
Bob has commented on this several times, here.
>Thanks for all of your comments and help on this matter.
You are welcome!
>Russell
Cheers,
Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.