Wednesday, February 8, 2017

Wythoff's Queens



Wythoff's Queens and Wythoff's Nim

Similar to Dawson’s chess-themed game we looked at last class, we’re going to look at another one 
called Wythoff’s Queens. This game is named after the Dutch mathematician Willem Abraham 
Wythoff who published an analysis of the game in 1907. Not to scare ya, but here’s a picture of 
Willem himself!




http://faculty.evansville.edu/ck6/bstud/wythoff.jpg

So, how do we play?

In this game, we have a chessboard (of any size n x n), and a singular queen placed at a predetermined starting position. The ultimate goal is to move the queen into the bottom left corner of the board. So if we think of a board that is 15x15, we could start at any position (m,n). 

(m,n)={(m,n) | 0 < m,n <15, if m=n then m≠0

We now try to move the queen to position (0,0). This makes Wythoff’s Queens a normal and impartial game.

Recall: Normal means both players can execute the same moves and impartial means the last player to move wins. 

If you’re unfamiliar with the game of chess, a queen can move as far as it wants in any direction (vertically, horizontally, or diagonally) on the board as long as it is in a straight line. Here is an image that shows these moves.


https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEic6sRcZJmVn4oxupWK3YIHMN-vXotZFHoPLwHOTJ8tgWDPEJSYfvY0MW03YHryOUoAIpOxPjpkbkVgOtyYFjW0TnCLYykzxq7hj18f-3ppRAgKyiE2_fH5BK0-yJPgMUzhQxu5j15QHg/s1600/queen.bmp

However, in Wythoff’s queens, we add a restriction that each turn the player must make a move that progresses the queen towards the terminal position (0,0). In other words, you can only move the queen left, down, or the diagonal between. This restriction guarantees a finite number of moves, and keeps the game from going into an infinite loop.


Now that we understand the rules, let’s try to figure out how to win!

We know that the space (0,0) is a p-position, so any spot where you can move to (0,0) would be an n-position.


We have the obvious p-position at (0,0), as well as two more p-positions that have no choice but to move to n-positions (2,1) and (1,2).


We can now repeat this process and see the p-positions begin to create the shape of a V along our board.




Can we figure out a pattern and determine the slope of the p-positions?

It turns out that we can prove the ultimate slope for the upper part of the V by proving that the ratio of different slopes is  (1+√5)/2, also known as the Golden Ratio. Since the bottom line is symmetrical to the top line, we can then find the slope of the bottom half of our V after we prove that we are in fact working with the Golden Ratio.

Prove it.

We will begin to dissect this pattern by only looking at the upper line of the V.
Only looking at the upper half of the V, we can see that there are two different slopes between any given consecutive points. These slopes are 2/1, and 3/2.
So now the question becomes, can we figure out a pattern as to when we use which slope in order to find all the p-positions?
If we represent the slope with letters, we can denote a=(2/1) and b=(3/2).
It turns out that the resulting pattern of slopes amongst the upper V is as follows.

ababbababbabb

To help understand this further, lets go one more step by denoting A=(ab) and B=(abb). Notice anything about the pattern of As and Bs? It should look familiar, because it is exactly the same as our original sequence of as and bs,
 
ABABBABABB

This pattern would continue if we kept doing this process by making A2=AB, B2=ABB, A3=A2B2, B3=A2B2B2
Because they are the same sequence, we know that the ratio of as to bs is the same as the ratio of As to Bs.  

*To be honest I get a little confused after this point. 
If you feel like you understand this last part of the proof feel free to comment, if not we can try to understand it together in class.

Looking further into this ratio, if we have 1 A for every B, then we have (1+r) as for every (1+2r) bs.
So r=(1+2r)/(1+r).
Simplifying even further, we can say 1+r=r2.
Therefore r=(1+√5)/2=Ф=”The Golden Ratio”.
Now that we know the ratio of the two slopes, our upper line’s ultimate slope can be written as (2+3Ф)/(1+2Ф) and the symmetrical bottom line should follow the slope 1/Ф= (5-1)/2.


So how does Wythoff's Queens relate back to Nim?

In addition to Wythoff’s Queens, there is also Wythoff’s Nim! Wythoff’s Nim is very similar to regular Nim. The only differences are that we can only have two piles, and you are allowed to take from each of them at the same time (you still have the option of only taking from one pile). However, if you take from both piles, you have to take the same number of paperclips (or whatever object you are using) from each.

Ready for the fun part? Yea you are…

http://www.baberuthleague.org/media/209935/fun1.gif

Wythoff’s Queens and Wythoff’s Nim are actually the same! But how?

Comment any hypotheses you might have, and I’ll explain how they are the same in my presentation. 
*Hint: Recall the spots on the board each have a specific x,y value

One last cool connection...

The Golden Ratio is related to the Fibonacci Sequence. If you haven't heard of this sequence, it is created by every number in the sequence equalling the sum of the previous two. 

f(n)=f(n-1)+f(n-2)

In the Fibonacci Sequence we can define xn=fIn+1)/f(n). 
Lets assume that x is the limit of xn as n goes to infinity.

x=1+1/x
x=(x+1)/x

x2=x+1
x2-x-1=0
x=(1+√(1-4(1)(-1)))/2
x=(1+√5)/2

All positive integers in the Fibonacci sequence are positive, hence we can simplify this to the Golden Ratio.  


That's all we've got! Leave any question you have in the comments!



Citations
"Wythoff's Nim." Wythoff's Nim. N.p., n.d. Web. 08 Feb. 2017.

Silber, Robert. "A Fibonacci Property of Wythoff's Pairs." North Carolina State University(1976): n. pag. Web. <http://www.fq.math.ca/Scanned/14-4/silber2.pdf>. 

"A Golden Observation." Three-Cornered Things. N.p., 22 Apr. 2012. Web. 08 Feb. 2017. <http://blog.zacharyabel.com/2012/04/a-golden-observation/>.

"Wythoff’s Game: Red or Blue?" Three-Cornered Things. N.p., 11 Apr. 2012. Web. 08 Feb. 2017. <http://blog.zacharyabel.com/2012/04/wythoffs-game-red-or-blue/>.

"Willem Abraham Wythoff (1865-1939) Number-theorist." W. A. WYTHOFF. N.p., n.d. Web. 08 Feb. 2017. <http://faculty.evansville.edu/ck6/bstud/wythoff.html>. 










12 comments:

  1. Hey, Mac. It seems like we can think of the two piles in Wythoff's Nim as an ordered pair. Meaning that taking from both piles would equate to a diagonal move in Wythoff's Queen and taking from one pile would be like moving to the left or down. Is this the right hypothesis?

    ReplyDelete
  2. So I think I understand the bottom portion of the proof from above, and I guess I'll find out if I do. Early on in the proof, we said that A=ab and B=abb. So, if we have one A, and one B, our total pattern would be ababb. So we have a grand total of 2 a's and 3 b's, or (1+1) a's and (1+2) b's. This generalizes to (1+r) and (1+2r), which is the numbers given above. Hence our ratio of b's to a's is (1+2r)/(1+r), or the Golden Ratio!

    ReplyDelete
    Replies
    1. Your logic makes sense to me, I think this is correct, nice work!

      Delete
  3. So, in theory: If we have a 5 x 5 board for our Queen, and the Queen is placed in position {3,3} to start. whoever goes first wins on the first move? With that, are we required to place the queen somewhere else aside from the diagonal axis?

    ReplyDelete
    Replies
    1. You're right on any sized board it would be trivial to start on any point (x,y) where x=y. In that case the first player would win every time.

      Delete
  4. Ok so maybe I'm being stupid, but if A=(ab) and B=(abb),and the original pattern was ababbababbababbababb, which splits up into (ab)(abb)(ab)(abb)(ab)(abb)(ab)(abb), then wouldn't the pattern of As and Bs be ABABABAB? So then the ratio of as to bs wouldn't be the same as the ratio of As to Bs and wouldn't this affect the rest of the proof?

    ReplyDelete
    Replies
    1. That's definitely a typo on my end (whoops). The pattern should read
      (ab)(abb)(ab)(abb)(abb)

      Delete
  5. Hey Mac! My hypothesis is that taking from one pile of paperclips or from two piles of paperclips, in Wythoff's Nim, ties back to Wythoff's queens because every paperclip you take away changes your location on the chess board? Also, what's the difference between thinking about this as coordinates or as the slope?

    ReplyDelete
  6. Great post Mac!
    So to answer the question, "Wythoff’s Queens and Wythoff’s Nim are actually the same! But how?", I suppose that the coordinates correspond to the number of paper clips in seperate nim piles. (the position (6,5) means we have 6 paperclips in one nim pile and 5 paperclips in the other.)
    We know that Wythoff's Nim has two-piles and I want to say that is because of the two-axises on the xy-plane.
    Now imagine if we play Wythoff's Queens on a 3-dimensional plane, then we would have 3 nim piles in Wythoff's Nim! One pile for each axis.
    Thoughs?

    ReplyDelete
    Replies
    1. I hadn't thought about the three dimensional plane but I can definitely see how that would work.

      Delete

Note: Only a member of this blog may post a comment.