
# Move Table

I don't know where this came from originally, but I know that GnuChess has used this method for many years.

The GnuChess implementation involves two "threads" associated with each type of piece located on each square.  All of the stuff in the threads is pre-computed, so you just wade through pre-digested stuff and spit moves out.

I would make this a little heavier by using an array of elements, each of which contains a pointer to a square on the board, and another pointer to an element within the same array.

If there is a bishop on d5, somehow associated with this bishop is a pointer to a list that corresponds to the list of pre-computed legal moves for a bishop on d5.

To generate moves, you look at the first element in the list.  The element will contain a pointer to a square on the board.  If the square is empty, you generate a move, then go to the next element.  If the square is not empty, you generate a move if the occupier is an enemy piece, then you follow the "blocked" pointer and resume processing there.

My description is a little confusing, but here's how this could work in practice for a bishop on d5:

typedef struct tagMT {

    int    square;

    struct tagMT * pmtBlocked;

} MT;

 

MT argmtBD5[] = {

    e6,    &argmtBD5[3], // Element 0, 1st ray.

    d7,    &argmtBD5[3],

    f8,    &argmtBD5[3],

    c6,    &argmtBD5[3], // Element 3, 2nd ray.

    b7,    &argmtBD5[6],

    a8,    &argmtBD5[6],

    e4,    &argmtBD5[6], // Element 6, 3rd ray.

    f3,    &argmtBD5[6],

    g2,    &argmtBD5[6],

    h1,    NULL,         // Element 9, 4th ray.

    c4,    NULL,

    b3,    NULL,

    a2,    NULL,

    -1,

};

 

void GenMoves(MT * pmt)

{

    for (;;)

        if (IsEmpty(pmt->square)) {

            GenMove(pmt->square);

            if ((++pmt)->square < 0)

                break;

        } else {

            if (IsEnemy(pmt->square))

                GenMove(pmt->square);

            if ((pmt = pmt->pmtBlocked) == NULL)

                break;

        }

}

There is not a lot to this.  You end up doing a lot of memory accesses, and there are special cases for pawns and castling and all that, but you can add more fields to the move table element in order to do all kinds of neat things, and the code is not that complex.

This mechanism also combines well with other techniques such as the history heuristic -- you can store your history value in the table and not have to index into a big array -- and zobrist hashing -- you can store the source and destination keys already XOR'd together in the move table element.  The possibilities are endless and you can end up consuming huge amounts of memory.

I don't know how this compares performance-wise to other techniques.  You don't get some of the stuff you get for free with 0x88, and you don't get some of the stuff you get for free with bitboards, but neither of those techniques give you some of the stuff you get for free with this.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 12/27/02
