Author: Robert Hyatt
Date: 19:10:11 10/25/99
Go up one level in this thread
On October 25, 1999 at 18:21:20, Michel Langeveld wrote:
>On October 25, 1999 at 16:38:07, Robert Hyatt wrote:
>
>>On October 25, 1999 at 16:05:20, Michel Langeveld wrote:
>>
>>>On October 25, 1999 at 14:48:54, Dann Corbit wrote:
>>>
>>>>On October 25, 1999 at 12:26:37, Michel Langeveld wrote:
>>>>>On October 25, 1999 at 10:17:53, Dann Corbit wrote:
>>>>>>On October 23, 1999 at 10:36:40, Robert Hyatt wrote:
>>>>>>
>>>>>>>On October 22, 1999 at 10:03:29, Dann Corbit wrote:
>>>>>>>
>>>>>>>>Change to binary insertion and you will see a much bigger benefit.
>>>>>>>
>>>>>>>I tried both (from Knuth Sorting and Searching). Binary is very bad for
>>>>>>>lists that have 1-5 entries max. from testing on my machine. Simple
>>>>>>>insertion is no faster than the bubble sort I used, but it also turns out
>>>>>>>to be no slower either, after testing Crafty over 300 different positions.
>>>>>>>
>>>>>>>I think I'll leave insertion in, to prevent such discussions in the
>>>>>>>future, however. :)
>>>>>>I have found a new modification to insertion sort (binary or linear) that will
>>>>>>make a large improvement in speed. It has to do with the data movements to
>>>>>>perform the actual insertion. By delaying the insertion, I can do all data
>>>>>>movements as a single permutation and never move any element more than once. It
>>>>>>won't work for big lists though, since the code size is O(n!). With just ten
>>>>>>items there are a million leaves in the tree. However, for very small sublists
>>>>>>I think it will do very well.
>>>>>
>>>>>Best way to prove your statement is code it, and prove it's faster!
>>>>>Good news by the way.
>>>>Got the idea from a web page. Here is an example for n=3. Number of
>>>>comparisons is O(n*log(n)). For the left branch (1,2,3) do not move anything.
>>>>For (1,3,2) permute the 3 & 2. For (3,1,2) and (2,3,1) we must move all of
>>>>them, since none is in the right place, and for (3,2,1) we permute 1 & 3. It is
>>>>very simple, really. I have a code generator to write the output, but I think I
>>>>can simplify it a lot and use the inline keyword (it's C99). The colon in the
>>>>diagram means compare. We don't actually compare twice (e.g. if I test for 1 <
>>>>2 I do not have another test for 2<1 {because that only finds equal which is
>>>>unlikely and therefore a mostly wasted comparison}
>>>>
>>>> 1:2
>>>> / \
>>>> < / > \
>>>> / \
>>>> 2:3 1:3
>>>> / \ / \
>>>> < / > \ < / > \
>>>> / \ / \
>>>> 1,2,3 1:3 2,1,3 2:3
>>>> / \ / \
>>>> < / > \ < / > \
>>>> / \ / \
>>>> 1,3,2 3,1,2 2,3,1 3,2,1
>>>
>>>Seems to be an hardcoded sort and indeed worth trying!!
>>>Maybe writing it immediatly in assembly will gain an extra kind of speed.
>>>Did you btw. run an profile lately on the source of Crafty 16.19?
>>>I'm wondering which source has to be analyzed to gain an extra speed.
>>>
>>>MichelLangeveld
>>
>>
>>Evaluate() and its children use more CPU time than everything else put
>>together in normal positions. IE > 50% of total time is spent in the
>>various Evaluation() functions.
>
>This Is what I thought also but I can remember from my latest profiler results
>that evaluate was _not_ that most costing function. I shall recheck this...
>
>Btw. (Same other point in the source) The book.c source is awfull... The only
>good thing about it now is that is is tested on multi platforms and that is
>works.. But I'm sure generating a book can be done in a more smarter form then
>generating all kind of tempory files. I hate also the giant malloc on line 864.
>
>
>Maybe a inserting with using a arching the book binary can clean much of the
>code and make it easily understandable. Since the makefile.nt works perfect for
>my I'm trying to changing things now in a good way at the moment... I shall give
>you all the modifications when the appear to better/faster/etc.
>
>I'm almost ready with stuffing all book positions to an epd file. So when
>generating a book simultaneasly and epd file is created of all positions in the
>book. This was only maybe 10 lines of adding code...
>
>Michel
1. don't run tactical tests. Material imbalance lets the lazy eval work very
well and cuts this way down.
2. be sure you add _all_ the Evaluate*() times, as there are several modules
in the evaluate family... all added together in normal positions should be 50%
or more...
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.