5
$\begingroup$

In turn-based board games with high branching factor (such as chess) are there any arguments that could ascertain the ideal first move but not solve the entire game?

I am asking because solving chess entirely seems infeasible but conceivably one could hope to determine the ideal first moves.

Improve this question
$\endgroup$
8
  • 12
    $\begingroup$ Well, you could have a game where every opening move but one is an immediate loss. For example, modified chess, where the zeroth move is deciding whether to play against Magnus Carlsen or against me. $\endgroup$
    – Gerry Myerson
    Commented Aug 22, 2021 at 6:51
  • $\begingroup$ That is true but I had more "realistic" (which is admittedly vague) games in mind. Like in chess you can't say for sure if e4 or d4 strictly dominates. $\endgroup$
    – magnus
    Commented Aug 22, 2021 at 6:53
  • 1
    $\begingroup$ from the game theoretic point of view all first moves in chess are likely to be equivalent, leading to a draw; from the point of view of an expert player, e4 or d4 are the "best first moves". $\endgroup$
    – Carlo Beenakker
    Commented Aug 22, 2021 at 6:53
  • 4
    $\begingroup$ This may be the opposite of what you want, but for a game with sufficiently symmetric initial conditions you might be able to say any first move will win without explicitly solving the game. For example, some versions of Hex on a torus-shaped board; see mathoverflow.net/questions/282088/study-of-hex-on-the-torus $\endgroup$
    – Martin M. W.
    Commented Aug 22, 2021 at 12:46
  • 2
    $\begingroup$ @CarloBeenakker One could define a variant of chess where players have a $1/1,000,000$ chance each turn of being forced to select each move at random among all legal moves. This would (imperfectly) model chess as played by human experts far beyond the ability of anyone alive now but which still make some mistakes, and it would be very unlikely that two moves are equivalent under this system. I would expect that the moves considered best now are more likely than other moves to be best by such a definition, but not with very high confidence (for multiple reasons). $\endgroup$
    – Will Sawin
    Commented Aug 22, 2021 at 16:41

1 Answer 1

Reset to default
8
$\begingroup$

Setting aside chess in particular, we can certainly come up with games for which we can determine the game-theoretically best move without solving the game in general. For example, it is easy to prove, via a strategy-stealing argument, that a game such as Hex is a first-player win. So you can invent a game called "meta-Hex" in which the first player's first move is to choose whether to be the first player or the second player of a game of Hex, and then to play a game of Hex accordingly. Obviously, the game-theoretically optimal best first move in meta-Hex is to choose to be the first player in a game of Hex. We have figured this out without figuring out how to play Hex (or meta-Hex) optimally in general.

For chess in particular, any kind of rigorous proof about the best first move appears to be hopelessly out of reach. As Carlo Beenakker noted in a comment, the conventional wisdom is that chess is a draw; if true, this might seem to be a favorable situation for mathematical analysis since it would mean that any reasonable first move (and perhaps any first move at all) would probably be game-theoretically optimal. But in practical terms, we cannot expect a mathematical proof. (It is also morally certain that if White gives Black queen odds, then Black has a win, but a mathematical proof of even this seemingly obvious fact seems out of reach.) At the same time, of course, it is even more hopeless to prove that we cannot find such a proof.

It's perhaps worth mentioning Fraenkel and Lichtenstein's paper Computing a perfect strategy for $n\times n$ chess requires time exponential in $n$. This result provides strong circumstantial evidence that there is not going to be a short proof that $8\times 8$ chess is a draw, but of course their result does not actually say anything about $8\times 8$ chess.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I just played a game where I opened f3 and then played whatever Stockfish suggested (for both sides). Black won. $\endgroup$
    – Gerry Myerson
    Commented May 18, 2023 at 7:52
  • $\begingroup$ @GerryMyerson It might be an interesting experiment to take an extreme tablebase position and see what happens when Stockfish plays it out (with tablebases turned off, of course, and ignoring the fifty-move rule). $\endgroup$
    – Timothy Chow
    Commented May 18, 2023 at 11:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .