Computer Chess Club Archives


Search

Terms

Messages

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

Author: Christophe Theron

Date: 18:15:31 04/29/04

Go up one level in this thread


On April 28, 2004 at 14:49:47, Uri Blass wrote:

>On April 28, 2004 at 10:50:35, Vincent Diepeveen wrote:
>
>>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
>>>>>>>>>>>>>>>>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.
>>>>
>>>>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
>>>something.
>>>
>>>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
>>it.



Well I happen to have done exactly that, so maybe I can comment.

Chess Tiger for 68K-based PalmOS devices is stronger than the version of Genius
you are talking about. Genius had been designed for this processor (Motorola
68000), when Chess Tiger for Palm is just a port of the PC version of the Chess
Tiger engine (not even written in assembly, it's 100% pure C).

You can do the same experiment on 386 and you will see that Tiger beats Genius
on 386. If you want to get a feel of this, just check the P90 SSDF list. They do
not have a 386 list with Tiger, but I have tried it myself. The P90 list gives a
very good indication of what happens.

So I do not know exactly what was you point, but you are definitely wrong.

...as usual. Sigh.



    Christophe





>>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.
>
>I did not talk about movei and I did not talk about older hardware than 1990.
>It is possible that Genius is better with inferior hardware than 386 but Genius
>was clearly the best for 386 and 486 when today there are better programs for
>that hardware.
>
>Uri



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