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

x²=x+1

x²-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>.