Looks like its basically the name for the value given to a game state saying whether a player is guaranteed to win or lose, based on optimal play from that point.
Consider a single-stack game of Nim – a stack of N balls, from which at any turn a player may take however many he would like, and the winner is the one to take the last ball (alternatively, the loser is the player who has no possible move). Clearly, the first player loses if there are N=0 balls to begin with, and wins in every other case – by simply taking the entire stack in one move. So, it would seem that all games of single-stack Nim with N>0 are equivalent, in the sense that they are all guaranteed wins for the first player; but this turns out to be a very weak form of equivalence, as we shall see.
Now consider a two-stack game of Nim, with sizes N and M, and in every move a player may take as many balls as he likes but from only one of the stacks. If N=M, it is easy to see that the second player can always win: Whatever move the first player makes in one stack, he copies in the second stack, and the game is again at a state where both stacks are the same size, but smaller; until the first player depletes one stack, whereupon the second takes the remaining balls in the second stack. And for the same reason, if N and M were not equal, the first player can always win – by removing |N-M| balls from the biggest stack, and reducing to the case where the stacks are equal and they are the second player, a guaranteed win.
Given two games, we can consider their “sum”, in which the two games are played simultaneously, and at each turn a player must make a legal move in exactly one of the games, of his choice. For example, a two-stack game of Nim is the sum of the two corresponding one-stack game of Nim. By the same “copying” argument as above, we see that the sum of a game with itself is always a win for the second player – which motivates us to saying that two games are equivalent if and only if their sum is a game where the second player can guarantee a win. For example, the argument above shows that single-stack games of Nim with N and M balls are equivalent if and only if N=M. This form of equivalence refines the first one: it’s easy to see that all second-player-win game are equivalent to each other, but first-player-win games form a multitude of equivalence classes (e.g. 7-ball Nim and 13-ball Nim are not equivalent, even though they are both first-player-wins). Additionally this definition respects addition – in the sense that if G1 is equivalent to G2 and H1 is equivalent to H2, then G1+H1 is equivalent to G2+H2 – whereas the first definition did not (e.g. 7 and 13 are both first-player-wins, but 7+13 is a first-player-win whereas 7+7 and 13+13 go to the second player).
But what makes this equivalence really interesting is the Sprague-Grundy theorem [1], which states that any game of a certain type is always equivalent in this sense to a single-stack game of Nim with a certain number of balls. This number is unique, since two games of single-stack Nim are equivalent if and only if they have the same number of balls in them – and this number is called the Nim-value of the game (amongst other names, such as Grundy number and Nimber). This theorem does not apply for every game – for example, chess, tic-tac-toe and basketball do not have Nim values – but only to 2 player games where (a) the loser is the player who cannot make a move and (b) the list of possible moves from a given configuration does not depend on whether the current player originally went first or second. These kind of games are called “impartial games” in normal play convention [2].
This fact can be very useful when analyzing games that naturally split up as sums of games (e.g. [3]), since it is easy to add up Nim games – a two-stack game of Nim with N and M balls is equivalent to the one-stack game with N^M balls (where ^ denotes the binary exclusive or operator [4]). Furthermore, if one knows the Nim-value of all possible configurations obtained after one move, it is easy to determine the Nim-value of the current configuration.
However, this is not too relevant for the game that the Baron participated in, which seems to be similar to Nim with the exception that at any point one may only take 1, 2, or 3 balls from a stack [5]; assuming the game was single-stacked, then perfect play can and should be analyzed by just considering winning and losing states – Nim-values are an overkill. If it were a multi-stack game, then Nim-values would be useful. It is not too hard to see that this game, with N balls, is equivalent to a game of Nim with K balls, where K is the unique number amongst 0, 1, 2, and 3 such that N-K is divisible by 4. This fact would be useful if the game had multiple stacks instead of only one.
Although, one has to admit, not nearly as useful as summoning a buttload of insta-kill guns. A much more versatile solution, applicable to a far larger set of problems.
And the great knight charges forth on his mighty steed to find the castle, and slay his mighty foe, all the while chased by yon fair maiden yelling about game theory and probability mechanics . . . .
Doesn’t quite fit the usual rhythm of these things, does it?
Well, if we’re looking at the scrambling of archetypes here, it’s more:
And the mighty steed, with yon fair maiden in tow, charges forth to find the castle and slay his might foe, all the while chased by yon great knight yelling about game theory and probability mechanics.
In a cringe-inducing reminder of how racist the 1950s were, it turns out that it was actually the other way around. Just look up “Tonto” in any Spanish dictionary.
She lacks an organic body; he lacked experience before his got mre’d… should be fairly equal there. I just picture Steve at mreinfo on YouTube opening a Nick mre… “Let’s get this out on a tray… nice!”
I had to look nim-values up, and I got flooded by Wikipedia posts on game theory. Gah.
Looks like its basically the name for the value given to a game state saying whether a player is guaranteed to win or lose, based on optimal play from that point.
Nim is the name of the game from the previous strips, where players take turns removing a certain amount of things from a heap.
Not exactly. Let me put my Lovelace hat on…
Consider a single-stack game of Nim – a stack of N balls, from which at any turn a player may take however many he would like, and the winner is the one to take the last ball (alternatively, the loser is the player who has no possible move). Clearly, the first player loses if there are N=0 balls to begin with, and wins in every other case – by simply taking the entire stack in one move. So, it would seem that all games of single-stack Nim with N>0 are equivalent, in the sense that they are all guaranteed wins for the first player; but this turns out to be a very weak form of equivalence, as we shall see.
Now consider a two-stack game of Nim, with sizes N and M, and in every move a player may take as many balls as he likes but from only one of the stacks. If N=M, it is easy to see that the second player can always win: Whatever move the first player makes in one stack, he copies in the second stack, and the game is again at a state where both stacks are the same size, but smaller; until the first player depletes one stack, whereupon the second takes the remaining balls in the second stack. And for the same reason, if N and M were not equal, the first player can always win – by removing |N-M| balls from the biggest stack, and reducing to the case where the stacks are equal and they are the second player, a guaranteed win.
Given two games, we can consider their “sum”, in which the two games are played simultaneously, and at each turn a player must make a legal move in exactly one of the games, of his choice. For example, a two-stack game of Nim is the sum of the two corresponding one-stack game of Nim. By the same “copying” argument as above, we see that the sum of a game with itself is always a win for the second player – which motivates us to saying that two games are equivalent if and only if their sum is a game where the second player can guarantee a win. For example, the argument above shows that single-stack games of Nim with N and M balls are equivalent if and only if N=M. This form of equivalence refines the first one: it’s easy to see that all second-player-win game are equivalent to each other, but first-player-win games form a multitude of equivalence classes (e.g. 7-ball Nim and 13-ball Nim are not equivalent, even though they are both first-player-wins). Additionally this definition respects addition – in the sense that if G1 is equivalent to G2 and H1 is equivalent to H2, then G1+H1 is equivalent to G2+H2 – whereas the first definition did not (e.g. 7 and 13 are both first-player-wins, but 7+13 is a first-player-win whereas 7+7 and 13+13 go to the second player).
But what makes this equivalence really interesting is the Sprague-Grundy theorem [1], which states that any game of a certain type is always equivalent in this sense to a single-stack game of Nim with a certain number of balls. This number is unique, since two games of single-stack Nim are equivalent if and only if they have the same number of balls in them – and this number is called the Nim-value of the game (amongst other names, such as Grundy number and Nimber). This theorem does not apply for every game – for example, chess, tic-tac-toe and basketball do not have Nim values – but only to 2 player games where (a) the loser is the player who cannot make a move and (b) the list of possible moves from a given configuration does not depend on whether the current player originally went first or second. These kind of games are called “impartial games” in normal play convention [2].
This fact can be very useful when analyzing games that naturally split up as sums of games (e.g. [3]), since it is easy to add up Nim games – a two-stack game of Nim with N and M balls is equivalent to the one-stack game with N^M balls (where ^ denotes the binary exclusive or operator [4]). Furthermore, if one knows the Nim-value of all possible configurations obtained after one move, it is easy to determine the Nim-value of the current configuration.
However, this is not too relevant for the game that the Baron participated in, which seems to be similar to Nim with the exception that at any point one may only take 1, 2, or 3 balls from a stack [5]; assuming the game was single-stacked, then perfect play can and should be analyzed by just considering winning and losing states – Nim-values are an overkill. If it were a multi-stack game, then Nim-values would be useful. It is not too hard to see that this game, with N balls, is equivalent to a game of Nim with K balls, where K is the unique number amongst 0, 1, 2, and 3 such that N-K is divisible by 4. This fact would be useful if the game had multiple stacks instead of only one.
Although, one has to admit, not nearly as useful as summoning a buttload of insta-kill guns. A much more versatile solution, applicable to a far larger set of problems.
—–
[1] https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
[2] https://en.wikipedia.org/wiki/Impartial_game
[3] https://en.wikipedia.org/wiki/Kayles
[4] https://en.wikipedia.org/wiki/Bitwise_operation#XOR
[5] https://en.wikipedia.org/wiki/Nim#The_21_game
It’s time for some game theory!
Aw, Nick *did* decide to hug Baron!
My grandpa was a math professor and we used to play Nim.
Whimsy could make a new animated movie, “The Secret of Nim”.
…in which the rats under the rosebush don’t really have any advanced technology, but /are/ very good at mathematical models of resource allocation?
And the great knight charges forth on his mighty steed to find the castle, and slay his mighty foe, all the while chased by yon fair maiden yelling about game theory and probability mechanics . . . .
Doesn’t quite fit the usual rhythm of these things, does it?
Well, if we’re looking at the scrambling of archetypes here, it’s more:
And the mighty steed, with yon fair maiden in tow, charges forth to find the castle and slay his might foe, all the while chased by yon great knight yelling about game theory and probability mechanics.
The Lone Ranger: Well, Tonto, it looks like we’re surrounded by Indians.
Tonto: Who’s “we,” paleface?
…puts me in the mind of Gary Larson’s Lone Ranger cartoon.
Long since retired, one day the Lone Ranger makes an unpleasant discovery.
In a cringe-inducing reminder of how racist the 1950s were, it turns out that it was actually the other way around. Just look up “Tonto” in any Spanish dictionary.
Nim! Nim nim nim!! The first (well only) big paper I ever had to write on math was about nim! Now I am all warm and fuzzy inside.
I had a whole class on games that reduce to Nim. One of my favorites. It’s a bit of math that excites all of about ten people, but I’m one of them.
In the name of Tip, why is it called “nim?”
It’s from an Old English word meaning “to take”. Because that’s what you do. You take stones from piles.
Actually, it’s the “fair damsel” that’s charging forth on the mighty steed.
The great knight is chasing along behind on foot…
Does the mighty steed have a say in the matter?
Yeah, Nick only makes a fair damsel (for certain values of damsel),
Tip would be making a FABULOUS damsel!
Why did the Baron abandon his cool scarf?
Why is Baron letting Nick ride, not Lovelace- in whom he is interested?
Because he’s a unicorn? 🙂
Because Nick’s qualified to ride one.
She lacks an organic body; he lacked experience before his got mre’d… should be fairly equal there. I just picture Steve at mreinfo on YouTube opening a Nick mre… “Let’s get this out on a tray… nice!”
Oh right, jumping on the bandwaggon, doing combinatorial game theory jokes like all the big webcomics are doing these days.