Author: Dan Newman
Date: 03:40:08 02/13/00
Go up one level in this thread
On February 13, 2000 at 02:58:42, Tom Kerrigan wrote: >On February 13, 2000 at 00:55:03, Andrew Dados wrote: > >>On February 12, 2000 at 22:37:50, Robert Hyatt wrote: >> >>>On February 11, 2000 at 18:10:57, Tom Kerrigan wrote: >>> >>>>On February 11, 2000 at 14:04:16, Andrew Dados wrote: >>>> >>>>>>As for holes in the piece list, I figured you could fill them up: >>>>>That way your piecelist will not be preserved during search... while it does not >>>>>have to, it introduces changes into, say, order of generated moves. I am not >>>>>sure if I want that. >>>> >>>>I don't see why that's a big deal. The searches are still deterministic. >>>> >>>>-Tom >>> >>> >>>It isn't really deterministic if you do hashing. Try fine 70 and fiddle with >>>your move ordering to see this. >>> >>>But the main thing is that you _must_ be able to produce identical node counts >>>during testing... >> >>Also for LVA/MVV thing you need your piecelist sorted...so why scramble it? > >No, you just need to know what kind of piece the victim/attacker is. > >The reason for "scrambling" the piece list is obvious... so you don't have to >check every entry to see if it's "dead"... > >-Tom I did this once. I think it was in my first chess program about 5 yrs ago (and an oddball program that was :). Whenever I had a capture I swapped the last piece in the list into the hole and when I restored the captured piece (in unmake()) I put it at the end. So, as searching progressed the piece lists got very scrambled. I didn't particularly like this because I had some idea that this would affect move ordering in some unfavorable way... In another program I used doubly linked lists to hold pieces (they were very heavy weight, what with the list pointers and a bunch of other stuff in them, so I didn't want to be copying them about). At any rate, when one of those pieces got captured, I simply detached it (and saved if off somewhere) and then when I put it back (on unmake()) it still had the pointers to where it belonged in the list. So no scrambling. This of course has a good deal of overhead... In my next to last program (Skyblue) I simply test a bit to see if the piece is dead or not. If you have very few pieces on the board and the move lists are in order, you can generate the moves directly into MVV/LVA order--assuming you can iterate through one of the lists in reverse order. The idea is to have an outer loop that loops through victims--most valuable first--and an inner loop that loops through attackers--least valuable first. You can then use a simple table lookup to exclude those pairs of pieces for which there is no possiblility of attack, etc.. I tried an experiment with Skyblue and found the break even was at about 5 pieces. Anything more and it was more expensive than generating them the usual way and sorting. And doing this with all the pieces was rather prohibitive... -Dan.
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.