Wythoff's Game (Get Home)
HTML-код
- Опубликовано: 3 окт 2024
- Wythoff's Game is played on a chessboard. Two players take it in turns to move a piece. That piece can move any number of square to the left, and number of squares down, or any number of squares on a down-left diagonal. The winner is the player who moves the piece to the bottom-left square. What are the losing squares?
See my first video with Katie Steckles here • Game: Get Home
--
If we call the bottom-left square (0,0) then the losing squares are (1,2), (3,5), (4,7) and their reflections that swap the coordinates.
The losing squares can be generated one at a time using the following two conditions: First, for the nth losing square, the difference between its coordinates is n. And second, each positive integer appears once and only once as either the x or y coordinate of a losing square.
These two conditions have the effect of putting all losing squares on different rows, columns and diagonals.
In 1907, Willem Wythoff proved that the nth losing square has coordinates (n*phi, n*phi^2) where phi is the golden ratio (1.618), and the two coordinates are rounded down to the previous integer. He showed that the golden ratio is the only number that will work in this way, giving the desired two properties of losing squares.
Play an interactive version of the nim version of Wythoff's Game (called Last Biscuit here) on nrich: nrich.maths.or...
Wythoff's Game on Wikipedia:
en.wikipedia.o...
Wythoff's Game on Mathworld: mathworld.wolfr...
Wythoff's Proof: archive.org/st...
An excellent series of blog posts by Zachary Abel, read in reverse order (Thanks to Daniel Kelsall for this link) blog.zacharyabe...
Willem Wythoff: en.wikipedia.o...
Rufus Isaacs: en.wikipedia.o...)
Simple: Think of the red and blue piles as the x and y coordinates. You can either subtract from x by going left, subtract from y by going down, or subtract the same amount from both by going down and left
L4Vo5 amazingly easy to understand! Thank you :*
Great observation! Also, it's called _subtract_ not "substract".
True, I think I was confused by the spanish translation, "sustraer".
I also used to think it was "substract" for quite a while, and I'm also spanish, must be a thing.
Your way of saying it is much clearer than my way, although somewhat less specific.
We've had surprise pi, surprise e, and now surprise Golden Ratio. I'm not sure what you have left, but I'm sure you'll surprise us.
+Peg Y Haha. I love it when that happens.
Surprise Parker Square
Surprise i?
Peg Y suprise tau
That'd just be 2 surprise pi's.
This happy little man makes maths so interesting and shows me that there is order in this chaotic world of ours.
What about a 3D equivalent game? Are the maths going to be the same? Interesting thought.
I think a good representation of that would be to use three piles of counters. The updated rules would be you can take any number from one pile, any equal number from two piles, or any equal number from all three piles. That would be the equivalent, in 3d space, of moving straight along any of the 3 axes, moving diagonally along any 2 axes, or moving diagonally along all 3 axes.
but what are the rules?
You can take any amount of coins from any amount of stacks, as long as you take the same amount from every stack you take from?
so if you wanna take 3 from 2 stacks you can choose which stacks, or only take 1 coin from 1 stack, or 7 from every stack? I think that makes most sense.
DaffyDaffyDaffy33322 im draw some stuff, im gonna make a program and to visualize it better
Robbe, Sounds awesome! Post it here when you got it! I'd love to see it :)
In 2D, alternating between two players means *the board is divided up into two kinds of spaces.* You're playing to leave the other player with no valid moves (not to have no valid moves yourself, which is a valid variant of the game), so *(0,0) is part of the "losing" set.* 2D symmetry means *losing points come in pairs (n,m) and (m,n).* The orthogonal moves mean that *once you have found a losing move (x,m) there can be no other move (x,n) which is also a losing move.* The diagonal moves mean that *once you have found a losing move (n,n-x) there can be no other losing move of the form (m,m-x).* All valid losing spaces are merely the smallest/most compact possible pairs that satisfy all these conditions. It's a very simple and elegant rule set, and once you see what its doing, you kinda see where phi sneaks in.
On the infinite 3D board, the 2D rules will hold for all 2D slices within that board. One difference to note is that, although within any single 2D slice we see only pairs of matching losers, in the whole cube these are always in sets of 6 symmetric losers, corresponding to the 6 permutations of (m,n,o)(o,m,n)(n,o,m)(o,n,m)(n,m,o)(m,o,n). You can visualize how the pairs relate to the whole group of six by imagining three sides of the infinite cube, coming off the winning corner. The three sides, corresponding to the slices (0,y,z) and (x,0,z) and (x,y,0) don't just follow the 2D rules, they are all actually perfect copies of the basic 2D board! So there are three copies of every pair of 2. (Unless some points on the interior of the cube, of form (m,n,n) only have 3 permutations, I'm still trying to figure that one out...)
Moving in from the outside one slice to (1,y,z), we see things getting... complicated. Integers y and z are still not allowed to repeat. And differences between y and z are still not allowed to repeat. However, we _also_ can't just use the tried-and-true values from slice (0,y,z). (1,1,2) seems legal for example, not being any kind of legal move away from (0,0,0). However the (0,y,z) slice has already used (0,1,2), meaning (1,1,2) is an orthogonal move away from a loser, and can't also be a loser. In general, moving up slices *you can never repeat a pair from any previous slice.* You also can't merely increase one of the other numbers by 1. For example (1,2,2) might seem alright, but if you reduce the x and the y both by 1, essentially making a diagonal move along a perpendicular slice, you can still get to (0,1,2). In general, *you cannot have a loser pair (x, y, z) if there is already a pair (x-n, y-n, z) **_or_** a pair (x-n, y, z-n) **_and_** if you use DaffyDaffyDaffy's rule, you **_also_** cannot have a pair (x-n, y-n, z-n).*
1:51 I actually said "whaaaat" in sync with James x)
Your enthusiasm is charming... I have no idea what all that meant, but I loved watching
"it's played on a chessboard" (chessboards are 8x8)
*shows 6x6 grid
+DirtyLenzes Oh flip, that was an accident if I did.
No, he did't. It's correct.
missliketrains2 The first time at 0:29 it was wrong, but it worked for the example so it's fine.
0:13 :) But it doesn't matter a lot for we all watched the other video, right? :)
There's an easy answer, taking inspiration from another RUclips mathematician: call it a Grime chessboard....
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!:) ♡
This means a lot to me. Thank you, and good luck with your studies!
"And its gradients of those lines are the golden ra-"
"I FUCKING KNEW IT"
Does this make you want to convert this into an algorithm for drawing pixelated lines with the golden ratio as the slope? :)
@@burts6896 No, but kinda related, I solved a few Project Euler problems that involved some variation of Wythoff's game, e.g. a 3D version of it.
(Project Euler is a website that has difficult programming questions that are heavily math-based)
glad to see you making more videos!
more games. This is great! You are a brilliant teacher
Golden Ratio is the last thing I'd expect to get in that kind of game...
I guess this means that when playing in a hundred by hundred chessboard, unless one player would actually bother memorizing all of the key squares, the winning chance is equal until... someone can trace the key squares...
Each pile is a coordinate, diagonal is 1:1 ration. Oh James, that was too easy ;)
1:51 let's make this a meme
... yeah
Outstanding move
Sounds like how Aziz Ansari says 'WHAT!?' in Parks and Recreations.
If we just look at the main squares above the diagonal, this is what we get.
it already is
Golden content
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!!
Thank you!
If you find my website and contact form I'll let you know some possible talks you could attend.
i want a 10hrs video of him sayng "whaaaaaaaT"
A 10 hr long WHAAAAAAAAAAT or a bunch of WHAAAAAAAAAAT that add up to 10 hrs?
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.
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.
⬅️ 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...
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.
They're equivalent because you're still working towards a goal of 0,0. Counters or coordinates on a grid, it's the same. Limiting moves to the left and down is the same as subtracting reds or blues (lowering the value of the x or y coordinates), respectively. And moving diagonally is the same as taking an equal number of counters from both piles.
I idolize this gentleman 👏🏻
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.
I watched the previous video and felt it was comfortably trivial. lalala I'm so clever 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.
Reckless Roges hah, same.
The equivalence is actually pretty easily proven: The amount of red or blue dots corresponds to your position on the board, 0-indexed. 1 blue and 2 reds is a losing 'square' or 'dot pair', as is 2b1r, etc.
Removing blue dots is equivalent to moving along one axis, i.e. the x-axis, towards zero, the bottom of the board. Same for red and the y-axis. If you remove both, you get the diagonal movement.
To equivalence: i would represent all possible states on a 2d grid. Number of one color on the x-axis and number of the other color on the y-axis. This way going left and down is the equivalent of taking from one color and going cross is the equivalent of taking equal amount from both. So we can go down,left and cross-down (as in the original) and our goal is to get to the bottom left square (as in the original). That's a beautiful representation! Would have never thought about this, thanks for sharing.
Taking a red disks is like moving to the left, and the blue as moving down, taking both is diagonal, when no more are left youre at the bottom left corner, when theres 7 in both piles youre at top right
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.
Thanks for the video James. You're awesome. Math is awesome.
The most astonishing thing is that this method of generating x and y described at 2:06 will give x/y approaching golden ratio. Wow, didn't expect that!
Thank you for the video! All of you friends are super awesome!
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.
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.)
Keep making more videos, of many different types !!!
Oh my goodness love this video..💝
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
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.
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.
short and an amazing video, I was shocked to see the presence of golden ration with this simple game.
Red is X, blue is Y, equal in both is diagonal and taking the last mean ending in 0/0
Those are the same rules that I figured out on the main video! I am incredibly happy with myself.
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.
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 :D
"red" and "blue" basically represent the axes of the chess board. "taking away" a counter is effectively moving down the respective axis.
And taking the same number of each is effectively moving diagonally.
Wonderful!
I was thinking the chess game was very nim-like... Really interesting solution though! Didn't expect that pattern. It's interesting that the first player can ALWAYS win, in a chess board of infinite large size, given perfect play. Even though that is also a very nim-like property, but its different seeing it visually on the board: with every row and column having a losing square in it.
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.'
That's some awesome maths, thank you for a very interesting video!
I love nim games, I have personally mastered the art of Notakto, one of the hardest ones out there ;)
How good is your mpaulweeks.github.io/achi/?
@singingbanana, Been a fan for years, your passion is contagious. I've seen a few chess based math puzzles. Do you study and play classical chess?
It wouldn't surprise me if he was a frenetic lichess.org/variant/crazyhouse fanatic.
He has made a couple of chess videos on Numberphile, where he says that he played growing up, but he just plays for fun.
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.
that's beautiful
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 :)
Brady needs to see this video... and make a WHAAAAAAT TShirt or something... Its just too good..
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
It's fully equivalent, actually, and it uses both sides of the "diagonal".
First of all, the 4 red and 7 blue counters were just an example. You could use any other combination of red and blue counters, and every combination of course corresponds to 1 possible starting position on the board.
Secondly, it's entirely possible to move from one side of the "diagonal" to the other using the counters. For instance, in the example given in the video, removing 5 blue counters gets you from (4, 7), above the diagonal, to (4, 2), which is below the diagonal.
Ahsim Nreiziev good point, I don't know why I thought the other side of the diagonal needed to be rejected. It works out much nicer that way anyway
Never thought it had to do with the golden ratio.
God dammit he's everywhere.
Edit: The two games are indeed equivalent if instead of taking one "red" or one "blue" we move our player on the chessboard subtracting a number from one, or both x and y axes.
GET HOME IS TWO PILE NIM
MY MIND HAS BEEN BLOWN
I did a double take when you mentioned Rufus Isaacs as there is a statue of a Rufus Isaacs in my town - but it's a different Rufus Isaacs!
Why the two games are equivalent:
Red stones represent x coordinate, blue stones represent y coordinate
For those interested there is also the Wythoff Array which can be constructed with winning solutions to Wythoff's Game: mathworld.wolfram.com/WythoffArray.html
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.
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.
"Fibonacci's Checker".
thanks sir, Love from Bharat.
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
that's really awesome. :D
**By the way, when you round a number down to its previois integer, it's called truncating; n*phi and n*phi^2 are truncated c:
Which is only true for positive numbers. -5.2 rounds down to -6 but truncates to -5. Not applicable for this game but just pointing out that rounding down and truncating is not the same thing.
I was aware of that xD
I guess truncating it is better explained as removing everything after the decimal point.
oof I really liked that equivalence at the end - thats a like from me
Do a video about the math in Three Body Problem trilogy.
don't know why youtube brought me here, but it's really cool
(1:35) Which is also a partial solution to the 8-queens chess problem, if you ignore the reflection. en.m.wikipedia.org/wiki/Eight_queens_puzzle
(you can only get 7 queens in)
Could you do a video about the Master Cube (4x4x4) permutations once? 😀
Just because there are many articles about that on the internet but they're very complicated and badly explained 😁
MagicKids. TV
Yes Please, I'm also very interested in that! Please do a video in that James :D
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
The two stacks correspond to the two coordinates. = Equivalent.
can we play the 3d variant by having a third pile?
would that even work?
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?
Gary Oldman called. He'd like his face back.
(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!
Nevermind, my brain finally started working again and I figured it out.
Isn't it essentially a 2D game of dr. Nim?
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? :D
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.
The "losing" or "winning" condition for a square is determined with the premise that the square in question is the one the piece is on at the *start* of your turn, rather than at the *end* of it. So if your turn starts with the piece on a winning square, there is a sure-fire strategy for you to win, whereas if your turn starts with the piece on a losing square, your opponent has a sure-fire strategy to make you lose.
Personally, I would find basing it on where a player's turn ends more logical too, but that's what James went for so I guess we'll have to go with it.
As for the strategies: if your turn begins on a "losing square", you are forced to move the piece either to a square from which your opponent can directly reach 0-0, or you are forced to move the piece to a position where the opponent can move the piece to another "losing square" that's closer to 0-0. So by the process of Recursive / Inductive reasoning, it is clear that if your turn begins on a "losing square" and your opponent plays an optimum strategy, you will always eventually lose. Hence the name "losing square".
By contrast, a "winning square" is a square from which either 0-0 can be reached directly, or from which a "losing square" can be reached directly. In the first case, you of course automatically win. In the latter case, though, you will win still win *eventually* , because you can just keep putting the piece on "losing squares" until your opponent is forced to put you within 1 move of 0-0, handing you the win.
Are there yellow dots in the corners between the squares that disappear when you look directly at them? ;-)
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.
In the chessboard version of the game, the piece is controlled by both players in alternating fashion. The initial position is unspecified. Maximal fun is found in solving the game for all possible initial positions.
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
Do a video on Brahmagupta pls
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 :D
Could you make a video about all or as many as possible math operations put into one (not necessarily meaningful) formula?
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).
cool!
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.
Dr Grime..what is your opinion of the Mandelbrot system..and do you believe that it is looking into the mind of God?
Link: "researchers at the national institute in Tokyo"
Singingbanana: 1:52
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?
Or maybe Lattice Theory?
He has said a couple of times he works specifically on group theory.
nice 6x6 chess board ;)
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
DON'T STOP PLS
Whaaaaaaaaaaaaaaat
why are there magic yellow dots on the grid which disappear when i look directly at them?
0:13 Am I the only one to notice that's not a chess board? It's 6x6
WHAAAAAAAAAAT?!
...yeah...