Author: Robert Hyatt
Date: 11:28:32 07/16/99
Go up one level in this thread
On July 16, 1999 at 07:22:29, Dan Homan wrote: >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 However, none of this sounds very 'cache friendly'. The PC's weakest link is memory bandwidth. Use it carefully. It is far better to use 20 more instructions, than it is to use one extra memory reference. And every time the clock speeds go up, this gets worse.
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.