Author: Omid David Tabibi
Date: 13:10:12 04/13/04
Go up one level in this thread
On April 13, 2004 at 14:11:04, Christophe Theron wrote:
>On April 13, 2004 at 09:26:54, Vincent Diepeveen wrote:
>
>>On April 12, 2004 at 14:45:28, Christophe Theron wrote:
>>
>>>On April 12, 2004 at 07:50:47, Tord Romstad wrote:
>>>
>>>>On April 12, 2004 at 00:09:48, Christophe Theron wrote:
>>>>
>>>>>On April 11, 2004 at 13:52:59, Tom Likens wrote:
>>>>>
>>>>>>On April 10, 2004 at 21:53:17, Christophe Theron wrote:
>>>>>>
>>>>>>>On April 10, 2004 at 15:55:17, Tom Likens wrote:
>>>>>>>>
>>>>>>>>I'm not sure where I come down on the bitboards vs. non-bitboard
>>>>>>>>architectures. My engine is a bitboard engine, but that doesn't
>>>>>>>>necessarily mean that the next one will be bitboard based.
>>>>>>>>
>>>>>>>>I don't believe though, that because no bitboarder has topped the
>>>>>>>>SSDF list that this really constitutes any kind of proof. My strong
>>>>>>>>suspicion is that if all the top commercial programmers converted
>>>>>>>>over to bitboards tomorrow (yourself included) that *eventually*
>>>>>>>>their new engines would again rise to the top of the SSDF. I'm
>>>>>>>>beginning to suspect that creating a strong (i.e. world-class) engine
>>>>>>>>involves a helluva lot more than just the basic data representation,
>>>>>>>>but instead involves...
>>>>>>>>
>>>>>>>>1. 24/7 dedication
>>>>>>>>2. A *real* way to measure progress
>>>>>>>>3. A selective search strategy that works 99.99999% of the time
>>>>>>>>4. Attention to about 2^64 minor details
>>>>>>>>5. A failed marriage (okay, maybe this is extreme but you see the point)
>>>>>>>>
>>>>>>>>regards,
>>>>>>>>--tom
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>Number 5 (or something close) was the reason why Tiger has made such a progress
>>>>>>>between 1997 and 1999. :)
>>>>>>>
>>>>>>>Number 2, seriously, is worth spending several months on it.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Christophe
>>>>>>
>>>>>>This has been my main focus over the past few weeks. It's become readily
>>>>>>apparent to me that the improvement slope from here on up is much steeper
>>>>>>and I rather not waste my time implementing features that I can't properly
>>>>>>test.
>>>>>>
>>>>>>regards,
>>>>>>--tom
>>>>>
>>>>>
>>>>>
>>>>>That's the secret of real professional chess programmers.
>>>>
>>>>Of course you don't want to reveal your secrets, but it would be interesting if
>>>>you could answer
>>>>the following question:
>>>>
>>>>Assume that you make a change to your engine which improves the playing strength
>>>>by
>>>>about 10 Elo points. How many hours of CPU time do you need before you are sure
>>>>that
>>>>the change was an improvement?
>>>>
>>>>Tord
>>>
>>>
>>>
>>>I would say approximately one week, and I would not even be really sure it is an
>>>improvement. We are talking about a 1.5% improvement in winning percentage here,
>>
>>That's very quick. I remember 1 test of diep which took 3 months to get tested
>>by Jan Louwman. 1000 games in total. About 500 for version A and about 500 for
>>version B. Level 40 in 2.
>>
>>>it's below the statistical noise of a several hundreds games match if you want
>>>95% reliability!
>>
>>>And unfortunately a 10 elo points improvement is becoming rare for me. Most of
>>>the changes I try make the program weaker, and many changes do not provide any
>>>measurable improvement!
>>
>>Another sneaky problem is that if you try to modify some behaviours of your
>>program, it first will score less until everything is retuned.
>>
>>>That's why not having a strong test methodology is totally out of question if
>>>you are serious about chess programming.
>>
>>I agree here with you.
>>
>>At the same time mentionning that a good test methodology has its limitations
>>too. If you just believe the tests without taking into account other factors
>>then it is a wrong concept too.
>>
>>Note that diep can use some testing, nothing is done systematic currently and
>>the number of testgames can be counted at 1 hand a day, if there is anything to
>>report at all ;)
>>
>>>Even with a good test methodology chess programming is still an art: in many
>>>cases you have to decide with your feelings, because the raw data does not give
>>>you a definite answer.
>>>
>>>Now of course there are small improvements that I do not even need to test for a
>>>long time: if I find a way to make my program 10% faster without changing the
>>>shape of the tree, then all I need to do is run some safety tests that will only
>>>look at the number of nodes searched on a large set of positions and compare it
>>>to the last stable version.
>>
>>Let's discuss that "without changing the shape of the tree". I suspect you mean
>>by that forward pruning.
>
>
>
>As Uri as pointed out, not changing the shape of the tree means to search
>exactly the same tree.
>
>Any kind of pruning, different extension scheme or even changing the evaluation
>changes the shape of the tree.
>
>I was talking about searching the same tree, but faster because of some speed
>optimization.
>
>
>
>
>>So far tests have convincingly showed (take the 1000 games of Louwman) that not
>>a single forward pruning experiment tried so far for DIEP has resulted in better
>>play.
>>
>>There is 1 week to go to now to the ict4 and i see that i can possibly win 1500
>>dollars. Now the problem is this time no good hardware for DIEP so i'll have to
>>find some spectacular improvements in DIEP in order to win that price :)
>>
>>Now i decided that forward pruning in the entire tree (i do not see nullmove as
>>a problem by the way) that so far all those experiments failed for DIEP.
>>
>>Plydepthleft 3 to 4 in DIEP i do next type of nullmove:
>>
>> score = -qsearch( .. );
>>
>> if( score >= beta ) return score;
>>
>>Of course as already explained it's not implemented like this because i'm
>>non-recursive, but it very well describes the rudeness in which i do things.
>
>
>
>Do I understand your code correctly? You are not doing any null move before
>calling qsearch, right?
No, he is doing normal null-move pruning. Take a look at the standard null-move
pruning pseudo-code:
int search (alpha, beta, depth) {
if (depth <= 0)
return evaluate(); /* in practice, quiescence() is called here */
/* conduct a null-move search if it is legal and desired */
if (!in_check() && null_ok()) {
make_null_move();
/* null-move search with minimal window around beta */
value = -search(-beta, -beta + 1, depth - R - 1);
if (value >= beta) /* cutoff in case of fail-high */
return value;
}
/* continue regular NegaScout/PVS search */
. . .
}
The line that calls the null-move search is:
value = -search(-beta, -beta + 1, depth - R - 1);
which means that the last parameter (depth) will be 0 if:
depth <= R + 1
Vincent is using R = 3, so his code is:
value = -search(-beta, -beta + 1, depth - 4);
which means that whenever depth <= 4, he is calling the null-move search with
depth = 0, which is in fact a direct call to quiescence.
>
>You call qsearch (a capture-only search, maybe throwing in some checking moves)
>instead of doing a normal (full-width) search.
>
>I don't remember having ever tried to do that.
>
>At first sight, I don't think this will be very efficient. If a capture move is
>to fail high, it is going to fail high very quickly anyway because most chess
>programs try captures first. So I don't think you will get a huge speedup from
>this.
>
>On the other hand, you are clearly going to miss many 4 plies tactical shots at
>the end of the tree.
>
>Have you tested this system thoroughly? Does it really give an improvement over
>a non-pruning version?
>
>Or maybe I don't understand and you do a null-move before calling qsearch, and
>in this case it's not really different than having a null-move search with R=3.
>
>
>
>
>>Measuring my tree i see that the vaste majority of nodes searched by diep are
>>qsearch nodes. About 80% of all nodes are in qsearch.
>>
>>I'm interested now in redoing a forward pruning experiment.
>>
>>The current thought is to forward prune at the last ply. So i try to select a
>>few moves there and play them.
>>
>>Now of course the amount of pruning is dependant upon how many moves you try
>>there.
>>
>>Yet i'm wondering what i can potentially win in search depth just weeding in
>>that last ply.
>>
>>What is your estimate?
>
>
>
>I guess you can get a 10 to 20% speedup of your search (searching 10 to 20% less
>nodes overall).
>
>You will not get an additional ply of search from this. Maybe 0.2 or 0.3 plies.
>
>
>
>
> Christophe
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.