Author: Dan Newman
Date: 02:00:15 10/16/99
Go up one level in this thread
On October 15, 1999 at 23:41:35, Robert Hyatt wrote: >On October 15, 1999 at 18:24:57, Ricardo Gibert wrote: > >>On October 14, 1999 at 18:00:02, Robert Hyatt wrote: >> >>>On October 14, 1999 at 10:02:18, stefan wrote: >>> >>>>What do you think sort (and if yes how) or search move by move? >>>> >>>>Thank you >>>>stefan plenkner >>> >>> >>>The only 'sort' I do is to sort captures based on expected material gain/loss >>>(SEE score). There are usually a very few, so I use a simple bubble sort >>>which works well. >> >>Perhaps you meant to say "insertion sort" instead of "bubble sort". Sedgewick >>comment about bubble sort: "It is not clear why this method is so often taught, >>since insertion sort seems simpler and more efficinet by almost any measure. The >>inner loop of bubble sort has about twice as many instructions as either >>insertion sort or selection sort." > >there is theory, and there is reality. > >:) > >In theory, you are right. In reality, I use a _real_ bubble sort, although >I do an early exit rather than going for N*N iterations. But it is a classic >bubble sort. > >the number of captures to sort is _very_ small. for small N, N^2 is very close >to N*log(n) type sorts. And the code is smaller and more cache friendly with >far fewer branches. > Insertion sort is O(N^2) just like the bubble sort, and instruction-wise it probably isn't much, if any, more complicated. I think it mainly avoids swapping the stuff (that's getting sorted) as much as the bubble sort does. In the bubble sort things sort of percolate to the top. In the insertion sort you look repeatedly through the list and move things directly to where they belong. I've been using an insertion sort on my capture list, but I doubt it's any big win over the bubble sort: there are generally very few captures (0-6 say), and I imagine either would be better than, say, a quick sort or some other horrendously complex N*log(N) type sort. -Dan. > > > >> >>> >>>For history moves I use a 'selection sort'... where I pass over the entire move >>>list one time, find the move with the best history score, and try that. I then >>>repeat for the next move, and do this 4 times before I decide that history is >>>not going to cause a cutoff. (this is called 'selection sort' although it isn't >>>really a 'sort' at all).
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.