Win at Nim! The secret mathematical strategy for kids (with challange problems in transfinite Nim for the rest of us)

Welcome to my latest instance of Math for Kids!

Today I had the pleasure to make an interactive mathematical presentation at my son’s school to the 7th / 8th grade Math Team, about 30 math-enthusiastic kids (twelve and thirteen years old) along with their math teachers and the chair of the school math department.

The topic was the game of Nim! This game has a secret mathematical strategy enabling anyone with that secret knowledge to win against those without it. It is a great game for kids, because with the strategy they can realistically expect to beat their parents, friends, siblings and parent’s friends almost every single time!

DSC00078

To play Nim, one player sets up a number of piles of blocks, and the opponent chooses whether to go first or second. The players take turns removing blocks — each player may remove any number of blocks (at least one) from any one pile, and it is fine to take a whole pile — whichever player takes the last block wins.

For the math team, we played a few demonstration games, in which I was able to beat all the brave challengers, and then the kids paired off to play each other and gain familiarity with the game. Then, it was time for the first strategy discussion.

What could the secret winning strategy be? I explained to the kids a trick that mathematicians often use when approaching a difficult problem, namely, to consider in detail some very simple special cases or boundary instances of the problem. It often happens that these special cases reveal a way of thinking about the problem that applies much more generally.

Perhaps one of the easiest special cases of Nim occurs when there is only one pile. If there is only one pile, then clearly one wants to go first, in order to make the winning move: take the entire pile!

Two balanced piles

A slightly less trivial and probably more informative case arises when there are exactly two piles. If the stacks have the same height, then the kids realized that the second player could make copying moves so as to preserve this balanced situation. The key insight now is that this copying strategy is a winning strategy, because if one can always copy, then in particular one will have a move whenever the opponent did, and so the opponent will never take the last block. With two piles, therefore, one wants always to make them balanced. If they are initially unbalanced, then choose to go first and follow the balancing strategy. If they are initially balanced, then choose to go second, and copy whatever moves your opponent makes to rebalance them.

DSC00076

A balanced position

With that insight, it is not difficult to see that it is winning to leave a position with any number of pairs of balanced piles. One can in effect play on each pair separately, because whenever the opponent makes a move on one of the piles, one can copy the move with the corresponding partner pile. In this way, we may count such a position overall as balanced. The more fundamental game-theoretic observation to make is that balanced piles in effect cancel each other out in any position, and one can ignore them when analyzing a position. When two balanced piles are present in a possibly more complicated position, one can pretend that they aren’t there, precisely because whenever your opponent plays on one of them, you can copy the move on the other, and so any winning strategy for the position in which those piles are absent can be converted into a winning strategy in which the balanced piles are present.

This idea now provides a complete winning strategy in the case that all piles have height one or two at most. One wants to leave a position with an even number of piles of each height. If only one height has an odd number of piles, then take a whole pile of that height. And if there are odd numbers of piles both of height one and two, then turn a height-two pile into a pile of height one, and this will make them both even. So any unbalanced position can be balanced, and any move on a balanced position will unbalance it.

DSC00074

1+2+3 counts as balanced

Let’s now consider that there may be piles of height three. For example, consider the basic position with piles of height one, two and three. The observation to make here is that any move on this position can be replied to with a move that leaves it balanced (check it yourself to be sure!). It follows that this position is winning to leave for the other player (and so one should go second on $1+2+3$). It would be nice if we could consider this position itself as already balanced in some sense. Indeed, we may incorporate this situation into the balancing idea if we think of the pile of height three as really consisting of two subpiles, one of height two and one of height one. In this way, the Nim position 1+2+3 counts as balanced, since the 3 counts as 2+1, which balances the other stacks.  The 1+2+3 position has two stacks of height two and two of height one, when one regards the stack of height three as having a substack of height two and a substack of height one.

This way of thinking produces a complete winning strategy for Nim positions involving piles of height at most three. (And this is a strategy that can be mastered even by very young children — a few years ago I had talked about Nim with much younger children, Math for six-year-olds: Win at Nim!, first-graders at my daughter’s school, and at that time we concentrated on posititions with piles of height at most three. Older kids, however, can handle the full strategy.) Namely, the winning strategy in this case is to strive to balance the position, to make an even number overall of piles of height one and two, where we count piles of height three as one each of one and two. If you always give your opponent a balanced position, then  you will win!  Faced with an unbalanced position, it is a fact that you can always find a balancing move, and any move on an balanced position will unbalance it.  If the game is just starting, and you are deciding whether to go first or second, you should determine whether it is balanced yet or not.  If it unbalanced, then you should go first and make the balancing move; if it is already balanced, then you should go second and adopt the copying strategy, in which you re-balance the position with each move.

The general winning strategy, of course, goes beyond three. The key idea is to realize that what is really going on when we represent $3$ as $2+1$ is that we are using the binary representation of the number $3$. To explain, I wrote the following numbers on the chalkboard $$1,\ 2,\ 4,\ 8,\ 16,\ 32,\ 64,\ \cdots$$ and was very pleased when the kids immediately shouted out, “The powers of two!” I explained that any natural number can be expressed uniquely as a sum of distinct powers of two. Asked for a favorite number less than one hundred, one student suggested $88$, and together we calculated $$88=64+16+8,$$ which means that the binary representation of $88$ is $1011000$, which I read off as, “one $64$, no $32$s, one $16$, one $8$, no $4$s, no $2$s and no $1$s. This is just the same as thinking of $9572$ as 9 thousands, 5 hundreds, 7 tens and 2 ones, using the powers of ten. It is interesting to learn that one may easily count very high on one hand using binary, up to 1023 on two hands!

The general strategy is to view every Nim pile as consisting of subpiles whose height is a power of two, and to make sure that one leaves a position that is balanced in the sense that every power of two has an even number of such instances in the position. So we think of $3$ as really $2+1$ for the purposes of balancing; $4$ counts as itself because it is a power of two, but $5$ counts as $4+1$ and $6$ counts as $4+2$ and $7$ as $4+2+1$. Another way to describe the strategy is that we express all the pile heights in binary, and we want an even number of $1$s in each binary place position.

The mathematical facts to verify are (1) any move on a balanced position in this powers-of-two sense will cause it to become unbalanced, and (2) any unbalanced position can be balanced in one move. It follows that leaving balanced positions is a winning strategy, because the winning move of taking the last block is a balancing move rather than an unbalancing move.

One can prove statement (1) by realizing that when you move a single stack, the binary representation changes, and so whichever binary digits changed will now become unbalanced.  For statement (2), consider the largest unbalanced power of two $2^k$ and move on any stack that contains a $2^k$ size substack. Since $2^k-1=111\cdots11$ in binary, one can attain any binary pattern for the smaller height stacks by removing between $1$ and $2^k$ many blocks. So one can balance the position.

As a practical matter, the proof of (2) also shows how one can find a (winning) balancing move, which can otherwise be difficult in some cases: look for the largest unbalanced power of two, and move on any pile containing such a subpile, making sure to leave a balanced position.

In most actual instances of Nim, the pile heights are rarely very tall, and so one is usually considering just $1$, $2$ and $4$ as the powers of two that arise.  A traditional starting configuration has piles of height 1, 3, 5, and 7, and this position is balanced, because one may view it as: $1, 2+1, 4+1, 4+2+1$, and there are an even number of 1s, 2s and 4s.

It is interesting to consider also the Misère form of Nim, where one wants NOT to take the last block. This version of the game also has a secret mathematical strategy, which I shall reveal later on.

Challenge 1.   What is the winning strategy in Misère Nim?

If you figure it out, please post a comment! I’ll post the solution later. One might naively expect that the winning strategy of Misère Nim is somehow totally opposite to the winning strategy of regular Nim, but in fact, the positions $1,2,3$ and $1,3,5,7$ are winning for the second player both in Nim and also in Misère Nim. Indeed, I claim that all nontrivial Nim positions that are winning for regular Nim (with a suitable meaning of “nontrivial”) are also winning for Misère Nim. Can you prove it?

Another interesting generalization, for the set-theorists, is to consider transfinite Nim, where the piles can have transfinite ordinal height. So we have finitely many piles of ordinal height, perhaps infinite, and a move consists of making any one pile strictly shorter. Since there are no infinite descending sequence of ordinals, the game will terminate in finitely many moves, and the winner is whowever removes the last block.

Challenge 2.  Who wins the transfinite Nim game with piles of heights: $$1\qquad \omega+3\qquad \omega^\omega+5\qquad \omega^{\omega+3}+\omega^\omega\cdot3+\omega\cdot 5+7\qquad \epsilon_0\qquad \omega_1$$ and what are the winning moves? What is the general winning strategy for transfinite Nim?

Post your solutions! You can also see my solution and further discussion.

 

An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014


This will be a talk for the interdisciplinary Group in Philosophical and Mathematical Logic at the University of Connecticut in Storrs, on December 5, 2014.

Value omega cubedAbstract. I shall give a general introduction to the theory of infinite games, with a focus on the theory of transfinite ordinal game values. These ordinal game values can be used to show that every open game — a game that, when won for a particular player, is won after finitely many moves — has a winning strategy for one of the players. By means of various example games, I hope to convey the extremely concrete game-theoretic meaning of these game values for various particular small infinite ordinals. Some of the examples will be drawn from infinite chess, which is chess played on a chessboard stretching infinitely without boundary in every direction, and the talk will include animations of infinite chess positions having large numbers of pieces (or infinitely many) with hundreds of pieces making coordinated attacks on the chessboard. Meanwhile, the exact value of the omega one of chess, denoted $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, is not currently known.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

The rule-making game

They said a king once ruled the forest, by Lizzie ThomasLet me tell you about a new game that we’ve been playing in our family, the rule-making game.  It is a talking game, requiring no pieces or objects of any kind, and it can easily be played whilst walking or traveling.  My children and I recently played several rounds of it walking around London on a recent visit there.

The game has no rules, initially, nor even any definite procedure — it is different every time — but things usually become clear soon enough.  It usually makes a better game to cooperate on the first several turns to lay the groundwork.

Let me explain how to play simply by example:

Papa:  The first rule is that the players shall take turns making rules, and that every rule shall have a rule number, which is incremented on each turn.

Horatio:  The second rule is that the players must state their rules in the form, “The first rule is…” or “the second rule is…” and so on, and that players are not allowed to ask what is the current rule number, or they lose.

Hypatia:  The third rule is that the other players must say, “thank you” after another player makes a rule.

     (… “thank you”…. “thank you”….)

Papa: The fourth rule is that the rules must not contradict each other, and no rule is allowed that abrogates an earlier rule.

     (… “thank you”…. “thank you”….)

Horatio:  The fifth rule is that after making an odd-numbered rule, the player must stomp on the ground.

     (STOMP… “thank you”…. “thank you”….)

Hypatia: The sixth rule is that no player may win immediately after their own rule.

     (… “thank you”…. “thank you”….)

Papa:  The seventh rule is that right after a player stomps according to rule five, the other two players must hop.

     (STOMP … “thank you”…. “thank you”….HOP….HOP…)

Horatio:  The eighth rule is that if a player loses, then the game continues without that person.

     (… “thank you”…. “thank you”….)

Hypatia: The ninth rule is that after stating a rule, the other two players must state a different color.

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “blue”… “green”…)

Papa:  The tenth rule is that furthermore, those colors must never repeat, and they must be stated simultaneously, on the count of 1-2-3.

     (… “thank you”…. “thank you”…. “1-2-3: neon green / violet”)

Horatio: The eleventh rule is that if there is only one player left, then that player wins.

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: red/orange”)

Hypatia:  The twelfth rule is that every player must jump up and down (…jump…) while stating their rule. (….jump jump jump…)

     (… “thank you”…. “thank you”…. “1-2-3: pink/turquoise”)

Papa: (jump jump…) The thirteenth rule is that (…jump…) in the case of dispute (…jump…), the question of whether or not someone has violated or followed a rule shall be decided by majority vote (…jump…).

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: yellow/brown”)

Horatio: (jump….) The fourteenth rule is that (…jump…) before stating their rule, the players must state a country, and that whoever repeats a country loses (…jump…)

     (… “thank you”…. “thank you”…. “1-2-3: black/gray”)

Hypatia:  (jump…)  Germany.  The fifteenth rule is that (…jump…) there can be at most twenty-five rules.

(STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: sky blue / peach”)

Papa:  (jump…)  United States.  The sixteenth rule is that (…jump…) if all current players lose at the same time after a rule, then the player previous to that rule-maker is declared the “honorary winner”.  (…jump…)

(… “thank you”…. “thank you”…. “1-2-3: white / white”)

Oh no! Since both Horatio and Hypatia said “white”, they both lose.  And then Papa also loses in light of rule six. So we’ve all lost!  But then, in light of rule sixteen, Hypatia is declared the honorary winner! Hooray for Hypatia!

I hope you all get the idea.  Please enjoy!  And report your crazy or interesting rules in the comments below.

The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014

Releasing the hordesI shall speak at the Virginia Commonwealth University Math Colloquium on November 21, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite chessboard stretching without bound in every direction—as a central example. Since chess, when won, is always won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values, which provide a measure in a position of the distance remaining to victory. I shall exhibit several interesting positions in infinite chess with very high transfinite ordinal game values. Some of these positions involve large numbers of pieces, and the talk will include animations of infinite chess in play, with hundreds of pieces (or infinitely many) making coordinated attacks on the board. Meanwhile, the precise ordinal value of the omega one of chess is an open mathematical question.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

Transfinite game values in infinite chess and other infinite games, Hausdorff Center, Bonn, May 2014

Releasing the hordesI shall be very pleased to speak at the colloquium and workshop Infinity, computability, and metamathematics, celebrating the 60th birthdays of Peter Koepke and Philip Welch, held at the Hausdorff Center for Mathematics May 23-25, 2014 at the Universität Bonn.  My talk will be the Friday colloquium talk, for a general mathematical audience.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite edgeless chessboard—as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question.

 

Slides | Schedule | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

Rubik's cube competition, CSI, November 14, 2013

Rubik's cube 2

Come and compete in the CSI Rubik’s cube competition!

November 14, 2013, College of Staten Island of CUNY, 1S-107, 2:30 pm.

Sponsored by MTH 339, and the CSI Math Club.

As a part of the undergraduate course in abstract algebra (MTH 339), which I am teaching this semester at the College of Staten Island, we shall hold a Rubik’s cube competition on November 14th.  In class, I have used the Rubik’s cube as a source of examples to explain various group-theoretic concepts, and I have encouraged the students to learn to solve the cube.  Several have now already mastered it, and there seems lately to be a lot of Rubik’s cube activity in the math department.  (I am giving extra credit for any student who can solve a scrambled cube in my office.)

Several students have learned how to solve the cube from the following video, which explains one of the layer-based solution methods:

Free New York Pizza!

The Competition.  On November 14, 2013, we will have the Rubik’s cube competition, with several rounds of competition, to see who can solve the cube the fastest.  Prizes will be awarded, and best of all, there will be free pizza!

Results Of the Competition

The event has now taken place. We had 15 competitors, from all around the College and beyond.  We organized two qualifying heats of 7 and 8 competitors, respectively, taking the top four from each qualtifying heat to form the quarterfinalist competitors. The top four of these formed the semifinalist competitors. And the top two of these headed off in the championship round.  The champion, Sam Obisanya, won all the rounds in which he competed, and his cube was a blaze of lightning color as he solved it.  Honorable mention goes especially to Oveen Joseph, who faced Sam in the championship round and who came out to the college from middle school I.S.72, where he is in the 7th grade, and also to Justin Mills, who had extremely fast times.

Quarterfinals:

Itiel Cohen (CSI math major)

William George (CSI math major)

Oveen Joseph (middle school I.S.72, 7th grade)

Wing Yang Law (CSI math major)

Justin Mills (CSI psychology major)

Mike Siozios (CSI math major)

Sam Obisanya (CSI nursing major)

James Yap (CSI math major)

Semifinals:

Oveen Joseph

Justin Mills

Sam Obisanya

James Yap

Championship round:

Oveen Joseph

Sam Obisanya

Final Champion:

 Sam Obisanya

Congratulations to our champion and to all the competitors.

Rubik's cube

 

Win the game of Nim! CSI Math Club, October, 2013

This will be a talk for the CSI Math Club on October 31, 2013 at 2:30 pm in room 1S-107.

DSC00074Abstract  Come and learn how to play and win the game of Nim!  The game has two players, faced with several small piles of blocks.  Each player, on their turn, can remove one or more blocks from one pile, but only one pile. (Removing a whole pile is fine.)  The player who removes the last block wins.  This simple-to-describe game is maddening for those who don’t know the secret mathematical winning strategy.  Come and learn the mathematical secret that will allow you to win every time against someone who doesn’t know it.

 

 

Doubled, squared, cubed: a math game for kids or anyone

The number that must not be named

Doubled, squared, cubed is a great math game to play with kids or anyone interested in math.  It is a talking game, requiring no pieces or physical objects, played by a group of two or more people at almost any level of mathematical difficulty, while sitting, walking, boating or whatever.  We play it in our family (two kids, ages 7 and 11) when we are sitting around a table or when walking somewhere or when traveling by train.  I fondly recall playing the game with my brothers and sisters in my own childhood.

The game proceeds by first agreeing on an allowed number range.  For youngsters, perhaps one wants to allow the integers from 0 to 100, inclusive, but one will want to have negative numbers soon enough, and of course much more sophisticated play is possible. Eventually, one lessens or even abandons the restriction altogether. The first player offers a number, and each subsequent player in turn offers a mathematical operation, which is to be applied to the current number, which must not be mentioned explicitly.  The resulting number must be in the allowed number range.

The goal of the game is successfully to keep track of the number as it changes, and to offer an operation that makes sense with that number, while staying within the range of allowed numbers.  The point is to have some style, to offer an operation that proves that you know what the number is, without stating the number explicitly.  Perhaps your operation makes the new number a nice round number, or perhaps your operation can seldom be legally applied, and so applying it indicates that you know it is allowed to do so.  You must offer only operations that you yourself can compute, and which do not rely on hidden information (for example, “times the number of grapes I ate at breakfast” is not really permissible).

A losing move is one that doesn’t make sense or that results in a number outside the allowed range. In this case, the game can continue without that person, and the last person left wins.  It is not allowed to offer an operation that can always be applied, such as “times zero” or “minus itself“, or which can always be applied immediately after the previous operation, such as saying “times two” right after someone said, “cut in half”.  But in truth, the main point is to have some fun, rather than to win. Part of the game is surely simply to talk about new mathematical operations, and we usually take time out to discuss or explain any mathematical issue that may come up.  So this is an enjoyable way for the kids to encounter new mathematical ideas.

Let me simply illustrate a typical progression of the game, as it might be played in my family:

Hypatia: one

Barbara: doubled

Horatio: squared

Joel: cubed

Hypatia: plus 36

Barbara: square root

Horatio: divided by 5

Joel: times 50

Hypatia: minus 100

Barbara: times 6 billion

Horatio: plus 99

Joel: divided by 11

Hypatia: plus 1

Barbara: to the power of two

Horatio: minus 99

Joel: times itself 6 billion times

Hypatia: minus one

Barbara: divided by ten thousand

Horatio: plus 50

Joel: plus half of itself

Hypatia: plus 25

Barbara: minus 99

Horatio: cube root

Joel: next prime number above

Hypatia: ten’s complement

Barbara: second square number above

Horatio: reverse the digits

Joel: plus 3 more than six squared

Hypatia: minus 100

and so on!

As the kids get older, we gradually incorporate more sophisticated elements into the game, and take a little time out to explain to young Hypatia, for example, what it means to cube a number, to take a number to the power two, or what a prime number is.  I remember playing the game with my math-savvy siblings when I was a kid, and the running number was sometimes something like $\sqrt{29}$ or $2+3i$, and a correspondingly full range of numbers and operations. It is fine to let the youngest drop out after a while, and continue with the older kids with more sophisticated operations; the youngsters will rejoin in the next round.  In my childhood, we had a “challenge” rule, used when someone suspects that someone else doesn’t know the number: when challenged, the person should say the number; if incorrect, they are out, and otherwise the challenger is out.

Last weekend, I played the game with Horatio and Hypatia as we walked through Central Park to the Natural History Museum, and they conspired in whispering tones to mess me up, until finally I lost track of the number and they won…

More math for six-year-olds: Win at Nim!

The latest installment of math for six-year-olds

Win at Nim!

Win at Nim!
Fold up the bottom flap to prevent parents from learning the super-secret strategy.

This morning once again I went into my daughter’s first-grade classroom, full of inquisitive six-and-seven-year-old girls, and made a mathematical presentation on the game of Nim.   

                   Win at Nim!

The game of Nim, I explained, begins with one player setting up a number of stacks of blocks,while the opponent chooses whether to go first or second.  Taking turns, each player removes one or more blocks from a stack of their choosing. (It is fine to take a whole stack on your turn.) The player who takes the last block wins.

 

DSC00078

We demonstrated the game by playing a number of exhibition rounds, and then the girls divided into pairs to play each other and also me.  They were surprised that I was able to win against them every single time.  In explanation, I told them that this was because in the game of Nim, there is a super-secret mathematical strategy!  Did they want to learn?  Yes!  I took as my goal that they would all learn the Nim strategy, so that they could go home and confound their parents by beating them again and again at the game.

Since this was a first-grade class, we concentrated at first on games with stacks of heights 1, 2 and 3 only, a special case of the game which can still challenge adults, but for which six-year-olds can easily learn the winning strategy.

Two balanced stacks

After gaining some familiarity with the game by playing several rounds amongst each other, we gathered again for the secret strategy session. We began by thinking about the case of a game of Nim with only two stacks. They had noticed that sometimes when I played them, I had made copying moves; and indeed I had purposely said, “I copy you,” each time this had occurred.  The copying idea is surely appealing when there are only two stacks.  After some discussion, the girls realized that with just two stacks, if one played so as to equalize them, then one would always be able to copy the opponent’s move.  In particular, this copying strategy would ensure that one had a move to make whenever the opponent did, and so one would win the game.

DSC00076

A balanced position

In short order, the girls also realized that if one had any number of pairs of such balanced stacks—so that every stack had a partner—then the whole position was also winning (for one to give to the other player), since one could copy a move on any stack by making the corresponding move on the partner stack.  Thus, we deduced that if we could match up stacks of equal height in pairs, then we had a winning strategy, the strategy to copy any move on a partner stack.

In particular, this balancing idea provides a complete winning strategy in the case of Nim games for which all stacks have height one or two.  One should play so as to give a balanced position to one’s opponent, namely, a position with an even number of stacks of height one and an even number of stacks of height two.  Any unbalanced position can always be balanced in this way, and any move on a balanced position will unbalance it.

DSC00074

1+2+3 counts as balanced

To handle positions with stacks of height three, the super-secret trick is that one can balance a stack of height three either with another stack of height three, of course, but also with two stacks:  one of height one and one of height two.   Thus, one should regard a stack of height three as consisting of two sub-stacks, one of height one and one of height two, for the purposes of balancing. Thus, the Nim position 1+2+3 counts as balanced, since the 3 counts as 2+1, which balances the other stacks.  The 1+2+3 position has two stacks of height two and two of height one, when one regards the stack of height three as having a substack of height two and a substack of height one.

In this way, one arrives at a complete winning strategy for Nim positions involving stacks of height at most three, and furthermore, this is a strategy that can be mastered by first-graders. The strategy is to strive to balance the position.  If you always give your opponent a balanced position, then  you will win!  Faced with an unbalanced position, you can always find a balancing move, and any move on an balanced position will unbalance it.  If the game is just starting, and you are deciding whether to go first or second, you should determine whether it is balanced yet or not.  If it unbalanced, then you should go first and make the balancing move; if it is already balanced, then you should go second and adopt the copying strategy, in which you re-balance the position with each move.

More advanced players will want to consider Nim positions with taller stacks than three, and we talked about this a little in the classroom.  Some of the girls realized that the copying strategy and the idea of balanced positions still worked with taller stacks.  One can balanced stacks of height four against other stacks of height four, and so one, but the trick for these taller stacks is that one may balance 5 with 4+1; balance 6 with 4+2; and 7 with 4+2+1. Mathematicians will recognize here the powers of two.

To teach the strategy to children, it is a great opportunity to talk about the powers of two. Any child knows how to count 1, 2, 3, 4 and so on, and most can count by twos 2, 4, 6, 8, 10, …; by fives 5, 10, 15, 20, …; by tens, by threes; by sevens; and so on.  , The powers of two are the numbers 1, 2, 4, 8, 16, 32, 64, 128, and so on, doubling each time.  Climbing this exponential growth, children are often amazed at how quickly one reaches very large numbers:

One plus one is two;

two plus two is four;

four plus four is eight;

eight plus eight is sixteen;

sixteen plus sixteen is thirty-two;

thirty-two plus thirty-two is sixty-four;

sixty-four plus sixty-four is one hundred twenty-eight.

For Nim, we don’t in practice need such big powers of two, since one doesn’t usually encounter stacks of height eight or larger, and usually just 1s, 2s and 4s suffice. The relevant fact for us here is that every natural number is uniquely expressible as a sum of distinct powers of two, which of course is just another way of talking about binary representation of a number in base two.  We regard a Nim stack as consisting of its power-of-two substacks.  Thus, a stack of height 3 counts as 2+1; a stack of height 5 counts as 4+1; a stack of height 6 counts as 4+2; and a stack of height 7 counts as 4+2+1.

Ultimately, the winning general strategy for Nim is always to play so as to balance the position, where one regards every stack as being composed of its power-of-two sub-stacks, and a position counts as balanced when these stacks and sub-stacks can be matched up in pairs. This is a winning strategy, since every unbalanced position can be balanced, and any move on a balanced position will unbalance it.  To balance an unbalanced stack, play on any stack containing the largest size unbalanced power of two substack, and reduce it so as to balance the parity of all the stacks.  If one thinks about it, at bottom what we are doing is ensuring that if we represent the stack heights in their binary representation, then we should play so as to ensure that the position has a even number of one digits in each place.

The theory of infinite games, with examples, including infinite chess

This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the  Yeshiva University Philosophy Club.  The event will take place in 5:45 pm in Furst Hall, on the corner of Amsterdam Ave. and 185th St.

Abstract. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers.  What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game?  Is there any reason to think that every game should have a winning strategy for one player or another?  Could there be a game, such that neither player has a way to force a win?  Must every computable game have a computable winning strategy?  I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.

NYlogic entry | Yeshiva University | Infinite chess | Video

 

The omega one of chess, CUNY, March, 2013

This is a talk for the New York Set Theory Seminar on March 1, 2013.

This talk will be based on my recent paper with C. D. A. Evans, Transfinite game values in infinite chess.

Infinite chess is chess played on an infinite chessboard.  Since checkmate, when it occurs, does so after finitely many moves, this is technically what is known as an open game, and is therefore subject to the theory of open games, including the theory of ordinal game values.  In this talk, I will give a general introduction to the theory of ordinal game values for ordinal games, before diving into several examples illustrating high transfinite game values in infinite chess.  The supremum of these values is the omega one of chess, denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\hskip-1.5ex {\ \atop\sim}}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we have specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot k$ and $\omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $\omega_1$.