0
$\begingroup$

The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and pick the best sequence of moves so far.

Let's suppose we remove this limit, and we search for the whole tree. Would this techinque always win? If the answer is no, would it ever lose? (so, would it only win+draw, or also lose?)

A good answer would include theoretical underpinnings of why or why not this would work, both from the game-theoretic aspects of chess and from the proprieties of the minmax algorithm.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ It might be useful to look at this problem with simpler games, such as tic-tac-toe. Can we force a win with infinite resources in that game? I think you can get a formal proof that minimax reaches the 'best' outcome in any 2 player perfect information game 'for free' with the proof of Zermelo's theorem, so looking there may help. $\endgroup$
    – Discrete lizard ♦
    Commented Jul 22, 2019 at 14:58
  • $\begingroup$ @Discretelizard Why would Zermelo's theorem be needed? It doesn't apply to chess anyway, since chess has draws. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jul 22, 2019 at 16:10
  • 1
    $\begingroup$ @Gilles Well, according to my WP page I linked, there are in fact multiple versions of Zermelo's theorem, of which some include 'draw', and apparently can be applied to chess. I think I got introduced to the version with a draw, but it is possible that the original theorem only has 'win' or 'loss' as a condition. $\endgroup$
    – Discrete lizard ♦
    Commented Jul 22, 2019 at 16:16
  • $\begingroup$ @Gilles The main reason I mentioned the theorem is that I vaguely recalled a proof that relies on the same alternating structure as minimax. I'm not sure, but I thought it was related, at least. $\endgroup$
    – Discrete lizard ♦
    Commented Jul 22, 2019 at 16:18
  • $\begingroup$ @Discrete lizard thank you. This will definetely help a lot. $\endgroup$
    – olinarr
    Commented Jul 22, 2019 at 16:19

2 Answers 2

Reset to default
2
$\begingroup$

By definition, minmax chooses the move that results in the best possible outcome if the adversary plays optimally, but within the bounds of what the evaluation function takes into account. More precisely, minmax results in the best outcome that can be guaranteed no matter how the adversary plays, as long as the adversary's behavior is no worse than what the evaluation function predicts.

If minmax searches on the whole tree, then it never calls the evaluation function, and therefore it models the adversary perfectly. So in this case, minmax achieves the best guaranteed outcome that can be guaranteed against an arbitrary adversary. This is true regardless of the game.

For chess, there are three possible outcomes: win, draw, loss (from best to worst). We don't know what the best guaranteed outcome for each player is. But whatever it is, if you can run minmax on the whole tree, you'll get that outcome or better (the outcome can be better if the adversary plays suboptimally). Of course, this is only practical near the end of the game when there are few pieces remaining in play.

Improve this answer
$\endgroup$
-1
$\begingroup$

Nobody knows if chess is a forced win for white, or even a forced draw for white.

If it is a forced win, then white with optimal gameplay will always win. If it is a forced draw, then white with optimal gameplay will always at least draw, and may win if black doesn't play perfectly. If it is neither a forced win nor a forced draw, then white with optimal gameplay will lose unless black makes a mistake.

If both white and black examine the complete game tree and always play optimally, then the outcome will always be the same (but we don't know if it will be white win, draw, or black win).

The answer to your question is quite trivial, nothing deep to see here or required.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How can I know if something is trivial or not before knowing the answer? I wasn't tryng to do anything bad with that remark, I just thought it made the question clearer. I was not implying I'm onto something deep or anything. $\endgroup$
    – olinarr
    Commented Jul 21, 2019 at 22:26
  • 2
    $\begingroup$ I think the question is more about (whether there exists) a formal proof of the effectiveness of minimax, rather than the fact that it is unknown whether a player can force a win in chess. $\endgroup$
    – Discrete lizard ♦
    Commented Jul 22, 2019 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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