Chess engine with no evaluation

Question

One of the most difficult parts of a chess engine is the evaluation function. Handcrafted evaluation functions are very long and complicated, while NN evaluations are hard to make and train. That's why I was wondering whether an implementation of a chess engine with no evaluation function would be possible. Search algorithms like MCTS don't need an explicit one, as they can rely on random playouts.

Could a similar approach be used to create a chess engine with a random search algorithm, which averages the results from those random games and optimally reach to the best move?

Theoretically, it should converge to the optimal solution (minimax), right? Of course it would be for testing and experimentation purposes, but I think with a good implementation of the algorithm, it should play at least at almost master level. I would implement it on Golang, as it would be easier to implement concurrency/parallelism. What are your thoughts on this?

Answer 1

I have tried using MCTS before for a chess engine and the results were not very good. The problem was that the results when playing out a game with only random moves were basically just that: random. Most of the results would only be reached after over 100 plies so the initial position had little to do with the result.

I had better results when I cutoff the tree after x plies where x would be somewhere between 20 and 50 and using a simple evaluation function for that position. But then you would be relying on a evaluation function again.

Answer 2

The number of board states is on the order of 10^45. That's within a few orders of magnitude of the number of water molecules in the Earth's oceans. So solving chess by exhaustively searching the possible board states is not currently considered computationally feasible.

Instead you're proposing Monte Carlo Tree Search. In this approach, you would use random roll-outs (i.e. playing a game to the end by making random moves, then seeing if you won). This is equivalent to randomly choosing a branch of the possible future board states and seeing if it results in a win, and from that, making moves that you estimate to be likely to lead to victory.

For this to work, given the scale of the possible board states, you need a sampling algorithm that is very thorough and very fast, and most importantly, very representative. Unfortunately, the surface you're trying to optimize over is not very smooth: even the best board position can be turned into a loss with a couple bonehead moves, and if you're sampling random future board states (the hallmark of Monte Carlo, vs. exhaustive, search methods), you have no way to know whether what you have sampled is representative of the entire branch, or if you just picked a rollout that included some really bad plays (or conversely, one where your opponent did something dumb that gave you a needlessly rosy view of your odds).

That's the entire point of the evaluation function: you estimate the value of a set of intermediate board states, which you can more thoroughly explore within a reasonable future-turn horizon. (Until you reach the endgame, where you can realistically do exhaustive search.)

Note that MCTS is in a sense learning an evaluation function: instead of an explicitly stated value for a board state, you're keeping statistics on the number of times a sequence of random moves from that board state have resulted in wins/losses. The problem is, because of how distant the eventual win/loss is from most board states, and because of your inevitable computational limits, you're learning a pretty bad evaluation function.

If your sampling rate was high enough, this could work; but with no evaluation function (or way to approximate an evaluation function, like a neural network), you're going to spend far too much of your time evaluating obviously bad plays and not learning anything actionable. It just isn't computationally feasible given the numbers involved.

Answer 3

MCTS is over-hyped. In general to make a computer player for such turn-based abstract games, you would need to use negamax/minimax plus alpha-beta pruning (see this post for an explanation of its correctness), together with a couple of heuristics:

• Position-evaluation functions: Estimates the true value of the given position. Must be used at the leaves of the search tree, but may also be used elsewhere. In chess, material imbalance is a reasonable first-order estimate, and costs almost nothing to compute, but a very big reason that StockFish has such good performance is that it has an far more intricate evaluation function than just computing material imbalance; it counts in king danger, passed pawns, control of open files, obstructed pieces, and many more things.

• Expansion heuristic: Decides which lines of play to search, possibly using a position-evaluation function to do so. This includes quiescence search (to avoid the horizon effect), which for chess typically means to search deeper for captures and checks.

• Move-ordering heuristic: Decides the order in which to search lines of play from each position, possibly relying on a position-evaluation function as well. This includes iterative-deepening, killer heuristic, null-move heuristic and so on. For chess, it is often useful to search 'attacking' moves first, besides the other general heuristics.

• Opening book: Decides the first few moves. It is computationally intensive to search deep, but one can do so on supercomputers and simply store the resulting evaluations of positions near the start in an opening book in the program. If you take a look at StockFish on Lichess, you can see that it indeed has such an opening book.

If you think about it, attempting to use MCTS to decide which move is best will perform approximately the same as a depth-1 greedy algorithm even if you have a material imbalance evaluation function at the leaves of the MC search tree, and actually a bit worse due to the random noise! To assist your intuition, consider a typical position that is win-in-10, and note that the winning strategy is typically sharp; the player that can win cannot make random moves and expect to win! MCTS is completely blind to that.

Moreover, as Tiercelet already mentioned, MCTS itself can be considered to be equivalent to using depth-1 search with a super lousy evaluation function (return the average position value after random plays)! Anyone who is not a beginner at chess can design a better evaluation function.

MCTS is bad not just for chess. Even for optimization problems where the objective function does not change drastically upon perturbing the state, a good heuristic would beat any pure MCTS algorithm hands down. Of course, to get a good heuristic you need a human to design it. So if you do not have any humans around you might have no choice but to use dumb algorithms like MCTS or simulated annealing with reheating.

The point is, with the same amount of computing resources, MCTS will always perform much more poorly than a reasonably good heuristic, regardless of the optimization/search problem.