Author: Bruce Moreland
Date: 14:44:02 01/11/99
Go up one level in this thread
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. What Vincent says is open to debate. bruce
This page took 0.02 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.