Home » Forum Home » Analysis

Topic: Universal first mover advantage
Replies: 41   Views: 66,817   Pages: 3   Last Post: Nov 17, 2009, 12:38 PM by: alisontate

Search Forum

Back to Topic List Topics: [ Previous | Next ]
Replies: 41   Views: 66,817   Pages: 3   [ 1 2 3 | Next ]
alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Universal first mover advantage
Posted: Sep 10, 2009, 4:52 PM

I had an interesting discussion with someone today about the solvability of Pente, whether or not it is solved, or close to it. I said that the stated position of the experts, that perfect play for white is a guaranteed win, is equivalent to claiming that the game is solved. Where solved doesn't mean we have plotted all possible trajectories, but that we know that all trajectories played optimally will result in white wins. The term solved then means that if the game is defined as the problem then 'white' is the answer.

To protect his indentity I shall simply refer to this person as 'Z'.

I think the game is solved in terms of how I am defining it. Z is reserving judgment.

However all of this led onto another point. I went on to say that the heavy advantage of white leads easily to the conclusion white simply has to maintain that advantage and that losing could only result from sub-optimal play on the part of white. Z said that this is true of many games - I agreed. Z further stated that if there is no element of chance, and no draws possible that the first mover must always win. This proposition was not just limited to Pente, Z was stating this for all games.

I said that this would depend on the rules of the game. Rules govern who has the advantage and dictates therefore if the first or second mover has a handicap or in fact if it is evenly balanced. Z disagreed with this.

So, to put it in other terms. Z is saying that for any two player, zero sum finite game with no draws, the first mover always wins - no matter what the rules are. I disagree with this and simply state that the advantage player one has is only as a result of the rules of the game. That it isn't some miraculous universal characteristic enjoyed by all first movers in all zero sum games.

Z then challenged me to suggest a set of rules whereby a game would not afford the first mover any advantage. We agreed that the forum might be a good place to discuss this further and perhaps attract the opinions of other experts - who I shall also treat with confidentiality and refer to them only as 'n' and 'r' and 'k' and 'm' (my apologies to any anonymous people for not, not mentioning them here). Z felt very strongly that these individuals will all agree with him. I am not so sure.

Rather than me having to invent a whole game complete with rules, playing pieces and board configuration that together support my contention that the rules govern the outcome, and to avoid the requirement to verify this with approximately a billion hours of test-play, I thought it would be possible to argue my case simply using logic. Given Z's statement to me that his position was arrived at solely on logical grounds, it makes sense to me to work on that basis too, and sure beats the hell out of the first option.

By now I know you are all just itching to find out who this mysterious 'Z' is, but my lips are sealed.

So, in the spirit of Pente I am going to play black on this and invite others to fire the first shot. If you wish to argue along the lines proposed by 'Z' - that the rules are irrelevant - then feel free to put forward your logical arguments in support of your contention. Once I have read these points I will attempt a rebuttal.

I also invite any who wish to support my contention to contribute.

Good luck

-Alison



watsu

Posts: 1,099
Registered: Dec 16, 2001
Home page
Re: Universal first mover advantage
Posted: Sep 10, 2009, 6:39 PM

I believe it wouldn't be too hard to come up with a disadvantaged game for the first player. By defining a game (anti Pente is only one of many possibilities) in which the objective is to play a game with a certain ruleset in order NOT to achieve a win by that ruleset (i.e. winning is defined as losing) and also defining the game so that no draws are possible- if the first player can place the last stone on a board which would otherwise be a draw, then the first player loses the game- this would seem to give a fairly clear disadvantage to the first player. Similarly, if in a game of D Pente, first player is defined as the one who proposes a position, then first player would have a slight disadvantage due to the fact that if no draws are possible in a game, then one side or the other must have a win. An opponent with perfect foresight would simply choose to play the game from that side no matter what position was proposed by their opponent.

I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
watsu

Posts: 1,099
Registered: Dec 16, 2001
Home page
Re: Universal first mover advantage
Posted: Sep 10, 2009, 9:31 PM

Just in case the above examples were unpersuasive- since they involve such things as swapping position and anti versions of games let me just say in addition that Othello has been shown to be a second player win on a 6x6 board and that the game of Kalah is also a second player win if 6 pits and 3 stones per pit are used. See the link below if you want more details on those games:

http://www.webcitation.org/5jgvs8zLP


Message was edited by: watsu at Sep 10, 2009 3:44 PM


I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
zoeyk

Posts: 2,007
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 11, 2009, 3:15 AM

alison;
perfect play for white is a guaranteed win (in pente under standard rules)


zoey;
yes of course you know i agree with this. ive been saying the same for a long while.



alison;
Z further stated that if there is no element of chance, and no draws possible that the first mover must always win.



zoey;
I Never said in "all games" that the first mover wins.

i said that if there is no draw, and no luck, that one side must have an advantage,..unless the game is not allowed to ever end,..in example; a game based on "Infinity".

you said that there could be rules where No Sides have a advantage, and that "draws" and "luck" do Not play a factor in the victory.

unless infinity is involved this is impossible to be true in my opinion, and possibly is a fact.
and actually if its infinity then obviously there is no victory,.Ever...

further more i agree that it is very easy to give player 2 the advantage by modifying rules (like swap), BUT that was Not what our original argument was about. you are altering the argument now....


even if the advantage ratio is designed as 1 trillion and one VS 1 trillion point zero zero zero one. the side that is 1 trillion and one will have the advantage in perfect play.

all that the rules (excluding "draw" "luck" "infinity") can do is increase the value of ratio to a point where the advantage is so small that you don't notice it,
Ie; 0.00000000000000000001 advantage over opponent.

...but you can not remove the advantage 100%. in my mind this would defy the laws of mathematics.

can any one prove that what I'm saying is wrong?


zoeyk




this thread is the result of a mis-communication, from a table with a small chat box, where both sides were not being read fully.

my advice, next time slow down, and clearly read what the other is saying, make sure we are both clear in our meanings, before jumping the gun into a public debate. but any how, no harm done, cheers

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 11, 2009, 4:25 AM

My apologies Zoey, I misrepresented a couple of your points. You are right in that you did not argue for automatic first mover advantage but that it is impossible for a game to be constructed where no side has an advantage. The name of this thread should therefore be 'Universal Advantage for one side"

Anyway, I still disagree. But lets see what others say first.

cheers
Alison

zoeyk

Posts: 2,007
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 11, 2009, 11:51 AM

What exactly are you still dis-agreeing about?

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 11, 2009, 4:23 PM

LOL. Ok, I'm saying that I think you are wrong that one side must have an advantage.

I am saying that it is possible for a zero sum game, without draws, to have no bias toward one player or the other, and that this can be dictated by the rules. This is the opposite to your position.

Zoey, I should also point out that since this is your proposition the burden of proof rests on you...

watsu

Posts: 1,099
Registered: Dec 16, 2001
Home page
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 11, 2009, 7:04 PM

If the game is zero sum and one assumes no draws are possible and that luck and infinite games are not involved, then provided both players of the game play perfectly and are able to play a complete game (if it takes more than a single lifetime to complete one game then it would be functionally equivalent to an infinite game), then one player or the other will always have an advantage- which player depends on whether the game turns out to be a forced win for the first player or for the second player. That advantage is simply stated as getting to make the first (or occasionally the second) move, and with perfect play it is an insurmountable advantage.

Even allowing games to have draws as a possible result doesn't negate one player having an advantage over the other (see chess, for example). In the case of chess, perfect play by both players would likely always result in a draw, but that is because the advantage which the first player has is insufficient to force a win (see tic tac toe for a simpler example of this concept).

I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
zoeyk

Posts: 2,007
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 11, 2009, 10:56 PM

before you read this i will say that i was actually confused by watsu's meanings in his post, thus if he further clarifies it may render my following paragraphs as a moot point. in other words it is possible i may end up retracting much of this.


chess draws are due to human error? we were speaking of perfect play. if God him/her self was playing chess as player one who would win? or would it still be a draw?

o.000000001 advantage is still an advantage. Fact


watsu said;
In the case of chess, perfect play by both players would likely always result in a draw, but that is because the advantage which the first player has is insufficient to force a win


if it is insufficient, then that means there never was an advantage from the beginning all the way to the end.
if there indeed was an advantage then it isn't that the advantage was insufficient, it is that the human's mind was flawed and limited rendering him or her unable to perform the act of perfect play from start to finish.


alison speaks of no advantage at all,...you watsu speak of a microscopic advantage, that's different, and at the same time tho, it seems you're trying to say that a microscopic advantage is the same as no advantage.

they may appear close to same, but the fact of the matter is that any kind of a "one", even to the right of a decimal point trailed by infinite zeros is still a number that is infinitely larger than the number ZERO surrounded by nothing more than other zeros infinitely.

when all you have to compare to the number one is the number zero the number one becomes a number as vast as infinity. thus, one has a heavy advantage over zero in perfect play. it is humans that don't have the capacity to see infinity far to utilize this heavy advantage. but then again they truth doesn't care about human limitations, the truth just is.

this discussion was about perfect play and advantage mathematically speaking, it is not about human's limited sight creating an illusion that the math is incorrect'ish looking.


in addition, a game taking a life time to complete being compared to infinity i find to be a false statement.
100 years is a drop in the bucket compared to the forever of infinity. besides 100 years entails that the game has a completion point, a victory goal, thus advantage is now possible.


watsu said;
and with perfect play it is an insurmountable advantage.


i assume you mean that insurmountable is meaning that the advantage side in perfect play can not be defeated nor drawn by the side of disadvantage. in which case i agree.



sorry for my long winded words, ill try to type less next post.



zoey

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
watsu

Posts: 1,099
Registered: Dec 16, 2001
Home page
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 12, 2009, 12:15 AM

Z- simplifying/clarifying what I was saying about games which have the possibility for draws within them- chess, checkers, tic-tac-toe, etc. It is quite possible that one side/player has an advantage in a game and yet have that advantage be insufficient to allow that player to actually win the game under the rules of the game- tic tac toe is an easy example of this. The first player would always have a win with perfect play if the board were not limited to 3x3 and ends the drawn games with the advantage of having an extra play. Chess also has an advantage for the first player, but with perfect play likely would always be a draw. So, this is not an advantage or edge which allows that player to win the game. Now, if one knew that both players would play a game perfectly then indeed there would be no advantage to playing one side versus the other in these games, since they would end in draws. But unless one has not only perfect move information but also perfect opponent information it is still advantageous to pick white in chess or X's in tic tac toe- because one's opponent may not play perfectly.

These games are distinct from games which don't appear to allow draws as a possibility- such as(at least as far as we know) Pente. In games without draws, one side or the other always has a WINNING advantage, and with perfect play we contend it is the first player in Pente who holds this edge.

And yes, of course there is a difference between 100 years and infinity (or for that matter the projected lifetime of the universe and infinity). I said more than a lifetime to complete for whatever player happened to be playing it. It would not be a completed game in other words. No, it would still not be an infinite game, but if a player no matter how perfect their play and insurmountable their advantage was unable to achieve a win due to dying before the completion of the game then the game would remain unfinished to that player. Not unfinishable, just unfinished. In other words, if a game were invented which took more time to play than all the nanoseconds in the life of the universe, would any being who was living within that universe, no matter how perfect their play be able to validly assert a win? It's not a big deal, this length of game point and I don't equate it to an infinite game. I just have a sense that for the purposes of game theory at least, games which require more moves than universal nanoseconds to win be lumped into a similar (but not exactly the same) category as games which actually have an infinite number of moves.

I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
zoeyk

Posts: 2,007
Registered: Mar 4, 2007
From: San Francisco
Age: 42
Home page
Re: No luck, draw, infinity = one side will have the advantage over the other.
Posted: Sep 12, 2009, 1:38 AM

i disagree, and after i finish watching this movie im watching i'll say why...to be continued

Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
up2ng

Posts: 542
Registered: May 9, 2002
From: Northeast USA
Age: 38
Re: Universal first mover advantage
Posted: Sep 13, 2009, 6:57 AM

Zoey is more correct than Allison. Watsu is more correct than Zoey.

In turn-based games that have no possibility of a draw (I'll lump games that last forever in here with "ending" in a draw), one side has an inherant advantage to win based on the rules of the game. A turn-based game without draws cannot be without advantage for one player. The player with the advantage always wins with perfect play.

In turn-based games with rules such that a draw is a strong possibility, Watsu is correct in describing that one player can have an advantage in winning the game, but that advantage may not be strong enough to overcome the high expectation of a draw, and so with perfect play the game ends in a draw.

Some examples:

Pente:

Technically, Pente can end in a draw -- at least 19x19 Pente -- however, I think I remember the original rules state that the board is actually infinite (I could be wrong about that). Pente on an infinite board cannot end in a draw. Pente on a 19x19 board can end in a draw, but not with perfect play.

Pente has a significant player 1 advantage.

Think of this graphically as a bar graph which goes from 0 to 100. The player 1 advantage is so significant that it is probably a 53/47 advantage, for example. If we include the possibility of a tie, it might be more like a 52.999999999999999 / 47 advantage with a sliver between them of 0.000000000000001 which represents the possibility of a draw. However, what is the median result? Who wins right at 50? If you draw a line through the graph at 50 (both sides played perfectly), P1 wins, and it's not even close, really. Now, if player 1 makes several bad mistakes and P2 plays perfectly, then perhaps you slide the line up to 60 -- who wins at this point? P2 by a landslide, but that's because P1 did not play perfectly. I hope you all can visualize the graph I'm describing cuz I'm not gonna draw it!

Chess:

The rules of chess are such that there is a strong possibility of a draw. It is still advantageous and better to be P1, but this advantage is not strong enough to overcome the significant possibility of a draw. For example, suppose that with perfect play, it comes down to a King and a Bishop for White and just a King for black. Well, in terms of the power of the pieces remaining, this is a HUGE advantage! Suppose one player got to start the game with an extra bishop! That is huge! However, because of the rules of the game, a King and a Bishop is not sufficient to checkmate the opponent's King -- this game is a draw.

Let me use my graphical example with more made up numbers. At a high level, there's probably much less advantage to P1 in chess than there is in Pente. So, it's certainly not a 53/47 siuation -- perhaps it's more of a 50.3/49.7 situation in chess. But, wait! Now we add in the possibility of draws! Remember, in Pente, this little sliver on the graph was basically negligible. However, in chess, it might take up 5 units on the graph. So now, we might have, for example, 47.8 units in favor of White, then 5 units for a draw, then the remaining 47.2 units in favor of Black, lined up on a bar graph in that order. So, who wins with perfect play by both players? The median result right at 50? Guess what, the median result right at 50 is a Draw -- with some room for error on each side -- there is a strong Expectation of a Draw in chess with perfect, or nearly perfect play. You'd have to slide that line a whole 2.2 units in white's direction -- with some slight mistakes by Black -- for white to be able to win. On the other hand, Black's situation is worse (white DOES have an advantage, after all) -- you'd have to slide the result much further, a whole 2.8 units towards black, due to significantly more or worse errors by White, for Black to now have an opportunity to win the game with perfect play.

What is certain is this -- you cannot devise a turn-based game where the graph will be exactly 50/50. In my opinion (and only cuz I'm not sure exactly how to prove that it's fact, but I'm sure that it is) that would be mathematically impossible.

alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Re: Universal first mover advantage
Posted: Sep 13, 2009, 5:17 PM

Up2ng, if you are going to categorize infinitely long games as draws then you will need to justify this in a robust and logical way. The reasons being that this is necessary if your argument is to have any rigor, and because the possibility of an infinite game or at least the idea of it is integral to my argument against zoey's proposition.

I realize that you could simply state that a game could have a rule that said that after X moves, the game is declared a draw, but I am saying that it would be possible to have a game where there was no advantage and that such a game would not have a rule that calls it a draw after X moves. If we are to simply state that all infinitely long games are to be treated as draws then I would not have disagreed with any of your points.

Here is the gist of the problem as I see it for anyone who wants to prove that there cannot be games that confer no advantage on either player, and that infinitely long games could be played by infinitely long-lived people with nothing better to do.

First point with respect to infinity. If we accept the idea that a given game could conceivably go on forever i.e. have an infinite number of moves played with no result, we ought to also allow ourselves to accept the proposition that there is also an infinite number of possible different games each with a unique set of rules. Now if there is an infinite number of possible games, then an infinite number of these will be games that can be played infinitely long without a result. Thus there must potentially exist an infinite set of possible combinations of rules, and within this an infinite number of sets of rules for games that go on forever without a result.

Now for the argument to hold that a no-advantage game cannot be constructed, you need to argue that there cannot exist a single combination of rules out of an infinite set of combinations of rules that could confer no advantage to either side. On what basis can you make this case? Why could there not be some set of rules that performs the trick of perfectly balancing player 1 and 2's chances? The argument that there must be a difference in advantage no matter how small is not an argument but simply a proclamation, since it does not tell us why such a difference must exist, and no actual logical reason has been provided for this, nor any evidence.

I would also ask this question another way: If there could exist a game where one player has an advantage of 0.0000for..infinity00000001 over the other player, then why could there not be a game with 0.000000for..infinity00000000 advantage? I mean, if you could so construct a set of rules with such finesse that you could achieve the infinite zeros + 1 situation, what fundamental law of mathematics do you propose would keep you from constructing a set of rules with zero advantage? Particularly given the two games are infinitesimally different. I mean if you were able to finesse a new design taking you from a game with infinite zeros + 2 down to infinite zeros + 1 then why could you not repeat this exercise and achieve zero? (btw, don't blame me for introducing this infinity of zeros concept that was zoey's idea!)

The second point I would make with respect to infinitely long games using perfect play, is that if such a game never finishes then by definition no winning advantage can exist. And, if no winning advantage exists then my proposition is correct. So either there are games that go forever with perfect play but there is no advantage to either player (in which case my proposition is true), or no game can go for an infinite number of moves. So, in order to prove the proposition that there are no evenly balanced games, you could start with demonstrating that no game can exist that could go for an infinite number of moves. Note though, that such a proof would be a necessary but not sufficient component of an overall proof since you would still need to demonstrate that of these finite length games there exist none that have zero player advantage. And to do that, you will need to prove the case that out of an infinity of rules sets that none could exist that are perfectly balanced..

My third point with respect to infinity is that if we assume that the proposition that all games must have at least an infinitesimal advantage from one player is true, we run into another problem. To take this proposition to its conclusion we must accept that such an advantage could have an infinity of zeros in front of the '1' as Zoey says. Such an advantage then is by definition infinitely small. In order for it to accumulate into an advantage that leads to a win it would need to be accumulated an infinite number of times prior to even reaching some threshold value whereby a forced win could be achieved. In other words for an infinite number of moves! So, it is not that such an infinitesimal advantage is insufficient to force a win per se, rather it is that it requires an infinite number of moves before it is sufficient to force a win. So, we cannot dismiss such tiny advantages as not being real advantages on the basis that they are insufficient to force a win because they are, but we have to accept that no win can ever eventuate from this advantage because an infinite number of moves would have to be played before such an advantage accumulates enough to force victory.

So where does this leave us? We have a contradiction. In my second point on infinity I pointed out that if infinitely long perfectly played games could exist then by definition no winning advantage can exist. So you will need to prove that no infinitely long games can exist in order to counter this. However, in my third point I pointed out that the only way an infinitesimally small advantage can become sufficient to force a win is that it accumulates over an infinitely large number of moves, and that this requires an infinitely long game. So your problem is this. The existence of infinitely long games disproves your conjecture, but at the same time you need them to exist in order for you to accumulate your infinitesimally small advantage. But if your argument relies on accumulating an infinitely small advantage over an infinite number of moves it fails because no result is ever achieved, and so by my second point to advantage exists. My challenge to you is to show a way out of this conundrum other than conceding that perfectly balanced games exist.

Cheers
Alison

watsu

Posts: 1,099
Registered: Dec 16, 2001
Home page
Re: Universal first mover advantage
Posted: Sep 13, 2009, 7:44 PM

okay, if this is truly primarily a discussion of infinite games, I'm bowing out. I recall enough of my Calculus studies to recognise how counter intuitive infinities can be. Hotels with an infinite number of rooms- all of them full- which can still hold an infinite number more people, with each person assigned to a different room and such. Not even going into the topic of the different levels of infinity. I thought the primary concern was to discuss games which were zero sum games- not infinitely long, and had little to no possibility for draws. which I think Up2ng has done well with. Since AI has only recently been able to resolve 170 year old positions in Checkers (see my earlier webcitation link if interested) we've got at leat a few more years before tougher finite games such as Pente, Chess and Go become anything more than weakly provable. No need for game theorists to attempt to tackle a hypothetical infinite set of infinitely long games which no one has even described in detail- aside from proposing that they exist. Sure, I like infinite discussions as well as the next person, but discussing something this nebulous- infinite zeros + a non zero term advantages in undefined ruleset hypothetical infinite gamesets- is a bit ungrounded even for me. Let me know when y'all return to Earth and we can talk about AI, game theory or whatever from a perspective which might actually mean something within our lifetimes.

I don't want to play non tournament rules games. If you take one of my unrated invites, play tourney
alisontate

Posts: 157
Registered: Nov 27, 2008
Age: 30
Re: Universal first mover advantage
Posted: Sep 14, 2009, 12:38 AM

I understand your point watsu. I studied Cantor's work (infinite hotels etc) and I agree that it can lead us into extremely nebulous and endless debate. This is not my intention, despite my lengthy last post.

I only discuss infinity because it was both raised as a counter-argument by zoey in our original discussion, and that it is an unavoidable consequence of perfect play of a balanced game with on draws. This is the whole point.

It is unfortunate that infinities have to be involved here, but a no-advantage, zero sum, no-draw game that has no arbitrary rules calling a draw and no built in attrition, played perfectly by both players must be infinitely long.

I am happy to take another tac on this discussion if you like as I also have a different line of argument that does not directly involve infinities. However, as long as my points regarding infinities remain unimpeached, I will have to consider zoey's original proposition untenable.

Cheers
Ali


Message was edited by: alisontate at Sep 16, 2009 9:10 AM


Replies: 41   Views: 66,817   Pages: 3   [ 1 2 3 | Next ]
Back to Topic List
Topics: [ Previous | Next ]


Powered by Jive Software