0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Good self-service ;) Could you elaborate your answer a bit (about no closed form)? (I have seen your question, but wanted to give more time). $\endgroup$ – Evil May 26 '16 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.