Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-28T13:56:05.460Z
Answers.LastActivityDate: 2020-07-28T13:56:05.460Z
Answers.UserDisplayName: Arne
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T05:51:26.463Z
Answers.Text: Great answer! I'd like to emphasize your key point "**the surface you're trying to optimize over is not very smooth**", because that is precisely why MCTS fails terribly at games with very sharp global play. And it is absolutely important to realize that the very *choice* of using MCTS is *itself* a heuristic move-ordering/selection mechanism, and that it is a **very lousy** one.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-28T21:48:23.617Z
Answers.LastActivityDate: 2020-07-28T21:48:23.617Z
Answers.UserDisplayName: Tiercelet
Answers.Body: <p>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 <a href="https://chess.stackexchange.com/a/29842/9192">this post</a> for an explanation of its correctness), together with a couple of heuristics:</p>
  <ul>
  <li><p><strong>Position-evaluation functions</strong>: 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.</p>
  </li>
  <li><p><strong>Expansion heuristic</strong>: 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.</p>
  </li>
  <li><p><strong>Move-ordering heuristic</strong>: 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.</p>
  </li>
  <li><p><strong>Opening book</strong>: 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.</p>
  </li>
  </ul>
  <p>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.</p>
  <p>Moreover, as <em>Tiercelet</em> 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.</p>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T06:42:01.957Z
Answers.LastActivityDate: 2020-07-29T07:01:29.537Z
Answers.LastEditDate: 2020-07-29T07:01:29.537Z
Answers.UserDisplayName: user21820
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T02:48:58.290Z
Comments.Text: A couple or three decades ago my father went to a talk by one of the programmers of the top chess program of the day.  One of his remarks was that people work hard on the evaluation function, but you shouldn't.  After all, if you search deeply enough all you need is a mate detector.  It was facetious, but he did claim that searching one ply deeper was more important than any reasonable improvement in evaluation.
Comments.UserDisplayName: Ross Millikan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T02:57:30.987Z
Comments.Text: People tend to overestimate the efficacy of certain "basic" engine paradigms. A basic minimax algorithm with a naive evaluation function and no fancy board representation/move generation will play at *maybe* a 1300 level. You (as an amateur) need a lot of bells and whistles to get it to 2000+, and will need a lot of reading up to get 2500+.  I find it *extremely* unlikely that a pure MCTS engine could get anywhere close to master. I'd be surprised if it could get over ~700.
Comments.UserDisplayName: Noah Caplinger
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T05:40:14.927Z
Comments.Text: @RossMillikan: Have you considered that such an anecdote is suspicious? I have done programming for computer players for many abstract games, and invariably a good heuristic evaluation increases the effective search depth **a lot**. Even if the remark was really made by a top chess program designer, it could be that he didn't want others to win, and the surest way of that is to make others underestimate the evaluation function!
Comments.UserDisplayName: user21820
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T05:53:37.737Z
Comments.Text: A chess engine without an evaluation function?? Is this trolling??? That would be like a scale that just tells you you're fat.
Comments.UserDisplayName: Savage47
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T07:30:05.660Z
Comments.Text: Just because there are many positions that lead to mate down in the tree, it doesn't mean your move is any good! The discussion about whether it's better to go one move deeper or have a better evalution function is meaningless because it depends on how big that improvement is (which is hard to quantify)
Comments.UserDisplayName: David
Tags: <engines>
Title: Chess engine with no evaluation
ThreadText: # Chess engine with no evaluation
  
  (Asked by: username_0 on 2020-07-28)
  
  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?
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: A couple or three decades ago my father went to a talk by one of the programmers of the top chess program of the day.  One of his remarks was that people work hard on the evaluation function, but you shouldn't.  After all, if you search deeply enough all you need is a mate detector.  It was facetious, but he did claim that searching one ply deeper was more important than any reasonable improvement in evaluation.  
  > **username_2**: People tend to overestimate the efficacy of certain "basic" engine paradigms. A basic minimax algorithm with a naive evaluation function and no fancy board representation/move generation will play at *maybe* a 1300 level. You (as an amateur) need a lot of bells and whistles to get it to 2000+, and will need a lot of reading up to get 2500+.  I find it *extremely* unlikely that a pure MCTS engine could get anywhere close to master. I'd be surprised if it could get over ~700.  
  > **username_3**: @username_1: Have you considered that such an anecdote is suspicious? I have done programming for computer players for many abstract games, and invariably a good heuristic evaluation increases the effective search depth **a lot**. Even if the remark was really made by a top chess program designer, it could be that he didn't want others to win, and the surest way of that is to make others underestimate the evaluation function!  
  > **username_4**: A chess engine without an evaluation function?? Is this trolling??? That would be like a scale that just tells you you're fat.  
  > **username_5**: Just because there are many positions that lead to mate down in the tree, it doesn't mean your move is any good! The discussion about whether it's better to go one move deeper or have a better evalution function is meaningless because it depends on how big that improvement is (which is hard to quantify)  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_6 on 2020-07-28. Score: 7
  
  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 by username_7 on 2020-07-28. Score: 6
  
  [The number of board states is on the order of 10^45](https://math.stackexchange.com/questions/1406919/how-many-legal-states-of-chess-exists). That's [within a few orders of magnitude of the number of water molecules in the Earth's oceans](https://www.quora.com/How-many-water-molecules-are-in-the-Earths-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](https://en.wikipedia.org/wiki/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.
  
  > **Comments:**
  > **username_3**: Great answer! I'd like to emphasize your key point "**the surface you're trying to optimize over is not very smooth**", because that is precisely why MCTS fails terribly at games with very sharp global play. And it is absolutely important to realize that the very *choice* of using MCTS is *itself* a heuristic move-ordering/selection mechanism, and that it is a **very lousy** one.  
  
  ---
  
  ### Answer by username_3 on 2020-07-29. Score: 0
  
  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](https://chess.stackexchange.com/a/29842/9192) 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 *username_7* 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.
  
  
  ---
  
  