11 December 2018

Null Moves

In yesterday's post, Kasparov vs. the Early Engines, one of the encounters mentioned by GM Kasparov in his book Deep Thinking was:-

1992-12 Match vs. Fritz 2, Cologne; +26-11=3 (?)

Of the two mentions of the match in the book, the first (loc.1880 using the Kindle location attribute) starts like this:-

In 1992, I played a long casual blitz match against one of this new generation of PC programs, one that would go on to become nearly synonymous with PC chess engines. Fritz was published by ChessBase, which explains the sardonic German nickname. Its creator was a Dutchman, Frans Morsch, who had also written programs for tabletop chess machines like Mephisto. As such, he was used to having to cram tightly optimized code into very limited resources. He also helped pioneer several of the search enhancements that allowed chess machines to keep improving despite the increasing branching factor that was supposed to slow them down.

This introduction to Fritz and its search heuristics continues with a discussion of the 'null move' concept:-

One of these is worth a brief technical detour because it's an interesting example of how machine intelligence has been augmented in ways that have nothing to do with the workings of the human mind. Called the "null move" technique, it tells the engine to "pass" for one side. That is, to evaluate a position as if one player could make two moves in a row. If the position has not improved even after moving twice, then it can be assumed that the first move is a dud and can be quickly discarded from the search tree, reducing its size and making the search more efficient. Null moves were used in some of the earliest chess programs, including the Soviet Kaissa. It's elegant and a little ironic that algorithms designed on the principle of exhaustive search are augmented by being less exhaustive.

Humans use a very different heuristic when making plans. Strategic thinking requires setting long-term goals and establishing milestones along the way, leaving aside for the moment how your opponent, or business or political rivals, might respond. I can look at a position and think, "Wouldn't it be great if I could get my bishop over there, my pawn up there, and then work my queen around to join the attack." There are no calculations involved yet, only a type of strategic wish list. Only then do I begin to work out whether it's actually possible and what my opponent might do to counter it.

The first point that caught my attention here was the assertion that a null move has 'nothing to do with the workings of the human mind'. When I'm using an engine to evaluate a position, I often inject a null move to identify the opponent's threats, like threatening mate in four or threatening a Knight fork. It's a useful technique that simulates a mental process that occurs after nearly every move in a game between humans: 'What's the threat?'

The following diagram illustrates the null move at the earliest stage of the game, the start position. It shows the position arising after two possible sequences, both of which use the null move (represented by '--').

1.e4 -- 2.d4 // 1.d4 -- 2.e4

As an added bonus, the diagram shows White's main threat after both 1.e4 and 1.d4, which is to advance the other center Pawn and make a strong central position with plenty of space behind the Pawns to develop the other pieces. After either of those moves, Black's objective is to prevent White from achieving that strong center unhindered. This is the underlying idea behind many of the most common opening variations after either 1.e4 or 1.d4.

As for the last paragraph I quoted from Kasparov's book, it starts 'Humans use a very different heuristic when making plans'. In fact, this type of strategic thinking is also possible using an engine by injecting a series of null moves, thereby preventing the opponent from making any moves at all. Here's an example, again using an engine on the traditional start position:-

1.e4 -- 2.d4 -- 3.Nf3 -- 4.Bd3 -- 5.O-O -- 6.c4 -- 7.Nc3 -- 8.Re1

After that sequence of opening moves, the engine I was using gave White's position a value of +3.00. In other words, White's advantage after eight straight developing moves is nearly the same as the value of a minor piece. With a series of null moves, the engine is helping the human to answer the question, 'What's the plan?'

One concept that applies mainly to engines is called 'Null Move Pruning', which I once covered in Chess Engines : Pruning (September 2015). Even here, the concept is similar to what humans do when they avoid looking at a move because it doesn't address the main threat.

No comments: