From:           mathwft@math.canterbury.ac.nz (Bill Taylor)
Date:           13 Dec 1996 02:35:46 GMT
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

ikastan@sol.uucp (ilias kastanas 08-14-90) writes:

|> @Now my question.  Does anyone know of a similar result in chomp, involving
|> @an (at least partly) infinite starting position, for which thus NO
|> @exhaustive search can apply, but which STILL HAS a non-constructive proof
|> 
|>   Well, we could play on  a x b, where a and b are ordinals (and
|>    higher-dimension analogues).  Every run of the game is finite, but of
|>    course there is no upper bound on run length.  The non-constructive
|>    argument works as stated.

Oh great bog!  Of course it does!!  How obvious, (once it's been pointed out).
Thanks Ilias.   Now I can red-facedly stammer out some followup queries...

|>  But don't take (1, 1, 1) when playing on  a x a x a !

Hah!  No.  BTW, does anyone know of any progress made on  wxwxw ?  Or even
4x4x4; or even 3x3x3 ?

And what about some of the simplest infinites?
Obviously  2xw is a 1st-player-loss; but what about 3xw ?

And how far is 3xn known, 1st-move-wise?

Anything else?

Cheers.
-------------------------------------------------------------------------------
            Bill Taylor             W.Taylor@math.canterbury.ac.nz
-------------------------------------------------------------------------------
            The answer may be right but it's not the answer I want.
-------------------------------------------------------------------------------

From:           ikastan@alumnae.caltech.edu (Ilias Kastanas)
Date:           13 Dec 1996 11:02:50 GMT
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

In article <58qfe2$j8t@cantuc.canterbury.ac.nz>,
Bill Taylor <mathwft@math.canterbury.ac.nz> wrote:
>ikastan@sol.uucp (ilias kastanas 08-14-90) writes:
>
>|> @Now my question.  Does anyone know of a similar result in chomp, involving
>|> @an (at least partly) infinite starting position, for which thus NO
>|> @exhaustive search can apply, but which STILL HAS a non-constructive proof
>|> 
>|>   Well, we could play on  a x b, where a and b are ordinals (and
>|>    higher-dimension analogues).  Every run of the game is finite, but of
>|>    course there is no upper bound on run length.  The non-constructive
>|>    argument works as stated.
>
>Oh great bog!  Of course it does!!  How obvious, (once it's been pointed out).
>Thanks Ilias.   Now I can red-facedly stammer out some followup queries...
>
>|>  But don't take (1, 1, 1) when playing on  a x a x a !
>
>Hah!  No.  BTW, does anyone know of any progress made on  wxwxw ?  Or even
>4x4x4; or even 3x3x3 ?

    Eh, regarding w...  For the non-constructive argument, there had
   better _be_ a corner to chomp!  So the infinite ordinals a, b had better
   be successors; the argument does not apply to, say, w x w.  It does to
   w+1 x w+1, when w itself is "there".

    Of course II still loses on w x w... by the constructive 'take (1,1)'!

    So  w x w x w  is interesting; it is the simplest of the "power"
   cases, w^3, for which it is not immediate just _who_ has the winning
   strategy!

>And what about some of the simplest infinites?
>Obviously  2xw is a 1st-player-loss; but what about 3xw ?

    Again, 2 x w  is a win for II constructively, because "chomp the
   corner" is a win for any  2 x m.   It follows that  3 x w, and any b x w
   with b > 2, including all infinite b, is a win for I:  take (2,0).

    So this is an alternative winning strategy for w x w as well.

>And how far is 3xn known, 1st-move-wise?

    Ah, who wants to bother doing the finite Nim counts when vistas of
   vast infinities lie unresolved?!

>Anything else?

    Well, 2 x b for b > w, even limit, is a win for I; take (0,w)...

                            Ilias

From:           Fred Galvin <galvin@math.ukans.edu>
Date:           Sat, 14 Dec 1996 15:49:08 -0600
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

>     So  w x w x w  is interesting; it is the simplest of the "power"
> cases, w^3, for which it is not immediate just _who_ has the winning
> strategy!

David Gale has offered a $200 prize for the answer to this one: see The
Mathematical Intelligencer, Vol. 15 No. 3 (Summer 1993), pp. 59-60, and
Vol. 18 No. 3 (Summer 1996), p. 26. Good luck!

From:           Mike Housky <mike@webworldinc.com>
Date:           Sun, 15 Dec 1996 20:07:29 -0800
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

Bill Taylor wrote:
> 
> ikastan@sol.uucp (ilias kastanas 08-14-90) writes:  <snip> 
> |>  But don't take (1, 1, 1) when playing on  a x a x a !
> 
> Hah!  No.  BTW, does anyone know of any progress made on  wxwxw ?  Or even
> 4x4x4; or even 3x3x3 ?
> 
> And what about some of the simplest infinites?
> Obviously  2xw is a 1st-player-loss; but what about 3xw ?

(If I read w correctly as omega...) Since 2xw is a first-move loser, then nxw
for n>2 is a first-move winner--since the first to play can reduce the board
to 2xw with opponent to play.  Am I missing something?

> And how far is 3xn known, 1st-move-wise?

Seems to me that, unless I'm totally off-base above, if there is a k such that
3xk is a first-move loser then 3xn is a first-move winner for n>k.  The first
player can hand 3xk to opponent.  Thus, there can be at most one 3xn that is
a first-move loser.

Happy Holidays,
Mike.

From:           mathwft@math.canterbury.ac.nz (Bill Taylor)
Date:           18 Dec 1996 04:20:07 GMT
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

Fred Galvin <galvin@math.ukans.edu> writes:

|> >   Some cases _are_ constructive; e.g.  on  a x a, take (1, 1) and
|> > then play symmetrically to a win.  But don't take (1, 1, 1) on a x a x a !
|> 
|> Is (1, 1, 1) a losing move for a > 2 ? How do you show that? 

Just reply to it with  (0,0,1)  which chomps off all above the x-y plane
just leaving the 2-axes part of  axa;  (kind of a "direct sum"  a+a,  as 
opposed to the direct product,  axa  itself).

Then play symmetrically between x & y.

-------------------------------------------------------------------------------
              Bill Taylor        W.Taylor@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Classical:  "now" is the last instant of the past.
Quantum:    "now" has a short but nonzero duration - namely the extent
            of future which will be collapsed by the next observation.
-------------------------------------------------------------------------------

From:           Fred Galvin <galvin@math.ukans.edu>
Date:           Wed, 18 Dec 1996 17:06:29 -0600
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

On 18 Dec 1996, Bill Taylor wrote:

> Fred Galvin <galvin@math.ukans.edu> writes:
> 
> |> >   Some cases _are_ constructive; e.g.  on  a x a, take (1, 1) and
> |> > then play symmetrically to a win.  But don't take (1, 1, 1) on a x a x a !
> |> 
> |> Is (1, 1, 1) a losing move for a > 2 ? How do you show that? 
> 
> Just reply to it with  (0,0,1)  which chomps off all above the x-y plane
> just leaving the 2-axes part of  axa;  (kind of a "direct sum"  a+a,  as 
> opposed to the direct product,  axa  itself).

No, chomping (1,1,1) & (0,0,1) leaves the *whole* direct product axa.
You must be thinking of (1,1,0), which *is* refuted by (0,0,1). Note that
(1,1,1) is the *winning* first move in the 2x2x2 case; that's why I wrote
"for a > 2 ?".

From:           ikastan@alumnae.caltech.edu (Ilias Kastanas)
Date:           19 Dec 1996 10:40:18 GMT
Newsgroups:     sci.math
Subject:        Re: CHOMP - Any more nonconstructive results?

In article <Pine.SUN.3.95.961218165940.23752A-100000@titania>,
Fred Galvin  <galvin@math.ukans.edu> wrote:
>On 18 Dec 1996, Bill Taylor wrote:
>
>> Fred Galvin <galvin@math.ukans.edu> writes:
>> 
>> |> >   Some cases _are_ constructive; e.g.  on  a x a, take (1, 1) and
>> |> > then play symmetrically to a win.  But don't take (1, 1, 1) on a x a x a !
>> |> 
>> |> Is (1, 1, 1) a losing move for a > 2 ? How do you show that? 
>> 
>> Just reply to it with  (0,0,1)  which chomps off all above the x-y plane
>> just leaving the 2-axes part of  axa;  (kind of a "direct sum"  a+a,  as 
>> opposed to the direct product,  axa  itself).
>
>No, chomping (1,1,1) & (0,0,1) leaves the *whole* direct product axa.
>You must be thinking of (1,1,0), which *is* refuted by (0,0,1). Note that
>(1,1,1) is the *winning* first move in the 2x2x2 case; that's why I wrote
>"for a > 2 ?".
>

    [This was _late_ in showing up on our server...]

    What I meant was that (1,1,1) is not necessarily and obviously a win,
   like (1,1).  I don't have a proof that it loses for all a > 2, but it
   does lose sometimes; e.g. for a = 3.

    In  3x3x3, the reply to  (1,1,1)  is  (2,2,0).  Matters become clear
   by noting the position "pyramid OABC", OA = i, OB = j, OC = k, containing
   ten points. (The rest have been taken).  It has Nim value 0, i.e. the
   player about to move from it loses.  The faces relate to value-0 positions
   in two dimensions, "equal axes" and "chomped-corner 2 x m".

    Briefly, II uses symmetry to lead I into OABC.  If I takes (0,1,2),
   II takes (1,0,2), and so on.  (Adding to OABC six adjacent edge midpoints
   yields another value-0 position).  Of course she might elect to lose in some
   other way rather than by "tempo" play near A, B, C.

    To win, I  plays  (2,2,2)  on the first move.  The anthropomorphic
   view is similar to the one above.

    On 2x2x2, (1,1,1) does win... but maybe not by virtue of being (1,1,1)
   but of being the cube corner!

                            Ilias

From:           David Eppstein <eppstein@ics.uci.edu>
To:             jeffe@cs.uiuc.edu
Subject:        Mancala-like CGT question
Date:           Sat, 10 Apr 1999 21:59:31 -0700 (PDT)

Here's an interesting impartial Mancala variant:

Start with some stones in a single row of pits.  Each move starts at one
pit and continues rightwards.  The player to move picks up any nonzero
number of stones from the first pit, and all stones from each successive
pit (even zero if the pit is empty), finally dumping all the picked up
stones in the last pit of the sequence.  Thus the move is determined by
the first pit, number of pits in the sequence, and number of stones
picked up in the first pit, but those three numbers may be chosen
independently by the player.

E.g. from a position (1,3,0,4) you could move to any one of (0,0,0,8),
(0,0,4,4), (0,4,0,4), (1,0,0,7), (1,0,3,4), (1,1,0,6), (1,1,2,4),
(1,2,0,5), or (1,2,1,4).

The game ends when all stones are in the last pit.  Obviously it's not
very interesting in normal play (just move everything to the last pit)
so you play misere.

To continue the example, (1,1,0,6) would be a winning move: after the
moves to (0,0,2,6) or (1,0,0,7) you can move to (0,0,1,7) and after
other moves you can move to (0,1,1,6) and then (0,0,1,7) next turn.

A strategy stealing argument shows that the first player wins
from (x,0,0,0,0...,0): if the second player had a winning move
from (x-1,1,0,0...,0) then the first player could also move to
the same position.  So maybe a better starting position
(more natural for Mancala like games) would be (x,x,x,x,...,x).

The question: what more famous combinatorial game is this a disguised
version of?  (I didn't find it in your Mancala paper nor WW so maybe
this disguise is new?)
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:           Jeff Erickson <jeffe@cs.uiuc.edu>
To:             David Eppstein <eppstein@ics.uci.edu>
Subject:        Re: Mancala-like CGT question
Date:           Mon, 12 Apr 1999 14:50:15 -0500 (CDT)

David Eppstein writes:
| Here's an interesting impartial Mancala variant:

Cool.  What do you call it?

| The question: what more famous combinatorial game is this a disguised
| version of?

It's Chomp!  The position vector (a,b,c,...,y,z) corresponds to a
Chomp position with a squares in the first row, a+b in the second row,
a+b+c in the third, and so on up to a+b+...+y in the last row.

Cute.  :-)

| (I didn't find it in your Mancala paper nor WW so maybe this
| disguise is new?) 

As far as I know, it's new.  But you might want to ask Conway or Guy
just to be sure.

                -- Jeff