World's most popular travel blog for travel bloggers.

Computing losing positions in modified Wythoff's game efficiently

, , No Comments
Problem Detail: 

Wythoff's game is as follows: there are two players $A$ and $B$ ( $A$ being the first player ) and there are $2$ piles of stones. When his turn a player can remove one or more stones from anyone pile or same number of stones from both the piles. A player unable to make a move loses. Also it is assumed that both the players play optimally.

As mentioned in the link the losing configurations $(n_k,m_k)$ ( $n_k$ stones in one pile and $m_k$ stones in another ) are given by $$ n_k = \lfloor( k*\phi) \rfloor$$ $$ m_k = \lfloor( k*\phi^2) \rfloor$$ where $k$ is any natural number ( and $n_k \le m_k$ ) and $\phi=\frac{1+\sqrt{5}}{2}$. For example $\{1,2\}$ ( two stones in one pile and one stone in another ) is a losing position.

Modification to Wythoff's game"

In this modified game instead of ${\it2}$ piles there are ${\it 3}$ piles. And when his turn a player can move one or more stones from anyone pile or same number of stones from any $2$ piles or same number of stones from all the $3$ piles.
How do I compute the losing positions for this modified game efficiently ? The inefficient way of course is to find the grundy number of each configuration $\{a,b,c\}$. This method is inefficient because I want to calculate number of losing positions given that number of stones in each pile can be between $1$ and $1000$.

This is a project Euler question ( stone game ). I would appreciate hints only.

Asked By : sashas
Answered By : sashas

There is no closed form for $n=3$ piles. But one can solve the question efficiently using dynamic programming.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback