Monte Carlo or Minimax?

[Aldus]

Hi,

I'm new to this forum and pondering about making a chess engine in the future, maybe. Which algoritm is best suited for this task, both practically and theoretically: Monte Carlo or Minimax?

If former, why everybody is implementing Minimax?

It latter, how come AlphaZero did such an impressive job against Stockfish, without any chess specific knowledge, as they say?

Are there any other algorithms to consider?

Thank you.

[Robert Pope]

Hi,

I'm new to this forum and pondering about making a chess engine in the future, maybe. Which algoritm is best suited for this task, both practically and theoretically: Monte Carlo or Minimax?

If former, why everybody is implementing Minimax?

It latter, how come AlphaZero did such an impressive job against Stockfish, without any chess specific knowledge, as they say?

Are there any other algorithms to consider?

Thank you.

Alphabeta/minimax is an exact calculation. It's been proven that if a player adopts a minimax strategy, the opponent does not have any strategy that will perform better than also adopting minimax. The reason minimax engines don't play perfectly is due to having to approximate the full tree by doing evaluation estimates at non-terminal positions which are inaccurate, and pruning that is done to increase depths reached, which increases the accuracy of some nodes at the expense of others.

Monte Carlo depends on average experience. Inaccuracies in the evaluation get averaged out and good paths tend to get explored and played. But since it depends on the average of a lot of playouts, it has a harder time with lines that require very precise play.

So, the better algorithm will depend on the situation, as well as the speed and quality of your evaluation. Also, AlphaZero didn't use monte carlo, per se, but a directed search called UCB.

And Alpha Zero had TONS of chess specific knowledge. It was just self-learned instead of spoon fed.

[Aldus]

Thank you. But still, I'm wondering why, if both methods have potential, almost everyone is using Minimax...

[elcabesa]

Because minimax for chess is a stable technology with known pros, cons.

Mcts is a new technology for chess and still is research

[hgm]

Thank you. But still, I'm wondering why, if both methods have potential, almost everyone is using Minimax...

Up to a year ago MCTS was considered totally unsuitable for a highly tactical game like Chess, and no engine existed based on it that wasn't at least 1500 Elo weaker than a top engine based on minimax. Only by using a neural network for guiding the search (which requires an enormous amount of training, and special hardware to make it competative) Google succeeded in showing that it can actually be (very) competitive.

But almost every engine is more than 1 year old.

It also depends on what your goal is. If you want to make an 1800-Elo engine based on minimax, you do 1 day of programming, 5 days of debugging, and you are done without significant electricity consumption. To reach the same point with an NN-guided MCTS search you would probably need a month of training the NN on a powerful computer, in addition to writing the program.

[Aldus]

Only by using a neural network for guiding the search (which requires an enormous amount of training, and special hardware to make it competative) Google succeeded in showing that it can actually be (very) competitive.

Special hardware that condensed that enormous amount of training in 9 hours, according to Wikipedia. But the point of interest here, imho, is that AlphaZero reached that level of play by only searching an average of 80k nps. This is a key point because it demonstrates much better chess knowledge and ultimately a superior AI compared to regular, brute-force approach of alpha-beta. I mean, the objective for a programmer should be to make his program smarter, not add more cores to the cpu, right? And yet, a lot of folks are buying or building for themselves special huge-multi-core hardware for their parallel chess program. Hmm.

But almost every engine is more than 1 year old.

What do you mean, the version of Stockfish and Elmo that AZ competed against?

It also depends on what your goal is. If you want to make an 1800-Elo engine based on minimax, you do 1 day of programming, 5 days of debugging, and you are done without significant electricity consumption. To reach the same point with an NN-guided MCTS search you would probably need a month of training the NN on a powerful computer, in addition to writing the program.

Well, I'm just curious atm, but some of you are making chess engines for years. So from your point of view, a month of training is nothing if it can give you such an impressive step up. You have some of the strongest chess engines in the world.

[Robert Pope]

Stockfish first release was in 2008. So the version that Alpha Zero played against had been in development for 9 years. More, if you count the development time of its immediate predecessor, Glaurung.

It was far, far down the alphabeta path before it was shown that monte carlo methods were a viable alternative. And to be honest, while it has tons of potential, it has yet to show it is a superior alternative.

[Aldus]

It was far, far down the alphabeta path before it was shown that monte carlo methods were a viable alternative. And to be honest, while it has tons of potential, it has yet to show it is a superior alternative.

Well, it did manage to have a much smaller branching factor with such an impressive play. Ten years from now, when computers will be X times faster, that lower branching factor will turn to dust every opponent.

Now sure, it used Google's special hardware, but you get my point. Humans are way more effective than the machines at chess: they only search a few positions per minute. If a program will have the exact same knowledge as a grandmaster, that would be, arguably, a superior alternative, wouldn't it?

[Sesse]

Well, it did manage to have a much smaller branching factor with such an impressive play.

But you don't know whether that was from the NN evaluation or due to MCTS. How well would AZ have played with Stockfish's evaluation and AZ's MCTS? Nobody knows.

You also have to consider the very real possibility that the best choice depends on factors such as time control and available parallelism.

[jorose]

A small issue in this discussion is that some of you are mixing UCTS and NNs together when they have very little to do with one another aside from them being used together in certain engines.

MCTS is a brute force search algorithm which relies on searching many nodes in a randomized fashion until their evaluations are clear and hoping the average result of those searches approximates the true values. This is fantastic in games like Go where it is extremely hard to design an evaluation function with any degree of accuracy, especially early in the game. This is less fantastic in games like chess where there are many trivial heuristics to base good evaluation functions on.

UCTS is a deterministic search algorithm which traverses the search tree in a similar manner to the main search portion of MCTS. In Google's case they started by approximating MCTS search results with neural networks. I don't think the AlphaZero version could be called MCTS anymore however, as there is nothing random in the search at all and the networks do not approximate a randomized search.

Alpha Beta is a(n efficient) search algorithm which lets optimal values propagate directly back to the root. This is great in theory, but if you have errors they can propagate as well.

Most evaluation functions are based on some (mostly) linear model. The top engines often times have non-linear components such as for king safety.

Neural networks are universal function approximators. They are extremely powerful but orders of magnitudes more expensive to evaluate then the previously mentioned linear models. That being said these are powerful enough that they can probably solve low level tactics, so they are more comparable to a low depth search than an actual evaluation function in the traditional sense.

There is no reason why you could not combine AB with NNs (as shown by Giraffe) or MCTS with a linear evaluation function (as presumably done by Komodo MCTS, I don't know much about it). While I am not aware of a chess engine using UCTS with a linear evaluation function, I don't see why this could not be done as well.