Author: Robert Hyatt
Date: 07:08:51 10/30/99
Go up one level in this thread
On October 30, 1999 at 06:24:46, Ed Schröder wrote:
>>Posted by Heiko Mikala on October 29, 1999 at 17:54:08:
>>
>>Hello Ed!
>
>Hi,
>
>
>>>The first program who had null-move (in the it is used now!) was the one
>>>of Don Beal during the WCC Cologne 1986, I remember it very well. And that
>>>moment Don had null-move only in Q-search. After Cologne his article
>>>"Selective Search without tears" came.
>>>
>>>Frans Morsch immediately fell in love with null-move after Cologne 1986
>>>because of this talks with Don. In that time Frans and I almost daily phoned
>>>each other to discuss computer chess programming and exchanged many ideas. I
>>>decided not to use null-move, Frans did, you can see the result in Fritz.
>>>
>>>Then after some years the Donninger null-move article came in the ICCA, I
>>>forgot about the year, maybe someone can have a look, and the ball got
>>>rolling. I clearly remember the heated discussions in RGCC in 1995. From
>>>that moment on null-move (using it as selective search) became kind of
>>>standard in chess programs.
>>>
>>>Frans Morsch and Chrilly Donninger gave you null-move in the way it is used
>>>now in chess programs. There is no single doubt on that.
>>>
>>
>>No Ed, this is not true.
>>
>>I have been using Null-Move in my own program for many years, long before I
>>heard that Chrilly Donninger had published something about it. Even long
>>before I heard the name Donninger for the first time.
>>
>>I have been writing on my own chess program for more than ten years, only as a
>>hobby. I do not fully remember, when I used null move for the first time
>>(would have to search through my old sources which I hope I still have somewhere -
>>and hopefully not on a 5.25 disk ;-), but for a very long time I used Null-Move
>>with a depth reduction of 1 and non-recursive, because r=2 and recursive would have
>>killed me on the 80286/80386 computers. But I already knew about r=2 and
>>recursive Null-Move.
>>
>>Now here comes something interesting for this debate. In the early days of my
>>chess program I started to make comments on top of my sources, mentioning from
>>where I got my ideas (just like Bob does in Crafty). Unfortunately I stopped
>>that, but fortunately this is the start of the comment in my search-function
>>code:
>>
>>/****************************************************************************/
>>/* Bibliographie: */
>>/* ============== */
>>/* */
>>/* - NULL-MOVE Heuristik: */
>>/* -------------------- */
>>/* "Experiments with the Null-Move Heuristic", G.Goetsch, M.S.Campbell */
>>/* in: 'Computers, Chess, and Cognition' von Marsland/Schaeffer */
>>/* S.159-168, Springer Verlag, (1990) */
>>/* */
>>/* - PVS (minimal window Principal Variation Search) */
>>/* ------------------------------------------------------------ */
>>/* "Computer Chess Methods", T.A. Marsland */
>
>>/* in: 'Encyclopedia of Artificial Intelligence', Vol.1 */
>>/* S.159-171, (1987) - PVS: S.162/163 ("minimal window search") */
>>
>>So I got my ideas from Goetsch and Campbell, from reading the book "Computers,
>>Chess and Cognition" which was published in 1990. I have it right here in my
>>hands, and it says on the bottom of page 159: "An earlier version of this
>>chapter appeared in the 1988 AAAI Spring Symposium Proceedings, pp. 14-18"
>
>I have the same book only that I will have a hard time to find it :-)
>
>The best book I have ever seen BTW for computer chess programmers.
>
>
>>One more point (hey Bob, don't you remember this?!?): In the same book
>>there is an article about Cray Blitz, pp. 111-130, and starting on page 112 there is a
>>paragraph called "7.2.2.1 Null Move". It describes the null-move in exactly
>>the same way as it is used today!
>
>I disagree.
>
>What Bob describes over there is the OLD (original) approach of null-move see
>my other posting on this topic. It is only about pruning on ply-1 situations.
>
>Nowadays null-move is done in the whole tree, quite a difference.
>
>Am I wrong about this?
>
Very definitely wrong. Let me give you the complete details:
Cray Blitz (late 80's) used a null-move search, where a null-move could be
played _one_ time in a single path. (this is called non-recursive null-move
search since only one null move is allowed anywhere between the root and the
tip.) I (and Campbell) also tried recursive null-move, which would allow
multiple null-moves anywhere in the path (as we do today) but I could only
test this on slow hardware (a Vax) and the 5 ply searches it could do really
suffered to horizon effects dealing with mate threats, just like today's null-
move programs suffer if the depth is limited or the time is short enough).
I also (as did Campbell) try R=2 but at those speeds (It turns out it would have
worked fine on the Cray since we were doing 9-10 plies then and we would have
been maybe 50 or so points stronger based on testing on today's hardware which
is fairly close to the 1988 hardware speed of CB) on the Vax, R=2 seemed to be
terribly risky and lost more than it gained.
Today I am using a dynamic null-move R factor, R=3 close to the root, R=2 closer
to the tips. I use recursive null-move, but don't allow two null-moves in a
row.
The main difference between what I do now and what I did then was that in 1988
I wasn't doing recursive null-move, and in 1988 I used R=1. But I (and
Campbell) had tested with code _identical_ to what I use today.
>
>>I may well have learned about the null-move before this book was published,
>>because at that time I used to spend hours in our Universities library,
>>searching through all the artificial intelligence journals and books I
>>could get my hands on, to find some more informations about chess programming (it was
>>really hard at that time to find informations about chess programming - but
>>I'm >sure you know that even better than I do :-)
>>
>>About Frans Morsch: He may well have been the first one, who used null-move
>>succcessfully in a commercial program. I bought Fritz 1.0 when it came out
>>(still a dos-program then of course, and sold by a company called "boeder" at
>>that time, not chessbase) and still have it on my hard disk, so I just had a
>>look and it is dated from 1991. I do remember that everyone wondered at that
>>time how a chess program can be so fast and reach such deep search depths
>>at the hardware that was used in these days. I guess he was already using
>>null-move at that time, but at least I'm pretty sure that he used it in Fritz 2 which was
>>again a bit faster IIRC. But there were others who used it earlier or at least
>>at the same time as Frans. Not only Don Beal.
>
>Sure.
>
>And good to know too.
>
>But think of this, I knew about the power of null-move all the time. It's a
>very safe (and relative safe) way of doing selective search if you are able
>to solve a few negative side effects of null-move.
>
>Then when I read the Donninger article in the ICCA journal I immediately
>recognized (and concluded) that this article had the power to come a lot
>closer in playing strength to the so-called commercials if the information
>was judged well. Apparently programmers judged well :-)
>
>The Donninger article was one of the "turning points" in computer chess. I
>repeat it again, after that the "null-move" ball got rolling. I point to the
>huge RGCC discussions in 1995. After that (almost) everybody implemented
>null-move in the way it is used today.
>
Go back to a 1990 ACM computer chess bulletin and note how many programs used
null-move. It was already very common. I'll post a list on Monday as I have
all of the ACM event publicity bulletins in a file in my office. In 1990 it
had become a non-novelty (tournament applications at one point even asked
null-move (Y/N)) when asking for details about an entrant. By 1995 it wasn't
being asked. In fact, 1995 was the _last_ ACM event ever held. And the list
of programs using null-move was already signficant before the JICCA article was
published.
>Null-move has been evolved from a simple bright idea to one of the most
>powerful ideas (and development) in computer chess. The origin of null-move
>is maybe not from commercials but the final evolution is.
>
I don't see how you can say that. The current 'evolution' was in place and
documented in 1988. And used in HiTech for (Campbell). Larry Kaufman already
had used it, and had test positions to rate a chess program (the infamous CCR
tests). He could look at the depth you found a solution and tell you whether
you used R=1, R=2, recursive, non-recursive, etc. It was already well-known.
>
>>By the way, thanks for your development of Rebel. I love it!
>
>Me too, I am a big fan myself :-)
>
>Thanks!
>
>Ed
>
>>Greetings,
>>
>>Heiko.
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.