0x88?

[Jan Eric Larsson]

Hi!

I read here the other day about the 0x88 technique in move
generation, (edge detection). How does it work?

Thanks beforehand!

Jan Eric Larsson Phone: +1 415 725 3859
Knowledge Systems Laboratory Fax: +1 415 725 5850
Department of Computer Science E-mail: Lar...@KSL.Stanford.Edu
Stanford University
701 Welch Road, Building C "We watched the thermocouples dance to the
Palo Alto, CA 94304, USA spirited tunes of a high frequency band."

[Robert Hyatt]

In article <4257te$4...@nntp.Stanford.EDU>,

Jan Eric Larsson <lar...@hpp.Stanford.EDU> wrote:
>
>Hi!
>
>I read here the other day about the 0x88 technique in move
>generation, (edge detection). How does it work?
>
>Thanks beforehand!
>

It's an "old" hack (we did this in Cray Blitz, I'm sure many others are
doing it too, if they don't use bitboards of course.) Simply, you make
the board a lot wider than normal (extra files off the edge) then detecting
the edge of the board can be done by looking at high order bits of to square,
rather than having to load a value from a square off the edge and discovering
that it's the "edge".

--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

[Bruce Moreland]

The idea is that you make your board 16 squares wide by 8 high, in
effect. If you have a piece on any square in the legal part of this
board (the left half), and you add some offset to its square in order to
simulate a chess move, you can check to see if you've moved off-board by
AND'ing the resulting board index with 0x88.

This doesn't work if you use an 8 x 8 board. If you had an 8 x 8 board,
you could AND with 0x40 to see if you went off the bottom or top of the
board, but there'd be nothing simple that you could do to figure out if
you went off the left or right edge. Using a 16-wide board effectively
gives you an extra "sign" bit in the middle of your word, which can be
used to detect off-left and off-right conditions.

To generate the "up and to the right" moves for a bishop you'd do
something like this:

iDst = iSrc + 17; // adding 17 takes you up and right one.
while (!(iDst & 0x88)) {
if (board[iDst].color == US)
break;
link(iSrc, iDst);
if (board[iDst].color == THEM)
break;
iDst += 17;
}

I've made no attempt to optimize the above.

There is at least one other advantage to this technique. If you take the
difference between any two board indexes, you will get a number that
uniquely defines the vector between the two squares represented. For
instance, if the difference is 5 (which would happen if the two squares
were a1 and f1), you could always be certain that the destination is five
squares to the right of the source. If the difference is 17, you can
always assume that the destination is up one and to the right one. You
can't make this basic assumption with an 8 x 8 board, an example of where
it breaks down is a1,b1, where the difference is 1 and the relationship
is one to the right, but h1,a2 also differs by one, and the relationship
is up one and seven to the left.

What you can do with a 16 x 8 board is make an array of 256 bit-fields,
each representing which piece can possibly move between two squares whose
relationship is defined by subtracting the source from the destination.
This lets you determine, for instance, if it possible for a knight to get
from a1 to b3. The difference in this case is 33, so element 161 in the
array (161 is 128+33, the reason you add 128 is to avoid negative
numbers) would have a bit set indicating "knight".

The code is somehthing like this:

#define bfWPAWN 0x01
#define bfBPAWN 0x02
#define bfKNIGHT 0x04
#define bfBISHOP 0x08
#define bfROOK 0x10
#define bfQUEEN 0x20
#define bfKING 0x40

BOOL FMightAttack(int src, int dst, int bf)
{
return atk_vec[dst - src + 128] & bf;
}

This would let you speed up stuff like in_check() or a static exchange
evaluator, you could very quickly determine that most pieces can't
possibly attack a given square.

bruce

In article <4257te$4...@nntp.Stanford.EDU>, lar...@hpp.Stanford.EDU
says...

>
>
>Hi!
>
>I read here the other day about the 0x88 technique in move
>generation, (edge detection). How does it work?
>
>Thanks beforehand!
>
>

>Jan Eric Larsson Phone: +1 415 725 3859
>Knowledge Systems Laboratory Fax: +1 415 725 5850
>Department of Computer Science E-mail: Lar...@KSL.Stanford.Edu
>Stanford University
>701 Welch Road, Building C "We watched the thermocouples dance to
the
>Palo Alto, CA 94304, USA spirited tunes of a high frequency
band."

--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.

[Michael Hermann]

hy...@willis.cis.uab.edu (Robert Hyatt) writes:

>It's an "old" hack (we did this in Cray Blitz, I'm sure many others are
>doing it too, if they don't use bitboards of course.) Simply, you make
>the board a lot wider than normal (extra files off the edge) then detecting
>the edge of the board can be done by looking at high order bits of to square,
>rather than having to load a value from a square off the edge and discovering
>that it's the "edge".

It's in fact a really old trick. Possibly works best if you use somewhat dedicated
hardware. In our design we had no access to the ALU itself, so we got the signal
from the adress register of the 1st level RAM that held the board.
So while the RAM decoded we used the otherwise mostly idle slot to abort a
direction based on the "out-of-board"-flag. Those were the days ...

Mike
--
Dipl.-Ing. Michael Hermann m...@regent.e-technik.tu-muenchen.de
Lehrstuhl fuer Rechnergestuetztes Entwerfen, Postfach 202420
Technische Universitaet Muenchen 089/21053651