Author: Bruce Moreland
Date: 23:52:15 06/14/00
Go up one level in this thread
On June 15, 2000 at 02:37:42, James Robertson wrote: >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 It's not just move generation. If you have an in-check function you could replace it with a simple loop through your pieces, doing a subtraction, an array lookup, and an "and" operation. In most cases the "and" would fail. In the cases where it succeeded, you check to see if the attacking piece is a slider, and if not you return true. If it is, you do another array lookup and traverse a vector. That seems pretty efficient. bruce
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.