AN ANALYSIS OF CHESS ENGINES AND ALPHA ZERO

      No Comments on AN ANALYSIS OF CHESS ENGINES AND ALPHA ZERO

MAN VS MACHINE

Machines that could play chess or “chess engines”, as they are commonly referred to have been around for a while but haven’t been taken seriously until the late 90’s. It was the year 1997 was when the famous match between then world chess champion Garry Kasparov and the IBM supercomputer called “Deep Blue” took place. The supercomputer was victorious which changed the way chess was played. Since then chess engines have performed at a level completely unmatched by humans.

Current world champion Magnus Carlsen once said “Engines are like really dumb savants that beat you every time.” This statement is pretty accurate when it comes to describing most current chess engines. They don’t know what chess is and they don’t realize that they are playing a game and yet they still win. How? In the next section this question will be answered and we will introduce the AI that was able to beat these engines with surprisingly “human like” play.

CHESS ENGINES AND HOW THEY WORK

Chess engines are simultaneously very simple and very complex. A modest explanation of how they work is that these programs use a decision tree to calculate moves into the future. The root of the tree is the current position and has a child node for each position that can be made by making a legal move. Each of these nodes in turn has a child node for various positions that can be reached by making a legal move from the current position. The number of “branches” of this tree is determined by the depth of the tree and is in turn determined by the capabilities of the engine and also how much time the system has to “think”. An analysis with a depth of 30 would yield higher level play than a depth of 10 but would also require a bit more time to calculate.

BRANCHING

After all the branches of this tree are formed the engine has to weigh the value of all the possibilities that are governed by a specific set of rules which in this case have to do with finding the absolute best move in every position or a move that will give the computer a superior position. Certain branches of the tree that don’t fit the criteria (bad moves) must be eliminated until only one move remains. This is the move that the computer will make. This entire process takes place in mere seconds and current engines are capable of evaluating millions of positions during this short period of time.

The approach described above is only possible if the engines are governed by very specific rules. In order to choose the best possible move for each position the computer must have very specific ways to evaluate whether it is winning or losing. There are a few ways in which they accomplish this.

chess

The above graphic illustrates what goes on inside a decision tree.

EVALUATION

First, each piece is given a numerical value, pawns are worth 1 point, minor pieces such as the knight and bishop are worth 3 points, rooks are worth 5 points, and the queen is worth 9 points. This system allows the computer to quickly figure out if a position is winning or losing based on how many pieces each player still has on the board. This makes engines extremely good at calculating variations that lead to winning material (capturing pieces).

There is more to evaluation than the value of the individual pieces. The computer also has to figure out which series of moves are worth calculating as its impossible for even a computer to calculate every single possibility because there are simply too many. Therefore, these computers are programmed to completely disregard entire lines of thought if it doesn’t lead to a win despite any material that is gained or lost. This is known as heuristics. The word heuristic refers to an approach to problem solving that employs a practical method that doesn’t have to be perfect as long as it achieves the desired goal.

THE END RESULT

After all is said and done the computer is able to assign a numerical value to entire positions on the board which is how it determines which side is winning, this evaluation is based on all the rules described above and the various heuristics programmed into it. These programs, however, are not artificially intelligent entities, they are merely powerful calculators that calculate moves into the future with a brute force algorithm which is incapable of taking into consideration long term abstract positional ideas that go beyond the simple evaluation these programs employ.

For example, a bishop may be worth 3 points but an extremely strong bishop that is placed on a powerful square is realistically worth much more. The computer is incapable of such abstract thought which is its biggest weakness. Some of the greatest human chess players in history have won by utilizing a style which employs this kind of thinking which is referred to as “positional play” in the chess world.

ALPHA ZERO

The problem is the humans just aren’t good enough to compete with engines anymore, because they are just too sophisticated with their calculations. Recently though, an AI was created called Alpha Zero. This AI was created by a small company called DeepMind which was recently bought out by Google. Alpha Zero was only given the rules of chess and 4 hours to play games against itself in order to learn. After that, it played a match against the best chess engine Stockfish in late 2017. The result of this match was rather interesting. First though, we will briefly touch on how Alpha Zero works.

HOW IT WORKS

Alpha Zero played millions of games against itself by making random moves and over time it learned that the winning side obviously had done something right while the losing side had obviously done something wrong. During the match it played against Stockfish the chess engine examined over 70 million positions per second while Alpha Zero only examined 80,000 per second. Since stronger players tend to calculate fewer variations than weaker ones because their highly honed intuition guides them this highlights the fact that Alpha Zero was able to teach itself to play chess exactly the way a human would which has never been done before.

We already explained how chess engines “think”. Alpha Zero has a much different method. It uses what is referred to as Monte Carlo Tree Search or MCTS for short. An engine using pure MCTS would evaluate a position by generating a number of move sequences (called “playouts”) from that position randomly, and averaging the final scores (win/draw/loss) that they yield. This approach may seem altogether too simple, but ultimately it is superior to the evaluation system of a typical engine so long as the level of accuracy and performance is high enough to win out against the brute force calculations of the engine. Alpha Zero also has a very sophisticated neural network that evaluates positions in a more abstract way compared to typical chess engines.

THE MATCH

In 100 games from the normal starting position AlphaZero won 25 games as White, won 3 as Black, and drew the remaining 72, with 0 losses. This result shocked the chess community as no one believed that an AI could possibly teach itself to beat Stockfish in only a few hours. The Stockfish developers were very quick to clarify some things though. The results of this match have given us a few things to ponder.

In response to this, Stockfish developer Tord Romstad commented, “The match results by themselves are not particularly meaningful because of the rather strange choice of time controls and Stockfish parameter settings. The games were played at a fixed time of 1 minute per move, which means that Stockfish has no use of its time management heuristics (lots of effort has been put into making Stockfish identify critical points in the game and decide when to spend some extra time on a move; at a fixed time per move, the strength will suffer significantly). I believe the percentage of draws would have been much higher in a match with more normal conditions.”

Grandmaster Hikaru Nakamura also showed skepticism of the significance of the outcome, stating “I don’t necessarily put a lot of credibility in the results simply because my understanding is that AlphaZero is basically using the Google super computer and Stockfish doesn’t run on that hardware; Stockfish was basically running on what would be my laptop. If you wanna have a match that’s comparable you have to have Stockfish running on a super computer as well.”

The video above is one of the games in the match in which Alpha Zero completely paralyzes Stockfish’s position and wins decisively. However, pay close attention to the 10:20 mark in the video when Stockfish plays that Queen to h8 move that seemingly seals its fate. The engine is incapable of understanding placing your queen in the corner where it is likely to get trapped is not a good idea because it is only calculating and nothing more. Engines are notorious for doing things like that. Stockfish evaluates that position as a dead draw. This highlights the fact that Alpha Zero has a far better understanding of long term abstract ideas than Stockfish and this is exactly why the AI won. It turns out that human like “intuition” is the best way to play chess it just took a very powerful AI to demonstrate this fact.

WERE THE RESULTS CONCLUSIVE?

Despite the arguments presented by the Stockfish developer and the concerns raised by Hikaru Nakamura Alpha Zero won the match decisively and fairly. The Stockfish developers simply had to do some damage control after they lost. The points that are raised against this conclusion and the effects they had on the outcome are minimal at best. It is certainly possible though that these conditions were rigged by Google to favor Alpha Zero in order to ensure it won for marketing purposes but the fact of the matter is even if Stockfish was running on faster hardware it might not have lost by as large of a margin but it probably still would have lost given the fact that its decision tree is no match for the neural network utilized by Alpha Zero. What do you think? Leave your comments down below.

Leave a Reply

Your email address will not be published. Required fields are marked *