Author: Don Dailey
Date: 11:43:59 05/08/98
Go up one level in this thread
On May 08, 1998 at 12:36:59, Brian McKinley wrote:
>
>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
Hi Brian and Bas,
I have a version of Cilkchess that caches the moves of the sliding
pieces. I basically have 2 vectors for diagonal pieces and 2 vectors
for orthogonal pieces. I thinks it's conceptual very similar to your
idea. I simply have a 64 X n table for each direction and do a serial
search for the appropriate signature. n is small, 2 or 3 I think.
The hit rate is really high and I usually have no need to regenerate.
In each table I store a little move list to save regeneration.
It's a definite speedup in Cilkchess.
- Don
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.