Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vincent Diepeveen

Date: 04:37:23 04/29/04

Go up one level in this thread


On April 28, 2004 at 14:02:38, Ed Schröder wrote:

>On April 28, 2004 at 10:41:08, Vincent Diepeveen 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
>>>>>>>>>>>>>>>two)
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>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.
>>>>>>>>>
>>>>>>>>>No
>>>>>>>>>
>>>>>>>>>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
>>>>>>>>>>important.
>>>>>>>>>>
>>>>>>>>>>His latest postings here made more sense however than the crap posted before
>>>>>>>>>>that.
>>>>>>>>>
>>>>>>>>
>>>>>>>>>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
>>>>>>>>>disinformation.
>>>>>>>>
>>>>>>>>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
>>>>>>>>dumb.
>>>>>>>>
>>>>>>>>Rasjid
>>>>>>>
>>>>>>>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
>>>>>>>improvements.
>>>>>>>
>>>>>>>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
>>>>>>>reductions
>>>>>>>and better order of moves then it is clear that going for search is the right
>>>>>>>direction.
>>>>>>>
>>>>>>>If you are not optimistic even about getting something equivalent to 1 ply
>>>>>>>forward then evaluation is the right direction.
>>>>>>>
>>>>>>>Uri
>>>>>>
>>>>>>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
>>>>important.
>>>>
>>>>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.
>>
>>The difference is that Eval brings more points. Selective search doesn't
>>(assuming you use nullmove and have a pretty efficient search, some programs we
>>cannot say that from though).
>>
>>>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.
>>
>>I'm not commenting here on Bruce in a negative sense. In the days that ferret
>>was strong, chessprograms simply didn't search deep enough yet. Around 1997 the
>>search dominated because it was hard to get > 10 ply.
>>
>>So his approach in those days made sense.
>>
>>>If you want a program with a great eval, you have to commit to it, let
>>>everything slow down, and go from there.
>>
>>Big eval also means that a lot of dubious search stuff no longer works.
>>
>>Correctness of search and worst case behaviour of forward pruning plays a big
>>role.
>>
>>>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.
>>
>>When posting in 1997 at RGCC that in the future just searching deeper wasn't
>>holy, i remember that all the internet guys were laughing loud for me (also
>>there programmers hardly posted).
>>
>>>Chess Genius dominated computer chess with a very unusual selective algorithm
>>>that worked great at low depths. Eventually, it became irrelevant. As hardware
>>>changes, all of these tradeoffs change.
>>
>>In the days that scientific programs searched at 100 nodes a second at 512
>>processors (Zugzwang), there genius was searching at a single cpu 10Mhz machine
>>already like what was it 2000 nodes a second or so?
>>
>>Of course using very dubious selective search and dubious qsearch methods.
>>
>>Even till today i do not know 100% sure what he was doing, but i know that at a
>>10Mhz machine Genius will beat diep, because diep will search 3 ply at it in C
>>and genius will get a tactical 10 ply and completely outgun it.
>>
>>Same holds true for Rebel. His dubious searching methods of course were genius
>>finds around 1991.
>>
>>This has changed however in 2004.
>
>This is all very poor Vince, I assume you don't play much with nowadays top
>programs. From 1982 to 2001 Rebel won its games by positional understanding and
>not by search and Rebel lost its games because it was outsearched. Today Rebel
>isn't outsearched at all, it now loses its games because the current top
>programs have a better positional understanding than Rebel.
>
>You should have a good look at the current tops, the positional progress has
>been great the last years. To me it all seems to indicate (provided your search
>is okay) the only way to make progress is to improve on chess knowledge. But
>what's new, I already came to that conclusion in 1986 after some intensive talks
>with Hans Berliner.

What i mean is Ed, is that you would not have accomplished the great results
with Rebel which you managed, had you just searched with a fullwidth search +
bunch of checks in qsearch.

I am under the impression that you just like diep try checks at several depths
in the qsearch. In diep i can try at the entire 32 ply of the qsearch checks.

Doing things like attacks in eval and mobility and scans for all kind of things
which are trivial for chessplayers and i do not even dare to write down the name
for here, they slow down once engine.

I would search 3 ply at 1991 hardware with it, simply because the code size is
so huge, the nps at 1991 machine (i had a 10Mhz XT at the time) would be around
a 100 nodes a second or so.

My point is would you have become world champion in 1991 searching 3 ply?

I very deliberately ask it this way, because fritz3 (1995) searching at todays
hardware handsdown would search 20 ply in any middlegame, when it would be
converted. Apart from that it single cpu would search 3.5 million nodes a second
hands down.

Todays fritz searched in 2003 world champs at a quad xeon 2.8Ghz about 13-15
ply.

The 2003 fritz at a 386 , 10Mhz would have a problem getting beyond 4 ply.

Would you beat it with Rebel-Madrid?

>My best,
>
>Ed



This page took 0.07 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.