Disproving game theory.
In any sufficiently complex game, given enough iterations, it can be demonstrated that both players become hyper-rational, and thus a winning strategy cannot be entertained.
Analogously, think about chess for a moment. Given that chess is the oldest game in human history, and given that it is deterministic, then through enough iterations it can be demonstrated that both players, given a sufficiently long backlog of past historical games, are going to face situations where winning becomes... impossible.
What is left to entertain is simply a mistake committed by either player to ensure victory. Since both players, given enough iterations, become hyper-rational, then winning becomes impossible, and the game looses its "fun-factor".
I believe the analogy can be demonstrated for ANY deterministic game, and thus, game theory has been refuted for any deterministic game.
Thoughts?
Analogously, think about chess for a moment. Given that chess is the oldest game in human history, and given that it is deterministic, then through enough iterations it can be demonstrated that both players, given a sufficiently long backlog of past historical games, are going to face situations where winning becomes... impossible.
What is left to entertain is simply a mistake committed by either player to ensure victory. Since both players, given enough iterations, become hyper-rational, then winning becomes impossible, and the game looses its "fun-factor".
I believe the analogy can be demonstrated for ANY deterministic game, and thus, game theory has been refuted for any deterministic game.
Thoughts?
Comments (76)
The larger truth here is that game theory, ought and should not be applied to reality, which indicates a disdain towards strategic outcomes derived from a rote logic of binary or higher order...
You have a point. But your point holds up much more with tic-tac-toe than chess. For chess, a computer could possibly "memorize" the nearly infinite iterations of the game. But a person would never get there. Now to be fair, more experience with the game leads to MORE ability to create a stalemate, but unlike tic-tac-toe where 2 reasonably informed people will ALWAYS end in stalemate, chess would at best OCCASIONALLY end in stalemate, because no human could memorize every possibility. And if I remember correctly, the game "Go" has far more potential iterations than chess, so it would be even less possible to know enough to consistently reach a stalemate.
Given a sufficiently long enough interval to analyze all the potential iterations of a game, then a human being would become no different than a hyper-rational computer.
True or false?
I would say false. Let's say 50 years was enough time for me to view EVERY iteration possible in a chess game. Unfortunately, by the second year any normal human is already forgetting large chunks of the first year.
Am I missing something?
And a quick google search has the number of iterations in a chess game somewhere between 10 to the 111th power and 10 to the 123rd power, so 50 years is not going to be enough. (and "Go" is vastly more complex...more iterations than atoms in the universe).
I once memorized the periodic table for shits a giggles...yes, I am a real fun person, haha. After 3 MONTHS of totally ignoring the table, I was already forgetting portions. I am sure there are people with much better memories, but I have never heard of THAT much better.
Overall, I don't think you are wrong, just that, currently, humans are not capable of such feats. And our inability to memorize the totality of anything even a little complex (if we are counting chess or Go as complex, surely war or economics are vastly more complicated?), is why game theory would hold some applicability?
There is no question in my mind that you understand game theory better than I do, so if you feel my analysis is missing something related to the small details of game theory, feel free to let me know.
Yeah. I'm not quite sure if the point can be made with algorithms with infinite prior elasticity, manifesting in decisions that are strategically absolute, but I suppose the larger point that you sort of bring up is that despite however hard one might want to eliminate mistake making from human rationality, then mistakes will inevitably be made.
Kinda scary?
Quoting Shawn
That is a much simpler way of saying it :up:
Quoting Shawn
It would be, if I wasn't so deeply conditioned to human fallibility :grimace:
Would you provide a source for this assertion, please. Thanks.
I actually came it up by myself as incredible as that sounds. I reached out to some mathematician friends to do a 3D analysis if possible.
Would you be able to help out?
I believe mathematical theories are not the same as scientific theories in that they can be disproved. :chin:
That's not true. There are games for which one side or the other has a winning strategy.
Quoting Shawn
If you have such a demonstration it's publishable as the solution to an open problem. At present nobody knows whether white, with the first move, has a forced win or not.
Why not?
Quoting fishfry
Oh, like chess? Have you played chess against a computer?
Why don't you test it out. Set a chess engine like Rybka, against Shredder, or Rybka vs Rybka, and see what happens?
This has nothing to do with the well-known fact that it is an open question as to whether white has a forced win with perfect play on both sides.
You have claimed a demonstration, your word, to the contrary. Have you got a link?
It's certainly the case that some games with perfect information (both sides know the current state of the game at all times) do have winning strategies. The example I thought of is a little technical but it's an interesting story I happen to know so I'll talk a little about it.
To be fair this is an infinitary game, it consists of a countably infinite sequence of moves. When mathematicians talk about game theory this is one class of games that's studied.
Choose a subset of the closed unit interval, [math]X \subset [0,1][/math]. There are two players, Alice and Bob as they're often called in these scenarios. Alice goes first, choosing a zero or a one. Bob then chooses a zero or a one, and so forth. They continue for a countably infinite sequence of moves, defining an infinite sequence of zeros and ones.
If you put an implied binary point in front of the resulting string, you have the binary representation of some real number in the unit interval. If that real number is in [math]X[/math] Alice wins; otherwise Bob wins.
Is there a winning strategy for Alice or Bob? Clearly it depends on which set [math]X[/math] we choose. For example suppose [math]X = [0, \frac{1}{2})[/math]. That's the half-interval that includes 0 but excludes 1/2. Then Alice chooses 0 as her first move, and no matter what Bob does, Alice has already won the game.
I hope this example is clear. Any binary number .0xxxxxanything is automatically in the left half of the unit interval.
So it's clear that at least for SOME sets, there is a winning strategy for one player or the other.
The statement For every set there is a winning strategy is known as the axiom of determinacy. It's one of the alternative axioms set theorists like to play with. It's inconsistent with the axiom of choice which is why it's not generally adopted. It's been proven true for various interesting classes of set of reals.
[The description of the game in the Wiki article is a little different than how I described it but it's equivalent].
I admit this is the example that popped into my head when you claimed that with perfect play all games must be draws. This is not true.
Even for finite games, which can in principle be completely analyzed, some games have winning strategies and others don't. And as far as chess is concerned, it's unknown whether there is a winning strategy. The problem space is so vast that even though it's finite, our current computers can't evaluate the entire game tree.
ps -- Here is a reference for the solvability of chess.
https://en.wikipedia.org/wiki/Solving_chess
Are you trying to point out that natural advantageous positions exist? Yeah, sure. But, even in chess, where white get's the first move, or utilizes the strongest opening, being the Italian, it still is tantamount to having a player that is super-rational as black deciding that a stalemate is the only winning strategy.
This is basic game theory, 101. Should I go on?
By all means, since you claim a solution to an open problem.
Winning strategies is something that can only exist for participants of a deterministic game where mistakes can be made. Once you have a super-rational player that is immune from making mistakes via forward and backward induction, along with no asymmetrical information problems, then winning becomes next to impossible.
Agree?
No, that's simply wrong. There are games in which one player or the other has a forced win with perfect play on both sides. I gave you an example of one earlier.
Doesn't count. Otherwise it wouldn't be much of a game if one had to memorize a certain causal chain in a deterministic tree to ensure victory at all times.
Does that make sense?
No, that's not what game theory's about. You seem more interested in the practical aspects of playing games. In that light your comments make more sense. When I think of game theory I think of the formal mathematical discipline of that name.
A game theoretic scenario entails that both players have an equal chance at winning... But, once you introduce the notion of a developing and advancement, through numerous iterations, and thus, hyper-rational players, then in some sense any notions of winning in a deterministic game becomes obsolete.
There are mathematical games in which one or the other player has a forced win with perfect play. You're redefining what game theory means. I'm curious. Where are you getting your definition from? You're correct that memorizing perfect play wouldn't be fun; but the idea of game theory is abstract, it's not about you and Uncle Fred sitting down for a friendly game of checkers.
https://en.wikipedia.org/wiki/Solved_game
Hello Nagase,
What are your thoughts about the first sentiment proposed in this thread, about games being unitary or zero-sum, after an exhaustive method of rote analysis of winning and counter-winning strategies?
Well, it is wrong, if it is implying that no deterministic game of perfect information can have a winning strategy for one of the players; indeed, I just gave you a counter-example (Hex). You seem to be supposing that (e.g.) the second-player can, by rote analysis, always find a counter-move to the first player, but this is highly non-trivial, and, in fact, false, as the example of Hex illustrates. The first-player may have a strategy that (i) either forces the second player to make a series of moves or else (ii) makes the moves of the second player irrelevant.
Perfect information seems to be irrelevant here. The point is that stochastically it would become deterministic after enough iterations of game playing, assuming that learning is possible.
If there is a deterministic game of perfect information with a winning strategy for one of the players, then, a fortiori, there is a deterministic game with a winning strategy for one of the players. So I don't understand your point.
Well, yes, as this applies to any deterministic game, correct?
What is the reference of "this"?
Assuming it is inconsequential if any player has a strategy that is infallible. And, if they do, then the game is no longer worth playing if no winning strategy can be entertained as a player with (n+1) move, with the player with the first move always winning.
Sorry for being dense, but I don't understand what property you're referring to in your last post. It seems to be talking about conditions for a game not to be worth playing, but I'm afraid I just didn't get it.
Let me be simple. If a player can't win a game, then what's the point of playing it?
I mean, everyone wants to start out as white when playing chess if there's money or financial reward for the simple fact of winning, correct?
I suppose there could be other motives, such as boredom, incredulity, or simply to better understand why you can't win. Incidentally, note that the existence of a winning strategy for one of the players does not mean that in an actual, particular play, one of the players is guaranteed to win. Maybe he doesn't know the strategy, maybe nobody knows the strategy, maybe he knows the strategy but has forgotten it, maybe there is a strategy but nobody can follow it because it is too complicated, etc.
As for chess, I don't think everyone wants to start out as white. For some time I personally was more comfortable playing black, and I think many players don't mind playing either way. And in any case, it's not clear that there is a winning strategy for white. Either black or white has a strategy for not losing (i.e. at worst to force a draw), but nobody knows which. It could be black's.
Well, think of it analogously towards such things where game theory is applied, such as warfare scenarios or nuclear warfare.
Does that help?
No, it does not help at all. I'm beginning to lose track of what is your point. At first, I thought you were (erroneously) claiming that there can be no winning strategies for any games, since, supposedly, players could readily adapt to any such strategy through rote training or whatever. Now you seem to be claiming that a game with a winning strategy for one of the players would be pointless to play, to which I replied that (i) the existence of a winning strategy does not imply that a particular play is determined, since, for a variety of reasons, it could be that the player with the winning strategy has no access to it and (ii) in any case people could want to play the game for a variety of reasons other than winning. Finally, you seem to claim in your last post that there is some kind of problem with applied game theory, but you don't indicate what the problem is or how it is remotely related to the fact that some games (like Hex) have a winning strategy for one of the players. So I'm kind of lost...
Yeah, this is pretty much what I'm getting at. Namely, the nonsense of applying game theory to real world problems.
Let me elaborate with a real life example.
Let's take the case of Mutually Assured Destruction. If game theory leads us to assure a suicide pact between two opposing nations, then we ought to reject it, or not?
Reject the pact or reject the applicability of game theory?
In any case, as with any mathematical formalism, game theory provides an ideal model of certain situations which involve strategic behavior. It is a model, in that it serves to highlight certain causal or structural dependencies of a given phenomenon (in this case, strategic behavior); it is ideal, because it involves a deliberate falsification of reality for simplification purposes (cf., among many others, the work of Nancy Cartwright and of Angela Potochnik for more on this). So I don't think applying game theory to reality is anymore nonsense than applying the Lotka-Volterra equations to study population equilibrium or the use of infinite populations in certain models to screen off genetic drift considerations, or even the application of ideal gas laws to explain the behavior of gases.
Yes, well we actually have a working model of game theory in practice in perhaps its most extreme form, being Mutually Assured Destruction.
Again the point about super-rational players is an inconvenient truth about the applicability of game theory manifest, yes?
Nobody likes super-rational players for the matter, as they can't be reasoned within, or from, dominant strategies.
I really don't understand what you're getting at. What exactly is your point?
Fishfry in particular has opened my eyes to modern set theory, but others have as well. And for game theory, I knew that Nash had used attractive fixed points but I now learn he employed a result I was unaware of, a set theory extension of Brouwer's Fixed Point theorem by Kakutani:
https://en.wikipedia.org/wiki/Kakutani_fixed-point_theorem
Brouwer's Theorem provides an existence result, but doesn't give an algorithm for reaching this point. I am quite familiar with Banach's Fixed Point Theorem (having generalized his result for infinite compositions of functions rather than iteration of a single function - there are dozens of generalizations!) which does describe a simple algorithm.
( https://www.coloradomesa.edu/math-stat/catcf/papers/banach-extension-theorem.pdf }
OK, I'm done. :cool:
That through enough iterations in any deterministic game, then advantageous situations are known prior to making a decision on the decision tree, and hence, the chance of winning becomes very small.
I hope that made some sense.
I've already replied to this in my second post in this thread: one of the players may be able to force the other to perform certain moves, or perhaps the other player's moves are somehow irrelevant (think of forced checkmates). That is, it may be that there are no advantageous situations in the decision tree of one of the players to be known.
Yes, so if that's the case that everyone wants to start out as white in chess, because there is a natural advantage to starting as white, then the game becomes meaningless for both players if an assured victory can always be entertained as white.
Notice that a perpetual stalemate is tantamount to the above.
But we don't know whether it is white that has the winning strategy. It may be black (or neither).
Statistically, white wins the majority of games against black. But, that's irrelevant to the point I'm trying to make about given enough iterations that both players at best would be able to enjoy a stalemate.
The case with humans, comparatively to warfare is that if both players have an absolute deterrent, then the notion of a zero sum game becomes irrelevant. Furthermore, if one of the players makes a mistake, then that spells doom for us all...
But it is not a matter of statistics, it is a matter of whether there is a winning strategy or not. For all we know about chess, maybe white has a winning strategy, maybe black, maybe neither (that is, maybe the best strategy leads to draw).
Yes, and all that hinges on whether the other player is;
1. Less informed.
2. Less rational.
3. Less motivated.
Once you have enough iterations and sufficiently motivated players, then whoever has the first move, will dominate the game if we strictly are talking about chess. I don't think the same applies for Hex, as you mentioned.
If you apply this same line of reasoning to such instances where both players have to be MORE, motivated, rational, and informed, then you have super-rational players.
First, the psychological conditions of the players are irrelevant. Either there is, or there isn't a winning strategy. This can be determined entirely by analyzing the space of the play, and is independent of such extrinsic factors.
Second, your claim that the first player will "dominate" the game is, again, pure speculation. We don't know that! If you do, I suggest that you write your proof and send it to a reputable journal on Game Theory.
We don't know if that's true of chess but it is true of Connect 4. I used to play against a computer that played a perfect game to try to learn what moves I should do when playing other people (I played a lot of Connect 4 in Thailand). Sometimes people like to play even if they're guaranteed to lose.
https://www.chessgames.com/chessstats.html
Years covered: 1475 to 2020 (546 years)
All time controls (946,291 games)
White wins 357,549 games (37.78%)
Black wins 266,196 games (28.13%)
322,520 games are drawn (34.08%)
Again, statistics are irrelevant for a mathematical proof that white has a winning strategy! I don't know what else to say in this regard.
Why is that so? Quite an interesting subject...
Namely, I still stand by the notion that for any deterministic game, humans or a CPU, will eventually solve the game. This happens for humans, in a similar manner, although in much larger time-frames than the CPU to elucidate the winning strategy for themselves.
The downside with this argument is that it is probably near impossible to find two human players at the same equilibrium point to entertain the notion that either side has a more rational player.
Therefore, it seems like we have to constrain the sentiment of two super-rational players that never make mistakes and are infallible with regard to the first move of the player or the response to the first move, et cetera.
With that said, I still believe that humans have the capacity to become super-rational, albeit not in the infallible manner of a CPU opponent. Although, in my opinion this thought is subject to scrutiny after realizing that white, statistically, is a winning player contrary to starting out as black, and that's quite profound in my opinion.
I think the statistics of which side wins is sufficient proof. Just that you don't think statistics matters here, which I find puzzling.
I'd be ecstatic if someone could demonstrate the two hyper-rational players would prevent victory from happening for either side, unless a mistake were made for either players. This would apply to games with a finite amount of moves for either player, meaning that the game is deterministic...
A proof is a sequence of statements each of which is justified by appeal to an axiom or to some previously justified (i.e. proved) statement. Statistics are not proof; they are at best heuristics. Otherwise, the Riemann Hypothesis and the Goldbach Conjecture would be considered proved by now. The problem is obvious: even if all the even integers greater than 2 tested so far have been found to be the sum of two primes, that is no guarantee that tomorrow we will not find one that is not a sum of two primes. Similarly, even if statistics show that there is a bias towards white winning, this is very far from a proof that white has a winning strategy. Perhaps this bias is explained by some quirk in human psychology, or perhaps in the next couple of years we will see a reversal towards black winning.
So much for mathematics, if reality has no bearing on the truth of certain mathematical statements.
Well, statistics is a branch of mathematics, so...
Nevertheless, here is another way of formulating my worry. The statistics you provided show a correlation between a player choosing white and the player winning. As anyone knows, however, correlation is not necessarily causation, i.e. just because two factors are correlated does not mean one causes the other. In order for the correlation to be a reliable indicator of causation, you need at least to screen off other potential causes, be it potential causes of white winning or potential joint causes of a player choosing white and winning. For example, perhaps there is a bias in strong players to choose white, not because white has an advantage, but because they like shiny white pieces. Or perhaps there is an odd psychological quirk that gives advantages to chess players when they go first. How do we eliminate such possibilities?
One way is to run experiments to rule out such odd explanations. But how can we rule out every other explanation? Here, experiments will be of no help. Fortunately, in the case of chess, there is another route available: we prove from a mathematical description of the game that white has a winning strategy. This way, we can show that the statistics are not merely reflecting an accidental correlation, but are actually a symptom of an underlying structural fact about chess.
Well. I believe that there is some kind of hidden hand operating in the background for deterministic games, such as chess, which would narrow down the correlation and causation aspect of white winning on average, rather than black.
It would be indeed strange to psychologize the issue and say that playing white brings in a false positive in terms of bias or some such reason.
But positing a "hidden hand" is just another way of saying that you believe that there is a structural feature of chess which explains the correlation. And this is exactly what requires proof, so that you can screen off the other explanations. Note also that causality is not merely statistical correlation; if you're saying that something has a cause, you're effectively saying that there is an underlying mechanism that explains how this something is produced. So this mechanism should be explanatory; a "hidden hand" falls short of this explanation, unless it is merely a placeholder for a structural feature, in which case we're back to the need for a proof.
For checkers it was proven so it lost its appeal to me.
When someone will prove that chess also always ends in a draw it will lose its appeal to me too.
How about NHL 2013, quite a hard game to master.
:-)
But, given that the game is deterministic, that's a plausible outcome for chess, if white doesn't have a natural advantage over black, yes?
Like in the westerners, the first one to shoot usually wins... :-D
https://www.youtube.com/watch?v=CTt1vk9nM9c
If you refute any of the fundamental propositions of a theory, doesn't that effectively refute the theory?
Chess to some measure is confined to a chess board. The universe and reality is a chess board with trillions of trillions of spaces on the board. Victory or defeat out here is much more of a spectrum. I understand chess is extremely complicated though.
I half way understand what you are saying. If you are saying the theory is atleast slightly flawed, i'm not sure any of us could argue with that.
When i was in college they gave us a very banal explanation of the theory using prisoners and testimonies. Lets not forget when one guy goes to prison he might find a real nice friend (unlikely) and enjoy his meals for whatever reason. lol
The point is its possible to not completely lose or completely win.
Have a good day, Sir!
now that i think about it i never read alot about game theory and college only offered the banal example. I don't understand your OP.
Not really. Every game is inherently deterministic. Reality seems to have an element of non-determinism in it.
thats fair.
Read my last post.