Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: 0x88

Author: Robert Hyatt

Date: 14:01:50 01/11/99

Go up one level in this thread


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...




This page took 0.03 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.