Answers.Body: <p>The secretary problem is very different from chess move evaluation for several reasons.  First and foremost, the number of chess moves in a given position is finite and usually fairly small (~30 moves in a position).  The second reason is that the cost of choosing a sub-optimal employee is quantifiable and the second best secretary is okay.  In many chess positions there is only one move that is at all reasonable, every alternative will lose the game immediately.</p>
  
  <p>In many chess engines, the most computationally expensive part of determining the best move is generating legal moves.  In the secretary problem, the number of applicants is known.  In chess, once we know the number of legal moves, we have already done some of the heaviest lifting.  </p>
  
  <p>Finally, chess engines already prioritize candidate moves very quickly, the real strength of the engine is selecting the best move out of 2 or 3 moves that have risen to the top of the list.  Chess engines will continue to evaluate all of the legal moves in a position, but they might only go 2 or 3 ply deep for the moves that are less likely to be good moves while searching 40+ ply deep for the moves that are under active consideration.  This is called pruning and its development is one of the main improvements in newer chess engines over the earliest chess engines.  </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-22T18:30:53.453Z
Answers.LastActivityDate: 2018-08-22T18:30:53.453Z
Answers.UserDisplayName: Andrew
Answers.Body: <p>No. What if recapturing your queen for an exchange is your first 
  candidate move?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T13:56:37.890Z
Answers.Text: The probability of rejecting such important of a move is (#possible moves / e), which means there's a 63% chance that it won't be missed which is more often than not the case.It still is a pretty high percentage,i get your point.
Answers.UserDisplayName: myname jeff
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T14:07:45.290Z
Answers.Text: @mynamejeff What's e? Anyway, 63% acceptance for an automatic queen exchange doesn't work for chess.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T14:14:56.917Z
Answers.Text: e is Euler's constant = 2.718.And yeah,it won't work most probably.Btw the probability that the selected move is the best move is again ~37%.
Answers.UserDisplayName: myname jeff
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-20T08:23:47.183Z
Answers.Text: Maybe the opposite is possible.kind of.Searching the first 63% of the possible moves and choosing the one that's best so far.
Answers.UserDisplayName: myname jeff
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-21T12:42:10.177Z
Answers.Text: @mynamejeff If you make sure that all capturing moves are in the first 63%... then you get something that engines already do (pruning), only less sophisticated than their methods.
Answers.UserDisplayName: Annatar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-21T12:46:11.863Z
Answers.Text: So do you think this method is sound? and if so ,is that all capturing moves are in the first 63% ,the only criteria for it to work reasonably well?
Answers.UserDisplayName: myname jeff
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-21T13:11:19.840Z
Answers.Text: @mynamejeff No and no. Capturing moves should have higher priority, but it doesn't end there. Your method version 2 (capturing first) will still miss 37% of non-capturing knight forks, for example.
Answers.UserDisplayName: Annatar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-21T13:19:57.100Z
Answers.Text: The point is: Chess is not gambling. Moves happen for reasons. If it has good reasons, it's totally fine for an engine to discard moves (e.g. if they fail to defend against a threatened mate). Filling an arbitrary quota is NOT a good reason, no matter how you rearrange the moves.
Answers.UserDisplayName: Annatar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T13:49:52.570Z
Answers.LastActivityDate: 2018-08-16T13:49:52.570Z
Answers.UserDisplayName: SmallChess
Body: <p>Can the solution to the famous Secretary Problem be applied to the search function of a chess engine? Rejecting the first 37% moves and choosing the best one after that,or maybe even just checking the first 63% of the moves and choosing the best one so far?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-28T23:51:39.020Z
Comments.Text: You could look up quiescence search.
Comments.UserDisplayName: Inertial Ignorance
Tags: <engines><programming><statistics>
Title: Can an Optimal Stopping strategy be applied to search functions?
ThreadText: # Can an Optimal Stopping strategy be applied to search functions?
  
  (Asked by: username_0 on 2018-08-16)
  
  Can the solution to the famous Secretary Problem be applied to the search function of a chess engine? Rejecting the first 37% moves and choosing the best one after that,or maybe even just checking the first 63% of the moves and choosing the best one so far?
  
  **Tags:** engines, programming, statistics
  
  > **Comments:**
  > **username_1**: You could look up quiescence search.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2018-08-22. Score: 1 | Accepted answer
  
  The secretary problem is very different from chess move evaluation for several reasons. First and foremost, the number of chess moves in a given position is finite and usually fairly small (~30 moves in a position). The second reason is that the cost of choosing a sub-optimal employee is quantifiable and the second best secretary is okay. In many chess positions there is only one move that is at all reasonable, every alternative will lose the game immediately.
  
  In many chess engines, the most computationally expensive part of determining the best move is generating legal moves. In the secretary problem, the number of applicants is known. In chess, once we know the number of legal moves, we have already done some of the heaviest lifting.
  
  Finally, chess engines already prioritize candidate moves very quickly, the real strength of the engine is selecting the best move out of 2 or 3 moves that have risen to the top of the list. Chess engines will continue to evaluate all of the legal moves in a position, but they might only go 2 or 3 ply deep for the moves that are less likely to be good moves while searching 40+ ply deep for the moves that are under active consideration. This is called pruning and its development is one of the main improvements in newer chess engines over the earliest chess engines.
  
  
  ---
  
  ### Answer by username_3 on 2018-08-16. Score: 1
  
  No. What if recapturing your queen for an exchange is your first
  candidate move?
  
  > **Comments:**
  > **username_0**: The probability of rejecting such important of a move is (#possible moves / e), which means there's a 63% chance that it won't be missed which is more often than not the case.It still is a pretty high percentage,i get your point.  
  > **username_3**: @mynamejeff What's e? Anyway, 63% acceptance for an automatic queen exchange doesn't work for chess.  
  > **username_0**: e is Euler's constant = 2.718.And yeah,it won't work most probably.Btw the probability that the selected move is the best move is again ~37%.  
  > **username_0**: Maybe the opposite is possible.kind of.Searching the first 63% of the possible moves and choosing the one that's best so far.  
  > **username_4**: @mynamejeff If you make sure that all capturing moves are in the first 63%... then you get something that engines already do (pruning), only less sophisticated than their methods.  
  > **username_0**: So do you think this method is sound? and if so ,is that all capturing moves are in the first 63% ,the only criteria for it to work reasonably well?  
  > **username_4**: @mynamejeff No and no. Capturing moves should have higher priority, but it doesn't end there. Your method version 2 (capturing first) will still miss 37% of non-capturing knight forks, for example.  
  > **username_4**: The point is: Chess is not gambling. Moves happen for reasons. If it has good reasons, it's totally fine for an engine to discard moves (e.g. if they fail to defend against a threatened mate). Filling an arbitrary quota is NOT a good reason, no matter how you rearrange the moves.  
  
  ---
  
  