Answers.Body: <p>There were attempts back in the 1980s to write chess engines with knowledge bases that would pick candidate moves like humans, but they were unsuccessful. The problem is that human pattern matching is difficult to put into words, so creating the rules for the knowledge base was extremely difficult.</p>
  
  <p>Training a neural network to pick candidate moves seems like a promising line of research. <a href="http://www.cs.utoronto.ca/~ilya/pubs/2008/go_paper.pdf">Here</a> and <a href="http://www.pradu.us/old/Nov27_2008/Buzz/research/parallel/movemap_heuristic.pdf">here</a> might be two pertinent papers. (FWIW, It is not my field of Comp Sci)</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-18T15:03:28.530Z
Answers.LastActivityDate: 2014-03-18T15:03:28.530Z
Answers.UserDisplayName: newshutz
Answers.Body: <p>You might take a look at Giraffe which was recently in the news:</p>
  
  <p><a href="https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/" rel="nofollow noreferrer">https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/</a></p>
  
  <p>The hype is that in 3 days it taught itself the game and reached IM level. On the other hand the research is at</p>
  
  <p><a href="http://arxiv.org/abs/1509.01549" rel="nofollow noreferrer">http://arxiv.org/abs/1509.01549</a></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-10-01T01:21:28.443Z
Answers.Text: Not exactly true... See my answer.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-09-30T12:57:50.350Z
Answers.LastActivityDate: 2015-09-30T12:57:50.350Z
Answers.UserDisplayName: Ian Bush
Answers.Body: <p>I'd like add details to @Ian_Bush's answer on Giraffe.</p>
  
  <p>In @Ian_Bush's answer, it's noted that Giraffe doesn't use brute-force computation. This is <b>not right</b>, because Giraffe is still an alpha-beta (nega-max) engine. The <b>only</b> difference to a standard engine is that the evaluation function is tuned automatically by deep-learning. Therefore, the engine learns how to play by itself.</p>
  
  <p>Traditionally, engine programmer self-tunes parameters in an engine. I've done a lot myself. For example, how much weight should you give to a bishop and a knight? 3.0? 3.1? 3.2? It's hard to tell.</p>
  
  <p>Giraffe approaches the problem in a much smarter way. It starts off with some initial values. The engine uses the gradient ascent algorithm to tune those values. We don't have to explicitly code how much weight a queen should be in the code. This is what we mean "learning". It doesn't mean that the engine can play chess <i>without</i> searching.</p>
  
  <p><strong>EDIT</strong>: Giraffe models the tree nodes as probability that they fall into the principal variatation. Check the paper for details. I personally don't believe this approach, and the paper shows little evidence how useful it would be.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-16T14:05:30.487Z
Answers.Text: Is it true that Giraffe use Stockfish eval as target? If so, it doesn't "learn chess" by itself, it just learns an approximation to Stockfish eval using a nnet on top of board features.
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-16T14:06:13.677Z
Answers.Text: @Fernando Giraffe doesn't have anything to do with Stockfish, I believe.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-16T14:51:10.463Z
Answers.Text: I'll read the entire paper, but on page 18 it says: `We evaluated board representations by training neural networks to predict the output of Stock-
  fish’s evaluation function in a supervised fashion, given 5 million positions as input, in the board
  representation under evaluation. ` So, this is not learning by selfplay IMO.
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-10-01T01:28:37.173Z
Answers.LastActivityDate: 2016-07-23T07:29:53.720Z
Answers.LastEditDate: 2016-07-23T07:29:53.720Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>Claude Shannon proposed two types of algorithms for creating chess engines.  A "type A" engine examines all possible moves to some finite depth, minimaxes the tree, and then plays the move with the highest evaluation from the minimaxed tree (a.k.a. brute force).  Type B engines limit their search to only a subset of possible moves based on some criteria.  I believed he favoured Type B as more promising.</p>
  
  <p>The engines that were created in the 1970's (eg. Hitech, Kaissa) tended to be pure brute force with no pruning or just alpha-beta, but people soon saw the value of pruning the tree of moves and lines that were unlikely to prove strong.  Almost all recent engines prune the tree of lines that are clearly weaker (alpha-beta), and most engines use various types of forward pruning as well (futility, late move reduction, null move, razoring).  In that sense, there aren't many engines that use pure brute force anymore.</p>
  
  <p>In the 1970's, Botvinnik was working on an engine called Pioneer conceived around the notion of attack paths which would have been evaluation guided.  It never reached the point where it could play a full game of chess.</p>
  
  <p>In the 1990's, Chris Wittington spoke out in favour of using incorporating more chess knowledge, and created a program called Chess System Tal which was fairly strong for its time.</p>
  
  <p>Kasparov, Anand and Tord Romstad have all noted that Hiarcs seems to have a more detailed evaluation than many of the top engines whose strength comes from a fast search.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-09-30T11:40:54.700Z
Answers.LastActivityDate: 2015-10-03T11:23:05.133Z
Answers.LastEditDate: 2015-10-03T11:23:05.133Z
Answers.UserDisplayName: A passerby
Answers.Body: <p>Its sort of debatable if you can call a heuristic based search and evaluate approach as brute-force. Most of top-tier chess engines today follow a rules-based approach to evaluate a position and a rules based search function to prune moves.</p>
  
  <p>This is actually not guaranteed to pick the "global optimal" move, however these moves are good enough for purpose. In this sense most chess engines are using an approximation on the global optimum and actually getting by.</p>
  
  <p>To date, we haven't many chess engines succeed at the top level using a different approach, at least not on cheap hardware.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-07-23T07:11:58.853Z
Answers.LastActivityDate: 2016-07-23T07:11:58.853Z
Answers.UserDisplayName: Jubin Chheda
Answers.Body: <p>I heard, I think it was GM Matthew Sadler on his Silicon Road channel, of grandmasters running Leela at zero or very low depth to test only how good its neural network board evaluation is. This is in spirit less &quot;brute force&quot; and more &quot;understanding&quot; (although training the neural net took a lot of computation!).</p>
  <p>Discussion at Leela mailing list: <a href="https://groups.google.com/g/lczero/c/YaJ6qpMKSl8" rel="nofollow noreferrer">If restricted to a &quot;human number of nodes&quot; to evaluate, who wins? Leela or GM?</a></p>
  <p>There was a claim that Leela with 1 node or 10 nodes of evaluation (effectively no search at all) played at 2300 Elo or IM level. For comparison, Stockfish on a laptop can search 1M+ nodes/sec.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-20T23:38:27.273Z
Answers.LastActivityDate: 2023-05-20T23:38:27.273Z
Answers.UserDisplayName: qwr
Answers.Body: <p>Basically all of them!</p>
  
  <p>Chess engines really only use brute-force when:</p>
  
  <ul>
  <li>told to</li>
  <li>are analysing positions (problem solving)</li>
  <li>Looking for a checkmate (problem solving, not when playing against, like "find the mate in N" style problems)</li>
  </ul>
  
  <p>Otherwise they have a "selective search", this will consider all the possible moves for a given board layout, but only explore a handful of them. An engine may switch to brute-force though if it rates two moves very similarly (more than one strong move) or if it cannot find a move it likes (no strong moves).</p>
  
  <p>They also tend to brute-force as a last line of defense, if you've seen a checkmate chances are it can see it coming and it will want to try really hard to draw, and cannot find a way out (the "Horizon effect" is a problem with engines, suppose it is going to loose it's queen, and it's been capped to only go 4 plays deep; if it can trade pawns and postpone that loss of the queen for 4 moves it will think it has saved the queen, in the process it'll loose at least 1 pawn (as the next move brings the horizon from before closer) and the weight it places on saving the queen may mean it sacrifices some defense, for nothing if the death goes over the horizon).</p>
  
  <p>It will also brute-force when the selective search isn't very useful. This is why engines take longer when they have like 3 pieces left. They have to brute-force because the selection algorithm cannot rate a move. The selection algorithm is great during the midgame because it can be like "Oohh, doing this with the pawn blocks his [whatever] and backs up my [whatever] and [whatever] which I have a lesser number defending than attacking" - for instance. </p>
  
  <p>If you have a king in the middle of the board there are 8 moves, the selective search will be like "None of these do anything useful, I can't tell". </p>
  
  <p>You can think of the selective search as having two parts, it is tactical in the sense of it'll try and spot tactical moves, it will ignore the weight of the pieces involved usually because a queen not a part of any strategy is not worth more than a pawn vital to it. It is also strategic in that it'll explore moves that bolster a defense, and open up later to potential attacks.</p>
  
  <p>The engine then does the same from your point of view, and back and forth and back and forth. </p>
  
  <p>Something called a transposition table is a big list of things it has thought about, that way if it ends up considering something it has already done, it knows and doesn't have to re-evaluate it. </p>
  
  <p>UNLESS (selective :)) it gets there a different way, or wants to explore further. Suppose for example it discovers that your ... rook is essential to an impending attack, the engine may re-evaluate a line when it discovers this. The previous weight it put on that rook (eg 5 points, how important it is to you) might be an under-estimate. </p>
  
  <p>The selective search can also backtrack, like say its considering a bishop moving right into enemy territory, to the move selector it is not important that it can be taken easily. Say it discovers that strategically that is a superb move! It may then backtrack to try and find a way to protect that square to get that bishop there. Suppose it involves a pawn to do so.</p>
  
  <p>The brute-force method would consider the line involving that pawn move, and (by brute force) the bishop move too, and the same stuff that rates the board position (the selective search itself) will say "this is good" so the board rates that variation highly, both find it.</p>
  
  <p>It's very hard to rate a position using the brute-force method, this is why the selective search works so well. </p>
  
  <p>The brute-force from the starting position might find that famous mate-in-4 that involves a queen f7 covered by a bishop, and if it were to rate that highly (I'VE FOUND A CHECKMATE! JOB DONE! PLAY!) it'd be wrong because black will obviously counter. The selective search rates a position (for further evaluation) because it is <em>appears</em> to be good. This means when it is considering your response it can decide what would be good for you....</p>
  
  <p>So the stuff that the selective search uses to rate things is used by the brute-force one anyway because "found a checkmate involving this move" is not enough to say that move is good. </p>
  
  <p>Hence <a href="https://chess.stackexchange.com/questions/5032/what-are-the-first-moves-chosen-white-by-brute-force-chess-engines/5041#5041">What are the first moves chosen (White), by brute force chess engines?</a></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-26T21:30:25.830Z
Answers.LastActivityDate: 2014-03-26T21:30:25.830Z
Answers.LastEditDate: 2017-04-13T12:48:53.193Z
Answers.UserDisplayName: Alec Teal
Body: <p>Every chess engine I've ever heard of (including all I found listed on Wikipedia) uses brute-force search with an evaluation function (minmax algorithm) to decide on its move.</p>
  
  <p>This is not how most humans approach the game, employing general pattern recognition instead, so in principle, it would be possible for computers to do the same.</p>
  
  <p>Is there any chess engine that does not rely on the brute-force approach to find its moves?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-09-30T11:50:52.187Z
Comments.Text: Regarding the people who say modern engines aren't brute force because they prune moves... I think it is pretty clear that when a chess engine evaluates tens of millions of positions, it is using brute force, regardless of the eyebrows someone might draw on the algorithm.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-09-30T12:07:25.240Z
Comments.Text: Modern engines can miss moves, eg. sacrifices where the payoff isn't until quite deep.  I think this is probably because they get pruned and not examined deeply.
Comments.UserDisplayName: A passerby
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-03-18T13:40:49.027Z
Comments.Text: Magnus Carlsen. ;)
Comments.UserDisplayName: NM Wesley Falcao
Tags: <engines><chess-algorithms><candidate-move><brute-force>
Title: Is there a chess engine that does NOT use brute-force search?
ThreadText: # Is there a chess engine that does NOT use brute-force search?
  
  (Asked by: username_0 on 2014-03-18)
  
  Every chess engine I've ever heard of (including all I found listed on Wikipedia) uses brute-force search with an evaluation function (minmax algorithm) to decide on its move.
  
  This is not how most humans approach the game, employing general pattern recognition instead, so in principle, it would be possible for computers to do the same.
  
  Is there any chess engine that does not rely on the brute-force approach to find its moves?
  
  **Tags:** engines, chess-algorithms, candidate-move, brute-force
  
  > **Comments:**
  > **username_3**: Magnus Carlsen. ;)  
  > **username_1**: Regarding the people who say modern engines aren't brute force because they prune moves... I think it is pretty clear that when a chess engine evaluates tens of millions of positions, it is using brute force, regardless of the eyebrows someone might draw on the algorithm.  
  > **username_2**: Modern engines can miss moves, eg. sacrifices where the payoff isn't until quite deep.  I think this is probably because they get pruned and not examined deeply.  
  
  ---
  
  ## 7 answers
  
  ### Answer by username_4 on 2014-03-18. Score: 5
  
  There were attempts back in the 1980s to write chess engines with knowledge bases that would pick candidate moves like humans, but they were unsuccessful. The problem is that human pattern matching is difficult to put into words, so creating the rules for the knowledge base was extremely difficult.
  
  Training a neural network to pick candidate moves seems like a promising line of research. [Here](http://www.cs.utoronto.ca/~ilya/pubs/2008/go_paper.pdf) and [here](http://www.pradu.us/old/Nov27_2008/Buzz/research/parallel/movemap_heuristic.pdf) might be two pertinent papers. (FWIW, It is not my field of Comp Sci)
  
  
  ---
  
  ### Answer by username_5 on 2015-09-30. Score: 4
  
  You might take a look at Giraffe which was recently in the news:
  
  <https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/>
  
  The hype is that in 3 days it taught itself the game and reached IM level. On the other hand the research is at
  
  <http://arxiv.org/abs/1509.01549>
  
  > **Comments:**
  > **username_6**: Not exactly true... See my answer.  
  
  ---
  
  ### Answer by username_6 on 2015-10-01. Score: 4
  
  I'd like add details to @Ian\_Bush's answer on Giraffe.
  
  In @Ian\_Bush's answer, it's noted that Giraffe doesn't use brute-force computation. This is **not right**, because Giraffe is still an alpha-beta (nega-max) engine. The **only** difference to a standard engine is that the evaluation function is tuned automatically by deep-learning. Therefore, the engine learns how to play by itself.
  
  Traditionally, engine programmer self-tunes parameters in an engine. I've done a lot myself. For example, how much weight should you give to a bishop and a knight? 3.0? 3.1? 3.2? It's hard to tell.
  
  Giraffe approaches the problem in a much smarter way. It starts off with some initial values. The engine uses the gradient ascent algorithm to tune those values. We don't have to explicitly code how much weight a queen should be in the code. This is what we mean "learning". It doesn't mean that the engine can play chess *without* searching.
  
  **EDIT**: Giraffe models the tree nodes as probability that they fall into the principal variatation. Check the paper for details. I personally don't believe this approach, and the paper shows little evidence how useful it would be.
  
  > **Comments:**
  > **username_7**: Is it true that Giraffe use Stockfish eval as target? If so, it doesn't "learn chess" by itself, it just learns an approximation to Stockfish eval using a nnet on top of board features.  
  > **username_6**: @username_7 Giraffe doesn't have anything to do with Stockfish, I believe.  
  > **username_7**: I'll read the entire paper, but on page 18 it says: `We evaluated board representations by training neural networks to predict the output of Stock- fish’s evaluation function in a supervised fashion, given 5 million positions as input, in the board representation under evaluation. ` So, this is not learning by selfplay IMO.  
  
  ---
  
  ### Answer by username_2 on 2015-09-30. Score: 2
  
  Claude Shannon proposed two types of algorithms for creating chess engines. A "type A" engine examines all possible moves to some finite depth, minimaxes the tree, and then plays the move with the highest evaluation from the minimaxed tree (a.k.a. brute force). Type B engines limit their search to only a subset of possible moves based on some criteria. I believed he favoured Type B as more promising.
  
  The engines that were created in the 1970's (eg. Hitech, Kaissa) tended to be pure brute force with no pruning or just alpha-beta, but people soon saw the value of pruning the tree of moves and lines that were unlikely to prove strong. Almost all recent engines prune the tree of lines that are clearly weaker (alpha-beta), and most engines use various types of forward pruning as well (futility, late move reduction, null move, razoring). In that sense, there aren't many engines that use pure brute force anymore.
  
  In the 1970's, Botvinnik was working on an engine called Pioneer conceived around the notion of attack paths which would have been evaluation guided. It never reached the point where it could play a full game of chess.
  
  In the 1990's, Chris Wittington spoke out in favour of using incorporating more chess knowledge, and created a program called Chess System Tal which was fairly strong for its time.
  
  Kasparov, Anand and Tord Romstad have all noted that Hiarcs seems to have a more detailed evaluation than many of the top engines whose strength comes from a fast search.
  
  
  ---
  
  ### Answer by username_8 on 2016-07-23. Score: 2
  
  Its sort of debatable if you can call a heuristic based search and evaluate approach as brute-force. Most of top-tier chess engines today follow a rules-based approach to evaluate a position and a rules based search function to prune moves.
  
  This is actually not guaranteed to pick the "global optimal" move, however these moves are good enough for purpose. In this sense most chess engines are using an approximation on the global optimum and actually getting by.
  
  To date, we haven't many chess engines succeed at the top level using a different approach, at least not on cheap hardware.
  
  
  ---
  
  ### Answer by username_9 on 2023-05-20. Score: 0
  
  I heard, I think it was GM Matthew Sadler on his Silicon Road channel, of grandmasters running Leela at zero or very low depth to test only how good its neural network board evaluation is. This is in spirit less "brute force" and more "understanding" (although training the neural net took a lot of computation!).
  
  Discussion at Leela mailing list: [If restricted to a "human number of nodes" to evaluate, who wins? Leela or GM?](https://groups.google.com/g/lczero/c/YaJ6qpMKSl8)
  
  There was a claim that Leela with 1 node or 10 nodes of evaluation (effectively no search at all) played at 2300 Elo or IM level. For comparison, Stockfish on a laptop can search 1M+ nodes/sec.
  
  
  ---
  
  ### Answer by username_10 on 2014-03-26. Score: -2
  
  Basically all of them!
  
  Chess engines really only use brute-force when:
  
  * told to
  * are analysing positions (problem solving)
  * Looking for a checkmate (problem solving, not when playing against, like "find the mate in N" style problems)
  
  Otherwise they have a "selective search", this will consider all the possible moves for a given board layout, but only explore a handful of them. An engine may switch to brute-force though if it rates two moves very similarly (more than one strong move) or if it cannot find a move it likes (no strong moves).
  
  They also tend to brute-force as a last line of defense, if you've seen a checkmate chances are it can see it coming and it will want to try really hard to draw, and cannot find a way out (the "Horizon effect" is a problem with engines, suppose it is going to loose it's queen, and it's been capped to only go 4 plays deep; if it can trade pawns and postpone that loss of the queen for 4 moves it will think it has saved the queen, in the process it'll loose at least 1 pawn (as the next move brings the horizon from before closer) and the weight it places on saving the queen may mean it sacrifices some defense, for nothing if the death goes over the horizon).
  
  It will also brute-force when the selective search isn't very useful. This is why engines take longer when they have like 3 pieces left. They have to brute-force because the selection algorithm cannot rate a move. The selection algorithm is great during the midgame because it can be like "Oohh, doing this with the pawn blocks his [whatever] and backs up my [whatever] and [whatever] which I have a lesser number defending than attacking" - for instance.
  
  If you have a king in the middle of the board there are 8 moves, the selective search will be like "None of these do anything useful, I can't tell".
  
  You can think of the selective search as having two parts, it is tactical in the sense of it'll try and spot tactical moves, it will ignore the weight of the pieces involved usually because a queen not a part of any strategy is not worth more than a pawn vital to it. It is also strategic in that it'll explore moves that bolster a defense, and open up later to potential attacks.
  
  The engine then does the same from your point of view, and back and forth and back and forth.
  
  Something called a transposition table is a big list of things it has thought about, that way if it ends up considering something it has already done, it knows and doesn't have to re-evaluate it.
  
  UNLESS (selective :)) it gets there a different way, or wants to explore further. Suppose for example it discovers that your ... rook is essential to an impending attack, the engine may re-evaluate a line when it discovers this. The previous weight it put on that rook (eg 5 points, how important it is to you) might be an under-estimate.
  
  The selective search can also backtrack, like say its considering a bishop moving right into enemy territory, to the move selector it is not important that it can be taken easily. Say it discovers that strategically that is a superb move! It may then backtrack to try and find a way to protect that square to get that bishop there. Suppose it involves a pawn to do so.
  
  The brute-force method would consider the line involving that pawn move, and (by brute force) the bishop move too, and the same stuff that rates the board position (the selective search itself) will say "this is good" so the board rates that variation highly, both find it.
  
  It's very hard to rate a position using the brute-force method, this is why the selective search works so well.
  
  The brute-force from the starting position might find that famous mate-in-4 that involves a queen f7 covered by a bishop, and if it were to rate that highly (I'VE FOUND A CHECKMATE! JOB DONE! PLAY!) it'd be wrong because black will obviously counter. The selective search rates a position (for further evaluation) because it is *appears* to be good. This means when it is considering your response it can decide what would be good for you....
  
  So the stuff that the selective search uses to rate things is used by the brute-force one anyway because "found a checkmate involving this move" is not enough to say that move is good.
  
  Hence [What are the first moves chosen (White), by brute force chess engines?](https://chess.stackexchange.com/questions/5032/what-are-the-first-moves-chosen-white-by-brute-force-chess-engines/5041#5041)
  
  
  ---
  
  