What is X88 in computing chess ?
Guido Stepken
Just one question to Mr.Hyatt, i hope it may be of public interest:
What is X88 ?
tnx, Guido Stepken
--
BND, SS, VS, Demo, Greenpeace, Molotov, Gas, Bombe, Anti neutrino ;-)
anarchie, PKK, PGP, plutonium, revolution, cannabis, hanf,
heroin, kokain, RAF, attentat, kohl, steuerhinterziehung,
schwarzgeld, schmuggel, mafia, gefaelschter fuehrerschein.
Robert Hyatt
It's an old move generation trick and I have no idea who came up with it.
I used it in the 70's and it was not anything tricky then.
The basic idea is this: when generating moves, you have the problem of
detecting when you slide a piece "off the board". There are at least a
couple of ways to do this:
1. have a board[file][rank] array. here, after computing the next
move for a bishop by (say) adding +1 to both the rank and file, you
have to compare each value to 8 to make sure you didn't either go too
far (9th rank) or off of one side (< a file or > h file). Two tests
after each cycle. (this representation is bad for other reasons like
having to compute an absolute offset by rank*8+file, which is even
worse.)
2. creating a board[120] array which gives you 64 squares for the board,
plus two extra ranks/files in either direction. on the non-board squares,
you put some impossible piece value like 99. Then, after computing the
next bishop square, you load the board value and if it's "99" you are at
the end of that diagonal or whatever, or your knight move jumped off the
edge of the board. This requires a memory reference which is slow on PC
machines.
3. organize the board so that it is addressed by an 8-bit subscript. Valid
squares are those where you get numbers like 33, 34, 54, etc (hex numbers
here, be careful.) therefore, each "hex digit" must be >=0, <= 7. if you
add to a rank and you are already at the max (7) you get "8". If you
take a knight move that moves ahead too far, you get 9. notice that both
of these have the "8" bit (2^3) set. Using this technique, after computing
a new bishop square by adding the proper offset, you simply "and" the resulting
square with 0x88. if this is non-zero, the square is illegal, is off the board,
and can be ignored. Note there's no memory fetch to get the illegal piece, nor
any complicated math. also note that if you have either of the two hex digits
equal to zero, and you subtract anything to go in the "negative direction" of
a sliding piece moving backward, you will have a "borrow" from the bit that is
"0" (left-most bit of the xxxx file or yyyy rank bits) which will turn it into
a "1", again kicking you out with a simple and. This is faster, because you
already have the square number you just calculated, and it typically takes one
machine cycle to do the and and test, rather than a slow memory load, followed
by a test and branch.
Hope that helps
BTW, none of the above apply to a bitmap move generator, as you never generate
moves off the edge of the board in the first place, so that no testing of any
type is required. Just generate moves and enumerate them into a list of some
sort.
Bob
--
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
Tom Kerrigan
square board, 16x8. Notice that the numbers of the squares in the left half are
zero when ANDed with 0x88. This isn't the case with any other number (until 256,
anyway). Therefore, you can see if an offset is out of bounds with a simple AND
instruction. The advantage is that you don't need the relatively large mailbox
arrays. The disadvantage is that you need a 128 square board, which can be a real
pain once in a while.
Cheers,
Tom
_______________________________________________________________________________
Tom Kerrigan kerr...@frii.com O-
When does summertime come to Minnesota, you ask? Well, last year, I
think it was a Tuesday.
Bruce Moreland
says...
>
>Hi !
>
>Just one question to Mr.Hyatt, i hope it may be of public interest:
>
>What is X88 ?
>
>tnx, Guido Stepken
>
>--
>BND, SS, VS, Demo, Greenpeace, Molotov, Gas, Bombe, Anti neutrino ;-)
>anarchie, PKK, PGP, plutonium, revolution, cannabis, hanf,
>heroin, kokain, RAF, attentat, kohl, steuerhinterziehung,
>schwarzgeld, schmuggel, mafia, gefaelschter fuehrerschein.
This reply will be a little hard to understand, but if you are going to
write a chess program, it would be good to understand it, so try hard.
0x88 is a board representation & move generation system. Here is how it
works.
A chess board is ordinarily 8 ranks high by 8 files wide. In this system
you make the board 16 files wide, but the right-most files are ignored,
I'll explain why they exist shortly.
You number the squares 0..127. a1 is 0, b1 is 1, a2 is 16, h8 is 135,
etc.
To generate the moves for a sliding piece you have a "square offset"
number that you use to get to the next square on the pieces' movement
vector. For instance, a bishop on c3 can move upward and to the right,
toward h8. You start with c3 and add 17 squares to get to d4, then 17
more to get to e5, until you either hit something or run off the board.
The idea behind 0x88 move generation is that it is easy to tell if you
have run off the board. All you do is AND the proposed new square number
with 0x88 and see if you have anything left over. If you do, you've run
off the board. The idea is that if you are on the H-file, and try to move
to the I-file, the 8's bit will be set in the resulting square number. If
you are on rank 8 and try to move to rank 9, the 128's bit will be set.
The same thing happens if you try to move to rank 0 or whatever you want
to call the file to the left of the A-file.
You end up with a loop that looks like this:
for (;;) {
isq += 17;
if (isq & 0x88)
break;
// In here you check to see if you are capturing a piece,
// or conflicting with one of your own pieces, or are just
// moving to a square, and either generate a move, break
// out of here, or both, as appropriate.
}
This loop ends up being very fast.
There is another benefit to this technique as well, you can use it to make
a fast "in check" function, among other things.
If you take the difference between any two squares on the board, you get a
number, either positive or negative. This number relates the two squares
in a manner that you can actually use. If A is 17 greater than B, A is
above and to the right of B. If it is one less than B, it is one square
to the left of B. If it is 14 more than B, it is two squares left and one
above B (a knight's move).
In an 8 by 8 board, you can't do this. If you subtract A from B and get
one, it MAY be true that B is one square to the right of A, but this
assumption is not ALWAYS true. The counter-example is if B is a4 and A is
h3. B - A is 1, but B is NOT one square to the right of A, it is
somewhere else, in an 8 x 8 board things can "wrap around". This can't
happen in a 16 x 8 board.
That you can subtract two squares and get a number that describes their
relationship is USEFUL. You can take this difference number, offset it by
128 so it's always >= 0, and indirect into a table. The value in the
table is a bitmask that describes what kind of piece can make a move
between two squares that relate in this manner. So in the element of this
table that corresponds to 17 (one up and to the right), you get QUEEN |
BISHOP | KING, or something like that.
In an in-check function, what you want to do is figure out if a particular
piece can attack the king. You would look up the relationship between the
square the piece is on and the square the king is on in this table, and
see if the bit for this piece type is set. If it is not set, you can't
get there from here, and you can move on to your next piece. If it is
set, in the case of a non-sliding piece (knight or king), you are DONE.
In the case of a sliding piece, you still have to walk the vector to see
if there are any interposing pieces, but this won't happen very often,
most often the bitmask in the table will discriminate for you.
I don't know which programs are using 0x88, but I suspect that many very
good ones are.
I hope the above was understandable.
bruce
Robert Hyatt
MANOHARARAJAH VALAVAN <man...@ecf.toronto.edu> wrote:
>In article <4kbse0$s...@news.microsoft.com>, Bruce Moreland <brucemo> wrote:
>>This reply will be a little hard to understand, but if you are going to
>>write a chess program, it would be good to understand it, so try hard.
>>
>>
>>good ones are.
>>
>>I hope the above was understandable.
>>
>>bruce
>>
>
>i.e. who used it first?
>
>--
I'm not certain about this, but I used it in the middle 70's. I believe that I
learned about it from Ed Kozdrowicki / Dennis Cooper, the authors of the famous
"COKO" computer chess program from the first few ACM events. Yes, the very one
that didn't know the difference between mate in 1 and mate in 2, and kept playing
a mate in 2 until it got mated itself. :)
Wouldn't surprise me that one of the early Slate/Atkin programs used it. Just
guessing, I'd say it's the sort of thing someone in cryptoanalysis might come
up with, since they are used to twiddling with bits, using such tricks to count
multiple parts of a word in one cycle, etc.
In any case, somewhere around 1980-81 I went to another representation that
better vectorized and have not paid much attention to move generation since,
until the approach I now use in Crafty which is also (so far as I know) something
that's never been done before. However, I've come to the conclusion that "there's
very little new under the sun." One person's "discovery" is another person's
"unpublished gem." :)
Maybe the *real* inventor will come forth, but it was long enough ago that he
might not be reading this sort of newsgroup any longer. Jim? any ideas?
MANOHARARAJAH VALAVAN
Ahh....Cool algorithm.... Does any one know the origins of the algorithm?
i.e. who used it first?
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Michael F. Byrne
On Sunday, April 07, 1996, Guido Stepken wrote...
> Hi !
>
> Just one question to Mr.Hyatt, i hope it may be of public interest:
>
> What is X88 ?
>
> tnx, Guido Stepken
>
> --
> BND, SS, VS, Demo, Greenpeace, Molotov, Gas, Bombe, Anti neutrino ;-)
> anarchie, PKK, PGP, plutonium, revolution, cannabis, hanf,
> heroin, kokain, RAF, attentat, kohl, steuerhinterziehung,
> schwarzgeld, schmuggel, mafia, gefaelschter fuehrerschein.
>
I believe this is a typo - and the designation is x86, standing for a
piece of his program that is geared towards the x86 class of personal
computers - 386, 486, 586, etc. . and then again I may be wrong.
Robert Hyatt
No, I think that he's referring to the "x88" move generation trick.
While this has been covered before, basically it's a quick and dirty
way of detecting when you generate a square that's off the board. Without
care, you can slide a rook from the h-file, one more square to the right,
and end up on the a-file. As a result, anytime you increment or decrement
a rank or file #, you have to check them.
with x88 squares that are "off the real board" have one or both of the
'0x88' bits set, because of the board layout with 16 squares per rank,
with the first 8 being legal, the last 8 not. then if you add any reasonable
number to a real square, either it produces a square with no 0x88 bit set
(10001000 in binary) which is a good square, or else if either or both of
those bits are set, it's off the board.
This lets you increment a square by (say) 16 to slide a rook one rank forward,
and then test whether it's legal or not. Even better, you can add 17 and
slide a bishop up one rank and to the right one file, and with one and
operation, determine if you went to a bad rank or a bad file. Simply saves
a little code...
MANOHARARAJAH VALAVAN
In article <01bb32b9.f34451a0$ccb6...@omni2.voicenet.com>,
Michael F. Byrne <ches...@voicenet.com> wrote:
>
>On Sunday, April 07, 1996, Guido Stepken wrote...
>> Hi !
>>
>> Just one question to Mr.Hyatt, i hope it may be of public interest:
>>
>> What is X88 ?
>>
>> tnx, Guido Stepken
>>
>> --
>> BND, SS, VS, Demo, Greenpeace, Molotov, Gas, Bombe, Anti neutrino ;-)
>> anarchie, PKK, PGP, plutonium, revolution, cannabis, hanf,
>> heroin, kokain, RAF, attentat, kohl, steuerhinterziehung,
>> schwarzgeld, schmuggel, mafia, gefaelschter fuehrerschein.
>>
>
>I believe this is a typo - and the designation is x86, standing for a
>piece of his program that is geared towards the x86 class of personal
>computers - 386, 486, 586, etc. . and then again I may be wrong.
>
>
It is not a typo.... x88 is a way of detecting when pieces are "off-board".
It is supposedly more faster for micros to use this approach than the older
approach of putting some "invalid" piece in the squares surrounding the
real board.