31
$\begingroup$

Computers have for a long time been able to play chess using a "brute-force"-technique, searching to a certain depth and then evaluating the position. The AlphaGo computer however, only use an ANN to evaluate the positions (it does not do any depth-search as far as I know). Is it possible to create an chess engine that plays chess in the same way as AlphaGo plays Go? Why has no one done this? Would this program perform better than the top chess-engines (and chess players) of today?

$\endgroup$
47
$\begingroup$

EDIT (after reading the paper):

I've read the paper thoughtfully. Let's start off with what Google claimed in the paper:

  • They defeated Stockfish with Monte-Carlo-Tree-Search + Deep neural networks
  • The match was absolutely one-sided, many wins for AlphaZero but none for Stockfish
  • They were able to do it in just four hours
  • AlphaZero played like a human

Unfortunately, I don't think it's a good journal paper. I'm going to explain with links (so you know I'm not dreaming):

https://www.chess.com/news/view/alphazero-reactions-from-top-gms-stockfish-author

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/move, which means that Stockfish has no use of its time management heuristics (lot 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).

Stockfish couldn't have played the best chess with only a minute per move. The program was not designed for that.

  • Stockfish was running on a regular commercial machine, while AlphaZero was on a 4 millions+ TPU machine tuned for AlphaZero. This is a like matching your high-end desktop against a cheap Android phone. Tord wrote:

One is a conventional chess program running on ordinary computers, the other uses fundamentally different techniques and is running on custom designed hardware that is not available for purchase (and would be way out of the budget of ordinary users if it were).

  • Google inadvertently gave 64 threads to a 32 core machine for Stockfish. I quote GM Larry Kaufman (world class computer chess expert):

http://talkchess.com/forum/viewtopic.php?p=741987&highlight=#741987

I agree that the test was far from fair; another issue that hurt SF was that it was apparently run on 64 threads on a 32 core machine, but it would play much better running just 32 threads on that machine, since there is almost no SMP benefit to offset the roughly 5 to 3 slowdown. Also the cost ratio was more than I said; I was thinking it was a 64 core machine, but a 32 core machine costs about half what I guessed. So maybe all in all 30 to 1 isn't so bad an estimate. On the other hand I think you underestimate how much it could be further improved.

  • Stockfish gave only 1GB hash table. This is a joke... I have a larger hash table for my Stockfish iOS app (Disclaimer: I'm the author) on my iPhone! Tord wrote:

    ... way too small hash tables for the number of threads ...

1GB hash table is absolutely unacceptable for a match like this. Stockfish would frequently encounter hash collision. It takes CPU cycles to replace old hash entries.

  • Stockfish is not designed to run with that many number of threads. In my iOS chess app, only a few threads are used. Tord wrote:

... was playing with far more search threads than has ever received any significant amount of testing ...

  • Stockfish was running without an opening book or 6-piece Syzygy endgame tablebase. The sample size was insufficient. The Stockfish version was not the latest. Discussion here.

CONCLUSION

Google has not proven without doubts their methods are superior to Stockfish. Their numbers are superficial and strongly biased to AlphaZero. Their methods are not reproducible by an independent third party. It's still a bit too early to say Deep Learning is a superior method to traditional chess programming.


EDIT (Dec 2017):

There is a new paper from Google Deepmind (https://arxiv.org/pdf/1712.01815.pdf) for deep reinforcement learning in chess. From the abstract, the world number one Stockfish chess engine was "convincingly" defeated. I think this is the most significant achievement in computer chess since the 1997 Deep Blue match. I'll update my answer once I read the paper in details.


Original (before Dec 2017)

Let's clarify your question:

  • No, chess engines don't use brute-force.
  • AlphaGo does use tree searching, it uses Monte Carlo Tree Search. Google "Monte Carlo Tree Search alphaGo" if you want to be convinced.

ANN can be used for chess engines:

Would this program perform better than the top chess-engines (and chess players) of today?

Giraffe plays at about Internation Master level, which is about FIDE 2400 rating. However, Stockfish, Houdini and Komodo all play at about FIDE 3000. This is a big gap. Why? Why not Monte-Carlo Tree Search?

  • Material heuristic in chess is simple. Most of the time, a chess position is winning/losing by just counting materials on the board. Please recall counting materials doesn't work for Go. Material counting is orders of magnitude faster than running neural networks - this can be done by bitboards represented by a 64-bit integer. On the 64 bits system, it can be done by only several machine instructions. Searching with the traditional algorithm is much faster than machine learning. Higher nodes per second translate to deeper search.
  • Similarly, there're very useful and cheap techniques such as null move pruning, late move reduction and killer moves etc. They are cheap to run, and much efficient to the approach used in AlphaGo.
  • Static evaluation in chess is fast and useful
  • Machine learning is useful for optimizating parameters, but we also have SPSA and CLOP for chess.
  • There are lots of useful metrics for tree reduction in chess. Much less so for Go.

There was research that Monte Carlo Tree Search don't scale well for chess. Go is a different game to chess. The chess algorithms don't work for Go because chess relies on brutal tactics. Tactics is arguably more important in chess.

Now, we've established that MCTS work well for AlphaGo but less so for chess. Deep learning would be more useful if:

  • The tuned NN evaluation is better than the traditional algorithms. However ... deep learning is not magic, you as the programmer would still need to do the programming. As mentioned, we have something like SPSA for self-playing for parameters tuning in chess.
  • Investment, money! There's not much money for machine learning in chess. Stockfish is free and open source, but strong enough to defeat all human players. Why would Google spend millions if anybody can just download Stockfish for free? Why's going to pay for the CPU clusters? Who's going to pay for talents? Nobody wants to do it, because chess is considered a "solved" game.

If deep learning can achieve the following, it'll beat the traditional algorithm:

  • Given a chess position, "feel" it like a human grandmaster. For example, a human grandmaster wouldn't go into lines that are bad - by experience. Neither the traditional algorithm nor deep learning can achieve that. Your NN model might give you a probability [0..1] for your position, but that's not good enough.

Let me point out:

No. Giraffe (the link posted by @Tim) doesn't use Monte Carlo Tree Search. It uses the regular nega-max algorithm. All it does is replace the regular evaluation function with NN, and it's very slow.

one more:

Although Kasparov was beaten by Deep Blue in the 1997 match. "Humanity" was really lost around 2003-2005, when Kramnik lost a match to Deep Fritz without a win and Michael Adams lost to a cluster machine in a one-sided match. Around that time, Rybka proved too strong for even the best players in the world.

Reference:

http://www.talkchess.com/forum/viewtopic.php?t=64096&postdays=0&postorder=asc&highlight=alphago+chess&topic_view=flat&start=0

I quote:

In chess we have the concept of materiality which already gives a resonable estimation of how well an engine is doing and can be computed quickly. Furthermore, there a lot of other aspects of the game that can be encoded in a static evaluation function which couldn`t be done in Go. Due to the many heuristics and good evaluation, the EBF (Effective-Branching-Factor) is quite small. Using a Neural Network as a replacement for the static evaluation function would definently slow down the engine by quite a lot.

$\endgroup$
  • 1
    $\begingroup$ Thank you. Some questions: Chess engines use the alpha-beta algorithm, is this not a "brute-force"-algorithm? Does "Monte Carlo Tree Search" mean that one looks a number of moves ahead of the current position? $\endgroup$ – lijas Oct 19 '17 at 8:43
  • 1
    $\begingroup$ @lijas "brute-force" is generally defined as searching all possibilities. Chess engines don't do that. $\endgroup$ – SmallChess Oct 19 '17 at 8:46
  • 6
    $\begingroup$ @lijas You just answered the question. Matrix multiplications is a slow operation. $\endgroup$ – SmallChess Oct 19 '17 at 9:06
  • 3
    $\begingroup$ Alpha Beta search sure is "brute forcish". Hans Berliner on AI trends: "I consider the most important trend was that computers got considerably faster in these last 50 years. In this process, we found that many things for which we had at best anthropomorphic solutions, which in many cases failed to capture the real gist of a human's method, could be done by more brute-forcish methods that merely enumerated until a satisfactory solution was found. If this is heresy, so be it." (see ieeexplore.ieee.org/document/820322/?reload=true) $\endgroup$ – Daniel Lidström Oct 19 '17 at 13:25
  • 1
    $\begingroup$ @smallchess alpha beta is de facto search algorithm, even it’s variants like negascout which are just incremental improvements. What else could he be referring to? This was written well before deep learning systems came to be. $\endgroup$ – Daniel Lidström Oct 19 '17 at 16:56
6
$\begingroup$

DeepBlue has already beaten Kasparov so this problem is solved with much simpler approach. This was possible because the number of possible moves in chess is much smaller then in go, so it is a much simpler problem. Moreover, notice that both NN and brute force need huge computing resources (here you can find a photo of the computer behind AlphaGo, notice that it uses not even GPU's, but TPU's for computation). The whole fuss with go was that when Deep Blue beat Kasparov, the go community has argued that this would not be possible with go (for lots of different reasons, but to summarize the arguments I'd need to give a detailed introduction to the game of go). Yes you can teach NN to play chess, Mario, or try teaching it to play Starcraft...

I guess that the reason for it is that you simply don't often hear in mainstream media about cases when people solve problems that were already solved.

Moreover your premise is wrong, Deep Learning is used to play chess, e.g. as described in Deep Learning Machine Teaches Itself Chess in 72 Hours, Plays at International Master Level. See also the corresponding paper, Giraffe: Using Deep Reinforcement Learning to Play Chess.

$\endgroup$
  • 3
    $\begingroup$ Despite there obviously being some chess programs trained with deep reinforcement learning, the fact remains that nobody built one that would beat "traditional" chess engines. I assume this is because this problem (beating traditional engines) is simply not interesting/motivating enough to invest a lot of effort needed to develop something of the AlphaGo level. $\endgroup$ – amoeba Oct 19 '17 at 8:14
  • 1
    $\begingroup$ @amoeba the widely available go-playing software also does not use deep learning and it is usually weaker then amateur 1 dan players, so much worse then AlphaGo. AlphaGo is a proof of concept. $\endgroup$ – Tim Oct 19 '17 at 8:16
  • 1
    $\begingroup$ @rus9384 it is not easy but we already "solved" it, Deep Bluie has beaten Kasparov, we have our black swan that has passed chess Turing test. $\endgroup$ – Tim Oct 19 '17 at 8:18
  • 5
    $\begingroup$ Solved game is another thing:we don't know if perfect play guarantees win for black/white or ends by draw. $\endgroup$ – rus9384 Oct 19 '17 at 8:19
  • 1
    $\begingroup$ @rus9384: It would be fun to start a game against a perfect chess AI and see "White wins. Checkmate in 97 moves". $\endgroup$ – Eric Duminil Oct 20 '17 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.