Thursday, October 8, 2015

Chess engines

I find chess engines, and how they have advanced in just the last ten years, really fascinating.

In 1997 the chess computer Deep Blue gained a lot of notoriety for being the first computer to beat a world-reigning chess master, Garry Kasparov, in a tournament of several games with long time controls. (More specifically, 6 games were played, and the score was 3½–2½ in favor of the computer.)

Since then, however, chess engines have advanced in major leaps.

Note that Deep Blue was a dedicated computer for the sole purpose of playing chess. It could calculate approximately 200 million nodes (ie. chess positions) per second.

Modern top chess engines will run on a regular PC, and their calculation speed on such a PC, even when using eg. 4 cores, is less than 10 million nodes per second, only a small fraction of what Deep Blue was capable of. Yet these modern chess engines, running on a regular PC, are significantly stronger than Deep Blue was, and would easily beat it (and even the strongest chess grandmasters.)

The reason for this is that their search tree pruning and position evaluation functions (and other more minor things) have vastly improved during the last 20 years. They are capable of finding the best moves with significantly less work than Deep Blue was. (It has been estimated that even Deep Blue back in 1997 would have got something like 200 ELO points stronger with some simple modern changes in its pruning functions, which would have made it significantly stronger than Kasparov.)

Modern chess engines do indeed find very easily moves that the best chess engines of just ten years ago would have struggled with (not to talk about engines of 1997). Consider, for example, this position from game 6 of the Kasparov vs. Deep Blue tournament:

Deep Blue is playing white, and Kasparov, as black, has just played h6. What is white's best response?

h6 is, in fact, a bad move. However, seemingly Kasparov played it to try to trick Deep Blue, because the proper response is so difficult that no chess engine of the day would play it. Deep Blue played the correct move, but only because it was in its opening book, not because it calculated it by itself. No engine of the time (or probably even for ten years since) would have found the correct response on their own.

The best move is Nxe6. This is a pure knight-for-pawn sacrifice because there is no immediate regaining of the lost material. It's done purely for positional advantage. It was extremely hard for chess engines to see this move as good, because at first it seems like a pure loss of material with no apparent advantage.

Yet, if you give this position to a modern top chess engine, like Stockfish 6, to analyze (with no opening books or anything), they will find Nxe6 in less than a second.

Or consider this position from the so-called "Kasparov Immortal" game (Kasparov vs. Topalov, 1999):

Black (Topalov) has just played Qd6. What is the best response by white?

The best response by white, and what Kasparov played, is the Rxd4 sacrifice.

I watched a YouTube video something like ten years ago about this game, and the person analyzing the game said that he gave this position to one of the top chess engines of the time (I don't remember which), and it took it over an hour to find Rxd4 as the best move.

If I give that position now to Stockfish to analyze, it finds Rxd4 as the best move in less than a second.

That's not to say that modern chess engines find the solution to all possible problems so fast, even today. For example, consider this very hard and contrived problem: White to play, mate in 6:

While Stockfish extremely quickly evaluates this as being overwhelmingly favorable to white, it nevertheless takes it between 4 and 5 minutes on my computer to find the mate in 6. (Note that it's not specifically mate-searching, just analyzing the position. It might find it faster if it were set to mate-searching.)

Chess engines have become so strong that they easily beat even the strongest human players, even when run on regular PCs rather than dedicated hardware.

But this blog is about things that grind my gears. And there is one such thing about chess engines. More specifically open source chess engines: Most, if not all of them, are horribly designed in terms of programming.

One of the major problems with all these open source chess engines is that they have been hard-coded into being UCI chess engines. This means that they are designed to be compiled into an independent executable which a separate GUI runs in the background.

What this means in practice is that none of them (or at least none I have looked so far), has been designed to work as a library. In other words, something that you can simply compile into your own program, and which you could then easily call from your own code. In other words, they are not reusable code.

They are not modular. In other words, they are not encapsulated eg. into a single class, which you could instantiate in your own code, and interact with through a minimal public interface. Instead, they are designed (ie. hard-coded) to be just a command-line program, rather than a library. Which means that they are just full of global functions and, more damningly, global variables all over the place, with no way to be incorporated into another program, and no clear public interface of any kind that could be called from other code.

Even the best-designed ones are like that. The worst ones are just outright horrible. (The worst one I have seen was one single gigantic source code file containing tens of thousands of lines, and being just a hard-coded command-line program, with absolutely no way of including it into another program, which could call it.)

The best design would be if the chess engine code is tightly encapsulated into a class, with a minimal public interface, and which could be instantiated (several times if so desired) and easily interacted with using its public methods. None of the engines I have looked so far use this design. All of them, instead, even the best ones, are rife with global variables, global functions, and zero library-style design.

(An even better design would be to separate the core engine from the UCI protocol part. These could be completely separate and independent classes, with the UCI class using the core engine class, eg. by inheriting from it, or using it as a member variable. This way a program could just use the core engine part if it does not need the UCI functionality. Also the main UCI command-line program code, ie. containing the main() function etc. ought to be completely separate from the rest of the code, and completely optional.)

This means that these engines are very hard, if not impossible, to use in a custom program. You can't simply compile them into your own program and use them, at least not without heavy modifications (which is often made harder by the fact that all the global functions and global variables are all over the place, rather than tightly encapsulated, and there is usually no easy way to selectively choose which parts of the engine you want into your program and which parts you don't.)

In short, they are very badly designed, in terms of their source code. They are hard, if not impossible, to reuse in and compile into a third-party program, which could benefit from them.

No comments:

Post a Comment