Computer Chess Club Archives




Subject: Re: When to do a null move search - an experiment

Author: Vincent Diepeveen

Date: 07:50:35 04/28/04

Go up one level in this thread

On April 28, 2004 at 06:39:30, Uri Blass wrote:

>On April 28, 2004 at 06:06:37, Vasik Rajlich wrote:
>>On April 27, 2004 at 21:05:11, Vincent Diepeveen wrote:
>>>On April 27, 2004 at 17:10:16, Dann Corbit wrote:
>>>>On April 27, 2004 at 06:10:04, Vasik Rajlich wrote:
>>>>>On April 27, 2004 at 01:38:49, Uri Blass wrote:
>>>>>>On April 27, 2004 at 00:44:34, rasjid chan wrote:
>>>>>>>On April 26, 2004 at 20:07:00, Uri Blass wrote:
>>>>>>>>On April 26, 2004 at 13:41:53, Vincent Diepeveen wrote:
>>>>>>>>>On April 26, 2004 at 12:14:33, José Carlos wrote:
>>>>>>>>>>On April 26, 2004 at 11:57:43, Vincent Diepeveen wrote:
>>>>>>>>>>>On April 26, 2004 at 11:48:35, José Carlos wrote:
>>>>>>>>>>>>On April 26, 2004 at 11:32:26, Tord Romstad wrote:
>>>>>>>>>>>>>On April 26, 2004 at 10:39:42, José Carlos wrote:
>>>>>>>>>>>>>>  An interesting experiment, of course. But I think your conditions are rather
>>>>>>>>>>>>>>different from 'most' programs. I mean:
>>>>>>>>>>>>>>  - You allow any number of null moves in a row (most programs don't do even
>>>>>>>>>>>>>This has no importance, I think.  My experience is that I almost always get the
>>>>>>>>>>>>>same score and PV when I enable/disable several null moves in a row, and that
>>>>>>>>>>>>>the difference in number of moves searched is *very* tiny.
>>>>>>>>>>>>  You're probably right, as you've tested and I speak from intuition, but at
>>>>>>>>>>>>first sight, it seems that the fact that you allow several null moves in a row
>>>>>>>>>>>>will increase your percentage of null-moves-tries/total-nodes-searched, and thus
>>>>>>>>>>>>that avoiding unnecessary null moves will be a good idea.
>>>>>>>>>>>In *all* experiments i did with nullmove and a program not using *any* forward
>>>>>>>>>>>pruning other than nullmove, the best thing was to *always* nullmove.
>>>>>>>>>>  Yes, that's what other programmers also said (including me) in the thread we
>>>>>>>>>>had last week. That's pretty intuitive. With not any other forward pruning (or
>>>>>>>>>>very little) but null move, the cost of not trying a null move that would have
>>>>>>>>>>produced a cutoff it terrible compared to the benefit of saving an useless null
>>>>>>>>>>move try. So avoid null move, in this case, must be only in a very few cases
>>>>>>>>>>where you're 99.99% certain you'll fail low... if any.
>>>>>>>>>99.99% means 1 in 10k nodes.
>>>>>>>>You can be 99.99% sure about fail low more often than 1 in 10k nodes.
>>>>>>>>>So doing nullmove always is cheaper, because in a lot of cases
>>>>>>>>>transpositiontable is doing its good job and in other cases you search more than
>>>>>>>>>10k nodes which you avoid searching now.
>>>>>>>>>>  Gothmog is very different from that 'paradigm' (he does a lot of forward
>>>>>>>>>>prunning and applies many ideas he has commented here), hence it works pretty
>>>>>>>>>>well for him.
>>>>>>>>>I get impression evaluation function plays a major role in when something is
>>>>>>>>>useful or when it isn't.
>>>>>>>>>Checks in qsearch is also a typical example of this.
>>>>>>>>>>>Double nullmove i invented to proof nullmove gives the same results like a
>>>>>>>>>>>normal fullwidth search for depth n which i may pick, and i use it as it finds
>>>>>>>>>>>zugzwangs and i am sure that is very helpful, because the weakest chain counts.
>>>>>>>>>>>So double nullmove always completely outgunned doing a single nullmove then
>>>>>>>>>>>disallowing a nullmove and then allowing the next one.
>>>>>>>>>>  I tried double null move some time ago, and it didn't work for me. Probably I
>>>>>>>>>>did something wrong, but I recall an old post (see the archives) from C. Theron
>>>>>>>>>>where he gave some points why double null move should not work. I, myself,
>>>>>>>>>>didn't invest too much time though as I had much weaker points to fix in my
>>>>>>>>>>program before.
>>>>>>>>>Christophe didn't post it doesn't work AFAIK.
>>>>>>>>>Further i must remind you that majority of commercial programmers posting here
>>>>>>>>>is not busy letting you know what works for them or doesn't work for them.
>>>>>>>>>To quote Johan: "don't inform the amateurs".
>>>>>>>>What reason do you have to tell other what works for you and what does not work
>>>>>>>>for you?
>>>>>>>>You do not plan to inform the amateurs about better code for tablebases than the
>>>>>>>>nalimov tablebases so I do not see you as a person who try to help the amateurs.
>>>>>>>>>I remember that Christophe also posted that evaluation function is not so
>>>>>>>>>His latest postings here made more sense however than the crap posted before
>>>>>>>>I understand that you claim that basically Christophe's claim that most of the
>>>>>>>>improvement in tiger came from better search and not from better evaluation was
>>>>>>>Firstly there is not that BIG a stake for disinformation and posting
>>>>>>>here is also just normal human behaviour that does not require
>>>>>>>asking "....why do I post ? ". Then also ask why do I talk.
>>>>>>>I think Christophe was quite clear about the reasons why chess programming
>>>>>>>is NOT about evaluation(not dumb evaluation). After pawn structures, passed
>>>>>>>pawns etc, it is very difficult to try to improve on it. The curve for
>>>>>>>evaluation is logarithmic for elo-increase/code-increase + huge overhead,
>>>>>>>the very reverse of exponential.Search almost have no trend patterns and
>>>>>>>search improvements usually have no overhead, you just need to be smarter
>>>>>>>then the rest. Assume your opponent searches on average 3 plys ahead.
>>>>>>>How do you do a good evaluation that can see 3 plys ahead? Evaluation is horizon
>>>>>>I did not claim that christophe claimed wrong things.
>>>>>>It is Vincent who claimed it.
>>>>>>I prefer not to talk about the top programs.
>>>>>>I can only say that it is clear for me that I can get much by search
>>>>>>Certainly searching 3 plies forward or doing something equivalent can help
>>>>>>significantly but the problem is how to do it.
>>>>>>If you are optimistic about doing it with no price by intelligent extensions and
>>>>>>and better order of moves then it is clear that going for search is the right
>>>>>>If you are not optimistic even about getting something equivalent to 1 ply
>>>>>>forward then evaluation is the right direction.
>>>>>I don't think you need objective answers to these questions.
>>>>>You just need a game plan.
>>>>>A plain, reasonably tuned eval combined with a state of the art selective search
>>>>>seems like a perfectly reasonable game plan to me.
>>>>>Ditto for plain search combined with a state-of-the art evaluation.
>>>>Bruce Moreland (who's program Ferret was at one time among the top two or three
>>>>in the world) found a great annoyance when as he improved his evaluation: he
>>>>discovered that he was then being outsearched.
>>>>I think the lesson is simple:
>>>>If your new smarter eval makes the program stronger, then keep the new
>>>>evaluation terms.  If not, rip them out.
>>>I feel search is overrated too much. It's so so hard to make a good eval, only
>>>when you have a real well tested and tuned eval making a good search is
>>>Even searching fullwidth i can beat Crafty.
>>>In fact i saw diep at a P4 2.8Ghz in blitz beat crafty at its dual Xeon lately
>>>at icc. I was pretty amazed because i always say that you need at least 12-14
>>>ply to search outside tactical barrier.
>>>Perhaps i'll change that back to 10 ply one day :)
>>Eval is hard, true. So is selective search.
>>Moreland's approach is definitely not the way to end up with a great eval. When
>>your eval is cheap, you can't just add one expensive thing to it and expect it
>>to pay off. One expensive idea might cost you 20% of your nodes. With this
>>approach, if you're testing honestly, you'll always end up throwing out the
>>expensive stuff.
>This was also my thinking in the past but I doubt it.
>If you have big stuff everything that you add cost you more than in case that
>you have small stuff.
>If you have small stuff then the program can use the fast memory when you add
>If you have big stuff it needs to use the slow memory so the theory that if you
>have a lot of knowledge you can add things with smaller price may be wrong.
>>If you want a program with a great eval, you have to commit to it, let
>>everything slow down, and go from there.
>>Another thing to keep in mind: a few years ago, it might well be the case that
>>allowing onesself to be outsearched was a death wish. This may be changing now.
>>Chess Genius dominated computer chess with a very unusual selective algorithm
>>that worked great at low depths. Eventually, it became irrelevant.
>I think that the top programs simply got better and can beat chess genius even
>if you give them the hardware that genius used to top the ssdf list.

>Chess Genius today is not the best also with 386 hardware.

386 hardware hello?

Genius basically has been put onto 680x0 dedicated machines. Millions sold from
them. The genius in software was a joke compared to that.

How are you *ever* going to beat genius with a program of today compiled for a
64KB ram + 512KB rom 68x motorola cpu 10Mhz with genius assembly optimized for

Or even worse: 4KB ram and 64KB rom. Note you also must make interface within
that memory.

Compilers have problems working within that.

In short you'll search 4 ply with movei onto that, versus 10 ply assembly
optimized genius.

Who wins?

I bet genius with 100-0.

>120/40 with 386 is like 1/40 with hardware that is 120 times faster and I do not
>see genius dominates in that time control.

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.