Author: Dan Homan
Date: 04:22:29 07/16/99
Go up one level in this thread
On July 15, 1999 at 17:37:42, Will Singleton wrote: > >On July 15, 1999 at 10:28:24, Dan Homan wrote: > >>I've decided to make some free time for myself this summer to work on >>my chess program. I've decided to do a complete re-write of EXchess >>from the ground up, using 0x88. >> >>My plan in writting previous versions of EXchess has always been to >>make everything as easy to understand as possible. I want to keep that >>in the new version, but I would also like to go faster! >> >>I have some ideas on making/unmaking moves during the search. In >>previous versions of EXchess, I have just done position copies for >>each new ply and had no need for an unmake routine. Several people told >>me it was faster to make/unmake but my experiments didn't show much >>improvement. I want to do unmake in the new version of my program, and >>I would like to make it as efficient as possible. >> >>One idea I had was just doing a bit-shift to undo moves. The idea >>is that a square on my board would be an int (or perhaps int64), but only >>the first 4 bits would store piece/color information. Then I could >>store 8 (or 16) "states" for a given square - all in order of how they >>occurred in the tree. My unmake move would just be a bit-shift on the >>appropriate squares. >> >>I have one concern with this - How many times can the state of a given >>square change in the tree? My feeling is that there will be situations >>where the state of a square will change more than 8 (or even 16) times. >>(I score any repeated position as a draw, so that may make these situations >>relatively rare, but just one such situation could be a big problem in >>a game.) I could have a scheme for storing the "lost" information in >>these rare cases, but I wonder if the speed-up from this idea is >>significant enough to warrant the added complexity? >> >>I would welcome any other ideas people have for making a fast "unmake" >>routine. >> >> - Dan > > >Sounds interesting, help me out on this. Is this substantially diferent than >storing each move into 64 arrays (each corresponding to a square), then indexing >into each array for the current state? The unmake would just be to subtract the >index. Then, you wouldn't have the limit problem. Just re-read this last sentence. You're right, that is a way around the limit problem! Then the current state of the board is contained all over the 64 arrays in memory, so I would have to be sure that I didn't need to loop over the board in a time critical location in the code. - Dan > >How about state info, like en passant and castle privileges? Would you have to >copy those from ply-to-ply if you wanted to simplify the unmake to a bit shift? > >Will
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.