Computer Chess Club Archives




Subject: Re: Beating MTD(n,f)

Author: Miguel A. Ballicora

Date: 08:08:04 06/08/01

Go up one level in this thread

On June 08, 2001 at 06:45:40, Tony Werten wrote:

>On June 08, 2001 at 05:06:25, Dan Newman wrote:
>>On June 08, 2001 at 03:44:44, Tony Werten wrote:
>>>On June 07, 2001 at 16:04:49, Dann Corbit wrote:
>>>>On June 07, 2001 at 06:52:07, Tony Werten wrote:
>>>>>On June 06, 2001 at 10:32:14, Gian-Carlo Pascutto wrote:
>>>>>>On June 06, 2001 at 09:06:40, Vincent Diepeveen wrote:
>>>>>>>Noop it doesn't make it void.
>>>>>>>To get from 100 to 200 is harder as it is to get from 10 to 20.
>>>>>>If they mean the same thing, not at all.
>>>>>>Note that I said you should be taking convergence acceletrators
>>>>>>into account. Every competetive implementation of MTD(n,f) has
>>>>>>them and the papers suggest them so that is a valid requirement.
>>>>>>If you increase the window forecefull from 100 to 200 when you
>>>>>>are using millipawns it's the exact same thing as increasing it
>>>>>>from 10 to 20 when you are using centipawns.
>>>>>>If you rely purely on the fail-soft and do not adjust the bounds
>>>>>>with the accelerators, I think you are right, but I really would
>>>>>>like to see evidence of it. When forcing the bounds it's just the
>>>>>>same thing however, and that is what every good MTD(n,f) implementation
>>>>>>is doing.
>>>>>>You are basically saying that the difference between 0.1 and 0.2
>>>>>>is different from that between 0.1 and 0.2. No it's not :)
>>>>>I think what Vincent is saying is that there's a difference between 0.1 and 0.2
>>>>>and 0.10 and 0.20 The first 2 are following each other while the second 2 have 9
>>>>>numbers between them.
>>>>>Suppose the current score is 0.10 Now I find a move with score 0.12 MTD will
>>>>>fail and I have to research. If I had scored 0.1 then the new move would have
>>>>>also been 0.1 and MTD wouldn't have to research.
>>>>>Of course is this not only true for MTD, but for all minimum window searches,
>>>>>but in MTD the first (best) move is also done with mws and this is most of the
>>>>>time the one that has the fluctuating scores.
>>>>I imagine that this is a stupid question, but what happens if we simply truncate
>>>>on the test to research?  We could just reorder the moves at that point instead,
>>>>if the difference is tiny.
>>>Not a stupid question.
>>>I was thinking about something like this. If I have time I'll test this weekend.
>>>( I'm messing with my code to get out the bugs )
>>>My idea is this: I like the millipawn stuff, because I can give small bonusses
>>>to things I like ( not nescessairily correct ). When I return from the
>>>evaluation I could divide it with 10, 100 or whatever. This would mean the
>>>millipawn stuff still works (since 10 millipawns is still 1 centipawn ) but my
>>>search might have more cutoffs.
>>>PS About my code. I found out that if I take a testposition and I mirror it, I
>>>get a different solutiontime ( even with material only eval ) I think it's in
>>>the extension discision part.
>>>Others might try if their engine doesn't have this problem.
>>The hash table can do this to you.  Even if all your code is mirror imaged
>>for black and white, if you use random numbers for the hash table, then
>>overwriting of positions will differ in the two cases, and the solution
>>times (node counts) will vary.  In my code I would get this effect even
>>without the hash because my move generator generates moves for black and
>>white in different orders for mirrored positions...
>I don't use random numbers, but I think you have the point.
>At the start I scan the board to fill my piece arrays. I do this from downleft
>to upright. If I mirror then 2 equal pieces will be in different order, so
>moveorder will change so nodecount will change.
>Sounds logic.

This is a perfectly normal behavior even without hashtables!
Mirroring the position could create a slightly different move ordering.
For instance, when you determine what move you are going to pick, if
there are moves that are exactly the same (i.e. no captures, no killers
etc) you pick the one that is generated first.
For instance, you start from the ones that have a lower rank, so for White
it would be Kb2-a1 but if you mirror that it would be Kb7-a6 which is
not the mirror move!
Of course, this could change depending how you generate the moves.


This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.