user24304: 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?

user24310: 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.

user24039: 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.

24304: <p>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.</p>
<p>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?</p>
<p>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?</p>
 24310: <p><a href="https://math.stackexchange.com/questions/1406919/how-many-legal-states-of-chess-exists">The number of board states is on the order of 10^45</a>. That's <a href="https://www.quora.com/How-many-water-molecules-are-in-the-Earths-oceans" rel="noreferrer">within a few orders of magnitude of the number of water molecules in the Earth's oceans</a>. So solving chess by exhaustively searching the possible board states is not currently considered computationally feasible.</p>
<p>Instead you're proposing <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="noreferrer">Monte Carlo Tree Search</a>. 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.</p>
<p>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, <em>very representative</em>. 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).</p>
<p>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.)</p>
<p>Note that MCTS <em>is</em> 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 <em>pretty bad</em> evaluation function.</p>
<p>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.</p>
 24039: <p>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.</p>
<p>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.</p>
