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