Author: Louis Verhaard
Date: 00:55:37 01/12/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... My chess program "Houdini" (which would be a respectable member of the "U2000 club") uses another way to represent the board: it is an array of 65 ints, 0 meaning "the illegal square", and the other ones the real squares. Arrays North, South, NorthWest, etc get you to the next rank, file, etc. (North[A8] would give the illegal square). KnightMoves gives the list of squares that can be reached by a knight from a certain square. Other arrays give the file, rank, diagonal, etc. of a certain square. Two-dimensional arrays can be used for representing other static properties about the relations between two squares, for exampe there is a KingDistance array that gives the "king distance" between two squares, and there is another array "Direction" that tells how two squares are related to each other (for example Direction[A1][G7] gives "NorthEast". An advantage of this representation is that the number of squares is quite small, which makes the arrays quite small, so in principle you can easily make more complex arrays, like "can piece P on square A attack square B" (on an empty board), although I don't use such arrays. I never tried any other approach, so I don't know about performance advantages/disadvantages. I like it because it is easy to understand, which is good for an amateur, but may be not for all of you guys that want to beat deep blue within 3 years. Any comments? Louis
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.