1

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

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.

1

No. What if recapturing your queen for an exchange is your first candidate move?

  • 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. – myname jeff Aug 16 '18 at 13:56
  • 1
    @mynamejeff What's e? Anyway, 63% acceptance for an automatic queen exchange doesn't work for chess. – SmallChess Aug 16 '18 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%. – myname jeff Aug 16 '18 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. – myname jeff Aug 20 '18 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. – Annatar Aug 21 '18 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.