Author: Dan Homan
Date: 05:36:20 07/20/99
Go up one level in this thread
On July 20, 1999 at 07:53:45, Frank Schneider wrote:
>Hi,
>
>I'm looking for all kind of information about 0x88 boardrepresentation.
>
>I know there have been descriptions here, has anybody collected them?
>Using DejaNews I found some messages in rgcc, but none of them described
>more than the basic idea (which I know). But where can I find the clever
>tricks?
>
>Is it possible to search for messages containing keywords like 0x88 in CCC?
>
>Who is also using 0x88 and what are your experiences?
>
>Frank
When I thought of re-writing EXchess, I went and collected all the 0x88
articles from here that I thought were useful. There may have been some
I missed, but here is what I found:
- Dan
------------------------------------------------------------------------
Subject: Re: 0x88
From: Robert Hyatt
E-mail: hyatt@crafty.cis.uab.edu
Message Number: 39085
Date: January 11, 1999 at 17:01:50
In Reply to: 0x88
Message ID: 39080
Posted by: Daniel Clausen
At: sargon@active.ch
On: January 11, 1999 at 16:21:40
On January 11, 1999 at 16:21:40, Daniel Clausen wrote:
>Hi,
>
>ok.. so Diepeveen is saying in ICC that bitboards are
>well.. not that useful.. and that he uses some algorithm
>called "0x88". Can anyone enlighten me what this is? I did
>a web-search on Altavista but couldn't find anything
>useful. Thanks.
>
>cu,
> -daniel
It's an algorithm that has been around basically forever. I first saw it in
another chess program written around 1970 or so, "coko" (I think).
It is based on a board with 8 rows of 16 squares each.
number the squares 0=a1, 1=b1, 7=h1, and the next 8 are 'unused." Then
16=a2, 17=b2, 23=h2 and the next 8 are unused.
If you look at a square number in binary you notice this:
xrrr yfff (the board is essentially treated like a 256-word array).
However, fff=file number, rrr=rank number, while x and y are always 0 for
squares that are on the board, and 1 for squares that are off the board.
when you increment down a file, after adding 16 to reach the next rank, if
you AND the resulting square with 0x88 (binary constant = 10001000) and get
a non-zero result, you have reached the end of the rank. Ditto for files.
And hence the name 0x88.
Another interesting property is that the difference between two squares "on
the board" is constant and there is no wrapping around. IE in a simple 64
word board, h1 is adjacent to a2. Here that doesn't happen. If you subtract
two squares like a1 and c3 you can tell they are on the same diagonal, by
looking at their difference. But if you move over and do the same for h1
and another square, you won't *ever* conclude that h1 is close to another
square. This solves a lot of odd happenings when you wrap from the 8th rank
back to the first or vice versa. 0x88 makes that easy to avoid...
there are other things you get, but that ought to give you the basic
gist of the algorithm...
Subject: Re: 0x88
From: Bruce Moreland
E-mail: brucemo@seanet.com
Message Number: 39133
Date: January 12, 1999 at 05:03:00
In Reply to: Re: 0x88
Message ID: 39102
Posted by: jonathan Baxter
At: jon@syseng.anu.edu.au
On: January 11, 1999 at 19:42:25
On January 11, 1999 at 19:42:25, jonathan Baxter wrote:
>On January 11, 1999 at 17:44:02, Bruce Moreland wrote:
>>You can write the whole thing in a few hours and have it go fast, without giving
>>yourself a stroke.
>
>Is there anywhere I could find source code for this? or a more detailed
>discussion?
You make your board a 128 element array, with 0..7 being a1..h1, 8..15 being
unused, 16..23 being a2..h2, etc.
A simple and fragmentary implementation would be as follows:
int argdBishop[] = { 17, 15, -17, -15, 0 };
void ProcTab(int * piTab, int iFrom, int coThem)
{
for (; *piTab; piTab++) {
int iTo;
for (iTo = iFrom + *piTab; !(iTo & 0x88); iTo += *piTab)
if (argsq[iTo].co == coThem) {
GenCap(iFrom, iTo); // Capture.
break;
}
if (argsq[iTo].co != coEmpty)
break;
GenMove(iFrom, iTo); // Move to vacant square.
}
}
To generate moves for a bishop on "iFrom" you would do:
ProcTab(argdBishop, iFrom, coThem);
Other pieces are analogous of course, although pawns are exceptional, and
en-passant and castling are insane and will be where most of your bugs are.
You would also make two arrays, each with 256 elements. I said something about
using 255 elements in a previous post, I was wrong, you really need a few less,
I believe, but I'll use 256 here in order to avoid looking anal.
The first is an array of bit masks. You'll index it by the delta between two
squares, plus a constant (128), which exists because the delta can be negative.
Each element in the array represents the kinds of pieces that can conceivably go
between two squares that are related to each other as described by the delta.
For instance, if you want to understand what can get from a1 to c3, you'd take
34 (c3) and subtract 0 (a1), and get 34. You'd add 128 to this in order to
avoid a negative array indexing situation if you are trying to go from c3 to a1
(-34), so you'd get 162 here. At element 162 would be the value "bfBishop |
bfQueen", since you put that value there at boot.
The other array is indexed the same way and contains the step you need to
increment by in order to get safely from one square to the other. For instance,
in the a1..c3 example, the step is 17, since you add 17 to a1 to get to b2, then
17 to b2 to get to c3.
If you don't use a 16 x 8 element board, the above will simply crash and burn.
You'll assume that a bishop can get from g1 to a3 by the path g1..h2..a3. A 16
x 8 board simply can't have this problem.
So to figure out if a piece can get from one square to another you do something
like this:
BOOL CanReach(int iFrom, int iTo, int pcFrom, int coFrom)
{
int dStep;
if (!(argbfMask[iTo - iFrom + 128] & argbf[coFrom][pcFrom]))
return FALSE; // Can't conceivably reach.
dStep = argdStep[iTo - iFrom + 128];
for (;;) {
iFrom += dStep;
if (iFrom == iTo)
return TRUE; // Made it.
if (argsq[iFrom].co != coEmpty)
return FALSE; // Blocked.
}
}
This can be used as most of the guts of an in-check routine, or as a part of the
guts of a static-exchange evaluator.
This isn't real code, it almost certainly has syntax errors and other bugs which
I don't care about.
bruce
Subject: Re: 0x88
From: Dan Newman
E-mail: dan.newman1@juno.com
Message Number: 39678
Date: January 16, 1999 at 19:00:58
In Reply to: 0x88
Message ID: 39616
Posted by: Frank Phillips
At: frank@frankp.force9.co.uk
On: January 16, 1999 at 06:40:05
Posted by Frank Phillips on January 16, 1999 at 06:40:05:
>I have vague thoughts of moving on from mailbox[] to 0x88 and would be
>grateful for a bit more detail on the second part of Bruce?s 0x88 message
>(Jan 12, message number 39133) about masks, particularly how to use them
>(bfBishop | bfQueen for instance)?
>
The idea is to make an array of bitmaps which can be indexed by the
difference in 0x88 coordinates of two squares. This index is in
the range of -119 to 119 since on-board 0x88 coords range from 0 to
119. This means the array must have at least 239 entries (I ususally
"round" this up to 240 with the idea that that might improve alignment
of data...). You can then index the array like this:
array[coord2-coord1+119]
What I usually do is set a pointer equal to array+119 and then
index that with the coordinate difference to save adding the
offset each time:
pointer[coord2-coord1]
The bits in each bitmap indicate which piece types are capable of
moving from coord1 to coord2, ignoring whether the intervening
and target squares are occupied or empty.
These sorts of tables are quite useful in testing for in-check and
in determining whether a side attacks a given square or not. For
the non-sliding pieces (knight and king and pawn when attacking)
this table tells you almost instantly whether the piece attacks a
given square. For the sliding pieces it tells you whether it is
possible for the piece to attack the square and tells you almost
instantly if it can't. I implemented my brute-force in-check
detector something like this:
int incheck( int side)
{
piece_t *p = plist[side^1];
int kcoord = coord( king[side]);
while( *p ) {
int diff = kcoord - coord( *p);
if( attacks[diff] & masks[ type( *p)] ) {
if( slider( *p) ) {
int step = steps[diff];
int i;
for( i = coord( *p) + step; i != kcoord; i += step ) {
if( board[i] != 0 ) break;
}
if( i == kcoord ) return 1;
} else return 1;
}
p++;
}
return 0;
}
I did this one off the top of my head--I hope it's correct. Notice
that I also have a steps[] array that is also indexed by the coordinate
difference and which returns the step offset in the proper direction of
motion for sliding the piece toward the target (king).
>Also, is there a simply way of initialising the board, the piece-square
>tables and masks with this approach, which from this perspective seem a
>bit more cumbersome than 64 element arrays? I guess this goes for
>looping through the square as well - to find pieces for example.
>
This trick does make those tables larger, and the initialization code
generally isn't very pretty.
One could do the board and piece square tables as 64 element arrays
and just convert coordinates to 0x88 (table lookup or calculation)
before subtracting them to index the coordinate difference tables.
I use piece lists instead of looping through the board. I've tried
looping though the board, but that gives a rather big hit on move
generator performance in my experience.
>Are there any reference works on this technique other than Frey, Chess
>Skill in Man and Machine, which I have failed to locate.
Hmm. I must have missed it in Frey. I think I saw brief mention of
0x88 in Levy & Newborn's _How Computers Play Chess_ but I'm not sure.
I first found out about it on RGCC a couple years back I think. The
most I've seen about it in print was in the Rajah article in ICCAJ
(Manohararajah, V. (1997). RAJAH: The Design of a Chess Program, ICCA
Journal, Vol. 20, No. 2, pp. 87-91.)
-Dan.
Subject: Re: 0x88
From: Dan Newman
E-mail: dan.newman1@juno.com
Message Number: 39796
Date: January 18, 1999 at 01:27:00
In Reply to: Re: 0x88
Message ID: 39728
Posted by: Frank Phillips
At: frank@frankp.force9.co.uk
On: January 17, 1999 at 07:45:46
On January 17, 1999 at 07:45:46, Frank Phillips wrote:
>In Reply to: Re: 0x88 posted by Dan Newman on January 16, 1999 at 19:00:58:
>
>On January 16, 1999 at 19:00:58, Dan Newman wrote:
>
>>Posted by Frank Phillips on January 16, 1999 at 06:40:05:
>>
>>>I have vague thoughts of moving on from mailbox[] to 0x88 and would be
>>>grateful for a bit more detail on the second part of Bruce?s 0x88 message
>>>(Jan 12, message number 39133) about masks, particularly how to use them
>>>(bfBishop | bfQueen for instance)?
>>>
>>
>>The idea is to make an array of bitmaps which can be indexed by the
>>difference in 0x88 coordinates of two squares. This index is in
>>the range of -119 to 119 since on-board 0x88 coords range from 0 to
>>119. This means the array must have at least 239 entries (I ususally
>>"round" this up to 240 with the idea that that might improve alignment
>>of data...). You can then index the array like this:
>>
>> array[coord2-coord1+119]
>>
>>What I usually do is set a pointer equal to array+119 and then
>[SNIP]
>
>Thanks Dan. My first and current attempt started as a rip of TSCP but as grown
>like topsy as I have added stuff and my understanding has increased - usually >in that order. I am looking for a reason to start again and stop me >constantly fiddling with what I have. So it is either plunging into bitboards >(doubtful) or 0x88 as the motivation for a complete redesign.
>
I really like 0x88, though I'm trying a (non-rotated) bitboard program now.
The main disadvantages of 0x88 that I've found are 1) the doubling in size
of many arrays and 2) the "holes" in the 0x88 coordinates that have to be
filled or removed to prevent tables like the history heuristic table
from becoming too large.
>I do wonder what sort of speedup 0x88 might bring.
In my experience 0x88 doesn't speed up move generation an awful lot, and
even if it doubled move generation speed that would probably only make
the program a few percent faster. It does make the move generator easy
to code though. I think where 0x88 really shines is with the coordinate
difference trick. This can make coding attack/in-check dection and SEE
much easier and can make the code a good deal faster. I suspect it is
quite useful in calculating certain eval terms too.
>The biggest I managed so for
>was after someone here (Werener I think) pointed out that his program spent >most of its time testing for check and I changed my approach from finding each >piece and seeing if it attacked to king, to working out from the king square >along diagonals, files and ranks, and testing whether knights and pawns where >located knight and pawn moves away. Obvious, and quicker since most paths to >king are usually blocked. Currently the program spends about 10% of its time >in the in_check function and about 10% generating captures.
In my first program I hadn't yet heard of pseudo-legal move generation, and I
tested each move in the move generator for legality using a brute force
in-check function. When I profiled the code incheck() was taking 80% of the
time. I knocked this down somewhat by using a piece inventory to skip
unnecessary tests (no sense looking out along diagonal sliding vectors when
the oponent no longer has any bishops or queens...). At some point I also
switched to the more efficient "working out from the king" trick. (I suspect
that 80% would only have been 40% if I'd had a decent amount of eval in the
program.)
>I pre-calculate moves at
>intialisation, so move generation involves an array lookup,
>nextsquare[piece][direction][sq], and an if() statement to check if it is -1 >and therefore off the board.
>
I used table lookup for to-squares in my first program but have used offset
calculations since then, under the theory that it should be faster to
add a constant than to retrieve a value from memory--but that's theory only
as I haven't actually compared them. I think I'll have to try it again
sometime; it looks like it would make for an nicely compact move generator.
I typically unroll loops and do other things to avoid tests and end up with
rather massive move generators--too much tweeking before I get a working
program...
Actually, when you consider how little of a chess program's time is spent
generating moves and how much is probably going to be spent doing evaluation,
it seems as if one probably should concentrate more on creating data structures
and algorithms to support fast evaluation rather than fast move generation.
I generally write my move generator first though, and that seems to get
most of my effort in optimizing things.
>Still aspiring to beat that pansy (as someone here called it) GNUchess though >:))
I'll have to try GNUChess (since it's *so* easy :). I've been playing my
programs mostly against Comet and have only occasionally managed to draw
it--this no doubt due to lack of any sophisticated eval and perhaps a bug
or two...
-Dan.
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.