Forum Index Register Members List Events Mark Forums Read Help

 JREF Forum Book: Winning Ways for your Mathematical Plays

 Welcome to the JREF Forum, where we discuss skepticism, critical thinking, the paranormal and science in a friendly but lively way. You are currently viewing the forum as a guest, which means you are missing out on discussing matters that are of interest to you. Please consider registering so you can gain full use of the forum features and interact with other Members. Registration is simple, fast and free! Click here to register today.

 26th November 2008, 07:03 AM #1 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 Book: Winning Ways for your Mathematical Plays 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. __________________ Almo! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia
 27th November 2008, 05:44 AM #2 Angus McPresley Muse     Join Date: Jan 2006 Location: Melbourne, Australia Posts: 645 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? :-) __________________ I can find no fault with Pascal's Wager. And so, I've decided to worship Thor.
 27th November 2008, 07:36 AM #3 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 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! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia
 27th November 2008, 12:29 PM #4 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 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. __________________ Almo! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia Last edited by Almo; 27th November 2008 at 12:31 PM.
28th November 2008, 01:30 PM   #5
blobru
Philosopher

Join Date: May 2007
Posts: 6,587
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.
__________________
"Say to them, 'I am Nobody!'" -- Ulysses to the Cyclops

"Never mind. I can't read." -- Hokulele to the Easter Bunny

1st December 2008, 06:52 AM   #6
Almo
Masterblazer

Join Date: Aug 2005
Location: Montreal, Quebec
Posts: 6,404
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.
__________________
Almo!
My Blog
"No society ever collapsed because the poor had too much." — LeftySergeant
"It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia

Last edited by Almo; 1st December 2008 at 07:15 AM.

 2nd December 2008, 01:37 AM #7 blobru Philosopher     Join Date: May 2007 Posts: 6,587 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 NimberWP. Hope that helps. __________________ "Say to them, 'I am Nobody!'" -- Ulysses to the Cyclops "Never mind. I can't read." -- Hokulele to the Easter Bunny
 3rd December 2008, 08:00 AM #8 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 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. __________________ Almo! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia
 3rd December 2008, 08:13 AM #9 Folly Thinker   Join Date: Oct 2003 Posts: 243 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.
 3rd December 2008, 12:02 PM #10 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 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. __________________ Almo! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia
 3rd December 2008, 07:31 PM #11 blobru Philosopher     Join Date: May 2007 Posts: 6,587 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]. __________________ "Say to them, 'I am Nobody!'" -- Ulysses to the Cyclops "Never mind. I can't read." -- Hokulele to the Easter Bunny Last edited by blobru; 3rd December 2008 at 07:42 PM.
 4th December 2008, 10:39 AM #12 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 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. __________________ Almo! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia
 4th December 2008, 10:36 PM #13 blobru Philosopher     Join Date: May 2007 Posts: 6,587 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. __________________ "Say to them, 'I am Nobody!'" -- Ulysses to the Cyclops "Never mind. I can't read." -- Hokulele to the Easter Bunny Last edited by blobru; 4th December 2008 at 10:46 PM.
 5th December 2008, 10:23 AM #14 Almo Masterblazer     Join Date: Aug 2005 Location: Montreal, Quebec Posts: 6,404 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. __________________ Almo! My Blog "No society ever collapsed because the poor had too much." — LeftySergeant "It may be that there is no body really at rest, to which the places and motions of others may be referred." –Issac Newton in the Principia

JREF Forum

 Bookmarks Digg del.icio.us StumbleUpon Google Reddit