Author: Robert Hyatt
Date: 21:10:14 04/17/98
Go up one level in this thread
On April 17, 1998 at 15:46:23, Dan Newman wrote:
>On April 17, 1998 at 07:30:51, Inmann Werner wrote:
>
>>Piece table question
>>
>>Can anybody help me?
>>
>>When generating moves in my chess programm, until now I search the whole
>>boad for pieces. I want to speed this up and use a figure list like
>>this:
>>
>>Typedef struct{
>> Char where /*Position on Table*/
>> Char what /*which piece (0=nothing;1=pawn ...*/
>> }TYPFIGLI;
>>
>>TYPFIGLI FIGLI[2][16]; (FIGLI[0].. is white, FIGLI[1].. is black)
>>
>>Char FIGBR[125(A board table with a 'pointer' to FIGLI (10*12 board))
>>
>>In the move Generator and the evaluation function, everything works
>>fine.
>>In the routine 'DO_MOVE' it is a little bit tricky, but it works.
>> FIGLI[color][FIGBR[from]].where=tomove
>> FIGBR[tomove]=FIGBR[from]
>> FIGBR[from]=-1
>>
>>But in the routine 'UNDO_MOVE' i have a problem, when I put back a
>>captured piece.
>>
>>There are two possibilities.
>>
>>1) search the structure FIGLI for an empty field and use it.
>>2) Increase the number of pieces in FIGLI and store the piece in the
>>last one
>>
>>If I use 1), I possibly have to search up to 16 times to find an emty
>>location.
>>If I use 2), I have to increase the structure of FIGLI and more and more
>>'pieces' are in it. In 'Generate moves' everything slows down. (maybe I
>>get even an overflow).
>>
>>Which possibility is better?(I think the first one)
>>Does anybody know anything much better and faster!!!.
>>
>>Thank you very much,
>>
>>INMANN WERNER
>>
>>PS: I am from Germany, and my English is rather poor. Excuse me!!
>
>Here are two tricks I've used for this.
>
>1) When a piece is captured (and removed from the piece list (figure
>list))
> move the piece at the end of the list into the now empty location.
> When undoing the capture just put the un-captured piece at the end of
> the list. You would of course maintain a count of the pieces in each
> list to make it easy to find the ends of the lists and for iteration
> through the lists.
>
>2) Use one of the bits in the piece to mark the piece as captured but do
> not remove the piece from the list. Use this bit to skip over this
> piece when doing move generation, etc. When undoing the capture,
>just
> clear this bit. (You could use the high order bit in the 'what'
> member of the piece.)
>
here's something we did in Cray Blitz: on the normal board, put a
pointer
to the piece "record" you defined above. then you can always find out
which piece record to "fix" since after making a move "to" points to
board[to] which points to the piece record for the piece on that
square...
>There are advantages and disadvantages to each of these. With 1) the
>piece
>list grows shorter as the game progresses. This helps with move
>generation
>in the endgame--it gets quite fast. But the order of the pieces in the
>list becomes scrambled and thus the order in which moves are generated
>may
>suffer.
>
>In 2) (the one I currently use--mainly because of its simplicity) the
>order
>of the pieces is fixed. This allows you to generate moves in order of
>piece type (which may help with move ordering). The main disadvantage
>is
>that the length is always 16 so that move generation has some overhead
>(especially noticeable in the endgame).
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.