{"id":616,"date":"2008-03-23T21:42:13","date_gmt":"2008-03-23T21:42:13","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/03\/23\/nim\/"},"modified":"2008-03-23T21:42:13","modified_gmt":"2008-03-23T21:42:13","slug":"nim","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/03\/23\/nim\/","title":{"rendered":"Nim"},"content":{"rendered":"

As an introduction to a mathematical game, and how you
\ncan use a little bit of math to form a description of the game that
\nallows you to determine the optimal strategy, I’m going to talk a bit about Nim.<\/p>\n

<\/p>\n

Nim is a simple two-player turn-taking game. The idea is you’ve got a collection of piles of rocks. The standard
\nterminology calls each pile a heap<\/em>. Each turn, a player can take any number of rocks from any single heap.
\nIn classic Nim, whoever takes the last rock loses. But we’re going to start with an easier to analyze variant, where
\nwhoever takes the last rock wins.<\/p>\n

Let’s look at an example game. We’ve got two players, which we’ll
\ncall Adam and Bill. We’ve got 5 piles of rocks, which have 6, 2, 3, 7, and 3
\nrocks each. Adam goes first.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Player<\/th>\nMove<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n5<\/th>\n<\/tr>\n
<\/td>\n<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n7<\/td>\n3<\/td>\n<\/tr>\n
Adam<\/td>\n3 from 4<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n3<\/td>\n<\/tr>\n
Bill<\/td>\n1 from 5<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n2<\/td>\n<\/tr>\n
Adam<\/td>\n2 from 5<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n2 from 2<\/td>\n6<\/td>\n0<\/td>\n3<\/td>\n4<\/td>\n0<\/td>\n<\/tr>\n
Adam<\/td>\n3 from 1<\/td>\n3<\/td>\n0<\/td>\n3<\/td>\n4<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n4 from 4<\/td>\n3<\/td>\n0<\/td>\n3<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Adam<\/td>\n2 from 1<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n2 from 3<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Adam<\/td>\n1 from 3<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n1 from 1<\/td>\n0<\/td>\n0<\/td>\n9<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/table>\n

So Bill wins.<\/p>\n

Now, mathematically, what can we say about the game of Nim?<\/p>\n

Nim has some really interesting properties. It’s a sort of canonical game: there are a wide class of games that are all ultimately reduceable to equivalent games of Nim. Better, if both players are perfect, Nim is completely deterministic: you can tell which player will win before the game even starts.<\/p>\n

The easiest way to understand what the optimal strategy is, and to see why the winner is predetermined, is to look at nimbers<\/em>. Nimbers are an alternative construction of a field of numbers which capture the basic behavior of Nim. Using nimbers, you can add up the number of rocks in the heaps in a way that tells you what the key properties of the heaps are. It’s called the Nim-sum. For computer scientists, the nim-sum is easy: it’s the bitwise exclusive or of the number of rocks in each heap. For non-CS folk, I’ll
\ndescribe it in more detail below. <\/p>\n

The idea is that you always want to make the nim-sum be zero. The first player whose move makes the nim-sum be zero is guaranteed to win. Why?<\/p>\n

The key to Nim is understanding the way how the nim-sum works, and what
\nthat means. So let’s look in a bit more detail at the nim-sum. What it does is
\ndecompose each number into a sum of powers of two. Then any time there’s two
\ncopies of a single number, they can be canceled with one another. For example,
\nlet’s look at 11+19. 11 = 1 + 2 + 8; 19 = 1 + 2 + 16. So nim-summed together,
\nwe get 1+2+8+1+2+16. There are two 1s, so we cancel them; and there are two
\n2s, so we cancel them, leaving us with 8+16. So the nim-sum of 11+19 is
\n24.<\/p>\n

The main property of the nim-sum is that it describes cancellation. If the
\nnim-sum of the heaps is zero before your move, then if you can make a move taking N rocks from a heap, then that means that there must<\/em> be some
\nway that I can also<\/em> take N rocks from a heap. Because each time
\nyou make a move, removing rocks from a heap, the new nim-sum must<\/em> include a move where I can remove the same number of rocks; if there weren’t,
\nthen the nim-sum wouldn’t have been 0.<\/p>\n

Look at an example. If the nim-sum is 0, and you take 11 stones, the new nim-sum is going to be 11. If it weren’t, then the nim-sum before your move
\nwouldn’t have been zero. <\/p>\n

So no matter what you do, I’ve got a move left that makes the nim-sum be zero. So I’m going to win.<\/p>\n

Let’s go back and look at our example game again, but we’ll add a column for the nim-sum of the heaps.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Player<\/th>\nMove<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n5<\/th>\nNim-Sum<\/th>\n<\/tr>\n
<\/td>\n<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n7<\/td>\n3<\/td>\n3<\/td>\n<\/tr>\n
Adam<\/td>\n3 from 4<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n3<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n1 from 5<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n2<\/td>\n1<\/td>\n<\/tr>\n
Adam<\/td>\n2 from 5<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n0<\/td>\n3<\/td>\n<\/tr>\n
Bill<\/td>\n2 from 2<\/td>\n6<\/td>\n0<\/td>\n3<\/td>\n4<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
Adam<\/td>\n3 from 1<\/td>\n3<\/td>\n0<\/td>\n3<\/td>\n4<\/td>\n0<\/td>\n4<\/td>\n<\/tr>\n
Bill<\/td>\n4 from 4<\/td>\n3<\/td>\n0<\/td>\n3<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Adam<\/td>\n2 from 1<\/td>\n1<\/td>\n0<\/td>\n3<\/td>\n0<\/td>\n0<\/td>\n2<\/td>\n<\/tr>\n
Bill<\/td>\n2 from 3<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Adam<\/td>\n1 from 3<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
Bill<\/td>\n1 from 1<\/td>\n0<\/td>\n0<\/td>\n9<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/table>\n

We can see that neither player played well at all. After his first move, Adam should have had the game locked up:
\nhe made the nim-sum be zero. If he’d just kept it there, he’d have won. But he screwed it up. Then, on the 6th move,
\nBill had a zero nim-sum – he could have guaranteed a win if he’d played properly. How should it have gone? If
\nwe’re playing to pick up the last rock, something like this:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
Player<\/th>\nMove<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\n5<\/th>\nNim-Sum<\/th>\n<\/tr>\n
<\/td>\n<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n7<\/td>\n3<\/td>\n3<\/td>\n<\/tr>\n
Adam<\/td>\n3 from 4<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n3<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n1 from 5<\/td>\n6<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n2<\/td>\n1<\/td>\n<\/tr>\n
Adam<\/td>\n1 from 3<\/td>\n6<\/td>\n2<\/td>\n2<\/td>\n4<\/td>\n2<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n2 from 2<\/td>\n6<\/td>\n0<\/td>\n2<\/td>\n4<\/td>\n2<\/td>\n2<\/td>\n<\/tr>\n
Adam<\/td>\n2 from 5<\/td>\n6<\/td>\n0<\/td>\n2<\/td>\n4<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n4 from 4<\/td>\n3<\/td>\n0<\/td>\n2<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
Adam<\/td>\n1 from 1<\/td>\n2<\/td>\n0<\/td>\n2<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n2 from 3<\/td>\n2<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
Adam<\/td>\n2 from 1<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n<\/tr>\n<\/table>\n

Once Adam got a nim-sum of zero, he just cancels out every move that Bill makes until the game is over.<\/p>\n

Now, let’s pull a switch, and look at the classic form of Nim, where whoever takes the last rock
\nloses. Basically, you do the same thing<\/em>: play for nim-sum of zero – up until you get
\nto the point where making your move will leave no heap with more than one stone. Then you make the move
\nthat leaves an odd<\/em> number of heaps with one stone each. So in the example game above, Adam would play the same way up to his last move. Then he’d only take one stone – leaving one heap with one stone, forcing Bill
\nto take last. That’s a trivial example of the winning strategy. Let’s look at a slightly more interesting one.<\/p>\n\n\n\n\n\n\n\n\n
Player<\/th>\nMove<\/th>\n1<\/th>\n2<\/th>\n3<\/th>\n4<\/th>\nNim-Sum<\/th>\n<\/tr>\n
<\/td>\n<\/td>\n4<\/td>\n2<\/td>\n4<\/td>\n5<\/td>\n7<\/td>\n<\/tr>\n
Adam<\/td>\n 3 from 4<\/td>\n4<\/td>\n2<\/td>\n4<\/td>\n2<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n 2 from 3<\/td>\n4<\/td>\n2<\/td>\n1<\/td>\n2<\/td>\n5<\/td>\n<\/tr>\n
Adam<\/td>\n 3 from 1<\/td>\n1<\/td>\n2<\/td>\n1<\/td>\n2<\/td>\n0<\/td>\n<\/tr>\n
Bill<\/td>\n 1 from 4<\/td>\n1<\/td>\n2<\/td>\n1<\/td>\n1<\/td>\n3<\/td>\n<\/tr>\n
Adam<\/td>\n 2 from 2<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n1<\/td>\n<\/td>\n<\/tr>\n<\/table>\n

In the last move shown, if Adam had make the nim-sum zero, there would
\nhave been an even number of single-rock heaps left. So instead, he takes 2 from heap two. And
\nthat’s pretty much it: there’s nothing Bill can do. Once Adam got the nim-sum to zero, there
\nwas nothing Bill could ever do.<\/p>\n

So what about getting the nim-sum to zero? If the initial nim-sum is zero, then there is absolutely no way for
\nthe first player to win unless the second player makes a mistake. If the initial nim-sum is not<\/em> zero, then
\nthe first player can always make it be zero in one move; and that means that the first player must win.<\/p>\n","protected":false},"excerpt":{"rendered":"

As an introduction to a mathematical game, and how you can use a little bit of math to form a description of the game that allows you to determine the optimal strategy, I’m going to talk a bit about Nim.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[88],"tags":[],"class_list":["post-616","post","type-post","status-publish","format-standard","hentry","category-game-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/s4lzZS-nim","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/616","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=616"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/616\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=616"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}