Author: Robert Hyatt
Date: 19:43:15 01/05/00
Go up one level in this thread
On January 05, 2000 at 20:07:26, Bas Hamstra wrote: >On January 05, 2000 at 18:21:04, Landon Rabern wrote: > >>On January 05, 2000 at 09:21:25, Robert Hyatt wrote: >> >>>On January 05, 2000 at 01:24:52, Landon Rabern wrote: >>> >>>>On January 05, 2000 at 01:03:47, Robert Hyatt wrote: >>>> >>>>>On January 05, 2000 at 00:49:50, Landon Rabern wrote: >>>>> >>>>>>After move generation, when putting a killer/pv/hash table move on top of the >>>>>>list I search through the list of moves until I find the move I am looking for, >>>>>>shift the whole list down and put the move I wanted on top. Is there a better >>>>>>way to do this? The way I am doing it seems inefficient. >>>>> >>>>>There are multiple answers. >>>>> >>>>>1. Don't generate moves before you try the hash move. If it produces a >>>>>cutoff you avoid generating anything. Otherwise, try it, and if it doesn't >>>>>cutoff, generate only captures (if you can do this easily). Try them next. >>>>>Before generating other moves, try the killer moves since they can be tried >>>>>without generating moves and they too may produce a cutoff that will avoid >>>>>move generation. Otherwise, generate all moves and then for the first pass >>>>>to select a history move, delete the killer moves and the hash move. >>>>> >>>>>2. Don't shift things around. Just make the move you want and zero it in >>>>>the list. no move should be represented as 0, so you can tell that an >>>>>entry is a move that has already been tried and cleared... no point in >>>>>shuffling stuff around as it uses a lot of memory bandwith, something the >>>>>PC has very little of. >>>> >>>> >>>>What if a killer move is not a legal move at some nodes? >>>> >>>>Landon >>> >>> >>>I store FROM, TO, MOVING_PIECE, CAPTURED_PIECE, PROMOTION_PIECE in my 21 bit >>>move format. With that information, I can test for psuedo-legality by making >>>sure that MOVING_PIECE is on FROM, CAPTURED_PIECE is on TO, etc. IE I have >>>enough information to be sure that moves are legal enough to not corrupt the >>>board. Later the in_check legality check will finish the testing.. >> >>Ok, I store all this stuff too except promotion piece, because I always have it >>setting it to a queen for now. What about sliding pieces? Checking that from >>is moving and to is captures works for non-sliding pieces, but for sliding >>pieces, do you check the squares in between from and to, to make sure nothing >>has moved there, to block the piece from moving? I guess you could just get a >>bitboard with the squares in between 1's and & it with all the pieces on the >>board, to test this. >> >>Thanks, >>Landon W. Rabern > >Exactly, it has to be checked and using a bitmap for blocks is efficient. About >what Bob said about not shuffling the movelist too much: I don't think I agree. > >You want somehow to get the best capture from that list first. So you have to do >a sort (n-best), which requires shuffling anyway. Or you do it like I do: no >pre-sorting but for the first n NextMove's lookup the highest sortvalue and swap >that move with the current listposition. Which is basically the same thing of >course, but in my opinion more efficient, because in case of a cutoff you have >saved much sorting work (and shuffling i.e. bandwidth). > > >Regards, >Bas Hamstra. You can always do a 'selection sort' where you make a pass over the captures to pick the best one. Then if you want to search another capture, pass over the list again. this is O(N^2) but most of the time you only search one capture. No swapping at all is needed.
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.