Book: Winning Ways for your Mathematical Plays

[Almo]

Hello,

I'm reading this book Winning Ways for your Mathematical Plays, which is a book on game theory. I'm accustomed to reading math and physics books from my time as a grad student in physics.

But I can't get past the first part of the diagram on p. 9. Has anyone here been through this book? It looks to me like the top part of the pyramid should have a value of {0|0} since L wins no matter who starts, but he's one move from losing at the end either way.

[Angus McPresley]

I found the book on Amazon, and had to navigate to the page by hitting "Surprise me!" until it was close to the page number, then using the arrow keys. :-)

The values are bubbled up directly from the values of the two nodes below them, so it should definitely by {0|1}. But I'm not sure I fully understand your objection.

The game seems really poorly explained. One would think that the players took turns, but the move tree seems to indicate sequences where the same player moves twice in a row. And I also don't get how {1/2|2} = 1, and not 1 1/2.

And for that matter, how can skiers be skiing towards each other, anyway? :-)

[Almo]

In { x | y } = z,

z is the number of free moves Left has.
x is the number of free moves Left has if he moves.
y is the number of free moves Left has if Right moves.

Half moves are ones that effectively are like passing your turn; you get no closer to losing, but your opponent has to move again. So jumping a skier gets you no closer to the end, which is like not moving, then it's you're opponent's turn.

So in a position like 11(a) on page 8, R can move 3 times, Left can move 5, so the total value of the game is 2.

In the first position on Fig 12, if L moves, he can then move 5 times, and R can move 5 times, so it's 0. If R moves, R can move 4 and L can move 5, so it's 1.

This didn't make any sense to me yesterday, now it does. I guess it was because it doesn't matter whose turn it is when you evaluate the number of moves available, and I was taking that into account yesterday. Somehow, or something.

[Almo]

Wow this book is rough. I'm on p. 22 and there's another thing that makes no sense.

Quote:

For example, if the best Left move from some game G is to a position of value 2 3/8, and the best Right move to one of value 5, we can show that G itself must have value 3, which we found before in the form {2| }, for in this form 3 has only one option, 2, which does not lie strictly between 2 3/8 and 5, while 3 does.

But I thought a game of type {a| } had no available move for Right! So what gives?!?!

From the back of the book:

Originally Posted by Martin Gardner

...No other work has been so packed with completely new and significant material, or presented with so much wit, depth, and clarity.

Clarity? I wonder if this guy read the same book I'm reading.

[blobru]

Originally Posted by Almo

Wow this book is rough. I'm on p. 22 and there's another thing that makes no sense.

Quote:

For example, if the best Left move from some game G is to a position of value 2 3/8, and the best Right move to one of value 5, we can show that G itself must have value 3, which we found before in the form {2| }, for in this form 3 has only one option, 2, which does not lie strictly between 2 3/8 and 5, while 3 does.

But I thought a game of type {a| } had no available move for Right! So what gives?!?!

From the back of the book:

Originally Posted by Martin Gardner

...No other work has been so packed with completely new and significant material, or presented with so much wit, depth, and clarity.

Clarity? I wonder if this guy read the same book I'm reading.

Hi Almo. I read the first few chapters of this book some years ago, when I was working on AI for Grundy's Game (split piles into unequal piles until 2's & 1's remain). You're right, it's got its share of WTF! moments; authors have a habit of giving results ahead of explanations, so the notation doesn't really sink in.

In the example on p.22, remember they're evaluating the game G in terms of Left's advantage. Moving in these games is a disadvantage, so from the position they're referring to, and as you say above we don't know whose turn it is, Right's best move leaves Left with an advantage of 5, Left's best move leaves Left up 2 3/8. So Left is at least 3 moves ahead of Right: the 3/8 advantage will simplify to a full move. The basic form for G = 3 in terms of their notation is {2| }, where Left, if it is her turn, can move to a position with 2 moves left, and Right, if it's her turn, has lost (can't move at all). In "Ski Jump", it's:

L               R

...where Right's already skied off the slope; even if Left had to move 3 times in a row (and ski off the slope), Right would still lose: she would be the first player to have a turn and no move.

Anyway, that's the best of my recollection of what they're talking about -- hope I haven't made it worse.

[Almo]

Originally Posted by blobru

Hi Almo. I read the first few chapters of this book some years ago, when I was working on AI for Grundy's Game (split piles into unequal piles until 2's & 1's remain). You're right, it's got its share of WTF! moments; authors have a habit of giving results ahead of explanations, so the notation doesn't really sink in.

In the example on p.22, remember they're evaluating the game G in terms of Left's advantage. Moving in these games is a disadvantage, so from the position they're referring to, and as you say above we don't know whose turn it is, Right's best move leaves Left with an advantage of 5, Left's best move leaves Left up 2 3/8. So Left is at least 3 moves ahead of Right: the 3/8 advantage will simplify to a full move. The basic form for G = 3 in terms of their notation is {2| }, where Left, if it is her turn, can move to a position with 2 moves left, and Right, if it's her turn, has lost (can't move at all). In "Ski Jump", it's:

L               R

...where Right's already skied off the slope; even if Left had to move 3 times in a row (and ski off the slope), Right would still lose: she would be the first player to have a turn and no move.

Anyway, that's the best of my recollection of what they're talking about -- hope I haven't made it worse.

Well, that makes sense to me, except where the book says if Right moves in G, but then they show the position has no move for Right. Seems contradictory to me.

ETA: Wait, it doesn't make sense. I don't see how that's a 2 3/8 move situation.

ETA2: And I don't see how this can be the position. I don't see a 5 move advantage there.

[blobru]

Originally Posted by Almo

Well, that makes sense to me, except where the book says if Right moves in G, but then they show the position has no move for Right. Seems contradictory to me.

ETA: Wait, it doesn't make sense. I don't see how that's a 2 3/8 move situation.

ETA2: And I don't see how this can be the position. I don't see a 5 move advantage there.

You're right. The positions aren't [tactically] equivalent in terms of what moves are available; they're equivalent in terms of how much one player is ahead. If each makes the best available move from {5 | 2 3/8}, they end up at {2| }.

Caveat: that's how I remember it at least... as I said it's been awhile, and the notation is weird... I might be way off.

Maybe at this point it's better to just mechanically apply the rules without too much interpretation. I see from the amazon.com "look inside", right above the p. 22 example:

The Simplicity Rule
......If the options in
............{a,b,c,...|d,e,f,...}
......are all numbers, we'll say that the number x fits just if it's
............strictly greater than each of a,b,c,..., and
............strictly less than each of d,e,f,...,
......and x will be the simplest number that fits, if none of its options fit.

In this notation, as a Game number: x = 3 = {2| }. 2 isn't between 5 & 2 3/8 (_ isn't an option), while 3 is (note no x less than 3 decomposes into choices {a...|d...} that satisfy the rule). So {5 | 2 3/8} = 3.

It may be confusing because sometimes the authors speak of {a|d} as a position, sometimes as a number, interchangeably. I think of Game numbers ("nimbers") such as {a|d} are binary sets of Game numbers which decompose into simpler binary sets of Game numbers until you get to a base form, such as {2| } = 3. See Nimber^WP.

Hope that helps.

[Almo]

I guess what I'm hung up on is that when they say L is 3 moves ahead, that means given perfect moves from each player. In games where players don't make perfect moves, a 3-move advantage can still lose, so it looks odd to me to say it's equivalent to a game where one has already lost because they have no moves left.

[Folly]

Originally Posted by Almo

I guess what I'm hung up on is that when they say L is 3 moves ahead, that means given perfect moves from each player. In games where players don't make perfect moves, a 3-move advantage can still lose, so it looks odd to me to say it's equivalent to a game where one has already lost because they have no moves left.

Ahh, well, perfect play or something like it is the simplifying assumption that makes analysis possible. There's generally not much you can say if you start considering opponents who can make arbitrary mistakes.

[Almo]

Yeah, I'm slowly coming to understand how this works. I've been designing games for many many years, but I've never gone into the theory behind how this stuff works.

In theory, practice and theory are the same. In practice, they're not. Some smart guy said that but I don't remember who.

[blobru]

Originally Posted by Almo

I guess what I'm hung up on is that when they say L is 3 moves ahead, that means given perfect moves from each player. In games where players don't make perfect moves, a 3-move advantage can still lose, so it looks odd to me to say it's equivalent to a game where one has already lost because they have no moves left.

Maybe think of it as strategic equivalence, but not tactical. If you assume perfect tactics, there is no strategic difference between {5|2 3/8} and {2| }. However, the tactics to win, to maintain the theoretical 3 move advantage, are of course harder to think through for Left in the former position than in the latter. Similarly, though {5|2 5/16} = {5|2 3/8} = {5|2 1/2} = 3 in terms of strategic advantage, the first position is least "obvious" tactically -- there are more ways for Left to screw up, or more dodges for Right -- the last postion most.

Originally Posted by Almo

Yeah, I'm slowly coming to understand how this works. I've been designing games for many many years, but I've never gone into the theory behind how this stuff works.

If you're a PC game-designer, you may never have run into games like these: turn-based, perfect information, first no move loses. They're a fascinating subset of games, for analysis that is; for play, especially on the pc, not so much.

Quote:

In theory, practice and theory are the same. In practice, they're not. Some smart guy said that but I don't remember who.

Perfect quote. Turns out that's a very useful distinction here, between strategy [theory] & tactics [practice].

[Almo]

Originally Posted by blobru

If you're a PC game-designer, you may never have run into games like these: turn-based, perfect information, first no move loses. They're a fascinating subset of games, for analysis that is; for play, especially on the pc, not so much.

I do both boardgames and video games. I've "finished" two major board games. One is a space conquest economic/military game with dice, so it's definitely out of the realm of that kind of analysis.

The other is a small abstract game with simple rules and pieces. I also play a lot of these kinds of games, like Quarto! and Pylos. Pylos is awesome, BTW.

[blobru]

Originally Posted by Almo

I do both boardgames and video games. I've "finished" two major board games. One is a space conquest economic/military game with dice, so it's definitely out of the realm of that kind of analysis.

That's right, I'd forgotten -- this stuff (combinatorial game theory) only applies to games of no chance. Deciding ideal strategy for dice is too... subjective, I guess (when and how much to gamble) and messy.

CGT analyses of even the simplest games can get plenty deep. I'm just checking out a book on amazon, Tic-Tac-Toe Theory -- 746 pages!

Quote:

The other is a small abstract game with simple rules and pieces. I also play a lot of these kinds of games, like Quarto! and Pylos. Pylos is awesome, BTW.

Quarto (board game)^WP, Pylos (board game)^WP.

Those look like great games, straightforward and challenging. In the book, Pylos would be classed a partisan game (pieces for each player); Quarto, impartial (common pieces).

I was a total boardgame geek as a kid. One of my idols you've probably heard of, the great game designer Sid Sackson. Tried to design a few myself, but never came up with anything I really liked. Congrats on yours, eh: no small feat.

[Almo]

Originally Posted by blobru

Quarto (board game)^WP, Pylos (board game)^WP.

Those look like great games, straightforward and challenging. In the book, Pylos would be classed a partisan game (pieces for each player); Quarto, impartial (common pieces).

Yeah, I like them a lot. Other good ones in the Gigamic series are Quoridor, Quits and Skybridge. That company actually gave my little game a 3-week test. They liked it, but said it wasn't deep enough.

Originally Posted by blobru

I was a total boardgame geek as a kid. One of my idols you've probably heard of, the great game designer Sid Sackson. Tried to design a few myself, but never came up with anything I really liked. Congrats on yours, eh: no small feat.

Yeah, Gamut of Games is a rockin' book. I particularly like Focus and Knight Chase. Of course, Knight Chase is from Alex Randolph, so of course it's awesome. That guy is the God of game design. Twixt is truly awesome.

I find that I'm good at designing play mechanics, but I have a hard time with victory conditions.