Ghost in the Engine

Intro

Anthropomorphism is the attribution of human characteristics to things other than humans - objects, animals or algorithms and computer software. We have all seen images of building facades that seem to give sly looks. Or interpreting animal behavior way beyond their natural behavior. We even used to and sometimes still do describe cold calculated engine moves in human emotions - playing safe, risky, or plain dumb. However, engines have long overtaken humans in their chess ability so we feel less inclined to characterize their play in human terms.

More often we see phrases like a "computer move". These are moves that human intuition is very unlikely to suggest and only the greatest masters can come up with bizarre looking moves that only deep analysis can explain. Trying to explain Stockfish or Lc0 moves makes us feel tiny and dumb - so we just throw up our hands and exclaim in resignation of the futility of that task- oh, well that's just computer chess for you.

In this blog post I want to push back against the notion that computers are just cold calculators and there is a bottomless rift between the machines and us.
Having worked on my engine I have written up very strange looking algorithms. They seem nonsensical at first but dig deeper and it's the same principles we follow just formalized in code that is unrecognizable.

Null Move Pruning (NMP)

To give a little bit of context before we dive into the topic. You should be familiar with how an engine searches the game tree. I describe the basics in a previous blog post. The examples there should be illustrative but the actual trees in chess have much higher branching factor. In the diagrams I draw every positions splits into 2~3 child nodes. An honest picture would have each node have ~35 children - the average number of moves in a position. Chess engines can evaluate millions of positions per second but looking at all moves would not allow a deep search. Even if it was billions of positions per second the depth would barely budge as the number of nodes grows exponentially with depth. The only way to fight this exponential power is with heuristics that prune or reduce the depth of search, effectively reducing the branching power. So engine developers spend a lot of effort in defining logic which identifies moves that do not deserve much/any attention to be able to dive deeper into moves that are more interesting. This is a fascinating group of techniques and I hope to write more on some of them.

Null Move Pruning, also called Null Move Heuristic (NMH), is a method based on the Null Move Observation to reduce the search space by trying a "null" or "passing" move, then seeing if the score of the subtree search is still high enough to cause a beta cutoff. Nodes are saved by reducing the depth of the subtree under the null move.

This is straight from the Chess Programming Wiki. This will probably not make a lot of sense to you as it contains a lot of jargon. Let me explain the idea in a less jargon dense way. During our search we might explore various candidate moves in a position as:

1. Opponent makes a move.
 2. It's our turn to move but instead we pass.
 3. Opponent moves again and we play out a few variations of moves from there.
 4. If the opponent is not winning we conclude the first move was not a good candidate.
 5. Assume opponent will not make the first move.
 6. Abandon this sub-tree.

At this point you should understand what is going on but I would not fault you for still being puzzled as to why exactly we are doing this. It's generally understood that making a move is better than not making a move - in the opening White always is ahead because of the first move advantage. Given the opportunity to make a move we will always try to improve our position and make life harder for the opponent.

Back to our algorithm laid out before. A move should improve the position. If we let our opponent to make a move to improve their position then pass on our turn and not improving in return and then playing from there. If the opponent is unable to show enough improvement in the position we conclude that the first move was not good - it did not improve.

While convoluted I hope this at least starts to make sense. However, it sounds weird - who plays chess like that? I skip a move and tell the opponent: Come get me if you can! Nobody does that. Do they? Actually yes - we all do that all the time every move we just frame it in a different more human way. I think it is a mantra of chess educators - checks, captures, threats. When analyzing a position and looking for a move those are the candidates you should explore. In our algorithm we just formalized the notion of a threat. What is a threat in chess? It's a move that requires direct reaction to avert the threat. When you threaten checkmate, material, damaging the opponents pawn structure or gaining some other tactical or strategic advantage, what you actually mean is: give me one more move and you will be punished. So when we passed our turn to move we actually asked a very basic question - did the last move come with a threat?

Let me ask again - who plays chess and does not think about threats when looking for their own moves or does not question the play of our opponent - what is the threat? Everybody does. It is one of the most fundamental chess principles that guides the beginner and the master making every move. It's as natural as riding a bike. Once you know how to do it you barely think of it but try to explain to someone how you ride the bike and a formulaic description of everything you do to keep balance. Same with threats in chess. They are natural but when you codify it - it looks just strange.

Quiescence. That's no pawn. That's a Queen promotion!

quiescence

noun qui·​es·​cence kwī-ˈe-sən(t)s
the quality or state of being quiescent

I hate when dictionaries do this. Not helpful. Let's try again.

quiescent

adjective qui·​es·​cent kwī-ˈe-sənt
1. marked by inactivity or repose : tranquilly at rest
2. causing no trouble or symptoms

Much better. If you're a nerd then you will likely recognize my adaptation of the quote from Star Wars: New Hope. When the Millennium Falcon approaches a small moon Obi-Wan Kenobi suddenly realizes - That's no moon. It's a space station. At that point it's already too late and they are in the firm grasp of a tractor beam and in deep trouble. If only Obi could have seen a bit further, he could have averted danger.

When engines analyze a position they look at moves at a fixed depth. They reach that depth evaluate the leaf nodes for material and piece activity but they are essentially blind beyond that point. That is called the Horizon Effect.

How do engines deal with this blindness? You should be familiar with the basics of how engines search the game tree. If you need a reminder you can refer to the same blog post as above.

In that post I explained the search algorithm by the engine reaching the leaf nodes and evaluating that node with the evaluation function and that evaluation is then propagated upwards via the minimax algorithm. That's not really what happens. When the engine reaches the final depth and arrives at a leaf node it actually drops into a new search but this time it only looks at captures, checks and queen promotions.

That's not how you play chess! That's checkers? That makes no sense! Those are probably some thoughts that might have crossed your mind. And you're right at this point the engine no longer plays real chess but that's not the goal. This is called Quiescence search often shortened to q-search. So what is going on here? If you evaluate the static positions at the leaf nodes you might think you're a pawn up. Your Queen just captured a pawn. We hit the horizon of our search. We would need to go one move further to see that you actually captured a protected pawn and on the next move your Queen is lost.

So how do we battle the nemesis of horizon effect? We could search one move further. Well that solves nothing it just pushes the same problem one step further. This is exactly what q-search does. It performs a new search with unlimited depth restriction but only captures, checks and queen promotions. This is no longer chess but a sanity check - I want to count all the pawns and assess the strategic aspects on the board, but first I need to get rid of all the tactics. So it quickly plays out all the captures and gives some checks to make sure the position is quiet before taking stock of the situation. And that's exactly what it says on the tin of Quiescence search - give it any position and it will only play out tactical moves and release all the tension.

Again this seems a little weird - half way through our analysis and search we stop playing chess and finish it off with a quick game of checkers. It's not rock solid logic. However, what makes even less logical sense is grabbing a protected pawn with a Queen and doing a fist pump in celebration while clearly leaving the Queen En Prise. No human would consciously ever play such a move. We calculate at a depth according to our analysis but we never abruptly stop we attempt to do a final safety check - Is everything protected? Is everything safe? Am I getting mated here? So in the same vein as the Null Move Pruning technique. Quiescence sounds weird to us but it actually does exactly what we do instinctively in a formalized orderly fashion.

In conclusion

During my freshman physics years I was reading Richard Feynman's lectures on physics. Early on it included an anecdote between a driver and a police man giving a ticket for speeding. Their exchange was a humorous but a mathematically sound argument. "You were going 80mph in a 30mph zone." "I how can I do 80 miles I just turned out of my drive way?" "Well you were speeding because if you kept going at the same rate for an hour in a straight line you would travel 80 miles" "That's impossible the street comes to an end in a few blocks there's no way for me to go 80 miles in a straight line!". They argue back and forth until they define speed as the time derivative of position. It's a funny exchange but it's so much more. Everyone knows what speed is. Everyone can read the speedometer on their car dash. The point is that a simple concept like speed can actually become a slimy elusive eel the harder you try to grasp it. While we all have that intuition it can actually be very hard to formalize it.

In this blog post I attempted to tell a bit of a similar story. We have these machines that play chess above our comprehension. We might look at the code and the algorithms and they look alien to us. But if we deconstruct them and look at all the individual parts we can put them back together. Scary formulations of Null Move Pruning and Quiescence search become all-familiar threats and don't hang your queen.

Feynman was one of the reasons why I fell in love with physics. (Funnily enough also the reason why physics broke me - Quantum Field Theory by Feynman). Similarly I fell in love with computer chess - it can all look intimidating but once you dig deeper many of the moving parts of the engines are formulations of our own intuition. That to me will never not be magic.