Answers.Body: <p>There is no need for research. Breadth-first, by definition needs to traverse all nodes at a level before going to the next. It just doesn't work for chess, where the number of positions is too many and most of the positions are just stupid (e.g. dropping a queen). Chess engines always use deep-first.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T14:09:20.937Z
Answers.Text: Maybe it wasn't clear from my question formulation, but I didn't mean pure DFS or pure BFS. Instead, I simply meant comparing engines that go deeper but explore fewer options per position to engines that go less deep but explore more options per position. It would be very surprising to me if all engines automatically explored the same number of moves per position, on average. It could also be that my question is based on a fundamental misunderstanding. If so, I would be happy if you could point out what I'm missing.
Answers.UserDisplayName: postnubilaphoebus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T00:30:38.907Z
Answers.Text: @postnubilaphoebus: I'm afraid you are misusing the terms then! Breadth-first search is qualitatively different from depth-first search. What you are talking about is simply a speed vs knowledge trade-off.
Answers.UserDisplayName: TonyK
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T12:01:54.623Z
Answers.LastActivityDate: 2020-04-06T12:01:54.623Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>One important point to consider is that <strong><a href="https://en.wikibooks.org/w/index.php?title=Artificial_Intelligence/Definition&amp;stable=0#Uninformed_Search" rel="nofollow noreferrer">BFS has a hugely higher space complexity than DFS</a></strong>.</p>
  
  <p>Notation: </p>
  
  <ul>
  <li>b = branching factor = number of moves per step, <a href="https://en.wikipedia.org/wiki/Branching_factor" rel="nofollow noreferrer">about 31 in
  chess</a> </li>
  <li>d = minimum depth of tree till optimal solution (e.g. 10 if checkmate in 10 turns is possible) </li>
  <li>m = maximum depth of tree (e.g. 150 moves till draw)</li>
  </ul>
  
  <p><strong>Space complexity of BFS: O(b^d)</strong></p>
  
  <p><strong>Space complexity of DFS: O(b * m)</strong></p>
  
  <p>Assuming that a position with b=31, d=10 and m=150 is evaluated and each node needs <a href="https://stackoverflow.com/questions/21374846/efficient-storage-of-a-chess-position">24 Bytes of space</a>, BFS would need about 20 <strong>Peta</strong>byte of space and DFS only  111 KB, making BFS infeasible. Also keep in mind that modern CPUs only have a few MB of cache (e.g. <a href="https://ark.intel.com/content/www/us/en/ark/products/192943/intel-core-i9-9900ks-processor-16m-cache-up-to-5-00-ghz.html" rel="nofollow noreferrer">16 MB for the i9-9900KS</a>), so they could not even fit all nodes of BFS at the depth of d=4 (22MB).</p>
  
  <p>With strong pruning (i.e. throw away very bad moves), the branching factor can be reduced to perhaps 5-10 good moves per step, but this does not solve the exponential space complexity of BFS.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T09:07:40.873Z
Answers.LastActivityDate: 2020-04-07T09:17:17.190Z
Answers.LastEditDate: 2020-04-07T09:17:17.190Z
Answers.UserDisplayName: Metlam
Answers.Body: <p>In addition to the great accepted answer, I'll point out that engines do differ in the amount of breadth/depth they analyze, even though all of them do use depth first search because of alpha beta search (something you should research if you want to learn more, as all traditional engines use it) being much better optimized for it.</p>
  
  <p>For example, Stockfish is very well known for aggressively getting rid of moves it has to consider through various pruning techniques, so it can consider the best few moves to extremely great depths because it doesn't need to calculate as many positions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T00:31:58.090Z
Answers.LastActivityDate: 2020-04-07T00:31:58.090Z
Answers.UserDisplayName: Alex Pawelko
Answers.Body: <p>Strength in chess engines depends on speed and speed depends on how strongly you can prune the tree. That is, how many nodes you can discard without degrading the accuracy of your search result. </p>
  
  <p>In principle you might be able to visit the same nodes using either BFS or DFS, so a priori it is not clear which would be better prunable i.e. faster. </p>
  
  <p>In chess, however, DFS is better prunable because one strong countermove is enough to invalidate a move. Therefore, the value of a move depends more strongly on a small set of next countermoves and the value of these countermoves on a small set of next moves etc. So, Min-Max-Search naturally lends itself to better pruning with DFS.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T14:03:15.623Z
Answers.Text: I see, that makes sense. I'll take 'Min-Max search' as a starting point in order to improve my understanding of the subject matter.
Answers.UserDisplayName: postnubilaphoebus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-07T00:31:38.760Z
Answers.Text: The usual term is _minimax_ search.
Answers.UserDisplayName: TonyK
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-06T13:25:59.777Z
Answers.LastActivityDate: 2020-04-06T13:25:59.777Z
Answers.UserDisplayName: BlindKungFuMaster
Body: <p>I would like to learn about the difference between depth-first and breadth-first search in knowledge-based chess engines (that, of course, excludes alpha-zero). The difference isn't that clear-cut, but, to my knowledge, some engines prefer to go deeper than explore more options per move. It seems that depth-first search, as it is used in Stockfish, has prevailed for now, but I don't necessarily find that obvious. Can anyone point me to research which has been done in this area?</p>
  
Tags: <engines><computer-chess>
Title: Breadth-first search vs Depth first search in knowledge-based chess engines
ThreadText: # Breadth-first search vs Depth first search in knowledge-based chess engines
  
  (Asked by: username_0 on 2020-04-06)
  
  I would like to learn about the difference between depth-first and breadth-first search in knowledge-based chess engines (that, of course, excludes alpha-zero). The difference isn't that clear-cut, but, to my knowledge, some engines prefer to go deeper than explore more options per move. It seems that depth-first search, as it is used in Stockfish, has prevailed for now, but I don't necessarily find that obvious. Can anyone point me to research which has been done in this area?
  
  **Tags:** engines, computer-chess
  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_5 on 2020-04-06. Score: 5 | Accepted answer
  
  Strength in chess engines depends on speed and speed depends on how strongly you can prune the tree. That is, how many nodes you can discard without degrading the accuracy of your search result.
  
  In principle you might be able to visit the same nodes using either BFS or DFS, so a priori it is not clear which would be better prunable i.e. faster.
  
  In chess, however, DFS is better prunable because one strong countermove is enough to invalidate a move. Therefore, the value of a move depends more strongly on a small set of next countermoves and the value of these countermoves on a small set of next moves etc. So, Min-Max-Search naturally lends itself to better pruning with DFS.
  
  > **Comments:**
  > **username_0**: I see, that makes sense. I'll take 'Min-Max search' as a starting point in order to improve my understanding of the subject matter.  
  > **username_2**: The usual term is _minimax_ search.  
  
  ---
  
  ### Answer by username_1 on 2020-04-06. Score: 3
  
  There is no need for research. Breadth-first, by definition needs to traverse all nodes at a level before going to the next. It just doesn't work for chess, where the number of positions is too many and most of the positions are just stupid (e.g. dropping a queen). Chess engines always use deep-first.
  
  > **Comments:**
  > **username_0**: Maybe it wasn't clear from my question formulation, but I didn't mean pure DFS or pure BFS. Instead, I simply meant comparing engines that go deeper but explore fewer options per position to engines that go less deep but explore more options per position. It would be very surprising to me if all engines automatically explored the same number of moves per position, on average. It could also be that my question is based on a fundamental misunderstanding. If so, I would be happy if you could point out what I'm missing.  
  > **username_2**: @username_0: I'm afraid you are misusing the terms then! Breadth-first search is qualitatively different from depth-first search. What you are talking about is simply a speed vs knowledge trade-off.  
  
  ---
  
  ### Answer by username_3 on 2020-04-07. Score: 3
  
  One important point to consider is that **[BFS has a hugely higher space complexity than DFS](https://en.wikibooks.org/w/index.php?title=Artificial_Intelligence/Definition&stable=0#Uninformed_Search)**.
  
  Notation:
  
  * b = branching factor = number of moves per step, [about 31 in
    chess](https://en.wikipedia.org/wiki/Branching_factor)
  * d = minimum depth of tree till optimal solution (e.g. 10 if checkmate in 10 turns is possible)
  * m = maximum depth of tree (e.g. 150 moves till draw)
  
  **Space complexity of BFS: O(b^d)**
  
  **Space complexity of DFS: O(b \* m)**
  
  Assuming that a position with b=31, d=10 and m=150 is evaluated and each node needs [24 Bytes of space](https://stackoverflow.com/questions/21374846/efficient-storage-of-a-chess-position), BFS would need about 20 **Peta**byte of space and DFS only 111 KB, making BFS infeasible. Also keep in mind that modern CPUs only have a few MB of cache (e.g. [16 MB for the i9-9900KS](https://ark.intel.com/content/www/us/en/ark/products/192943/intel-core-i9-9900ks-processor-16m-cache-up-to-5-00-ghz.html)), so they could not even fit all nodes of BFS at the depth of d=4 (22MB).
  
  With strong pruning (i.e. throw away very bad moves), the branching factor can be reduced to perhaps 5-10 good moves per step, but this does not solve the exponential space complexity of BFS.
  
  
  ---
  
  ### Answer by username_4 on 2020-04-07. Score: 2
  
  In addition to the great accepted answer, I'll point out that engines do differ in the amount of breadth/depth they analyze, even though all of them do use depth first search because of alpha beta search (something you should research if you want to learn more, as all traditional engines use it) being much better optimized for it.
  
  For example, Stockfish is very well known for aggressively getting rid of moves it has to consider through various pruning techniques, so it can consider the best few moves to extremely great depths because it doesn't need to calculate as many positions.
  
  
  ---
  
  