Author: Robert Hyatt
Date: 20:15:58 01/24/99
Go up one level in this thread
On January 24, 1999 at 20:54:26, Paul Tillotson wrote: >On January 24, 1999 at 20:08:27, Robert Hyatt wrote: > >>On January 24, 1999 at 11:11:55, Hugh Cumper wrote: >> >>>This may be very simple matter to the old pros. When I first wrote a chess >>>program I created a stack of boards for lookahead and copied the current board >>>each time I wanted to look further ahead, discarding it again to go back up. I >>>suppose I did that because I started writing programs for games like Kalah where >>>the board is small and moves are relatively epensive to take back. Recently I >>>have seen programs the have one board and store unmake move information in >>>addition to move information so the move can be retracted. I am trying to think >>>which is more efficient but I can't decide. Has anyone worked this out >>>theoretically or practically? >> >>If you are running on a PC, there is no comparison. the copy idea doesn't >>work, because the PC has practically no memory bandwidth to speak of, compared >>to what the CPU actually requires to keep it busy. >> >>Early versions of crafty did a copy-make approach so unmake just backed up the >>pointer and that was it. I went to the full make/unmake and picked up a lot >>of speed, once everything was cleaned up. > >Wouldn't the more complex the board structure determine this? >If it were simply a process of moving pieces I would agree. Undoing >moves requires a function call plus other code execution. If you use >a simple copy then it's much simpler. Does the bandwidth hit for a PC >really cost that much? yes... when I can execute two instructions every clock tick, but have to wait for 20+ ticks for every word of memory I access (actually that big delay is for the first word in a cache line but each word has a penalty as well, and while you are filling a cache line for data copy, you aren't fetching memory for other things like instruction fetches.. But you are right.. _if_ you can copy a tiny thing, it is probably better than updating it twice. But for a chess board, which also has other things like the hash signatures, etc... copying that can be very expensive when compared to a really optimized make/unmake approach...
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.