What Will Become of Humanity?

Bobby Fischer thought that a computer becoming World Champion was possible as "it can't be as hard as getting a man on the moon".

"But I hope it doesn't happen in my lifetime!", Fischer counterpointed in his 1969 Boys Life Chess column.

Mikhail 'Iron Man' Botvinnik wanted to create an Iron Man of his own. The last chapter of his autobiography is titled: 'The Artificial Player'.

Botvinnik was an electrical engineer by trade and in January 1977 he was working with a team on a chess machine called 'Pioneer'.

'Pioneer' failed to solved Réti's classic endgame study over a two month period. However when they programmed the concept of the Rule of the Square it managed to solve it in 70 minutes. The lesson is that chess machines need some simplifying principles. A standard chess game tree has a lower bound of 10^120 possible games according to the pioneer of information theory, Claude Shannon. Calculating chess moves involves forming a tree of variations. There is not enough computing power to solve chess completely (creating a 32 piece tablebase).

Mac Hack VI was programmed in MIDAS on a PDP-6 computer. Mac Hack VI is playing in a tournament against humans (the moves were sent by teletype to the tournament site a few miles away and vice versa). January 21st, 1967. Credit: MIT and The Computer History Museum.

In order to create any machine there are three considerations (Marr's levels of analysis):

1. The purpose of the machine - (Win a chess game) (The Computational Level)

2. The algorithm that will carry out the purpose - (transform inputs to outputs) - (Input position and output best move till completion of game) (The Algorithmic Level)

3. The physical realization of the algorithm - (silicon chips etc.) (The Implementation Level)

So how do we win chess games? We play good moves. But what's a good move? One that keeps the possibility of winning to its maximum. To find the move with the maximum possibility of winning we need to consider our opponents possibilities.

This leads to the idea of the 'minimax' algorithm. A minimax algorithm seeks to find moves that maximizes our advantage and moves for the opponent that minimizes our advantage. We assume that our opponents are also using a minimax algorithm.

So we calculate our move and then we calculate our opponents response. And then we calculate our response to our opponents response and so on based on the minimax principle.

How do we know what moves should be chosen?

We need a way of assigning values to different moves. There are too many possible positions to calculate to a certain win, loss or draw. This leads to the idea of an evaluation function. The evaluation function is based on human knowledge. A basic idea for an evaluation function is counting material. If we are up a queen then the position could be labelled as '+9' to indicate we are up material. This could help us find good moves by finding moves which win material. But chess is more than just material.

So we can add other factors to the evaluation function such as piece activity, outposts etc. Piece activity could be measured by counting the squares a piece can go to for example. This would all be put together in a formula which would output a single number which outputs the position evaluation.

This is how Stockfish and all other chess engines do it. The formula involves way more details than what I mentioned but that's the basic feature. We can also use table bases to evaluate endgames perfectly.

How to optimize the search?

We need to think about how to start the search. We have to look at multiple moves, as well as all the responses to those moves and so on. But where do we start and where do we stop?

There are some neat ideas for this in chess engineering.

A chess engines can decide what move to search by first using the evaluation function on each possible move without a search. Then the engine can search in the order of evaluation, starting with the position with the best evaluation.

Chess engines can also utilize quiescence searching. That means that they would search deeper than the usual search depth when it came to lines with captures and/or forcing moves. This means that tactics can be seen more effectively which reduces blunders.

Null pruning is when we stop searching a branch of moves if the evaluation is still winning even if we give our opponent a free move. If we can pass our turn and still have a winning position then it makes sense not to look at the variation further since we know its good. This idea was implemented in the chess engine Fritz at the beginning of the 1990s which led to Fritz becoming the top ranked engine with GM level strength.

A major innovation which is used in modern chess engines is called 'alpha-beta' pruning. If one of our opponents' replies to one of our candidate moves (let's call it Move A) leads to a losing position for us, and we find we can't stop their threat on our turn then this means that the algorithm will no longer look for our opponents replies to Move A as they already have a winning continuation so it would be redundant. This reduces search time.

Mac Hack VI was the first chess engine created in 1966 and it utilized alpha-beta pruning. Mac Hack VI was about 1500 Elo. Bobby Fischer played 3 games with Mac Hack VI in 1977 at Cambridge, Massachusetts in Boston. Fischer won all the games. Here's one where he wins in 19 moves with the King's Gambit:

In 1997, Kasparov played a match sponsored by IBM with the chess engine Deep Blue. Kasparov had won against Deep Blue in an earlier match in 1996. Deep Blue combined software with hardware. 99 percent of the search was done on the hardware which had 500 parallel processors. This meant that it was easier to program Deep Blue as a purely software search can cause problems when trying to change the software, but it also makes the hardware search less flexible. A major goal was to have non-uniform search to replicate how humans spend more time on relevant moves. The Deep Blue team also wanted to have a good depth of search in their lines to avoid blunders or errors. The Chess Chips were what did the searching. It contained a move generator, an evaluation function and a search control.

Deep Blue. Source: https://phamoxtech.com/ibm-deep-blue/

Kasparov won Game 1. In Game 2, Kasparov gave himself a passive position as Black in the Ruy Lopez. He thought that computers couldn't play closed positions.

Deep Blue rightfully smacked him down. Kasparov cried foul at the moves 36.axb5 and 37.Be4. Apparently they were too 'human', he thought that the computer would go for extra material instead of protecting their king against counterplay.

Games 3-5 were draws. Kasparov also thought that computers valued material too much. In Game 6 he played a bad Caro-Kann opening move (7.h6). He thought Deep Blue would never play (8.Nxe6) as computers couldn't see long term positional compensation for a sacrificed piece. He thought that computers had to calculate to a forced win.

Deep Blue played Nxe6.

Kasparov's position was mutilated and ripped apart in ten more moves.

Image taken on move 10. Kasparov resigned on move 19.

Kasparov's defeat to the robotic mind of Deep Blue was hailed as the triumph of the machines.

Korchnoi smacked down Kasparov saying no one asked him to represent humanity and no one asked him to lose.

Fischer probably thought Kasparov's games were 'a disgrace to the human race' (that's how he referred to a human amateur who lost to a computer in his 1969 Boy's Life Chess column).

One of the main reasons Kasparov lost was because of his misguided assumptions about computer chess as well as his belief that IBM and the Deep Blue team were cheating against him with a human. In his book Deep Thinking he writes: "I was wrong and owe the Deep Blue team an apology."

On a 2016 podcast Kasparov says: "While writing the book I did a lot of research – analysing the games with modern computers, also soul-searching – and I changed my conclusions. I am not writing any love letters to IBM, by my respect for the Deep Blue team went up, and my opinion of my own play, and Deep Blue's play, went down. Today you can buy a chess engine for your laptop that will beat Deep Blue quite easily."

A chess engine had now defeated a World Champion. And they kept getting stronger. We all know Stockfish. As it is a open-source chess engine this allowed it to have many helpful modifications. One example is iterative deepening where Stockfish increases the search depth of the game tree incrementally which allows more relevant branches to be searched. Stockfish also uses an algorithm which prioritizes using its least valuable piece to capture the opponents most valuable piece when looking at move captures. Stockfish took the throne as the platinum hero of chess in 2008.

AlphaZero was the first chess engine to utilize neural networks. Neural networks are the basis for what we call 'AI' nowadays, even though AI already existed before neural nets. A neural net involves a input layer, hidden layers and an output layer. The input layer would take the chess position, the hidden layers would perform the computation and the output layer would give the chosen move and its probability. So the classic evaluation function is not used.

AlphaZero defeated Stockfish in a match in 2017. The version of Stockfish used was an older version which did not have its conditions optimized like being allowed to spend different times on different moves. But it was a proof of concept that neural nets were very efficient at playing chess. Neural nets can produce results through reinforcement learning. AlphaZero played chess with itself and was reinforced to play moves which led to victory which made it stronger. It's evaluation function was the probability percentage of winning the game.

Alpha Zero uses a Monte-Carlo Tree Search. That's a way of exploring moves based on statistics in a well defined way. Imagine a upside down tree, the current position is the root.

There are four phases:

1.Selection: From the root, the search chooses different tree branches to search which correspond to different lines.

2.Expansion: The search goes down and expands a branch to see all the different responses.

3.Simulation: This is the cool part. In order to determine whether a position is good, the search simulates games from that position with absolutely random moves. The point is over time, taking the average results of those random games will give you a probability indicator of how good the position is. If you have a winning position and both sides play absolutely randomly, the losing side may win occasionally. But on average the winning side will have a much greater win rate.

4.Backpropagation: The statistics of the simulation get sent back from the tree branches to the root nodes (roots of the upside down tree), this updates the system so that in the future, the selection will be more efficient. So this is a self-reinforcing system.

Leela Chess Zero was another chess engine which emerged, using neural networks inspired by AlphaZero. In 2020, Stockfish combined its alpha-beta pruning with neural networks to make it even stronger. It uses neural networks in balanced positions and uses the classic search in positions with an advantage.

Leela's hopes of taking the virtual crown were pixelated into nothingness. The current version of Stockfish would dismantle AlphaZero.

Epilogue

Kasparov was transfixed by a red light that was beaming through his retina and into his brain. There seemed to be a chess set in front of him. The engineer seemed to move the pieces for a machine. A cell assembly of 'A Space Odyssey' and a cell assembly of the 1997 Deep Blue match merged in an unfathomable synchrony.

Kasparov's seat seemed to eject forcefully like a tape cassette from a VCR. Kasparov was simply a pawn in this sick game. The 'engineer' wasn't human, it had an interface which made Kasparov's mind 'crack'. He felt a tug of gravitational force and saw his vision pull back like a dolly zoom in a Hitchcock movie.

They say that the exposure to the vacuum of space makes your blood literally boil. They say your eyes become bloodshot. They say no one can hear you scream.

Suddenly, the dream and its memory vanished into the deep blue. Kasparov wakes up: it's 12 p.m. He needs to be ready to give another corporate talk about 'how the machines can work together with the humans'.

A single tear rolls down his face. He doesn't know why.

Sources

• Bobby Fischer vs Mac Hack VI 1977 Games
• Garry Kasparov vs Deep Blue 1997 Games
• Bobby Fischer, Boys Life, 1969
• Mikhail Botvinnik, Achieving The Aim, 1981
• Artturi Siven, Systematic Analysis of the Evolution of Chess Computers, 2024
• Rebecca Perry, MacHack VI: Computer chess and the roots of AI, 2020
• Feng-hsiung Hsu, IBM’S Deep Blue Chess Grandmaster Chips, 1999
• Campbell, Hoane Jr., Hsu, Deep Blue, 2001
• Feng-hsiung Hsu, Behind Deep Blue, 2002
• Garry Kasparov vs Deep Blue, Wikipedia
• Stockfish NNUE, Chess Programming Wiki
• AlphaZero, Wikipedia
• Silver et al., Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm, 2017
• Monte-Carlo Tree Search, Chess Programming Wiki

---

Visit Blog Creators Hangout for more featured blogs.