Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: Universal first mover advantage
Posted:
Sep 16, 2009, 2:08 AM
Hey Alison,
You bring up some very interesting points. When I briefly read through the description of the arguments before making my post, I didn't realize that the possibility of an infinitely long game was such an important piece of your arguments.
You were right, I was basically dismissing this possibility as unimportant or trivial to the main point of the discussion. There is certainly a difference between mathematics / math theory and applied math, and when you apply math to tangible problems you often do things like calculate to a certain number of significant digits, and anything much further out than this can be categorized as "negligible" and not having any true tangible effect on the overall result. Basically, that's what I'm doing here -- I'm lumping games with large expectations of becoming infinitely long games in with games that have large expectations of ending in a draw -- because it's basically the same result, there is no winner.
Quick examples:
Tic-Tac-Toe: By my definition of advantage, I'm saying that P1 has a large advantage in Tic-Tac-Toe. However, with perfect play or nearly perfect play, this advantage is not sufficient to overcome the large expectation of a draw. However, P1 certainly has a better chance of winning than P2. P1 has the advantage.
Gomoku, Played on an Infinitely Large Board, Except Instead of 5-in-a-row Wins, We Play One-Trillion-In-A-Row Wins:
It's easy to see that the rules of the game are such that this game should go on forever. With perfect play, I'm sure it does. In fact, if one player plays perfectly and the other plays disasterously bad (a monkey mashing keys on a keyboard?) it still probably goes on forever.
However, in my opinion, P1 still has the advantage. The advantage is small -- basically it's negligible in this case, but not because the advantage over the other player is not clear -- it's because the rules of the game dictate that neither player has any real chance to win. In my graph example from before, basically the entire 100% middle section would be sectioned off in favor of a Draw (or no winner), and a tiny sliver on each side would be for the chances of each player winning. P1's chances might be measurably greater, but still negligible. The way I view "advantage", P1 has the advantage. You might disagree with this, but then perhaps we're just working off different definitions of what is an "advantage".
Forgetting about this infinitely long games possibility for a moment, my view of this whole thing is much more basic.
I believe that it can be mathematically proven (and I'll leave the proof to someone else) that:
1. A Turn-Based Game 2. Having Universal, Ongoing Rules In Effect Throughout the Game
yields, by its very nature, a situation where one player or the other has the advantage to win -- even if more and more complex rules are piled on top of it to smooth out and reduce this advantage, there will always be an advantage to one player, however small, such that with perfect play that player always wins.
If the rules of the game allow any significant expectation of a Draw (or an infinitely long game), it is possible that with perfect play the game should end in a draw.
Examples:
Chess: I'm not a chess expert, but it is my opinion that a graphical illustration like I described above probably holds for chess, where, for example: White wins: 0 - 48 Draw: 48 - 55 Black wins: 55 - 100
With perfect (50/50) play, the expectation is (at Point 50): Draw
Othello: I'm also not an Othello expert, but I do know that it is possible for Othello to end in a Draw (both P1 and P2 end with an equal number of squares filled in their color). However, it is my opinion that with perfect play, the expectation is NOT a Draw. I can't remember if someone earlier said who has the Advantage, but suppose it's Player 2. An example of what I'm describing might look like this:
White wins: 0 - 45 Draw: 45 - 47 Black wins: 47 - 100
So, in this example, even though a Draw is a possible outcome of the game, with Perfect (50/50) play, the expected result (at Point 50) is for Black to win. So, in this game, for a Draw to occur, White would have to play slightly better than Black.
Keep in mind that I don't necessarily think this idea of one Player always having the advantage is true of all games. Just games with properties I've noted above. There are plenty of other types of games that have no built in advantage for either side. (Basketball, for example)
thanks for your examples and further explanation of your position. I share your views and concepts regarding these games and your assessments all seem fair.
I also think it is fair to say that collectively we should have agreed on a definition of the term 'advantage' before now. So here is my take on it, although I think it doesn't vary that much from your definition.
It seems to me that advantage can only be applied if, when coupled with perfect play, it results in the desired payoff. Otherwise it is meaningless to use the word. So from a given point in a game, whether it be at the start or anywhere along the line, if perfect play leads to a draw or an infinitely long game then that position held no advantage for either player.
Now, lets just say I invent a game that meets our target game definition, but it does have a demonstrable advantage for player one. Now lets play this game slightly less than perfectly from the beginning up to a point where player 1 has squandered her advantage and the position is now perfectly balanced (no advantage for either player), even though one of those players moves before the other from that position, this is taken into account when assessing their respective chances.
OK, so now I decide that this new balanced game position is actually a better starting configuration for the playing pieces than my original design. So I redesign my game so that it actually starts with this new balanced layout. Would not such a game then have no advantage for either player? Note that in this situation, the concept of perfect play now simply means play that avoids a loss.
Now to generalize this: Using imperfect play with some arbitrary game (but not something simple or finite like tic-tac-toe or othello), is it possible to reach a position where all of player one's first mover advantage is gone and the ledger is now square? Or would you argue that only an unequal situation is possible? Are you saying that since there is always one player who gets to make the next move that this gives an advantage that cannot be perfectly offset by anything? In short there can be no 50:50 positions?
If this is your argument, then you would have to explain why this would be so. Why such an exact offset is not possible? I know you have said that you will leave it to someone else to supply the mathematical proof, but I think we don't need to go there in this case because logic alone should tell us the answer without the need to manipulate symbols.
I ask the question: If a position could be reached where there is an extremely tiny variation in advantage in the sense that this will, with perfect play, eventually lead to a win, then why could there not be a position reached which, from that point forward, there is exactly no advantage? (Note that this assumes imperfect play to have reached that point in the game). Another way to put this is, 'Could there not be an imperfect sequence of moves such that all initial difference in advantage is exactly removed?'
So far up2ng, watsu and zoey have all said that a balanced position is not possible in one way or another but have not actually explained why. Saying that you believe something could be mathematically proven does not leave us with even the grounds upon which you make this claim. I think you have been too hasty on your judgment of this and haven't perhaps considered the myriad ways in which one could work to construct a game that countered any advantage.
I would be very interested in seeing an argument that demonstrates some logical flaw in my above thought experiment, and an answer to the question I have posed. I am hoping one of you will take my position and illustrate some internal contradiction, or by using the method of extremes find an absurdity, or simply identify some situation where it didn't work. I know this is difficult for you to argue - I know I couldn't do it - but I think without doing this we have not moved forward because in the end it is still just a claim with no real basis. (I am being deliberately provocative here because I want one of you to attempt a response on this).
One last thing. Can I also say at this point what a pleasure it is to read your thoughts and discuss this with you all.
I was working based on the no draws, luck, or infinite game assumption. Assuming that there is indeed a chance for a draw, then it would (at least theoretically- how you would prove it would be another matter) be possible to have a balanced game with no advantage to either player. Proving that one had indeed found such a position rather than one in which an advantage was outweighed by a draw- as in chess, tic tac toe, etc. would, however, be very challenging, I think.
Message was edited by: watsu at Sep 16, 2009 1:55 PM
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Universal first mover advantage
Posted:
Sep 17, 2009, 12:38 AM
Watsu, I make a clear distinction between an infinitely long game and a draw.
One type of draw in chess for example is determined by a rule that says that if the same position is reached 3 times then a draw is declared. This is an arbitrary rule, and if removed doesn't mean the game will keep repeating that position forever. The 50 move rule is another example of an arbitrary rule put in place to avoid endless play or overly long games.
So when we use the term draw we can be using it either in a sense of a rule or rules imposed for playability purposes, OR where there is mechanically no way either part can effect a win (lack of mating material for example).
What I am saying is that an infinite game is one where it is the first type of situation but without the arbitrary rule put into the game to prevent it going on forever. This is not a draw simply because no rule in that game calls it a draw.
So, if you are conceding my point on the basis that my argument relies on the inclusion of a draw, then you should perhaps retract this because I am not saying that. I am saying that in a zero sum, no draw, two player game, that a balanced game is possible. AND, that such a game would not contain arbitrary rules to stop the game because of repetitive play as per my examples from chess.
Re: Universal first mover advantage
Posted:
Sep 17, 2009, 2:25 AM
Hmmm. If no draws are possible, I continue to contend that one side or the other will always have the advantage in a zero sum game. Because, perfect play by both players yields a draw in a hypothetical non advantaged game when a draw is admitted as a possibility. Win, lose or draw seem to be the options here, and if draws are factored out it appears to leave only a win or a loss as options.
Look at it from the back end for a minute and assume for the sake of argument that both players have played perfectly for x number of moves (to allow for a game which has started from an imperfect- but balanced- position). If no draws are allowed or possible, then either player 1 or player 2 will win on the last move. Which means that the player who loses was at a disadvantage at the position of move N (total number of moves by that player) - x (number of perfect moves). If the position were not imbalanced at that point, the player who lost would not have lost, but would have been able to achieve at least a draw through perfect play for x moves (but since no draws are allowed, this player would have won). Thus, I conclude that since the game ends in a win for one side after perfect play by both sides that one side had an advantage over the other side. Hope this makes sense, because I don't really feel up for more discussion of the point, lol.
Message was edited by: watsu at Sep 16, 2009 8:26 PM
Message was edited by: watsu at Sep 16, 2009 8:36 PM
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: Universal first mover advantage
Posted:
Sep 17, 2009, 3:48 AM
vvvvvvvvv It seems to me that advantage can only be applied if, when coupled with perfect play, it results in the desired payoff. Otherwise it is meaningless to use the word. So from a given point in a game, whether it be at the start or anywhere along the line, if perfect play leads to a draw or an infinitely long game then that position held no advantage for either player. ^^^^^^^^^
Yes, that's why I made the comment before about defining the term "advantage". I had a feeling from your earlier comments that this is how you were viewing it.
I strongly disagree with this. Now, if we are discussing Pente or most other stone games where the possibility of a Draw is negligible, I don't think we have any disagreement about the term, and these non-draw games should be our focus anyway since these are the games we play on this site. However, when a significant possibility of a Draw exists, I still prefer to extend the use of the term "Advantage" to describe the fact that one player has a better chance of winning than the other. I was hoping my graphical examples would show this. We could take it to an extreme -- suppose that P1 wins on the graph from 0 - 49.99. A Draw occurs from 49.99 - 100. P2 simply cannot win. Well, under these conditions, if both players play exactly perfectly (50/50 point on the graph) the game should end in a Draw. But just barely! If P2 had done even one tiny, miniscule thing less than perfectly, P1 has an opportunity to win. However, P1 could be a monkey smashing keys randomly on a keyboard and P2 could play flawlessly, and yet the game will still end in a Draw. To me, this is a MASSIVE P1 advantage. If you think a different word would be better to use to describe this situation, fine. I will stick with extending the concept of "Advantage" from non-Draw games into other games with the possibility of a Draw AND the expectation of a Draw with perfect play.
vvvvvvvvv Now, lets just say I invent a game that meets our target game definition, but it does have a demonstrable advantage for player one. Now lets play this game slightly less than perfectly from the beginning up to a point where player 1 has squandered her advantage and the position is now perfectly balanced (no advantage for either player), even though one of those players moves before the other from that position, this is taken into account when assessing their respective chances. ^^^^^^^^
I believe strongly that for finite, TURN-BASED games without Draws, such as Pente, this situation is not possible. When one player who has the advantage squanders it to the point where they cannot force a win, that means the other player now has the advantage to be able to force a win. A perfectly balanced position where both players have an equal chance to win does not exist.
Incidentally, this is the idea behind D-Pente. If an early opening position existed that was equal for both players, you'd have expert players using this position every time, and two expert players would fill up the entire board and it would end in a Draw. The fact that this never comes even close to happening should be at least circumstantial proof that an equal position (at least in the early opening stage) does not exist. Instead, D-Pente is a strong P2 advantage game. Not quite to the degree of the P1 advantage in Pente, but pretty close. The advantage is very significant.
vvvvvvv ...is it possible to reach a position where all of player one's first mover advantage is gone and the ledger is now square? Or would you argue that only an unequal situation is possible? ^^^^^^^
Precisely. It is impossible for the position to be all square. I DO argue that ONLY an unequal situation is possible. And, I don't think it's ever close, really.
vvvvvvv Are you saying that since there is always one player who gets to make the next move that this gives an advantage that cannot be perfectly offset by anything? ^^^^^^^
Interestingly, this is sort of what I'm saying, but not exactly (I think). I'm saying that turn-based games have a built-in, mechanical imbalance. I don't think it has to do with who gets to make the next move so much as the underlying mechanics of turn-based play which causes it. Some turn-based games have a built-in P1 advantage, some have a built-in P2 advantage. This assumes that the rules stay consistent throughout the game, and are not randomly changed mid-stream or something wierd like that. The rules DO dictate who has the built-in advantage. For example, regular Pente strongly favors P1. Pro-Pente rules also favor P1, but less so -- a rule restriction being imposed on P1 lessens the advantage. If the rule instead was, "P1's 2nd move must be played on one of the four corners of the board", then we'd create a game with a P2 advantage, despite the fact that P1 moved first and has more material on the board throughout the game. However, it is impossible to create a rule or a set of rules such that it completely balances a turn-based game, because none of these rules address the very fact that the game is turn-based, which is what creates the imbalance in the first place. Because these mechanics stay in place despite adding complex rulesets, the game will remain imbalanced in favor of one player or the other.
vvvvvvv In short there can be no 50:50 positions? ^^^^^^^
In short, and I hope I'm not overgeneralizing, in a finite, turn-based game, there can be NO 50:50 positions.
vvvvvvv If this is your argument, then you would have to explain why this would be so. Why such an exact offset is not possible? ^^^^^^^
I don't think I can fully explain how I visualize this in a way that does it justice. All I can say is that it has to do with the fact that we're talking specifically about turn-based games and this is precisely what causes the scenario where no state or snapshot of the game is ever equal to all parties (let's limit this to games with only 2 players). One player will always have an advantage. I believe this is also true for games involving Draws like Chess (when one expert player asks another expert player for a Draw early in the game it's because they've both analyzed the position to fall within that "Draw" expectation and assume each player would play flawlessly enough to stay within that band, even though one player does have an advantage to win, it's not enough to overcome the likelihood of a Draw). Regardless, I certainly believe that this is definitely true for games that do not involve Draws like Pente.
vvvvvvv I ask the question: If a position could be reached where there is an extremely tiny variation in advantage in the sense that this will, with perfect play, eventually lead to a win, then why could there not be a position reached which, from that point forward, there is exactly no advantage? (Note that this assumes imperfect play to have reached that point in the game). Another way to put this is, 'Could there not be an imperfect sequence of moves such that all initial difference in advantage is exactly removed?' ^^^^^^^
Again, I strongly believe this to be impossible.
Let me try it this way. Let's choose Pente:
One way or the other this game is going to end in less than 35 moves or so. Especially with reasonably strong play. This really is not very many moves to yield a decisive result. Given that this game will quickly end in victory for one player or the other, which player will win? I believe that at any given position one player has the opportunity to win which can only be thwarted if that player makes a mistake, however small. It does not make sense that this player could make perfect moves to win and yet the other player can also play perfect moves which will also force a win. Make no mistake, someone is going to win within the next 35 moves -- there is no situation that is so balanced that the game "should" last forever. Either one player can force a win, or they cannot. If they cannot, it means that the other player can. It's a logical outcome which is created by the fact that we are dealing with Turn-Based play.
vvvvvvv I think you have been too hasty on your judgment of this and haven't perhaps considered the myriad ways in which one could work to construct a game that countered any advantage. ^^^^^^^
PLEASE do not make this mistake of thinking this was hasty analysis. You have clearly not done your research. I have explained, reexplained, taught, preached and in many other ways written about this exact subject matter all over the forums here going back to AT LEAST 2004. Maybe earlier. It forms the crux of my numerous attempts to prove why exactly it's so critical to move to a "SET BASED RATING SYSTEM", since no rule changes exist that can perfectly balance a single game of Pente -- however, a SET of Pente is by its very nature PERFECTLY BALANCED. ALL of the myriad ways to construct a turn-based game have been considered, and none of them fix the natural built-in advantage that results from the game being turn-based. In fact, I believe that understanding this, and related concepts, is the top rung of understanding the game of Pente. Years ago, when I was playing a lot and finally had a "breakthrough moment" in my understanding of the game and my rating all of a sudden shot up from the 1700 range to nearly 2000, it had to do, in part, with these concepts. It was all of a sudden really and truely KNOWING that Pente has an insurmountable advantage. When this is really known at the core, playing styles change. Because you know when you sit in the P2 seat that you've already lost the game -- when you make your first move you're hopelessly behind. So, you resort to more trickery, traps, understudied lines, knowing your opponent's tendancies, and various other ways of trying to get your opponent to make a mistake, because only when your opponent makes a mistake can you seize upon the opportunity to attempt to win the game. Conversely, as P1, you KNOW that you've already won, so you make your moves more confidently, not caring about various gambits and scary moves that your opponent makes because if you've analyzed every position correctly and made the correct moves, you will win. From there, you eventually see clearly that there are no equal positions -- either one player presses their advantage, or they've lost it and the other player now has the advantage, there is no inbetween and it's really not even close. This conclusion was not a hasty one.
vvvvvvv I would be very interested in seeing an argument that demonstrates some logical flaw in my above thought experiment, and an answer to the question I have posed. I am hoping one of you will take my position and illustrate some internal contradiction... ^^^^^^^
Well, I guess I have not disproven your position through contradiction. I'm just trying to explain how I've come to the thoughts that I feel pretty certain about after working through this problem over time. Even then, I'm sure I haven't been concrete enough for your liking -- as I said I was hoping to leave the proof up to someone else since I'm not quite sure how to explain it in black and white. It's a tricky thing to try to "prove", but I'm pretty confident that it works the way I'm thinking it does.
vvvvvvv One last thing. Can I also say at this point what a pleasure it is to read your thoughts and discuss this with you all. ^^^^^^^
Likewise, Alison! It is clear that you are extremely intelligent, thoughtful and well-spoken. Your thoughts and ideas are intreguing and your questions are well constructed. It has been a lot of fun going down this road again on this topic. Great stuff!
Re: Universal first mover advantage
Posted:
Sep 18, 2009, 3:29 AM
The power and advantage P1 holds over P2 effects primarily the early game. This happens by always having an extra stone on the board over P2. This advantage diminishes as the game progresses, and the extra stone becomes less of a commanding influence in the game as more and more stones are put into effect.
That advantage though is a distinct power in that early game, and being that pente is such a short game where every early advantage is a potent edge as both players wrestle to gain the quick upper hand in a game that punishes any mistakes. The player with the early edge in shape and position then has a definitive advantage with which to carry on through to a win. That being said the player with an extra stone on the board has a marked though precarious advantage in that most important early game phase.
P1's extra stone gives him that edge, though only briefly. This is why P1 must only play safe and sound moves in the early game, while P2 must play in a more oblique and obscure manner to trick or confuse P1 in the early game, in hopes of a mistake from P1, gaining P2 the edge he needs to win.
This is all I personally have to say about this subject.
Thanks for your kind words up2ng. I will respond here to both you and watsu.
First Watsu: There is definitely a point with these discussions where one has said all they have to say, so I understand where you are coming from! At the risk of being tedious though I would like to make a couple of quick comments in relation to your last post Watsu. 1. If you are firm on the idea that a perfectly balanced game IS in fact a draw because it would go on forever (your apparent definition of a draw), and we are excluding games with draws, then of course my position makes no sense since balanced games (while perhaps possible in theory) are excluded. 2. In your second paragraph about looking at things from the back end, you have simply assumed a winner (the last player to move) and worked backwards to find the unsurprising result that there was an advantage. All you have done there is simply change the thought experiment to become one that supports your position, but that is not the way I designed it. If you remove the option of an infinite game from a thought experiment that relies on infinite games, all you have done is create a different thought experiment. So, perhaps we should leave it there since, without agreement on what is or is not a draw, we can't really press the point any further. I thank you for your great insights into game theory though, and your efforts to convey these to me.
Up2ng: When I read back the comment about being ?hasty? I can see that your inference is quite justified, but it was not my intention to convey that message. I expressed myself poorly and so gave you the wrong impression. I did not intend to suggest that any of your thinking in relation to Pente and its relatives is hasty. Clearly you are one of the great players and highly revered, and have worked on all aspects of the game over a long time. I, on the other had never seen or played Pente until November last year. So on that score I defer to you. The intent of my comment was to refer to all possible two player zero sum games of which there are those thousands that exist and an infinite variety that could exist but don?t. Pente is clearly not a game where my thought experiment could apply, but I think we should not be quick to dismiss the possibility that in just one of the infinity of other possible (non Pente) game designs, that a game situation could be constructed that meets the requirements of my thought experiment.
I would like to point out though that games that have become popular (like Pente), did so precisely because they can be played in a reasonable amount of time with a high likelihood of a non-draw result. Thus our everyday experience of games does not include playing for hundreds of moves, or dealing with tightly balanced positions, or where gaining any advantage is extremely difficult. It should not be a surprise therefore that we have a sense of there being something about turn-based games that gives an insurmountable advantage to one player with perfect play ? the popular games we play were designed that way. If we had experienced all the other possible game designs, I have a hunch that our intuitions would be different.
I know that you strongly believe that it would not matter if the game took 1,000,000 moves to complete because there is an inherent imbalance in turn based games that cannot be overcome. It's not that I don't find your reasons compelling - I mean I want to believe you - but I just can't get past what I think is a flaw in this thinking.
So, I will give this one last stab and see how it goes. Please take into account that I am talking about the endless array of possible games beyond just stone placement games.
At any point during a game, the advantage that can be assigned to the player just before they move is equal to the ?gain value? of the best move available. In a balanced game position, the position would be 50:50 at the start of the player?s move and of all the moves available the best one would have a gain of zero and would only serve to keep that player?s position from getting worse, because 50 + 0 = 50. The other player then faces the exact same situation and after moving is also left at 50:50.
From this we can see that the advantage of being next to move is nil and has already been factored in to the assessment of advantage. But this goes further because it also applies to the move after next. If the next move starts and ends with a balanced position, it is only that way because the potential for the other player to then improve her situation is also zero. In fact, with perfect play all moves to infinity would only serve to maintain a 50:50 balance. Imperfect play however would cause an imbalance and potentially a loss for that player.
I have played many games of chess where the only moves available make the situation worse or just keep things at the state they are. This can occur when the position is 70:30, 90:10, 40:60 or 50:50. If at the start of a chess position it is 70:30 it can still be 70:30 after a zero value move. Thus the position is 70:30 two moves in a row. If it can occur twice in a row at 70:30 then why not twice in a row at 50:50? Why not three times in a row, or an infinite number of times in succession? What characteristic of turn-based games would force this situation to simply not occur?
You may like to argue that 50:50 positions could not be reached in the first place, but if we can get from 60:40 to 40:60 because there is a move available that has a gain value of 20, then we could get from 60:40 to 50:50 if the best move available has a gain value of 10. Once reached, I think it is also possible that a 50:50 position could at least theoretically be maintained.
Therefore I think it is possible to see that 50:50 situations could at least theoretically be created and then perpetuated. And, if such a situation could be reached in a game that started out unbalanced, and then via imperfect play become balanced, then it must be possible to create a game that starts in that balanced position and continues that way with perfect play of continuous zero gain moves.(Yes I know this is theoretical math, but that is beside the point!)
For me it all comes down to one thing. As I said to watsu, if you allow that an infinite and balanced game is not actually a draw, then I think my proposition is correct for the reasons stated. If you consider infinite balanced games to be draws then my proposition cannot stand. I contend that infinite balanced games are not draws, but that is just my opinion.
