7
$\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?

Improve this question
$\endgroup$
8
  • $\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
    Commented Dec 15, 2015 at 8:15
  • 1
    $\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
    Commented Dec 15, 2015 at 9:29
  • $\begingroup$ Do you know what happens for $3 \times \omega$ Ordinal Chomp? $\endgroup$
    – Tony Huynh
    Commented Dec 15, 2015 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
    Commented Dec 15, 2015 at 13:34
  • 3
    $\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
    Commented Dec 15, 2015 at 16:10

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .