Author: Dan Newman
Date: 16:35:23 12/09/97
Go up one level in this thread
On December 08, 1997 at 15:00:20, Jari Huikari wrote:
> <snip>
>Last night :-) I decided not to have any maximum of legal moves in
>my program. Or more probably I set it to very high number ...
>say 500. (It doesn't cost much in my program.)
> <snip>
Hi,
No need to set the maximum number of moves as high as 500: all
you need to do is calculate the sum of the absolute maximum number
of moves of each piece from the set (9Q, 2R, 2B, 2N, 1K)--the idea
being that a queen's absolute maximum number of moves is greater
than that of a pawn or any other piece--so just promote all the
pawns to queens and calculate. If we do this we get an upper
bound on the maximum number of moves possible from any legal
position:
9*27 + 2*14 + 2*13 + 2*8 + 8 = 321.
Of course you must place a queen or bishop in the center to get
the maximum number of moves from it--which is impossible to do
with 9 queens and 2 bishops, and the pieces will tend to block
each other as well--so the real absolute maximum is lower than
321, maybe much lower, and may well involve a different set of
pieces. The biggest number I've ever been able to get (with a
completely unrealistic position) is only a little greater than
200. Required much rearrangement of 9 queens and sheltering of
the black king so that it was a "legal" (though perhaps
unreachable) position.
The trick I use (after reading discussions in RGCC and seeing
how Bob Hyatt does it in Crafty) is to "allocate" move lists at
each ply from a much larger array of moves (set large enough to
accommodate about 64 plies, say). This is very cheap to implement,
consumes much less memory, and prevents crashes from inadequately
sized move lists. (In my first chess engine the move lists were
auto arrays defined in the search functions and I had to set aside
a *very* large stack--I had rather bulky structs with 'from' and
'to' members, etc. for moves and dimensioned the arrays to 321
just to be sure.)
A little pseudo-code:
//
// Array from which move lists are allocated:
//
move_t move_array[ 4096];
//
// Array of pointers to the top elements of
// the move lists (to be indexed by ply number):
//
move_t *mlp[ MAX_PLIES+1];
//
// Initialization code to be called at start-up:
//
void init()
{
mlp[0] = move_array;
}
//
// The move generator:
//
void generate_moves( int side, int ply)
{
move_t *movep = mlp[ ply];
//
// Generate moves here, incrementing movep as we go.
//
//
// Mark the end of the move list--I use integers for moves
// in my codes now, so I mark the end with a zero (or just
// keep track of (or calculate) the count and save or
// return it, if you want to):
//
*movep++ = 0;
//
// Set the move list pointer for the next ply:
//
mlp[ ply+1] = movep;
}
Now, whenever you generate moves, the move list pointer at the
next ply gets set automatically (you must also make sure this gets
done when searching null moves or transposition table moves).
-Dan.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.