Author: Dan Newman
Date: 12:46:23 04/17/98
Go up one level in this thread
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.)
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.