Author: Robert Hyatt
Date: 13:26:10 05/30/04
Go up one level in this thread
On May 30, 2004 at 15:44:07, James Swafford wrote: >On May 30, 2004 at 07:54:29, Sune Fischer wrote: > >>On May 30, 2004 at 07:17:01, James Swafford wrote: >> >>>On May 30, 2004 at 03:36:59, Sune Fischer wrote: >>> >>>>On May 29, 2004 at 22:53:38, James Swafford wrote: >>>> >>>>>On May 29, 2004 at 16:09:22, Sune Fischer wrote: >>>>> >>>>>>On May 29, 2004 at 14:41:28, Anthony Cozzie wrote: >>>>>> >>>>>>>On May 29, 2004 at 14:26:55, Russell Reagan wrote: >>>>>>> >>>>>>>>On May 29, 2004 at 04:24:18, Tony Werten wrote: >>>>>>>> >>>>>>>>>Yes, you would have to hop to nextsquare to see how it would go from there. Now >>>>>>>>>you only have to look what square we are talking about, and if !nil, you will >>>>>>>>>always know that the nextsquare will be given at *sq++ >>>>>>>>> >>>>>>>>>So you basicly made "nextsq" and "location of nextsq" independant of each other, >>>>>>>>>thereby making it independant of board representation and making it more >>>>>>>>>efficient since you will be traveling through the array in a row, rather than >>>>>>>>>randomly accesed. >>>>>>>> >>>>>>>>Would this be any faster than a traditional array based move generator? As far >>>>>>>>as I can tell, the array based movegen will iterate over an array, while the >>>>>>>>move table approach loops over a linked list (effectively). Looping over an >>>>>>>>array will almost always be at least as fast as looping through a linked list, >>>>>>>>right? Plus the move table approach uses more memory to accomplish the same >>>>>>>>thing. You may get some other advantages from a move table approach, but with >>>>>>>>regard to speed, the move table approach doesn't seem like it would be the >>>>>>>>fastest. >>>>>>> >>>>>>>The magic of Vincent's generator is that there are almost no branches and >>>>>>>relatively little memory. The two biggest wastes of time in a modern deeply >>>>>>>pipelined superscalar processor are branch mispredictions and cache misses. >>>>>>> >>>>>>>anthony >>>>>> >>>>>>I really don't understand all the hype about a generator. >>>>>>I just had a look at a profile, mine spends something like 5% generating moves. >>>>>>That's hardly worth even looking at to optimize. >>>>>> >>>>>>It might be due to its incremental design that it's so fast though ;) >>>>>> >>>>>>Sorting the moves however, now that takes time. >>>>> >>>>>What type of sort do you use? How often do you sort your >>>>>move list(s)? >>>> >>>>I use SEE for the most part, expensive but seems to be well worth it. >>> >>>SEE scores moves, it doesn't sort: >> >>Assigning scores is the first step in the sorting process. >> >>>do you use (1)bubble sort, >>>(2)quick sort, (3) no sort (scan for best) .. ? > > > >> >>Depends on which is the fastest. :) > >Well, that's an interesting question! > >The magic "number" for sorting is to do it in O(n lg n), >but I've heard others (I think Hyatt) use bubble sort, >which has a running time of n^2. > >I'm using a stupid bubble sort, but I don't sort very >often, and I plan on trying others at some point. For the typical case of 2-3 captures, n log n and n^2 are about the same. :) Then it becomes which is most efficient. N log N sorts are not very good for very small numbers of elements. They do too much wasted effort. IE quicksort/heapsort. Why break a list of length 3 into two parts??? > > >> >>-S. >> >>>-- >>>James >>> >>> >>>> >>>>-S.
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.