Author: James Robertson
Date: 23:37:42 06/14/00
Go up one level in this thread
On June 14, 2000 at 21:26:30, Bruce Moreland wrote: >On June 14, 2000 at 16:21:40, James Robertson wrote: > >>Could someone please point me to a place where I can read about this board >>representation and how to use it? If someone is willing to post a description of >>it here, that would be cool too. >> >>James > >Here is yet another try: > >0x88 board representation and move generation > >It's called something else, but I don't know what it is called. I heard about >it from David Kittinger at the Hong Kong WCCC in 1995, and it's been spreading. >David told me that it was a common technique before that point, but I haven't >seen it described in literature. > >The advantages of the technique are that you get simple move generation and you >get easy attack detection. This latter advantage is especially important, and >is probably the major reason for using the technique. > >The data structure is a 16 x 8 board, rather than an 8 x 8 board. 0..7 are >a1..h1, then you get 8 empty squares numbered 8..15, then 16..23 are a2..h2, >etc. > >The idea is that if you have an index into the board, you can add an offset to >the index to travel along a vector. You can do a simple test to see if you've >gone off the board. The test is "index & 0x88". If that comes back non-zero, >you are off the board. For instance, if you are at h1 (7) and add 1 to go right >one square, you get 8, which has one of our 0x88 bits set. If you are at a2 >(16) and go left (-1), you get 15, which has the same bit set. If you go off >the top or bottom of the board, you also get one of those two bits set in every >case. > >You can't use an 8 x 8 board to do this, because right one from h1 gets you to >a2, which is on the board. It only works if you go off the bottom or top of the >board, but it doesn't work with left or right. > >Your critical test in your move generation loop is something like: > > if ((location += offset) & 0x88) > >This is easier than having to try to manage rank and file variables and trying >to figure out if you've gone off the board in one direction or the other, and >it's also more elegant than several other obvious techniques. > >The other advantage of 0x88 is attack detection. If you want to know if e4 (52) >is one square above and to the right of d3 (35) you subtract the indexes to get >17. It is a feature of this kind of board representation that if you get 17 >when you subtract two indexes, you are always one square up and to the right. > >This is not true on an 8 x 8 board. e4 (28) - d3 (19) = 9, but 9 doesn't always >mean one square up and to the right. For example, if you relate a3 (16) and h1 >(7), you get 9, but a3 is certainly not one square above and to the right of h1. > >You can use the fact that in a 16 x 8 board, 17 means one squre up and to the >right, to do quick attack detection. > >You can make an array (256 elements works nicely but you need a few fewer) of >bit-fields. You can have a white pawn be 0x1, a black pawn be 0x2, and knight >be 0x4, a bishop be 0x8, etc., and fill in the array (-127..127) with the >appropriate masks that indicate a possible attack by a piece of one type, on a >given square, of another square. > >For instance, in the element for +34, which is two squares up and two to the >right, you could have the value "queen|bishop". If you have a queen on f3 (37) >and want to know if it attacks a king on d1 (3), you can subtract 3 from 37, to >get 34, and in the element for +34 you find "queen|bishop", which anded with >"queen" is non-zero, so you know that an an attack is possible. > >You can have another array that contains a -17 in position +34, which tells you >how much to add each time to the queen's square (f3) in order to try to get to >the king's square (d1), so for sliding pieces you can very easily determine that >there is a possible vector, and what it is, and start checking the vector for >intervening pieces. > >You can use this to easily write a quick in-check routine, or a static-exchange >evaluator (SEE). > >I haven't included source code with this example, but the code is easy to write, >and in the past I've included it. There are lots of ways to write it, most of >them are very easy and fast. > >bruce Thanks for this. I'll whip up a move generator and compare it with Insomniac's bitboard representation... I am curious to see how the results will turn out. James
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.