3
$\begingroup$

In my earlier question I asked about the winning move in Ordinal Chomp played on a $3 \times 3 \times \omega$ board. So far the problem has seemed intractable. Therefore, I now consider Ordinal chomp played on an L-shaped board \begin{pmatrix}a&b&c \\ d&0&0\end{pmatrix}

  • This game is played between two players on the set $2 \times 3 \times \omega$. A move is to pick any remaining $(i,j,k)$ and remove all $(i^\prime,j^\prime,k^\prime)$ where $i^\prime \geq i$, $j^\prime \geq j$ and $k^\prime \geq k$. The player to take $(0,0,0)$ loses. I have represented the positions I am considering the whole remaining chomp board as a matrix to make it easier to analyse. For a more full explanation, see (https://en.wikipedia.org/wiki/Chomp)

I have been able to prove various results, including that \begin{pmatrix}\omega&\omega&c \\ d&0&0\end{pmatrix}

is a losing position for (c, d) = (0, 0), (1, 1), (2, 3), (4, 2), (3, 5) (I can post a proof if anyone is interested).

My questions are: 1) What research has been done on these positions, if any? 2) If research has been done, what other values of (c, d) are known such that the above is a losing position? 3) Is there a number n such that \begin{pmatrix}n&n&n \\ n&0&0\end{pmatrix} is a losing position?

Improve this question
$\endgroup$
4
  • $\begingroup$ I have found that \begin{pmatrix}5&5&5 \\ 5&0&0\end{pmatrix} is a losing position. It is interesting to see a finite "semi-rectangular" position that is losing, as I had previously thought these might not exist. $\endgroup$
    – Thomas
    Commented Jan 25, 2016 at 15:13
  • $\begingroup$ Could you please explain what Ordinal chomp is? $\endgroup$
    – Ilya Bogdanov
    Commented Jan 25, 2016 at 16:04
  • $\begingroup$ I edited the question above to provide an explanation of ordinal chomp. Also, I have found that \begin{pmatrix}1&1&0 \\ 1&0&0\end{pmatrix} \begin{pmatrix}3&3&1 \\ 3&0&0\end{pmatrix} \begin{pmatrix}4&4&2 \\ 4&0&0\end{pmatrix} \begin{pmatrix}7&7&3 \\ 7&0&0\end{pmatrix} \begin{pmatrix}11&11&4 \\ 11&0&0\end{pmatrix} are all losing positions. $\endgroup$
    – Thomas
    Commented Jan 26, 2016 at 6:09
  • $\begingroup$ I have just finished my classification of all (finite) losing positions with c<=4. The final case, \begin{pmatrix}a&10&4 \\ d&0&0\end{pmatrix} was particularly nasty, as the solution has period 80. Higher values of c should be easier (unless they're huge), because if c>=5 and d>=5 then the only solution is the constant 5 case, so only d<=4 need be considered. Although, chomp has a tendency to interfere with all of its conjectured patterns after a while, which is what causes it to be so frustrating (and interesting). $\endgroup$
    – Thomas
    Commented Jan 26, 2016 at 15:47

2 Answers 2

Reset to default
1
$\begingroup$

(I put this into another answer because it was too long for a comment) I made a database of losing positions. I noticed after calculating a few positions by hand that there were some positions, like \begin{pmatrix}3&3&1 \\ 3&0&0\end{pmatrix} that are losing positions, which means that there are only finitely many cases with c=1 (analogously with the other cases in my earlier comment). Therefore, I can list all the classes of solutions. Then I made a computer program, which had two functions. The first calculates for a given b, c, and d, what value of a makes \begin{pmatrix}a&b&c \\ d&0&0\end{pmatrix} a losing position, and the second takes c and d and for all b from c to c+14, so I could find the pattern in the losing positions.

It was only then that I found that \begin{pmatrix}5&5&5 \\ 5&0&0\end{pmatrix} was a losing position. After that, I built up a database of all solutions with a fixed value of c, slowly increasing c as I covered more cases. None of the cases were too hard, except for c=4, b=10, which, because of period multiplication in the c=4 case, had period 80. For that case I had to construct a specialised program.

Actually, I just realised that the way I was programming the functions was extremely inefficient, and after correcting my program it works up to c = 200 in under a minute, and uses no cataloging of positions prior to runtime, (which I had to do for the last program). It also records positions for future use, so once you've calculated a position it will remain in the memory (until the program is reset).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ You can also edit your original answer to provide this more thorough information there. $\endgroup$
    – Joel David Hamkins
    Commented Jan 27, 2016 at 20:11
0
$\begingroup$

After a bit more research (and a very helpful python program), I have been able to solve answer all of my questions. First, the values of (c, d) such that \begin{pmatrix}w&w&c \\ d&0&0\end{pmatrix} is a losing position are: (0, 0), (1, 1), (2, 3), (3, 5), (4, 2), (5, 4). Second, the position \begin{pmatrix}5&5&5 \\ 5&0&0\end{pmatrix} is losing, which means that any other position with c,d>=5 can be reduced to this, and is therefor a winning position. Also, this means that there are no other (c, d) answers to question 1. Also, I have calculated all the finite losing positions where c<=8 (going through c is much easier than d because d=0 is not even fully solved!).

Edit: I have also found that \begin{pmatrix}8&8&8 \\ 4&0&0\end{pmatrix} is a losing position.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I would be interested to know more about your method. Did you just recurse backwards through the game tree? Did you build up a database of determined positions? Or did you make use of symmetry and strategy-stealing arguments, or what? The bare-bones list of losing or winning positions is less enlightening. $\endgroup$
    – Joel David Hamkins
    Commented Jan 27, 2016 at 12:50
  • $\begingroup$ @JoelDavidHamkins I can't speak to Thomas's methods, but when I looked at $n\times3$ cases I found it easiest to build a database of positions - there's a natural indexing on them, and that made it possible to get up to the range of $n=1000$ (several years ago) without much trouble - now I'm sure it could be pushed to $n=10000$. No really compelling pattern emerged for the question I was looking at, though I know that other people have found some indications of structure in different facets of the $3\times n$ case. $\endgroup$
    – Steven Stadnicki
    Commented Jan 27, 2016 at 20:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .