this post was submitted on 20 Dec 2023
158 points (93.9% liked)
Asklemmy
43945 readers
639 users here now
A loosely moderated place to ask open-ended questions
Search asklemmy π
If your post meets the following criteria, it's welcome here!
- Open-ended question
- Not offensive: at this point, we do not have the bandwidth to moderate overtly political discussions. Assume best intent and be excellent to each other.
- Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
- Not ad nauseam inducing: please make sure it is a question that would be new to most members
- An actual topic of discussion
Looking for support?
Looking for a community?
- Lemmyverse: community search
- sub.rehab: maps old subreddits to fediverse options, marks official as such
- !lemmy411@lemmy.ca: a community for finding communities
~Icon~ ~by~ ~@Double_A@discuss.tchncs.de~
founded 5 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
That doesn't seem quite correct for any game meeting those criteria (I'd also add that the game is deterministic - no true randomness in the game either, since that is distinct from state - otherwise the outcome could trivially depend on random events). There are two other possibilities for a deterministic game: that optimal gameplay by both players will always end in the second (or another player if more than two) winning, or that optimal gameplay by both players will result in a game that never ends (impossible for games with a finite number of states, and rule that the game ends in an outcome if the same state recurs too many times - like chess).
A trivial example of a (poor) game that would meets your criterion but where the first player loses under optimal strategy: Players take turns placing a counter anywhere in the play area from an infinite supply of counters. Players cannot skip a turn. If there are an even number of counters on the board after a player's turn, the player who placed the counter can optionally declare victory and win. Not a game I'd play, but it does prove there exist deterministic open state games where one player moves first where the first player will not win or tie.
In a 3+ player deterministic open state game, the actions of a player who goes on to lose could impact which of the remaining players win (they are essentially just a different source of non-determinism).
I think it is correct to say that any two-player deterministic open-state game which can only end in a draw, win, or tie, for any fixed initial conditions, there exists a strategy for one of the two players that will ensure that one of the three outcomes occurs: the game continues forever, that player draws, or that player wins. That can be proved by contradiction: either one or more move in the strategy decision tree can be improved to make the player win, which contradicts the strategy not existing, or the other player can rely on the strategy not existing for the first player to devise a strategy, which also contradicts no strategy existing for either player.
I'm a bit sleepy and ate far too much seafood to process all you've written here presently -- but the specific thing I was referring to is called Zermelo's Theorem. Which is up there for top 10 theories with cool-sounding names, as far as I'm concerned -- here it is in case you're interested (I periodically forget about this theorem and it's always neat to re-find it -- which you could call an... optimally suboptimal move)
https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)