Wythoff’s Game (Get Home)

Wythoff’s Game (Get Home)


Hi, everyone! Recently, I made a quick video with my friend, Katie Steckles, about a game with a winning strategy. Well, actually, I think there’s more to say about this game. It’s called Wythoff’s Game, and as a quick recap you play it on a chessboard, and there are two players. You take it in turns to move a piece. And that piece can move any number of squares to the left, any number of squares down, and any number of squares on a down-left diagonal. And the winner is the one who moves the piece to the bottom left square. And I asked you “What are the losing squares?” Well, let’s take a look at this, because it actually involves some surprising maths. Let’s start with a 3 x 3 grid, and work our way backwards. And we’ll call the goal (0,0). Then any square in direct line of sight of the goal, we’ll call a ‘winning square.’ So you can reach the goal from a winning square. Any other square we’ll call a ‘losing square.’ You can reach winning squares, but you can’t reach the goal itself. So, in this coordinate system, the losing squares are (1,2) and (2,1). Now let’s work backwards to a 6 x 6 grid. Any square in direct line of sight of the goal, or of a losing square, is a winning square. That means you can move directly to the goal or you can move your opponent into a losing position. If we carry on, we can do the full chessboard and we see that the losing squares are (1,2), (3,5), (4,7), and their reflections, which means the two coordinates are swapped. And if we carry on, we can see that the losing squares form two very definite lines. And the gradient of those lines are the Golden Ratio, and it’s reciprocal. WHAAAAAAAT??? Yeah. If we just look at the losing squares above the main diagonal, this is what we get. Just remember that you get their reflections for free. Now there are a couple of things to notice here. The first thing to notice is that for the nth losing square, the difference in the coordinates is n. So, for example, for the third losing square the coordinates are (4,7), and the difference is 7 minus 4, and that’s 3. The second thing to notice is every positive integer appears once, and once only, either as an X coordinate or a Y coordinate. And using those two rules we can generate all the losing squares one at a time. For example, if we want to work out what the fourth losing square is, we use the smallest positive integer that hasn’t appeared yet, which is 6 in this case. We know the difference in coordinates has to be four, so the fourth losing square has coordinates (6,10). So Willem Wythoff was a Dutch mathematician, and what he did was to find a formula for the coordinates. That means you don’t have to keep generating the losing squares one at a time. He did this in 1907. And the formula he found for the nth losing square was this. So here phi stands for the Golden Ratio, which is 1.618. And the first coordinate is n times the Golden Ratio, and then rounded down to the previous integer. And the second coordinate is n times the Golden Ratio squared, also rounded down to the previous integer. What Wythoff showed was that the Golden Ratio was the only number you could use in this way that had the desired properties. Those properties are that each number appears once, and once only, and the difference in the coordinates is n. And that’s it! But with just one more thing to say. This version of the game that I showed you with the chessboard was actually invented much later, and independently, by a different mathematician, called Rufus Isaacs. Wythoff’s description was actually very different. He described the game as having two piles of counters. Let’s say a red pile of counters, and a blue pile, and you can have any number of counters in each pile, and then two players take it in turns to remove the counters. They can either take as many red counters as they want, they can take as many blue counters as they want, or they can remove an equal number of red and blue counters at the same time. And the winner is the one who takes the last counter. Some of you may recognize this as being a lot like the game “Nim.” But this is equivalent to the game that I showed you. And I will let you think about why those two games are equivalent. And so, for now, if you have been, thanks for watching.

100 thoughts on “Wythoff’s Game (Get Home)

  1. ⬅️ movement = the blue Nim pile,
    ⬇️ movement = the red Nim pile,
    ↙️ movement = equal amounts from both piles

    Still, I can't help but be amazed that φ is coming out of this game, rather than something like √2, since it involves diagonal movement. I usually associate φ more with Fibonacci and Fibonacci-like sequences…

  2. That game with the counters is equivalent to just playing on one side of the diagonal but starting on square (4,7) or (7,4) depending on which side of the diagonal

  3. on the 6by6 squared – why a square like 1-5 is not loosing ? You cannot go directly from 1-5 to 0-0. Why squares in line with loosing squares are winning ? The goal of the game is to move a piece to 0-0, not to any loosing point.

  4. In regard of game equivalence, the "two-piles Nim game" simply can be visualized by taking the two piles as x and y coordinates.

    Just one note about the symmetry. Though we have the symmetry, we cannot play this game on only half the board (including the middle diagonal, of course). Just think about starting in the third column. If the losing square on c2 or (2,1) does not exist, the reason all squares above it are winning squares is gone (two can still reach (1,2), but most of them not). This causes another square of the c column to become a losing square and has a ripple effect, which causes a much simpler pattern sequence of losing squares.

    The half-board then would look like this:
    𝚆𝚆𝚆𝚆𝚆𝚆𝚆𝚆
    𝚆𝚆𝚆𝙻𝚆𝚆𝚆𝚇
    𝚆𝚆𝚆𝚆𝚆𝚆𝚇𝚇
    𝚆𝚆𝙻𝚆𝚆𝚇𝚇𝚇
    𝚆𝚆𝚆𝚆𝚇𝚇𝚇𝚇
    𝚆𝙻𝚆𝚇𝚇𝚇𝚇𝚇
    𝚆𝚆𝚇𝚇𝚇𝚇𝚇𝚇
    𝙻𝚇𝚇𝚇𝚇𝚇𝚇𝚇

    Where 𝚇 is unallowed (removed half), 𝙻 is losing and 𝚆 is winning square as used here by others. (By the way: Using MATHEMATICAL MONOSPACE CAPITAL letters helps here to have that monospaced section in an otherwise proportional font)

    Losing squares now are all (1,2) steps from (0,0), so all (n,2n) squares are losing squares and this would become rather boring. So the interesting constellation of losing squares only is induced by the lower half of the board.

  5. I watched the previous video and felt it was comfortably trivial. <singing>lalala I'm so clever</singing> After watching this I feel like a naive character who is oblivious to the huge scary spectre of Mathematics standing behind them. Thank you Dr @JamesGrime.

  6. Fun fact: if we have two real positive numbers x,y then 1/x+1/y=1 if and only if every positive integer appears in sequence {⎿nx⏌} or {⎿ny⏌} (n is a positive integer). We can replace the 1 with 2(3,4,…) and then every integer appears twice (thrice,..) in a sequences.

  7. I found a nice set of blog posts that prove the results mentioned. (read from the bottom up) http://blog.zacharyabel.com/tag/wythoffs-game/

  8. Id love to see you at least sketch out a proof of results in these videos. Dont assume your audience is math averse!

  9. They're equivalent this way: if the red pile is considered the y coordinate and the blue pile is considered the x coordinate, then the losing squares on the chess board indicate the losing piles in the pile game. The rule on the chessboard of only moving straight down, left, or diagonally (which is equally down and left) is the same as the rule in the pile game of taking pieces away from one or the other, or both equally.

    Thanks @singingbanana! I love your work with Brady Harambe in Numberphile. I hope my explanation was accurate and correct.

  10. I got why they were equivalent basically as soon as the video ended (so within like 3 seconds).
    To the left and to the down are kind of like red and blue, and diagonally is kind of like both. And by 'kind of like' I mean 'precisely the same.'

  11. The games are equivalent because 1 pile is an x coordinate and 1 pile a y, (0,0) is the home. By removing some number from one pile you move towards the home on a row/colum and by removing from both you move diagonally.

  12. It's essentially the same as X and Y coordinates right? Hence your rules say you can't go up or right since that would equate to adding counters haha

  13. You have two numbers of counters which are analogous to a coordinates system, and you are trying to move towards zero, zero. You start with two positive integers, and you can reduce each integer by any number, which is equivalent to moving left or down on a coordinates system, or you can reduce both integers by the same number, which is the same as moving down-left diagonally. The ratio you start with in the example is also 4:7 which is consistent with the formula shown and therefore represents a losing square. With perfect play, whoever goes first will lose.

  14. "red" and "blue" basically represent the axes of the chess board. "taking away" a counter is effectively moving down the respective axis.

  15. They're equivalent because you can start off with a number of red and blue counters, telling you the coordinates of where you are on the chess board. (Origin at bottom left.) Then taking red counters is the equivalent of going left by that number of pieces. Taking blue counters is the equivalent of going down by that many counters. Taking both red and blue counters is going diagonally. It has to be the same amount because you are only going on a perfect bishop-like diagonal.
    (Note that red and blue can be switched, and it doesn't effect the game. This is equivalent to the symmetry of the board along the line y=x.)

  16. When you first uploaded the originaly video, my first thought was, "This is a lot like nims".
    I was really surprised that you mentioned it in this video 😀

  17. Another reason to get out my Go board!
    I really didn't think it would respond to the golden ratio though. That was a really big surprise!
    I wonder how the game works out for any n number of piles though. That would be hard, but I'll sleep on the idea.
    Cheers!

  18. Everything in the normal convention is equivalent to games of nim and presumably can be solved using nim sums. But I've never had even an inkling of how to go about this for some non-trivial normal convention game.

  19. At 1:27 you should have shown the extended board without the colours, so we could pause the video and try to make out the losing squares

  20. For those interested there is also the Wythoff Array which can be constructed with winning solutions to Wythoff's Game: http://mathworld.wolfram.com/WythoffArray.html

  21. Anyone curious about his open ending.

    Removing from one pile is essentially moving along that axis any number, and taking evenly from both is essentially a diagonal move. So yes, the two games are identical. You just have squares to move instead of counters to take away.

  22. Hey Dr. Grime, what branches of mathematics do you research? I know you said in a Numberphile video that you research algebra, but which part? Representation Theory? Class Field Theory? Transcendental Number Theory?

  23. You definitely did not explain the rules of the game well enough for me to follow along. What's all this about moving your opponent's piece?

  24. By the way your maths is wrong technically there are no losing squares as the lines that get you there directly take 1 move the rest take 2

  25. The two colors are equal to the x and y axis with the bottom left corner being zero. All you are doing when you move down or to the left is subtracting from whatever distance you started with. Diagonally you are always subtracting the same number from both x and y. Really cool adaptation of the same game.

  26. Hello sir can you do some videos on ramanujans's continued infinite fraction which is in his first letter to hardy. Please do look after it because I am stuck on math do called ''math research''.Thanks 😀

  27. https://drive.google.com/file/d/0B4nrXQIFSQT2VHdYY3NJeS1TNW8/view?usp=sharing
    I made a one player version. If you know the rules for winning, it's no big deal, but it's still satisfying to play with (especially on the larger board sizes; it goes up to 16×16). All the squares are just JButtons, so you just click one of the yellow squares to move to it.

  28. Hey James, I just wanted to tell you that I really appreciate the content that you put up there. I am a senior high-school student and your videos have helped to show me a lot of fun and fascinating sides of math I didn't know before. Seeing your passion makes me love math even more than I did before, so much so that now I'm thinking about taking a math major in university.:)

    Math is pure awesome, and the fact that you're showing it and spreading it to the world is neat and much needed.
    I guess that's all I wanted to say. Keep up the awesome work!:) ♡

  29. Could you make a video about all or as many as possible math operations put into one (not necessarily meaningful) formula?

  30. (not the best at phrasing things so pardon me if I don't make much sense. Also it's quite possible my question has a simple answer so sorry if it is a dumb question) So I got bored after completing my midterm in geometry and I decided to do random equations with factorials and realized that if you take two consecutive integers' factorials and divide the bigger one by the smaller, it will equal the larger integer. Is there an obvious reason that I'm not catching for whatever reason or is there something to this? Also I love these videos I watch them constantly in my free time!

  31. sir why the area of triangle comes out to be the same irrespective of the base chosen for the same triangle or in other words why is 0.5*base*height = 0.5 second base*second height=0.5*third base*third height of the same triangle or why these numbers should come out to be same. for me this is not intuitive as i was taught that area of rectangle is base*height by definition and then we use it to deduce the formula for area of triangle. Regards
    Show less
    REPLY

  32. I found this ancient video about kids who can't get it straight in math class, and to my surprise there was a mention of a mister Grime! My how far he's come… and might I say, he doesn't look a day over 70 years old!

    https://youtu.be/eTaOCFs8pPI?t=18s

  33. james!! you completely inspire me to study maths, i love your creative and enthusiastic approach about everything and learning about all the cool stuff we can do with numbers. im 16 and watching u talk about maths makes the future seem brighter. if you ever do a lecture or talk in london ill be there!!

  34. Hello. I have a question about mathematics in general. Did we discover or make it? Because I feel like infinity does not actually exist anywhere but on the other hand, counting things is very much based on the real world. So my question is what is your opinion as a professional mathematician on whether or not math is manmade. Thanks!

  35. Hi Dr. Grime,
    I'm also very interested in the question of MagicKids. TV (permutations if the Master Cube). Could you do a video on that once? 😀

  36. Interesting how when I saw the first game (with the chessboard) I was like, this looks like it would be pretty close to nim. And at the end you show an equivalent game that is very close to nim.

  37. WHAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAААААААААААА́ААААААААААААААААААAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAÀAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAT?

  38. (1:35) Which is also a partial solution to the 8-queens chess problem, if you ignore the reflection. https://en.m.wikipedia.org/wiki/Eight_queens_puzzle

  39. Number of remaining red counters is your X coordinate the number of remaining blue counters is your Y coordinate. The person to take the last counters is the winner.

  40. Those two game are equivalent because if week-end associate each kind of pawn (blue and red) to a coordinate (x and y), the possible removals are equivalent to move to left, to the bottom and diagonally to the bottom left on the chessboard.
    The “diagonally” is because we can remove only the same amount of pawns of each colors if we want to remove pawns of both colors

  41. What type of board is required for other metallic ratios? For example, the silver ratio is the convergence of the ratio between the terms of 0, 1, 2, 5, 12, 29 where F_n= 2*F_n-1 + F_n-2. Is this even a logical question?

  42. Quite simple. If we match the blue pool to the x-coordinate and the red pool to the y-coordinate, the connection is clear. Moving on the x-axis is equivalent to removing only from the blue pool. Moving on the y-axis is equivalent to removing only from the red pool, and the diagonal movement is equivalent to removing from both pools, since both the movement's x/y ratio and the ratio between the removed balls are 1.

  43. You can imagine the number of blue tokens as the x coordinate of the starting position and the number of red tokens as the y coordinate of the starting position. Then taking blue tokens is the same as moving left, taking red tokens is the same as moving down and taking an equal amount of both is the same as moving diagonally left and down.

  44. I don't understand at all how you marked all but 1 square on the y=7 range as a "winning square." The only squares that you can win from in that range are (0, 7) and (7, 7).

  45. We used to play a variation of this in the Army, but with 3 lines of 3, 5 and 7 counters from which, each turn, a player may remove any number of counters from a single line.
    The LOSER being the one that took the last counter.
    As we used to play for a crate of beer (PER GAME !!!!) I spent a couple of hours learning/memorising the winning/losing patterns before playing my first game and ended up being one of only two people to never have to buy a crate 🙂

  46. Great video, also I have a question. So on move one, you're in a winning position, so the game is purely for the math? Or what

  47. 1:14 – 1:18
    "Any square in direct line of sight of the goal, OR OF A LOSING SQUARE, is a winning square."

    Why? After all the aim of any move is towards the goal alone . . . not towards a losing square at all. Am I missing something?

  48. Hi! I really like this video, the maths is incredible. However I think it's lacking something. What are the rules of Wythoff's Game? Who gets to choose the initial positions? From the sound of it, you can move your opponent's pieces. The explanation is incomplete.
    Apart from that though, awesome video. It blew my mind. Amazing how the golden ratio and its square can produce such a sequence.

  49. The game with 2 piles of counters is equivalent to Wythoff's game because the two piles are effectivlel stand-ins for the x and y coordinates of a grid. Taking from pile x is the same as moving along the x axis, likewise for pile y and the y axis, and taking equally from both pile is the same as moving diagonally.

  50. Dr Grime..what is your opinion of the Mandelbrot system..and do you believe that it is looking into the mind of God?

Leave a Reply

Your email address will not be published. Required fields are marked *