Author: Brian McKinley
Date: 09:36:59 05/08/98
Go up one level in this thread
On May 07, 1998 at 15:51:16, Bas Hamstra wrote:
>Do you think it would be possible to generate moves incrementally? Most
>of the legal moves remain the same after a move is made, it seems. I
>think it might be possible to generate only moves for the pieces that
>are "affected" by the prior move.
This is exactly how my program generates moves. After each move, I only
re-calculate moves for pieces whose coverage area or movement range is
impacted by the move. This part is very fast. On average, I only
re-calculate moves for 15% of the pieces on the board.
>
>If I'm not mistaken KnightCap does this (or was in another program?). It
>has a board representation in which each square is a 32 bit number, each
>bit representing the (uniquely identified) piece by which that square is
>attacked. There can be no more pieces on the board than 32.
>
>Suppose a move a2-a3 is made. Adjust the board (="attackmap") for the
>new squares a3 attacks and delete the a2-attacks. If a2 OR a3 is
>attacked by a piece (of both colors) only the moves for those pieces are
>to be regenerated and the board has to be updated again, for just those
>pieces.
>
>Would that work you think?
I am not sure. I keep three 64 bit masks for each piece. The first is
a mask of moves that the piece can make. The second is the coverage
area (for all but pawns this is the only mask you need). And the third
is a mask of squares the pawn could move to if it were not blocked. You
could fold this in to one mask if you don't use the information else
where. To determine if I need to recalculate:
if (movesquares & coverage ) || (type == PAWN && movesquares & (coverage
| moves | potentialmoves)
{
Recalculate...
}
Where movesquares is another 64 bit mask with the from and to square
bits on. You will need a little extra work to handle empassant.
>
>Problem: what to do with unmake? Compute it all "back" seems expensive.
>Or no unmake at all and fetch the previous board? Wouldnt that be
>expensive too on a PC (bandwitdh and all)?
The information used to determine which pieces need to be re-calculated
cannot be easily unmade through calculations. So, anytime a piece's
information is re-calculated, I push the old information on to a stack.
The unmake function then pops piece information that was pushed at that
ply.
>
>Could someone please react on this thoughts?
Unfortunately I can't give you good comparisons because I only generate
valid moves, and much of the work to determine if a move is valid could
be put off to the search (Something I am considering). Currently, on my
P200, average nps is 35K at the beginning of the game and 80K+ at the
end. I am sure you could gain quite a bit of speed using a semi-valid
move generator.
Brian
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.