Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: 0x88

Author: jonathan Baxter

Date: 16:42:25 01/11/99

Go up one level in this thread


On January 11, 1999 at 17:44:02, Bruce Moreland wrote:

>
>On January 11, 1999 at 17:01:50, Robert Hyatt wrote:
>
>>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...
>
>Bottom line is memory-, speed-, and code-size- efficient move generation, plus
>the ability to determine the relation between two squares (on the same diagonal,
>rank, or file, king's move away or knight's move away) with an array lookup,
>which can be used to speed up in-check or static exchange evaluation functions.
>
>If I were writing a program today I think I would try this first.
>
>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?


>
>What Vincent says is open to debate.
>

What's new :)

Jon
>bruce



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.