Discuss:Mathematics, Logic, Philosophy:Infinite Games
From da Vinci Concept
Chat - Sept 9 12:01:00 2006
Henrik Nordmark (12:04:01 PM): I am taking a class on Infinite Games that seems very cool.
Sunny (12:04:31 PM): By 'Infinite Games' do you mean MMORGs?
Henrik Nordmark (12:05:11 PM): MMORG
Henrik Nordmark (12:05:16 PM): ?
Sunny (12:05:33 PM): Massive Multiplayer Online Role-Playing Game
Sunny (12:05:50 PM): Most of these do not have an end or any fixed outcome.
Henrik Nordmark (12:06:07 PM): I C
Henrik Nordmark (12:06:14 PM): then, no.
Henrik Nordmark (12:06:38 PM): Infinite Games as in games that last more than finitely many rounds
Sunny (12:08:35 PM): You do mean, 'can' last more than finitely many rounds, as I don't see anyone completing an infinite game, placing it in the past tense.
Henrik Nordmark (12:08:57 PM): hehehehehe...
Sunny (12:09:00 PM): Hmm.. rather, I mean to say that we would start, but then eventually quit.
Henrik Nordmark (12:09:02 PM): well...
Henrik Nordmark (12:09:30 PM): Hmmmm...
Henrik Nordmark (12:09:46 PM): The idea is to take some concepts from game theory
Sunny (12:09:48 PM): Or we die off and the game ends because there is no one to play.
Henrik Nordmark (12:10:11 PM): and then generalize them using concepts from set theory
Henrik Nordmark (12:10:22 PM): in particular infinite ordinals
Henrik Nordmark (12:10:53 PM): and in this sense you can have games that last omega many rounds
Henrik Nordmark (12:11:09 PM): where omega is the smallest infinite ordinal
Sunny (12:11:25 PM): Like the global economy, with its many facets, and ever changing rules. But in application, the game can end.
Henrik Nordmark (12:12:08 PM): in this mathematical abstraction, both players live infinitely long so no worries about death.
Henrik Nordmark (12:13:02 PM): Most games can be put into the following form
Sunny (12:13:04 PM): Sure, that tells you that the game is capable of lasting infinite rounds. What about games that are capable of either?
Henrik Nordmark (12:13:14 PM): Player one plays x1
Henrik Nordmark (12:13:22 PM): Player 2 plays x2
Henrik Nordmark (12:13:35 PM): Player 1 plays x3...
Henrik Nordmark (12:13:38 PM): etc,,,
Sunny (12:13:54 PM): A checkmate or stalemate is possible in chess, but then you decide that either are valid stopping points.
Henrik Nordmark (12:14:05 PM): this generates an infinite sequence: x1, x2, x3, x4, x5 ...
Sunny (12:14:12 PM): Even though a stalemate is in essence infinite.
Henrik Nordmark (12:14:44 PM): then IF this infinite sequence belongs to some set A, player 1 wins
Henrik Nordmark (12:14:53 PM): if it doesn't belong to A
Henrik Nordmark (12:14:59 PM): then player 2 wins.
Sunny (12:15:36 PM): So, you are talking more about playing games with infinite sets? And set construction as a game?
Henrik Nordmark (12:16:06 PM): it's about constructing sequences
Henrik Nordmark (12:16:41 PM): and each of the two players try to force a certain outcome
Sunny (12:16:46 PM): That sounds sort of unfair to player 1 as all of the burden is on their ability to counter the noise that player 2 creates such that a set A exists.
Henrik Nordmark (12:16:58 PM): hehehehehehe...
Sunny (12:17:11 PM): Is set A predetermined, or does it represent ANY valid set.
Henrik Nordmark (12:17:21 PM): it very strongly depends on the complexity of set A.
Henrik Nordmark (12:17:49 PM): set A is a parameter of the game that gets decided before the game begins
Sunny (12:18:11 PM): How about two sets that are non-orthogonal, player 1 must construct set A of a given class and player 2 must construct set B of a related class.
Henrik Nordmark (12:18:41 PM): this is also possible
Sunny (12:18:52 PM): could it be determined in less than an infinite number of steps that the construction of set A has failed?
Henrik Nordmark (12:18:57 PM): however then there is no guarantee that there will be a winner
Sunny (12:19:04 PM): Such as the stopping points common in chess?
Henrik Nordmark (12:19:04 PM): there could be stalemate
Sunny (12:19:26 PM): (i.e. the set of only black OR white pieces)
Henrik Nordmark (12:19:50 PM): yes, sometimes one of the two players will have a winning strategy from some point onwards in the game
Sunny (12:20:28 PM): Maybe not a guarantee before the game is played, but could a very good player 1 reach the stopping point before an infinite number of steps has passed?
Henrik Nordmark (12:20:40 PM): In the finite case, one can prove that all perfect information games of two players are determined
Henrik Nordmark (12:21:06 PM): i.e. one of the two players has a winning strategy from the very beginning of the game
Henrik Nordmark (12:21:16 PM): I think John Nash proved this.
Sunny (12:21:43 PM): How is chess defined in the context of infinite games? Finite or infinite?
Sunny (12:21:52 PM): I certainly know which type I'd rather play.
Sunny (12:21:56 PM):
Henrik Nordmark (12:22:44 PM): Assuming you do not put an artificial time constraint, chess is an infinite game
Henrik Nordmark (12:22:58 PM): in the sense that you can reach a stalemate
Henrik Nordmark (12:23:12 PM): where nobody can win and things go on forever.
Sunny (12:23:29 PM): But just because it is possible that it is infinite, the whole point of the game is in foreshortening the stopping point, in reaching conclusion.
Sunny (12:23:52 PM): Is this the purpose of all infinite games, or are there games that have the converse purpose?
Henrik Nordmark (12:24:39 PM): well in most infinite games studied by set theorists, you presume that the game will always last infinitely many rounds
Henrik Nordmark (12:24:42 PM): BUT
Sunny (12:24:48 PM): Perhaps like playing chess where the purpose for one (or both players) is in achieving stalemate.
Henrik Nordmark (12:25:13 PM): there are usually clearly established winning conditions after these infinitely many rounds.
Henrik Nordmark (12:25:33 PM): right
Henrik Nordmark (12:26:19 PM): If the goal is to reach stalemate, then that would be analogous to creating an infinite sequence of a certain type.
Sunny (12:26:20 PM): If you could construct such a board game the winner would have to prove that they had reached conditions that would always result in the construction of set A.
Henrik Nordmark (12:26:34 PM): correct
Sunny (12:27:02 PM): But the purpose of the game, oddly enough, would be to achieve this goal before an infinite number of steps had transpired!
Henrik Nordmark (12:27:11 PM): right!
Sunny (12:27:55 PM): If you can't recognize stalemate, (in a game where stalemate is the stopping point) then you can't win.
Henrik Nordmark (12:28:18 PM): What is cool about infinite games is that it provides you with a method to measure the complexity of sets.
Sunny (12:28:51 PM): Meaning a measure of the minimum(?) number of steps that must be taken to construct the set?
Henrik Nordmark (12:30:06 PM): Whether player 1 has a winning strategy depends on how complex A is.
Henrik Nordmark (12:30:40 PM): Actually that's not quite right
Henrik Nordmark (12:30:58 PM): whether the game is determined depends on the complexity of A.
Sunny (12:31:00 PM): Or perhaps, the complexity of A might determine whether player 1 can construct a winning strategy in a given number of turns.
Henrik Nordmark (12:31:32 PM): The more complex A is the less likely it is that either of the two players will have a winning strategy.
Sunny (12:31:46 PM): Or the longer it will take them to reach it, right?
Henrik Nordmark (12:31:55 PM): hehehehehehehe...
Henrik Nordmark (12:32:05 PM): it is interesting you mention that!
Henrik Nordmark (12:32:46 PM): the first example of an infinite game one sees is one that lasts omega many rounds
Henrik Nordmark (12:33:09 PM): but you can have one that lasts omega + 3 rounds..
Henrik Nordmark (12:33:19 PM): or omega + 517 rounds
Henrik Nordmark (12:33:29 PM): or omega + omega rounds
Sunny (12:33:33 PM): Or root(omega)?
Henrik Nordmark (12:33:45 PM): hmmmm...
Henrik Nordmark (12:33:55 PM): not sure what that would mean
Henrik Nordmark (12:34:10 PM): but you definitely have omega squared
Sunny (12:34:21 PM): The stopping condition could be less than omega.
Henrik Nordmark (12:34:23 PM): or even omega to the power of omega
Sunny (12:34:36 PM): Even omega/omega?
Henrik Nordmark (12:35:07 PM): As far as I know, ordinal division has not been invented by anybody
Henrik Nordmark (12:35:22 PM): so I can't really say what that would mean.
Sunny (12:36:16 PM): Can you have an infinite game that lasts omega - 3 rounds?
Henrik Nordmark (12:36:43 PM): yes, however...
Henrik Nordmark (12:36:56 PM): it turns out that omega - 3 = omega
Henrik Nordmark (12:37:33 PM): the longer these games get in umber of rounds
Henrik Nordmark (12:37:45 PM): the more weird stuff starts happening.
Sunny (12:37:55 PM): Like what?
Henrik Nordmark (12:38:15 PM): Well, if you assume AD
Henrik Nordmark (12:38:23 PM): the axiom of determinacy
Henrik Nordmark (12:38:52 PM): and you allow for games that last more than omega 1 rounds
Henrik Nordmark (12:39:13 PM): then you can show mathematics to be inconsistent.
Henrik Nordmark (12:40:15 PM): or at the very least you have to give up on the axiom of choice
Henrik Nordmark (12:40:37 PM): which is something most mathematicians are unwilling to do.
Sunny (12:41:19 PM): That just means that there is a hidden assumption within the basic construction of the system of infinite games that you are studying.
Sunny (12:41:37 PM): Or within the mathematics that you are using to describe it.
Henrik Nordmark (12:41:47 PM): there are no "hidden" assumptions
Henrik Nordmark (12:41:57 PM): the assumption is quite explicit
Henrik Nordmark (12:42:03 PM): the assumption is AD
Sunny (12:42:47 PM): I didn't mean that assumption, I meant an assumption within set theory or within the definite of infinite games.
Henrik Nordmark (12:43:04 PM): AD states that ALL infinite games of a certain type have a winning strategy for one of the two players.
Henrik Nordmark (12:43:21 PM): hmmmmm...
Henrik Nordmark (12:43:26 PM): well...
Henrik Nordmark (12:43:52 PM): the only other thing one assumes besides AD are the standard ZF axioms...
Sunny (12:44:59 PM): I'm just saying that if a contradiction exists, it is due to a sort of hidden agenda of the underlying mathematics and thus the axioms that these mathematics are based.
Henrik Nordmark (12:45:41 PM): well... yes... it would definitely seem like that...
Henrik Nordmark (12:46:12 PM): And because the standard ZF axioms seem so incredibly uncontroversial...
Henrik Nordmark (12:46:34 PM): it would seem more logical to be suspicious of AD.
Henrik Nordmark (12:47:48 PM): As far as we know, ZF+AD is ok.
Sunny (12:47:48 PM): Only in context. If you change the context of application, even application within another system of mathematics, ZF may need to be changed as its descriptive power is limited to those systems that are consistent with its axioms.
Sunny (12:47:54 PM): Sort of self referential right?
Henrik Nordmark (12:47:55 PM): and ZF + Axiom of choice is ok
Henrik Nordmark (12:48:10 PM): the problem is ZF + AD + Axiom of choice.
Henrik Nordmark (12:48:26 PM): AD and Axiom of choice lead to contradiction.
Henrik Nordmark (12:48:39 PM): it makes the mathematical universe inconsistent.
Sunny (12:49:35 PM): I think that is just shows that our understanding of the mathematical universe is inconsistent.
Henrik Nordmark (12:50:08 PM): hehehe...
Henrik Nordmark (12:50:43 PM): Unlike Gödel, I tend to be very pragmatic on these issues...
Henrik Nordmark (12:51:32 PM): I feel that ZF + AD is simply a different language game than ZF + Axiom of choice.
Sunny (12:51:51 PM): What do you mean? Assuming that it is the mathematician that is inconsistent is more pragmatic than assuming that the universe is inconsistent. lol
Henrik Nordmark (12:52:11 PM): There is no reason to believe that one language game is closer to the "truth" than the other, whatever that is supposed to mean.
Sunny (12:52:35 PM): Sure. Now, are there applications of ZF+AD+Axiom of choice. Likely not.
Henrik Nordmark (12:53:20 PM): All of standard everyday mathematics can be done both within the context of ZF + AD and ZF + Axiom of choice.
Henrik Nordmark (12:53:27 PM): Just pick your choice.
Sunny (12:53:37 PM): But not both...its broken...right?
Henrik Nordmark (12:53:51 PM): not at the same time anyways
Henrik Nordmark (12:55:18 PM): And since most mathematicians are accustomed to Axiom of choice, there are strong sociological pressures to favor ZF + AC.
Sunny (12:57:16 PM): I'll still hold to my earlier proposition that mathematics and its consistency is determined by its real-world application. One assumption versus another may be equally valid depending upon the specific context in which it is applied. Both mathematics being valid, just not describing the same mathematical, or real object(s).
Sunny (12:58:30 PM): Perhaps the assumption in the axiom of choice is that we assume that both players have perfect knowledge.
Sunny (12:59:11 PM): If both chess players have perfect knowledge the game will always result in stalemate.
Henrik Nordmark (1:00:02 PM): The problem for the mathematician who believes in definite truth values is that there seems no way to determine which axioms to accept as being true
Sunny (1:00:10 PM): Wouldn't this be contradicting the axiom of determinacy?
Henrik Nordmark (1:00:25 PM): and the physical world is incapable of providing those kinds of answers
Sunny (1:00:33 PM): Why not. It seems simple. Just apply them.
Henrik Nordmark (1:00:45 PM): because the physical world gets described equally well by both systems
Sunny (1:01:00 PM): In different contexts.
Sunny (1:02:36 PM): The axiom of choice appears to describe the situation where both players have perfect knowledge, the axiom of determinacy seems to better describes a situation where perfect knowledge is irrelevant to the outcome.
Henrik Nordmark (1:03:28 PM): AD states that all infinite games with perfect information of a certain type are determine
Henrik Nordmark (1:03:42 PM): i.e. one of the two players has a winning strategy.
Henrik Nordmark (1:03:57 PM): when you add Axiom of choice...
Henrik Nordmark (1:04:34 PM): you can construct an infinite game in which both players have a winning strategy, which is of course a contradiction.
Sunny (1:06:54 PM): Because both players have a perfect knowledge of the game. If you set two machines at playing tic-tac-toe neither will ever win. This is not a contradiction, but a failure of the game to obscure the winning strategy in its structure and complexity.
Henrik Nordmark (1:08:40 PM): yes, but that just says that tic-tac-toe is not a determined game and that it allows draws.
Sunny (1:08:56 PM): You could test this hypothesis by constructing two games, one with perfect knowledge and another without.
Sunny (1:09:24 PM): No, just expand the tic-tac-toe board to be infinite and you have the same problem.
Henrik Nordmark (1:09:33 PM): but AD says nothing about games with imperfect information.
Henrik Nordmark (1:10:18 PM): whatever information you gain from studying infinite not-perfect-information games will be irrelevant to AD.
Sunny (1:10:57 PM): I would say that it isn't a contradiction, it is exactly representing reality, i.e. that a game with perfect information will always result in a draw, unless perfect information is irrelevant to the outcome (i.e. a game of dice)
Henrik Nordmark (1:11:42 PM): I think you are misunderstanding the term "perfect information"
Henrik Nordmark (1:12:19 PM): perfect information in game theory just means that the player knows where he is on the "board".
Sunny (1:12:20 PM): What I mean is that the player has perfect knowledge of all states in the game in the current round.
Sunny (1:14:49 PM): The other problem that I see with the contradiction is that in most complex games (i.e. chess) perfect knowledge (of all post and possible future 'moves') is not physically computable. there are too many possibilities
Henrik Nordmark (1:15:07 PM): And as I said before all finite perfect information games in which there are only two outcomes (win or lose) are determined.
Henrik Nordmark (1:15:10 PM): mmmm.
Henrik Nordmark (1:15:18 PM): once again that is irrelevant
Henrik Nordmark (1:15:31 PM): computability is a whole different topic
Henrik Nordmark (1:15:41 PM): e.g.:
Sunny (1:15:49 PM): this leads to the possibility that in order for consistency to be reached the computability of perfect knowledge must be as unreachable as the end state.
Sunny (1:16:04 PM): But it isn't a separate topic if you are designing a computer to play chess.
Sunny (1:16:09 PM): This is the application.
Henrik Nordmark (1:16:11 PM): We have a mathematical proof showing that checkers is a determined perfect information game.
Henrik Nordmark (1:16:40 PM): That does not mean that we know how to compute a winning strategy for either of the players.
Sunny (1:17:56 PM): Of course not, someone has to move first!
Henrik Nordmark (1:18:17 PM): huh?
Sunny (1:19:54 PM): You can't compute a winning strategy if you are assuming the best possible strategy for both players. The winning strategy is dependent upon the arbitrary strategies of the players during the course (especially the beginning) of the game.
Henrik Nordmark (1:20:19 PM): actually no
Sunny (1:20:45 PM): Or maybe who gets to make the first move.
Henrik Nordmark (1:21:12 PM): the definition of a winning strategy is a strategy which no matter what the other player does you have a response which will eventually lead to victory.
Sunny (1:22:03 PM): Then, like tic-tac-toe you are talking only about games that are simple enough that the only difference between the players is which takes the first move.
Henrik Nordmark (1:22:26 PM): hehehehe...
Sunny (1:22:33 PM): i.e. games even simpler than tic-tac-toe
Henrik Nordmark (1:22:37 PM): you make it sound very trivial...
Henrik Nordmark (1:22:46 PM): but as I said before...
Henrik Nordmark (1:23:02 PM): we know that checkers is a determined game
Henrik Nordmark (1:23:23 PM): in fact we know that whoever plays first has a winning strategy
Henrik Nordmark (1:23:47 PM): i.e. he has a way to respond to player two that will guarantee victory.
Henrik Nordmark (1:24:12 PM): However, as of today no one has been able to compute this winning strategy.
Sunny (1:24:27 PM): Yep, I didn't say that it would be easy to determine that the game was simple.
Sunny (1:25:09 PM): Or what the winning strategy would be.
Henrik Nordmark (1:25:26 PM): right
Sunny (1:27:19 PM): But, is the winning strategy for checkers computable?
Henrik Nordmark (1:27:28 PM): it is
Sunny (1:27:46 PM): but only once the game has begun, right?
Henrik Nordmark (1:27:48 PM): but that doesn't mean that it is easily computable.
Henrik Nordmark (1:28:04 PM): no before the game has begun
Henrik Nordmark (1:28:34 PM): you can compute a strategy that will always work against player 2.
Henrik Nordmark (1:29:20 PM): but this is not useful if it takes a computer a hundred years to compute it.
Sunny (1:30:32 PM): But it won't be 'easily' computable until the game has started and the first moves have been made.
Sunny (1:30:46 PM): If you just start the game, it becomes much easier.
Henrik Nordmark (1:31:21 PM): well the further into the game you are in the less things need to be computed so the easier it becomes
Henrik Nordmark (1:32:00 PM): but the further you are into the game the greater the odds that the first steps you made were not according to the winning strategy
Sunny (1:32:08 PM): But then you take a chance at losing.
Sunny (1:32:14 PM): Right.
Henrik Nordmark (1:32:29 PM): in fact you might have put yourself in a position where player 2 has a winning strategy.
Henrik Nordmark (1:32:37 PM): correct.
Sunny (1:32:38 PM): b
Sunny (1:33:44 PM): But because of the computability problem neither player has the advantage.
Henrik Nordmark (1:33:48 PM): in a finite game like checkers at any point in time in the game, one of the two players has a winning strategy.
Henrik Nordmark (1:33:57 PM): correct
Henrik Nordmark (1:34:08 PM): if these things were easy to compute
Henrik Nordmark (1:34:20 PM): the game would no longer be interesting to play.
Henrik Nordmark (1:35:14 PM): It is possible that chess is a determined game.
Henrik Nordmark (1:35:36 PM): However, nobody has been able to prove or disprove this.
Sunny (1:36:24 PM): I would make a guess that it is not because the stalemate is possible.
Henrik Nordmark (1:36:43 PM): no
Henrik Nordmark (1:37:32 PM): the question is whether at the very beginning of the game one of the two players has a way of guaranteeing that there will be no stalemate and that he will win.
Henrik Nordmark (1:37:56 PM): We also know that the question: Is chess a determined game?
Henrik Nordmark (1:38:08 PM): is a computable question
Sunny (1:38:29 PM): How so?
Henrik Nordmark (1:38:35 PM): we can put this question into a computer and if we wait long enough we will get a yes or no answer
Sunny (1:39:04 PM): But if we ever got an answer it would ruin the game for everyone!!
Sunny (1:39:06 PM): lol
Henrik Nordmark (1:39:13 PM): lol
Henrik Nordmark (1:40:02 PM): probably not really
Henrik Nordmark (1:40:19 PM): cuz even if we know that the game is determined
Henrik Nordmark (1:40:33 PM): we wouldn't necessarily know what the strategy is
Henrik Nordmark (1:40:43 PM): just like with checkers.
Henrik Nordmark (1:41:42 PM): ah well...
Henrik Nordmark (1:41:51 PM): I guess I should go to bed...
Henrik Nordmark (1:42:14 PM): tomorrow I will be taking the new students to go look at the Botanical Garden...
Sunny (1:44:19 PM): Cool.
Sunny (1:44:29 PM): Thanks for the great discussion. Interesting stuff.
Sunny (1:44:41 PM): Do you think it would be worth posting on davinciconcept?
Henrik Nordmark (1:44:56 PM): hmmmm...
Henrik Nordmark (1:45:11 PM): perhaps if we clean it up a bit yes
Henrik Nordmark (1:45:20 PM): yeah why not...
Henrik Nordmark (1:45:28 PM): that sounds like a nice idea
Henrik Nordmark (1:46:19 PM): Let me save this chat log...
Sunny (1:46:35 PM): I can post it as is and we can clean it up together.
Henrik Nordmark (1:46:45 PM): sure
Henrik Nordmark (1:46:49 PM): sounds good
Henrik Nordmark (1:46:59 PM):
Henrik Nordmark (1:49:26 PM): good night.
