Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: 0x88

Author: Robert Hyatt

Date: 20:01:45 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.


I would agree.  We used it way back when because of the very issues this
addresses.  Machines weren't fast, and it made a lot of sense.  I used this
after I saw it in the Coko source in fact...  but somewhere around 1983-84
we canned this when Harry dreamed up a vectorized attack detector that didn't
work well with the board being this big.

>
>You can write the whole thing in a few hours and have it go fast, without giving
>yourself a stroke.
>
>What Vincent says is open to debate.

:)

The main point here is 0x88, bitboards, or whatever, you *must* make a
commitment to doing the best you can do, for a period of time sufficient to
make sure you extract all there is to extract from the approach.  Too many
try bitboards and give up after they find some difficulties they can't over-
come.  Others try 0x88 and give up without ever realizing all the places it
is useful...

classic mistake to try and give up too soon...



>
>bruce



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