Help with x88
John Stoneham
Pardon me for showing my ignorance, but I have seen "x88" a few times in
discussions of what I recall as move generation. What the heck *is*
that? Some sort of bit mask? If so, how is it used?
jms:>
Tom Kerrigan
Somebody *must* put together a r.g.c.c FAQ. It would be worth its weight (bits?)
in gold if it just had the answer to this question.
Cheers,
Tom
_______________________________________________________________________________
Tom Kerrigan kerr...@frii.com O-
We wish you a Hare Krishna
We wish you a Hare Krishna
We wish you a Hare Krishna
And a Sun Myung Moon!
-- Maxwell Smart
Joe Stella
John Stoneham <j...@electrotex.com> wrote:
>[...] have seen "x88" a few times in
>discussions of what I recall as move generation. What the heck *is*
>that? Some sort of bit mask? If so, how is it used?
I think we might have to put this question in a FAQ or something,
it crops up so often. I'll answer *this* time, and maybe spare others
the trouble...
Instead of an 8x8 board, use an 8x16 board (8 rows, 16 columns).
The valid squares for the chessboard are in the leftmost 8 columns.
The lower left square is 0x00 (hex 0) and the numbering proceeds to
the right.
Under this scheme, all valid chessboard squares have both hex digits
between 0 and 7. A square with an index like 0x80 is off the board,
i.e. an invalid square.
One of the nice things about it is that you can add an offset to any
square to get to the next square (you would add 0x11 for a bishop for
example) and then "AND" the result with 0x88 to see if you are still
on the board. A "TRUE" result from the AND operation indicates that
you have left the board. This helps to speed up move generation.
There are other good things about it, like you can subtract two square
indices from each other and if the answer is 0x01, then the two squares
are adjacent. This is not guaranteed to be the case if you use an
8x8 board.
Joe Stella
Martin Borriss
In article <4r6sji$6...@europa.frii.com>, kerr...@frii.com (Tom Kerrigan) writes:
> Somebody *must* put together a r.g.c.c FAQ. It would be worth its weight (bits?)
> in gold if it just had the answer to this question.
>
I was about to say the same...
Urban Koistinen
Tom Kerrigan (kerr...@frii.com) wrote:
: Somebody *must* put together a r.g.c.c FAQ.
: It would be worth its weight (bits?)
: in gold if it just had the answer to this question.
I can write it.
What should be in it and in what order?
Here are some questions I think it should answer:
* About this FAQ
- How to get errors and omissions corrected
* What chess programs are there?
- List of chess playing, database and interface programs
* How and where are games and positions stored?
- PGN, FEN, CB, CA, NB, TB, BU
* How can I write my own chess program?
- minimax search
- tricks like X88
Short handholding answers like:
* Where can I find a chess program in my programming language?
Search the chess program list for the name of your programming
language.
Bruce Moreland
In article <31D6C4...@electrotex.com>, j...@electrotex.com says...
>
>Pardon me for showing my ignorance, but I have seen "x88" a few times in
>that? Some sort of bit mask? If so, how is it used?
>
I've answered this already a couple of times, but maybe I can do better this
time since I've had practice.
"x88" is a time-honored method of board representation and move generation. The
idea is that you use a board that is 16 squares wide by 8 squares high. Since
this is twice as wide as a normal chessboard, you only really "use" the left
half of it, the right half just sits there and does nothing.
The reason you have those extra 8 files is because by wasting these files you
can index the board in a manner that has advantages. The squares are numbered
0..127, with 0 being a1, 1 being b1, 16 being a2, etc.
There are two reasons that indexing a board like this is a good idea: you can
detect off-board conditions easily, and you can figure out if a given piece on
square X can attack square Y easily.
If you are generating moves for a bishop, and want to generate moves that are
"up and to the right" of where the bishop is now, you can add 17 to the current
location of the bishop, and keep doing this until you either hit something or
run off the board. You know that you've run off the board because the
expression "index & 0x88" comes back non-zero. Here is why. If you go off the
top of the board, in all practical cases you will end up with an index that is
greater than 128, which means that the 0x80 bit in the index will be set. If
you go off the right edge of the board, you will end up with a number that has
the 0x08 bit set.
Due to the magic of twos-complement math, if you go off the left or bottom edges
of the board, you will also get a number that has either the 0x80 or 0x08 bits
set, or both.
Here is what this ends up looking like when you code it:
for (;;) {
index += offset;
if (index & 0x88)
break;
else if (color(board[index]) == empty)
link_non_capture();
else if (color(board[index]) == mycolor)
break;
else // color(board[index]) == theircolor
link_capture();
}
The use of the function "color", and the use of a "board" data structure is
purely for example, you can do this however you want. The important part of the
loop above is that you have a very simple check to see if you went off the
board. You don't have to do something noxious like keep a "rank" and a "file"
value seperately, add a seperate value to each of them, and check to see if
either of them is out of range, you can do it all in one shot.
This is not to say that this is the fastest or best move generation technique,
it is just known that this is a good technique, lots of people have used it for
years. I don't use it.
The other advantage to this system is that with one memory access you can figure
out if a piece of a certain type can possibly get from square X to square Y.
This doesn't take into account interpositions, but that's no big deal, just
knowing that it is possible is very useful for doing an in-check function or a
static-exchange evaluator, or whatever else you might need this for.
The property you will take advantage of to do this is the fact that if you
subtract the offsets of two squares, you will get a "delta" between the two
squares that uniquely identifies the geometric relationship between the two
squares. This does NOT work with an 8x8 board, but it DOES work with a 16x8
board. Here is the deal:
If you want to figure out if a rook can go from d4 to e4, you can subtract the
offset for d4 from the offset for e4, and you will get a value of 1. d4 is one
square to the left of e4. For ANY square on the board that is one square to the
left of ANY OTHER square on the board, you will ALWAYS get a delta of one when
you subtract the two offsets. The same goes for any other useful relationship
that you can think up (prove this yourself, if you wish). Two squares up and
one square to the right is ALWAYS 33.
In an 8x8 board this falls apart because you can wrap from the right edge of the
board to the left edge. The offset for a2 on an 8x8 board is 8, and the offset
for h1 is 7. If you take 7 from 8 you get 1, which is the same thing you get if
you take 4 (e1) from 5 (f1). In both of these cases the delta (1) is the same,
but the geometric relatioship (one square to the left) is not the same.
You can use the property of a 16x8 board to make an array of something less than
256 elements (when I implemented this scheme I used 256, who cares, so I will
pretend that you are using 256 as well). Each element represents a possible
delta. Since some of the deltas are negative, you have to offset the deltas by
a value that is large enough to erase the "negativeness". 128 works just fine
in this example.
So you have an array that you can index by delta. In each element of the array
is a bitmask, which represents which pieces can legally move between two squares
that are related by this particular delta. For instance, in the array element
for delta=1 (which is element 129 in this example, since I added 128 to 1), I
will have something akin to "bfRook | bfQueen | bfKing".
You can also make another array, indexed the same way, which tells you how to
iterate from square X to square Y if they do relate in some manner. For
instance, in the element for the delta between a1 and h8, you'd have a 17, since
you add 17 each iteration to travel across the board from a1 to h8.
The guts of an in-check function would work something like this:
for (i = 0; i < cPieces; i++) {
int offset;
int delta;
int index;
delta = rgpiece[i].index - indexTarget + 128;
if (!(argbfDelta[delta] & rgpiece[i].bf)) // <-- Important!
continue;
//
// You never get here unless you at least have a CHANCE
// of giving check, the only cases where you don't give
// check involve interposing pieces along the vector.
//
if (!rgpiece[i].fSliding) // Catch N or K, and maybe P.
return TRUE; // No interposers possible.
index = rgpiece[i].index; // Verify vector for B, R, Q.
offset = argoffset[delta];
for (;;) {
index += offset;
if (index == indexTarget) // Gotcha.
return TRUE;
if (color(board[index]) != empty) // Blocked.
break;
}
}
Obviously there are numerous ways to optimize this, but that is your job (also,
I didn't even compile it, so it might have some bugs, finding them is also your
job, but obviously you can handle that or you would still be writing
tic-tac-toe). The most important line in the above function is the line with
the "&" in it, that test will almost always fail, causing the "continue"
statement to be executed. As a consequence you almost never get to that noxious
little loop at the bottom of the function.
You can use essentially the same code in a static exchange evaluator.
Anywhere, there it all is if you want to use it.
bruce
--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.
Joseph McCaughan contra
Hi All,
I wrote a little awk/bin/sh script to generate an
X88 board so we can get a better visual idea.
NOTE: I started counting at 1 instead of 0 since
it's more humanly intuitive :)
So remember - the high order (or is it low order)
bit check in this example is "9" - not 8.
Here it is:
>off the board over here>>>
VVVVVVVVVVVVVVVVVVVVVV
------------------------------
8 | 71 72 73 74 75 76 77 78 | 79 7a 7b 7c 7d 7e 7f 80
| |
7 | 61 62 63 64 65 66 67 68 | 69 6a 6b 6c 6d 6e 6f 70
| |
6 | 51 52 53 54 55 56 57 58 | 59 5a 5b 5c 5d 5e 5f 60
| |
5 | 41 42 43 44 45 46 47 48 | 49 4a 4b 4c 4d 4e 4f 50
| |
4 | 31 32 33 34 35 36 37 38 | 39 3a 3b 3c 3d 3e 3f 40
| |
3 | 21 22 23 24 25 26 27 28 | 29 2a 2b 2c 2d 2e 2f 30
| |
2 | 11 12 13 14 15 16 17 18 | 19 1a 1b 1c 1d 1e 1f 20
| |
1 | 1 2 3 4 5 6 7 8 | 9 a b c d e f 10
---------------------------
A B C D E F G H
--Joe
--
Joe McCaughan / Do yer givin,
jmc...@hposl61.cup.hp.com \ While yer livin,
Phone: (408) 447-7892 / So yer knowin,
\ Where it's goin. Unknown
Bruce Moreland
In article <4s0vt8$c...@hpax.cup.hp.com>, jmc...@cup.hp.com says...
>[snip]
>NOTE: I started counting at 1 instead of 0 since
>it's more humanly intuitive :)
False. Learn C.
bruce
Joseph McCaughan contra
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: Joseph McCaughan contra (jmc...@cup.hp.com) wrote:
: :
: : Hi All,
: :
: : I wrote a little awk/bin/sh script to generate an
: : X88 board so we can get a better visual idea.
: : NOTE: I started counting at 1 instead of 0 since
: : it's more humanly intuitive :)
<snipped out intuitive stuff>
: :
: :
: : --Joe
: :
: Might be more "intuitive" but you just gave *me* excedrin headache
: #144... :)
: Seriously, subtract 1 from everything and us hex-types can then cope
: with this...
: Bob
OK, thanks for the *merciful* correction folks -
after all I am a newbie at this. I thought I had the
x88 concept down but I guess I need to give it a little more
thought.
Would someone post an accurate x88 board?
thanks, and again, my apologies...
--Joe
--
Joe McCaughan / The heights by great men reached and kept,
jmc...@hpuxps.cup.hp.com \ Were not attained by sudden flight,
Phone: (408) 447-7892 / But they, while their companions slept,
\ Were toiling upward in the night.
/ Henry Wadsworth Longfellow
Joe Stella
jmc...@cup.hp.com (Joseph McCaughan contra) wrote:
>I wrote a little awk/bin/sh script to generate an
>X88 board so we can get a better visual idea.
>NOTE: I started counting at 1 instead of 0 since
>it's more humanly intuitive :)
But that's going to mess it up. For example, start at
square 68. Add a bishop offset of 11, and you get 79.
OK, it's off the board because there is a 9.
Now start at square 41. *Subtract* a bishop offset, and
get 30. This is off the board, but there is no 8 *and* no
9. There's a 0. So it seems to me that you have increased
the amount of testing you have to do.
Starting the count at 0 is important because it takes 3
binary bits to count from 0 to 7, and these are the valid
squares. If the fourth bit (the "8" bit) is set, this
denotes an illegal square.
Joe Stella
>So remember - the high order (or is it low order)
>bit check in this example is "9" - not 8.
>Here it is:
> >off the board over here>>>
> VVVVVVVVVVVVVVVVVVVVVV
>------------------------------
>8 | 71 72 73 74 75 76 77 78 | 79 7a 7b 7c 7d 7e 7f 80
> | |
>7 | 61 62 63 64 65 66 67 68 | 69 6a 6b 6c 6d 6e 6f 70
> | |
>6 | 51 52 53 54 55 56 57 58 | 59 5a 5b 5c 5d 5e 5f 60
> | |
>5 | 41 42 43 44 45 46 47 48 | 49 4a 4b 4c 4d 4e 4f 50
> | |
>4 | 31 32 33 34 35 36 37 38 | 39 3a 3b 3c 3d 3e 3f 40
> | |
>3 | 21 22 23 24 25 26 27 28 | 29 2a 2b 2c 2d 2e 2f 30
> | |
>2 | 11 12 13 14 15 16 17 18 | 19 1a 1b 1c 1d 1e 1f 20
> | |
>1 | 1 2 3 4 5 6 7 8 | 9 a b c d e f 10
> ---------------------------
> A B C D E F G H
>--Joe
>--
Robert Hyatt
: X88 board so we can get a better visual idea.
:
: NOTE: I started counting at 1 instead of 0 since
: it's more humanly intuitive :)
: bit check in this example is "9" - not 8.
:
: Here it is:
:
: >off the board over here>>>
: VVVVVVVVVVVVVVVVVVVVVV
: ------------------------------
: 8 | 71 72 73 74 75 76 77 78 | 79 7a 7b 7c 7d 7e 7f 80
: | |
: 7 | 61 62 63 64 65 66 67 68 | 69 6a 6b 6c 6d 6e 6f 70
: | |
: 6 | 51 52 53 54 55 56 57 58 | 59 5a 5b 5c 5d 5e 5f 60
: | |
: 5 | 41 42 43 44 45 46 47 48 | 49 4a 4b 4c 4d 4e 4f 50
: | |
: 4 | 31 32 33 34 35 36 37 38 | 39 3a 3b 3c 3d 3e 3f 40
: | |
: 3 | 21 22 23 24 25 26 27 28 | 29 2a 2b 2c 2d 2e 2f 30
: | |
: 2 | 11 12 13 14 15 16 17 18 | 19 1a 1b 1c 1d 1e 1f 20
: | |
: 1 | 1 2 3 4 5 6 7 8 | 9 a b c d e f 10
: ---------------------------
: A B C D E F G H
:
:
: --Joe
Benoit St-Jean
brucemo (Bruce Moreland) wrote:
>In article <4s0vt8$c...@hpax.cup.hp.com>, jmc...@cup.hp.com says...
>>[snip]
>>NOTE: I started counting at 1 instead of 0 since
>>it's more humanly intuitive :)
>>[snip]
>False. Learn C.
>bruce
Both false! With Smalltalk such restrictions don't
exist : you can start counting anywhere... :)
Robert Hyatt
: : Joseph McCaughan contra (jmc...@cup.hp.com) wrote:
: : :
: : : Hi All,
: : :
: : : I wrote a little awk/bin/sh script to generate an
: : : X88 board so we can get a better visual idea.
: : : NOTE: I started counting at 1 instead of 0 since
: : : it's more humanly intuitive :)
: <snipped out intuitive stuff>
:
: : :
: : :
: : :
:
: : Might be more "intuitive" but you just gave *me* excedrin headache
: : #144... :)
:
: : Seriously, subtract 1 from everything and us hex-types can then cope
: : with this...
:
: : Bob
: OK, thanks for the *merciful* correction folks -
: after all I am a newbie at this. I thought I had the
: x88 concept down but I guess I need to give it a little more
: thought.
:
: Would someone post an accurate x88 board?
70 71 72 73 74 75 76 77 | 78 79 7a 7b 7c 7d 7e 7f
60 61 62 63 64 65 66 67 | 68 69 6a 6b 6c 6d 6e 6f
50 51 52 53 54 55 56 57 | 58 59 5a 5b 5c 5d 5e 5f
40 41 42 43 44 45 46 47 | 48 49 4a 4b 4c 4d 4e 4f
30 31 32 33 34 35 36 37 | 38 39 3a 3b 3c 3d 3e 3f
20 21 22 23 24 25 26 27 | 28 29 2a 2b 2c 2d 2e 2f
10 11 12 13 14 15 16 17 | 18 19 1a 1b 1c 1d 1e 1f
0 1 2 3 4 5 6 7 | 8 9 a b c d e f
0=a1, 7=h1, 70=a8, 77=h8, all numbers are in base 16...
numbers (squares) on right of "|" are off the board...
Bob
Robert Hyatt
Benoit St-Jean (fk69...@merlin.si.uqam.ca) wrote:
: brucemo (Bruce Moreland) wrote:
:
: >In article <4s0vt8$c...@hpax.cup.hp.com>, jmc...@cup.hp.com says...
: >>[snip]
: >>it's more humanly intuitive :)
:
: >False. Learn C.
:
: >bruce
:
: Both false! With Smalltalk such restrictions don't
: exist : you can start counting anywhere... :)
As with APL. Just set the "origin" to 0 or 1 or whatever. However, to
use the "X88" trick, you'd better org at 0. :)
Bob