2

I've been running simulations of two strong agents playing Chess which always ended in a draw. Followed by this simulations, can we state that two-player perfect-information games like Go and Chess will always end in a tie when both players play optimally?

9
  • I find your premise that homo economicus is considered the "perfect human" rather questionable. The homo economicus is driven by their rationality, but usually their goal is a self-centered one. This behavior is optimal for the individual, but can be harmful for many others. For as long as the homo economicus is not harmed by the harm inflicted to others, it's rational for them to continue this behavior. Yet, this is only a "perfect human" in the same sense that the robot Ash in the movie Alien describes the predatory alien as "the perfect organism".
    – Schmuddi
    Commented Sep 21, 2019 at 10:06
  • Right. To prevent confusion I guess I'll change it to super-intelligence.
    – Someone
    Commented Sep 21, 2019 at 11:12
  • 2
    In general, this assertion clearly cannot be true. Imagine a game called "Player 1 wins". Here are the complete rules: Player 1 wins. When played by two super-intelligences, this will not end in a tie.
    – Philip Kendall
    Commented Sep 21, 2019 at 14:12
  • @PhilipKendall Well in the question I clearly meant board games like chess or go - so we’re talking about that kind of board games
    – Someone
    Commented Sep 22, 2019 at 5:24
  • 2
    Imagine a turn-based two-player game where on each turn you choose to either say "win" or "pass". If you choose "win", you win. If you choose "pass" the other player gets a turn. It should be trivial from this example that this game will not end in a draw with perfect play.
    – GendoIkari
    Commented Sep 23, 2019 at 14:11

3 Answers 3

Reset to default
23

Accurding to Zermelo's theorem, in finite two-player games of perfect information in which the players move alternately and no affect of chance, one of those three possibilities is true:

  1. First player can always win.
  2. Second player can always win.
  3. Both players can force a draw.

For example, Tic-Tac-Toe is known to have a strategy by both players that will force a draw. In 4-in-a-row it is known that the first player has a winning strategy. Chess haven't been solved yet, I think that the conjecture is that a draw can be forced.

2
  • 1
    On a bit of a tangent, for some games it's possible to prove which of these possibilities is true without knowing the optimal strategy needed to achieve it. For example, if the first player can (effectively) skip their first turn (and if the rules of the game are symmetric for both players) then the second player cannot possibly have a guaranteed winning strategy — if they did, the first player could skip and then use the same strategy to win instead. This is an example of a strategy-stealing argument.
    – Ilmari Karonen
    Commented Sep 24, 2019 at 17:58
  • 1
    @IlmariKaronen, right, this non-constructive proof of the winning player is called Ultra-weak solution. It makes very elegant solutions.
    – Cohensius
    Commented Apr 21, 2020 at 6:15
8

No - there need not always be a tie in the general case. Even in games of perfect complete information there may still be a bias towards one player. For example the game of nim cannot end in a tie, and depending on the starting position gives an advantage to either the first or second player - e.g.

Size of heaps | Result with
A     | B     | perfect play
----------------------------------
1     | 1     | First player wins
2     | 2     | Second player wins

For the specific games you mentioned (go and chess) then it is not known what the result is with perfect play. For more details see the corresponding Wikipedia articles:

3
  • Thank you for your answer! But isn't the Chess article based on statistics of played games (by not that super intelligent humans)?
    – Someone
    Commented Sep 21, 2019 at 11:29
  • 1
    Another well known counterexample: Hex. Perfect information, yet we can trivially prove that the first player has a winning strategy.
    – Philip Kendall
    Commented Sep 21, 2019 at 14:10
  • 1
    @AnatolyWein The chess article covers perfect play, and includes statistics from games played by computers (significantly better than humans) as well as theoretical studies. For example in the opening section it says "White's winning percentage is about the same for tournament games between humans and games between computers" and "Chess is not a solved game, and it is considered unlikely that the game will be solved in the foreseeable future."
    – tttppp
    Commented Sep 21, 2019 at 16:38
1

You are missing a couple of important factors in your question that make it impossible to answer as it stands. Mainly that a game with perfect information available to both players doesn't mean that it is not balanced in one players favor.

While it may be true that there are games out there where it is balanced between both players it is also true that there games where it is not the case it can be balanced in favor of either player (such as the second player is more likely to win which is why they go second).

A secondary point is that there are games where a tie or draw is not possible and if it gets to a point where nothing more can be done a player is declared the victor by default.

You must log in to answer this question.

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