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