This message was rejected by Math Fun, on account of the attachment. Without it, to make sense, you'll need to find: N E Clarke, S Finbow, S L Fitzpatrick, M E Messinger & R J Nowakowski, Seepage in directed acyclic graphs. It's evidently been submitted to Australasian Journal of Combinatorics ---------- Forwarded message ---------- Date: Wed, 30 Jan 2008 14:07:03 -0700 (MST) From: Richard Guy <rkg@cpsc.ucalgary.ca> Subject: Re: Hexago Dear all, I've looked at Adam Holer's research project, that Erich Friedman pointed me to: http://www.stetson.edu/mathcs/students/research/math/ms498/2006/aholer/propo... There are close relations between Adam's games and SEEPAGE [SEE PAGE?] Perhaps at least one of the 5 authors of the (no longer) attached should compare & contrast? Best, R. On Wed, 30 Jan 2008, rjn@mathstat.dal.ca wrote:
Richard et al,
this last summer, a group of Maritimers looked at a graph game, which we called `Seepage', similar in nature to Hexago. The players are Pollution and Green. The rules are:
Let G be a directed, acyclic graph with root v. Vertex v is assumed to be polluted at the start of the game but all other vertices are clean and unprotected. On his turn Pollution is allowed to pollute exactly one non-protected, clean vertex that is adjacent to some polluted vertex. On her turn, Green is allowed to protect a non-protected, clean vertex, which stays protected throughout the rest of the game. Pollution wins if he can pollute a terminal vertex (we assume all terminal vertices to be on the shores of a lake---if the lake gets polluted, it's "game over"); Green wins if she can form a barrier between the root and the lake.
The main three results were:
0) If Pollution can win, he can win by only polluting the vertices of a path.
1) A characterization of trees that are Green-win.
2) It is too easy for Pollution to win in general, so we considered letting Green protect more than one vertex. Let P_n={0,1,2,3,...,n} be a path of length n. In the Cartesian product P_n x P_n x P_n rooted at (0,0,0) consider the subgraph G_d consisting of all vertices at distance at most d from (0,0,0). Now
If d>=3 then, Green only needs to protect 2 vertices on each turn to win on G_d.
We didn't consider looking for game values though.
Richard
PS: Shameless Plug: I've attached a copy of the paper since at least one of you expressed interest.
------------------------------------------------------------- From Richard Guy ------------------------------------------------------------- I've just (re?)invented the game of Hexago:
A Hexapod starts at the origin and moves on a triangular grid, a distance equal to one of the sixth roots of unity at each move, and endeavors to reach the edge of the board. Her opponent places Go stones at grid points in an attempt to block her, in the manner of the games of Chap 19 of Winning Ways (Variants of Chessgo, Angel & Square-eater, etc.)
Problem: are there shapes & sizes of board for which the game makes sense (allows a complete analysis, makes for a reasonably fair game, etc.)? E.g. _____________________ ...... / / / / * ??? \ \ \ \______________________......
Comments? R.