Author: Dan Newman
Date: 12:00:52 04/18/98
Go up one level in this thread
On April 17, 1998 at 19:34:27, Carsten Kossendey wrote: >On April 17, 1998 at 15:46:23, Dan Newman wrote: > >>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). > >You can improve this by rebuilding the list at the root position of your >search, such that it contains only as many elements as pieces are on the >board in the root position. (I assume you don't need the list while you >are not searching, otherwise you need another version of UndoMove() >which re-inserts a captured piece in case of a "take back" command.) > I have done some of that (rebuilding at the root) in the past. It didn't buy me much until the endgame (I'm guessing now)--maybe 10%. I figured once I added more complex eval that that would go down to, say, 5%. (Well I've done more than that for a mere 5%. :)) Currently I'm using a (doubly) linked piece list. I remove the captured piece from the list and save it in another data structure in which I maintain/save info during the search. >Also one thing you didn't mention is how you handle promotions. Do you >re-sort the list (since the piece type changes) or do you just leave the >promoted piece in the middle of the pawns? Ah yes, promotions (yet another drawback to simple piece list schemes). Currently they get left in the middle of the pawns which are at the head of the list. Not entirely to my liking. I'd like to do something about this--sorting at the root would help--but inside the search it would be a bit messy. If it helps the move ordering enough, it would certainly be worth doing though. -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.