Answers.Body: <p>Yes. Chess engines prune moves quite extensively. Chess programming is all about pruning.</p>
  
  <p>When an engine says "search up to depth 15", it really mean depth as in <a href="https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search" rel="nofollow noreferrer">iterative deepening depth-first search</a>. It <strong>doesn't</strong> mean that the engine attempts to search everything up to depth 15. No good chess engine would search everything to depth 15.</p>
  
  <p>It's complicated, but most of the bad moves should be reduced by depth (or even eliminated), and some critical lines variations extended beyond depth 15.</p>
  
  <p>90% pruning is not uncommon, in fact it'd be more like 99.999999999999999999% according to your definition.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-10T03:51:47.380Z
Answers.LastActivityDate: 2018-03-10T03:57:00.213Z
Answers.LastEditDate: 2018-03-10T03:57:00.213Z
Answers.UserDisplayName: SmallChess
Body: <p>I was looking at Fritz Online (<a href="https://fritz.chessbase.com/" rel="noreferrer">https://fritz.chessbase.com/</a>) engine's parameters/performance. Here is screen relating to one of made moves.</p>
  
  <p><a href="https://i.sstatic.net/yJdit.png" rel="noreferrer"><img src="https://i.sstatic.net/yJdit.png" alt="enter image description here"></a></p>
  
  <p>It means that there was a general depth equals to 15 but some branches were even explored to depth 39. Engine was analysing at average speed 530k positions per second. It lasted 5 sec. so ~2.6M nodes were evaluated.</p>
  
  <p>Let's consider branching factor 3 at each level. Then there are 3^15=14M leaves to evaluate (not taking into account internal nodes). As we see in case of branching factor 3 we have more nodes to analyze (14M) than it really took place (2.6M) (not even considering branches explored deeper than 15). </p>
  
  <p>Branching factor in chess is aproximately 35. I'm aware there are many, many sophisticated techniques to prune branches in search tree. But really from 35 to less than 3? How it's possible that more than 90% of branches are pruned?</p>
  
  <p>Two remarks:</p>
  
  <ol>
  <li>Provided parameters/performance come from phase between opening and middlegame. This is NOT taken from ending where branching factor is significantly lower.</li>
  <li>Depth 15 is not something unusual. In most cases program performed analysis to depth between 13 and 16 in couple of seconds.</li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-07T06:44:49.223Z
Comments.Text: Assess a random chess position, all the moves but a few will look ridiculous to you. Same way engines can prune branches which start with bad moves.
Comments.UserDisplayName: ferit
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-07T09:12:50.383Z
Comments.Text: What is the specific algorithm to do that? Good human player does it intuively and it's hard to provide exact way/algorithm. There are only some psychological researches stating man uses chunks, trajectories, etc.
Comments.UserDisplayName: stanwar
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-07T10:10:46.960Z
Comments.Text: @stanwar That's what it means to have an efficient evaluation function, which roughly is a superposition of a long set of factors (king safety, material difference, mobility, ...) which are weighted differently from engine to engine. The weights are determined heuristically. Here are many links where this is discussed: https://chess.stackexchange.com/questions/17957/how-to-write-a-chess-evaluation-function or https://chess.stackexchange.com/questions/2204/how-do-chess-engines-think or https://chessprogramming.wikispaces.com/Evaluation
Comments.UserDisplayName: user929304
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-07T15:47:30.497Z
Comments.Text: Evaluation function can be used to decide which branches to prune.
Comments.UserDisplayName: ferit
Tags: <engines><depth>
Title: Do chess engines really prune more than 90% of branches?
ThreadText: # Do chess engines really prune more than 90% of branches?
  
  (Asked by: username_0 on 2018-03-06)
  
  I was looking at Fritz Online (<https://fritz.chessbase.com/>) engine's parameters/performance. Here is screen relating to one of made moves.
  
  [![enter image description here](https://i.sstatic.net/yJdit.png)](https://i.sstatic.net/yJdit.png)
  
  It means that there was a general depth equals to 15 but some branches were even explored to depth 39. Engine was analysing at average speed 530k positions per second. It lasted 5 sec. so ~2.6M nodes were evaluated.
  
  Let's consider branching factor 3 at each level. Then there are 3^15=14M leaves to evaluate (not taking into account internal nodes). As we see in case of branching factor 3 we have more nodes to analyze (14M) than it really took place (2.6M) (not even considering branches explored deeper than 15).
  
  Branching factor in chess is aproximately 35. I'm aware there are many, many sophisticated techniques to prune branches in search tree. But really from 35 to less than 3? How it's possible that more than 90% of branches are pruned?
  
  Two remarks:
  
  1. Provided parameters/performance come from phase between opening and middlegame. This is NOT taken from ending where branching factor is significantly lower.
  2. Depth 15 is not something unusual. In most cases program performed analysis to depth between 13 and 16 in couple of seconds.
  
  **Tags:** engines, depth
  
  > **Comments:**
  > **username_1**: Assess a random chess position, all the moves but a few will look ridiculous to you. Same way engines can prune branches which start with bad moves.  
  > **username_0**: What is the specific algorithm to do that? Good human player does it intuively and it's hard to provide exact way/algorithm. There are only some psychological researches stating man uses chunks, trajectories, etc.  
  > **username_2**: @username_0 That's what it means to have an efficient evaluation function, which roughly is a superposition of a long set of factors (king safety, material difference, mobility, ...) which are weighted differently from engine to engine. The weights are determined heuristically. Here are many links where this is discussed: https://chess.stackexchange.com/questions/17957/how-to-write-a-chess-evaluation-function or https://chess.stackexchange.com/questions/2204/how-do-chess-engines-think or https://chessprogramming.wikispaces.com/Evaluation  
  > **username_1**: Evaluation function can be used to decide which branches to prune.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2018-03-10. Score: 4
  
  Yes. Chess engines prune moves quite extensively. Chess programming is all about pruning.
  
  When an engine says "search up to depth 15", it really mean depth as in [iterative deepening depth-first search](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search). It **doesn't** mean that the engine attempts to search everything up to depth 15. No good chess engine would search everything to depth 15.
  
  It's complicated, but most of the bad moves should be reduced by depth (or even eliminated), and some critical lines variations extended beyond depth 15.
  
  90% pruning is not uncommon, in fact it'd be more like 99.999999999999999999% according to your definition.
  
  
  ---
  
  