Is AlphaGo approach unsuitable to chess?

[melajara]

AlphaGo, "Master" version just trounced the best Go player in the world and he had never a chance.

Now, this version used 1/10 of the computational power from the version which beat Lee Sedol last year.

Besides, this version was exclusively bootstrapped by playing against itself, no human players database were used.

Given the complexity (branching factor) of Go, why is this approach not suitable to Chess?

AFAIK, after Giraffe and the fact that the author is now a Deepmind employee, nobody followed this approach in chess, why so?

[cdani]

Given the complexity (branching factor) of Go, why is this approach not suitable to Chess?

The branching factor is so high compared to chess that tactics are relatively less important than long term strategy, or "intuition" like stuff if you like.
So for chess very specific technically well defined algorithms work very well.
Anyway who knows if something can be achieved...

[CheckersGuy]

The reason why DeepMind used DeepLearning is not just the enormous branching factor but the fact that it is incredibly hard (if not impossible) to come up with a static evaluation function which gives a reasonable estimate of how good the position for a player is.

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.

My guess is that using Neural Networks is still too slow on current hardware and the static evaluation functions engines like Komodo/Stockfish use already do quite well and I wonder what a Neural-Net would add that would justify the performance penalty.

[jorose]

Now, this version used 1/10 of the computational power from the version which beat Lee Sedol last year.

Yes, though it still used a huge amount of power on top of technology said to be several years ahead of what is currently on the market.

Besides, this version was exclusively bootstrapped by playing against itself, no human players database were used.

I don't believe this is quite correct, though I admit I only read the details fleetingly. If I understood it correctly it still relied on a database of games in order to bootstrap itself. Those games were not from a human database, but a database generated by some previous version of AlphaGo, which is a rather arbitrary difference.

Given the complexity (branching factor) of Go, why is this approach not suitable to Chess?

It really bothers me with how consistently people mention the branching factor in Go. Some food for thought: Imagine somebody loved chess and wanted to design a very hard game. He reads lots of articles and hears about how Go is such a hard game due to its branching factor, so he decides to invent a new game called chess prime with a much larger branching factor! In order to ensure lots of people play the game he keeps the rules simple, chess prime has all the original moves as in regular chess. On top of this instead of a regular chess move a player may opt to place any number of opposing queens on any empty square on the board without placing himself in check! A quick analyses of chess prime yields that it has an absolutely astronomical branching factor (more than 2^32 legal moves in the starting position!), but is it a hard game? It is clear that in almost every position a player can completely ignore the differences between chess and chess prime, in fact it is not trivial to come up with a position where the best move is not legal in regular chess. The branching factor of a game is not really relevant whereas the effective branching factor, being the moves which must be analyzed to some degree of depth is indeed relevant. This last point is purposefully vague.

What I realized when writing my BSc thesis is that what is much harder to deal with in Go then the branching factor is writing an accurate evaluation function. That is part of the reason Monte-Carlo Tree Search is so effective in Go; contrary to approaches used in chess there is significantly less reliance on an evaluation function.

Something you have to consider with respect to whether the same approach is good in chess or not is that it is unclear how good the approach really is in Go relative with how good approaches used in chess are in chess. The main reason it looks so good in Go is that other approaches are absolutely terrible in Go. Monte Carlo Tree Search has been state of the art in Go for quite a while now, yet it completely sucks in chess. Chess and Go are two very different games with lots of differing problems and difficulties.

AFAIK, after Giraffe and the fact that the author is now a Deepmind employee, nobody followed this approach in chess, why so?

I am a bit confused by your formulation, do you mean why nobody followed Giraffe's approach or AlphaGo's approach?

[melajara]

I meant there is a possible overlap from Matthew Lai's Giraffe and DeepMind's dual neural network used for AlphaGo. Also, why not to use AlphaGo's approach to define a much more sophisticated evaluation function than the crude material based ones (+ bonus for open files, passed pawns, rook on 7nd rank, etc)?
Sure this improved eval has to be quick to be useful but my understanding is that once a neural network is trained, eval is quick too, it's just the training time and the number of examples to be presented that are huge.

Giraffe had an interesting style as with time, it started to play endgames better and better.

Anyway, Hassabis today promised a new research paper summarizing the new improvements introduced in AlphaGo "Master", maybe it will give a new impetus to neural network evolved evaluation functions for chess.

[jorose]

I meant there is a possible overlap from Matthew Lai's Giraffe and DeepMind's dual neural network used for AlphaGo.

Actually my BSc thesis was essentially adapting and implementing Giraffe's ideas in Go. I think Giraffe's probability based search is very interesting and has potential. I don't believe search as in AlphaGo will ever be a good idea in chess on the other hand.

Also, why not to use AlphaGo's approach to define a much more sophisticated evaluation function than the crude material based ones (+ bonus for open files, passed pawns, rook on 7nd rank, etc)?

This is definitely something which is a hot topic at the moment, but more because it is a natural progression than due to AlphaGo imo. I don't think the fully fledged raw input into huge CNN approach of AlphaGo will be a good idea in chess in the near future but there is a large room in between. There have been discussions on this forum about "deepening the network" and adding one or more layers to the linear classifiers which are standard in chess.

I think just using raw input is a waste of useful features that are cheap and easy to implement in chess. There isn't really a point aside from handicapping yourself.

Sure this improved eval has to be quick to be useful but my understanding is that once a neural network is trained, eval is quick too, it's just the training time and the number of examples to be presented that are huge.

While evaluation is much faster than training it is still significantly slower than the extremely fast functions used in chess engines today. Tactics are more important in chess which makes the speed penalty very painful.

Anyway, Hassabis today promised a new research paper summarizing the new improvements introduced in AlphaGo "Master", maybe it will give a new impetus to neural network evolved evaluation functions for chess.

Indeed, I am really looking forward to reading it. AlphaGo was quite the engineering achievement.

[Ras]

Given the complexity (branching factor) of Go, why is this approach not suitable to Chess?

Because chess is way more tactical. One piece one square further can decide everything. This is bad for neuro networks because they are designed to give a similar result for similar input (pattern recognition).

What might actually work: let a conventional chess engine sort out the, say, three best moves. If the drop among them is small, there is no forced variant.

And then let a neuro network decide among these moves - they are all tactically sound, but which one is strategically best?

This could mimic the "computer plus human" teams, which are stronger than either computers or humans alone.

[kbhearn]

Perhaps the biggest reason is that what people have already been doing is working so well that there's not a strong motivator to try new approaches other than as a curiousity. Giraffe already represents a significant amount of effort and isn't close to the top of the line engines - it's likely a huge amount more effort to close that gap. You need someone with the spare time, interest, and knowledge of deep learning techniques to take up the process.

It's impossible to say that it wouldn't work as well as it did in go because the effort hasn't been put in to make it so (and even if it had, that perhaps some key factor still needed to be thought of to tip the scales).

[lucasart]

AFAIK, after Giraffe and the fact that the author is now a Deepmind employee, nobody followed this approach in chess, why so?

AFAIK Giraffe is an alpha/beta negascout search engine, like any other. Uses all the same techniques, such as null move, search reductions, quiescent search, etc. That's where almost all of Giraffe's elo is.

The only difference is that the author used neural networks for the evaluation. That is something entirely different from replacing the search with NN (which is totally hopeless for chess).

I'd say that NN have a negative elo contribution to Giraffe. Replace that with a normal eval, properly tuned, and Giraffe would likely be much stronger.

[brianr]

Actually, there are two NNs in Giraffe. One is for position scoring and the other for move search order sorting. Also, in the paper there is some data about the quality of the position evaluation NN using STS. I suspect the position eval NN contributes more strength than the move sorting NN.