5
$\begingroup$

I have been trying to analyse the game of Ordinal Chomp played on a $3 \times 3 \times \omega$ board. The rules can be found in the Wikipedia article, briefly:

  • This game is played between two players on the set $3 \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.

Unfortunately, the analysis is extremely complicated, so I have been unable to find a winning move for the first player or a proof that none exists. So, my question is:

Is there a winning move in $3 \times 3 \times \omega$ Ordinal Chomp for the first player, and if so, what is it?

$\endgroup$
  • $\begingroup$ Have you studied $3\times3\times n$ boards for, say, $n\lt 10$ or so? That's where I'd start experimentally. $\endgroup$ – Steven Stadnicki Dec 15 '15 at 8:15
  • $\begingroup$ Unfortunately, the finite case also grows complicated very fast. The strategy stealing argument works for $3 \times 3 \times n$, so there is a winning move. Having already studied $3 \times n$ chomp, I can say that there probably isn't a nice general form for the winning moves in $3 \times 3 \times n$. One thing I was able to show in my analysis is that taking the "top" square in $3 \times n$ chomp is never a winning move, unless n = 2. I'll give the proof if anyone is interested. $\endgroup$ – Thomas Dec 15 '15 at 9:29
  • $\begingroup$ Do you know what happens for $3 \times \omega$ Ordinal Chomp? $\endgroup$ – Tony Huynh Dec 15 '15 at 12:51
  • $\begingroup$ Yes, the winning move is to $2 \times \omega$. $3 \times 3 \times \omega$ is the first unsolved infinite position. Also, if it happens to be a losing position, then (0, 3, 0) is an answer to (3, 0, 0) in $\omega \times \omega \times \omega$ chomp, which this is a special case of (and I am also trying to solve). $\endgroup$ – Thomas Dec 15 '15 at 13:34
  • 2
    $\begingroup$ I studied $3\times n$ myself for a while and I agree, it's an immensely complicated thing - even the question of whether the winning move is a height-1 or height-2 bite appears to be almost structureless (though see, e.g., emis.de/journals/INTEGERS/papers/fg7/fg7.pdf). Given the complexities in the analysis of $2\times 2\times\alpha$ chomp that showed that the $P$-position is (IIRC) $\alpha=\omega^3$, and that $3\times3\times\omega$ subsumes both of these cases, your problem is likely to be Hard. $\endgroup$ – Steven Stadnicki Dec 15 '15 at 16:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.