X88 board representations
MANOHARARAJAH VALAVAN
X88 move generation/board representation techniques. I have used regular
64 square reps and bit board reps before... and I want to give this X88
move generation stuff a try (since I am rewriting a chess program I wrote
long ago).
Obviously, we can do detection of "off board/on board" easily with a bit
operation. And furthermore, we can also do quite fast "in check" detections.
Is there some other tricks that one can play with this kind of representation?
Also, is this kind of representation good for PCs... I am not too familiar with
optimization techniques, but someone mentioned that bit boards reps are
rather bulky (in terms of tables and such) and do not fit in the L1 processor
cache. I would assume X88 (with its simple bit operations and offsetting)
should quite handilly fit inside L1 caches (along with most of the Alpha-Beta
code, I guess).
Is there any source code/documents that describe this particular technique?
....I went through my collection of ICCA stuff, but there is nothing in there!
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Robert Hyatt
MANOHARARAJAH VALAVAN <man...@ecf.toronto.edu> wrote:
-->There was a cool post a while back by Bruce Moreland and Robert Hyatt on
-->X88 move generation/board representation techniques. I have used regular
-->64 square reps and bit board reps before... and I want to give this X88
-->move generation stuff a try (since I am rewriting a chess program I wrote
-->long ago).
-->
-->Obviously, we can do detection of "off board/on board" easily with a bit
-->operation. And furthermore, we can also do quite fast "in check" detections.
-->
-->Is there some other tricks that one can play with this kind of representation?
-->
-->Also, is this kind of representation good for PCs... I am not too familiar with
-->optimization techniques, but someone mentioned that bit boards reps are
-->rather bulky (in terms of tables and such) and do not fit in the L1 processor
-->cache. I would assume X88 (with its simple bit operations and offsetting)
-->should quite handilly fit inside L1 caches (along with most of the Alpha-Beta
-->code, I guess).
-->
-->Is there any source code/documents that describe this particular technique?
-->....I went through my collection of ICCA stuff, but there is nothing in there!
I'm personally not sure. I did the move generation trick, and the attack
detection trick until we found an even faster attack detection mechanism that
required one occupied-squares bitmap (64bits). Once we switched to this and
then the vectorized move generator, the X88 stuff was gone from Cray Blitz, and
all this happened in the 1982-83 time-frame.
I wouldn't be surprised if there are other things that this helps, because I have
a long list of things that the Crafty bitmap approach has produced that I did not
know about when I first started Crafty about 1.5 years ago. More importantly, I
don't think the bitmap well is dry yet either.
As far as documents, there are none I know of, which is one of the reasons I
queried this group about writing a "Inside Computer Chess" sort of book that
explains various approaches both verbally, algorithmically, and with enough
detail and explanation that it would be "intuitively obvious to the most casual
observer" exactly how to implement *that*... (whatever *that* might be.)
You'll have the same criticism when you try to implement hashing, evaluation,
ordering, move generation, attack detection (in check function), the actual
search, search extensions, etc. :)
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
MANOHARARAJAH VALAVAN
Robert Hyatt <hy...@cis.uab.edu> wrote:
>I'm personally not sure. I did the move generation trick, and the attack
>detection trick until we found an even faster attack detection mechanism that
>required one occupied-squares bitmap (64bits). Once we switched to this and
>then the vectorized move generator, the X88 stuff was gone from Cray Blitz, and
>all this happened in the 1982-83 time-frame.
>
>I wouldn't be surprised if there are other things that this helps, because I have
>a long list of things that the Crafty bitmap approach has produced that I did not
>know about when I first started Crafty about 1.5 years ago. More importantly, I
>don't think the bitmap well is dry yet either.
>
>As far as documents, there are none I know of, which is one of the reasons I
>queried this group about writing a "Inside Computer Chess" sort of book that
>explains various approaches both verbally, algorithmically, and with enough
>detail and explanation that it would be "intuitively obvious to the most casual
>observer" exactly how to implement *that*... (whatever *that* might be.)
the sooner you write the book the better... looking foward to it!
>
>You'll have the same criticism when you try to implement hashing, evaluation,
>ordering, move generation, attack detection (in check function), the actual
>search, search extensions, etc. :)
>
>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
I went ahead and rigged up 0x88 move generation/attack detection last night..
I was using a gnuchess type move generation algorithm before. The gnuchess
algorithm is rather simple and uses a table to generate all the moves. The
gnuchess scheme gave me about 550000 mvs per sec. The new scheme gave me
about 600000 mvs per sec. On the same hardware, crafty generates moves
at around the same rate - so I know, I am not doing too badly. These figures
don't involve the cost of make_move()/unmake_move() (since I haven't written
that yet :-(). But with the simple 0x88 representation, very little updating
has to be done anyway...I would expect to see around 200000 mvs per sec with
the make_move/unmake_move stuff in place.
Urban Koistinen
MANOHARARAJAH VALAVAN (man...@ecf.toronto.edu) wrote:
: I went ahead and rigged up 0x88 move generation/attack detection last
: night..
: I was using a gnuchess type move generation algorithm before. The gnuchess
: algorithm is rather simple and uses a table to generate all the moves. The
: gnuchess scheme gave me about 550000 mvs per sec. The new scheme gave me
: about 600000 mvs per sec. On the same hardware, crafty generates moves
: at around the same rate - so I know, I am not doing too badly.
: These figures
: don't involve the cost of make_move()/unmake_move() (since I haven't written
: that yet :-().
: But with the simple 0x88 representation, very little updating
: has to be done anyway...I would expect to see around 200000 mvs per sec with
: the make_move/unmake_move stuff in place.
A variation on 0x88 move generation is to store udlrwbe for each square,
(border is up, down, left, right and piece on square is white, black
or empty), as then you save about one conditional per move generated.
The extra cost is that when you make a move you must set the color bits
of the affected squares (usually two squares) when making the move.
Instead of:
GenerateSweeping(int offset, int starting)
{
int sq;
int i;
sq = starting;
/* optimization: unroll this loop */
for(i=7;i--;) {
sq+=offset;
if(sq&0x88) return;
if(board[sq] != empty) break;
add_move(starting, sq);
}
if(board[sq] == opposing color)
add_capture(starting, sq);
}
You would do:
GenerateSweeping(int offset, int starting, int mask)
{
int sq;
int i;
sq=starting;
/* by making board[] larger, this might be done more cheaply */
if(board[sq]&mask&udlr) return;
/* optimization: unroll this loop */
for(i=7;i--;) {
sq+=offset;
if(board[sq]&mask) break;
add_move(starting, sq);
}
if(!(board[sq]&(empty|movingcolor)))
add_capture(starting, sq);
}
To generate rook moves upwards you would use:
GenerateSweeping(up_offset, from, white|black|up);
To generate bishop moves right downwards you would use:
GenerateSweeping(down_offset+right_offset, from, white|black|down|right);
If you find the above useful, please send me a note about it.
Urban.K...@abc.se - e...@algonet.se