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