Author: Andrew Williams
Date: 16:21:21 09/01/02
Go up one level in this thread
On September 01, 2002 at 19:15:39, Kip Werking wrote: >On September 01, 2002 at 18:56:28, Andrew Williams wrote: > >>On September 01, 2002 at 18:37:57, Kip Werking wrote: >> >>>Hello - I am a newbie who just joined. I have three questions: >>> >>>1. I am sure many people have thought of this before, but there must be faster >>>ways to updating lists of legal moves, other than using brute force. Obviously, >>>the program would not check every possible square, but only a list of pieces. >>>My question is: would it be faster to set flags for each piece, and only update >>>a piece's list of possible moves if one of the flags has been tripped? >>> >>>For example, if an h pawn moves, it seems almost silly to have to update the >>>list of possible moves for a knight on the a column and simply check to see >>>whether or not the list of moves for the knight needs to be updated, and if not >>>(as in this case), know that the list of moves has not changed. >>> >>>Do programs already do this? Or is this inefficient or even incoherent in some >>>way that I do not realize? > >>Sounds like an interesting idea. Remember you need to take account of *two* >>moves. ie if you're generating for white, you need to consider both what black >>just did and what white did before that. Unless of course you're generating all >>moves for both at every level in the tree, which might be rather inefficient >>unless you're using this information to do something clever which makes the >>inefficiency worth it. > >I apologize. I meant to write this instead: > >"For example, if an h pawn moves, it seems almost silly to have to update the >list of possible moves for a knight on the a column. COULDN'T YOU simply check >to see whether or not the list of moves for the knight needs to be updated, and >if not (as in this case), know that the list of moves has not changed." > >Yes, if I was only generating the list of possible moves at every other move, >then I would need to consider TWO moves, and not ONE. To be honest, I had >intended to update the list of possible moves after EVERY CHANGE TO THE BOARD >(at every board considered in the game tree). I cannot really imagine how you >could run an evaluation function without knowing the list of possible moves? > >Let me give another example to illustrate my point. Imagine a knight that has >all possible 8 moves available. Instead of running a Knight::PossibleMoves >function that looked at all 8 squares every time the board changed, couldn't you >have a function that said: "Hey, if the knight didn't move: > >1. check to see if the king moved into pinning the knight, if so set all of the >knights possible moves to 0 (but remember what they were in case the king moves >again) >2. check to see if a same-color piece moved onto one of the knights possible >moves, if so subtract that move from the possible list > >Wouldn't this be much faster than checking all 8 possible squares at every board >along the game tree? I'm not sure it would, but it would depend on the data structures you maintain. It also might be more difficult for sliding pieces. There's only one way to find out and be absolutely sure. One way to find out but not be sure is to wait for other contributors to offer their opinions :-)( Andrew
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.