Author: Tony Werten
Date: 02:44:44 06/19/00
Go up one level in this thread
On June 15, 2000 at 02:52:15, Bruce Moreland wrote: >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. It's more efficient to just look at the squares the last moved piece came from and moved to, no looping through pieces. If you want to look if you put yourself in check just look at the from square ( if you weren't incheck to start with ) Tony > >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.