Cold Positions of three heap Wythoff Game

Question

This is HW:

Wythoff's game is where there are two players and in this instance there are 3 heaps of stones. Each player takes stones off the heaps in turns and a player wins if they pick up the last stones. Each turn a player can either take off N stones from one pile, N stones from two piles, or N stones from all three piles.

A winning configuration is one where the first player can force a win. For example, (0,0,13), (0,11,11) and (5,5,5) are winning configurations because the first player can immediately remove all stones.

A losing configuration is one where the second player can force a win, no matter what the first player does. For example, (0,1,2) and (1,3,3) are losing configurations: any legal move leaves a winning configuration for the second player.

Consider all losing configurations (xi,yi,zi) where xi <= yi <= zi <= 100. We can verify that Σ(xi+yi+zi) = 173895 for these.

I have searched and searched but can't figure out how to find all the losing (cold) positions. By summing the binary values of the coordinates to get the nimnumber and if nimnumber > 0 then it is a cold position. But I end up with a Σ(xi+yi+zi) > 1mil. Can anyone help point me in the right direction?

Answer 1

Since it's homework, I won't post a complete solution, but here's a tip:

You already know that xi <= yi <= zi <= 100, so the number of configurations is never going to exceed 2*101^3 (the x2 for whoever's turn it is), which isn't much more than 2 million. Try making a lookup table (say, isWinningPosition[][][][] where isWinningPosition[a][b][c][d] corresponds to piles of size a,b,c and it's d's turn) and recursing. (Caveat: Each entry in your lookup table needs to handle true, false, and not computed as three separate things.)