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?
1
-
You could look up quiescence search.– Inertial IgnoranceCommented Sep 28, 2019 at 23:51
Add a comment
|
2 Answers
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.
No. What if recapturing your queen for an exchange is your first candidate move?
answered Aug 16, 2018 at 13:49
-
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. Commented Aug 16, 2018 at 13:56
-
1@mynamejeff What's e? Anyway, 63% acceptance for an automatic queen exchange doesn't work for chess. Commented Aug 16, 2018 at 14:07
-
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%. Commented Aug 16, 2018 at 14:14
-
Maybe the opposite is possible.kind of.Searching the first 63% of the possible moves and choosing the one that's best so far. Commented Aug 20, 2018 at 8:23
-
@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.– AnnatarCommented Aug 21, 2018 at 12:42