|
|
Re: Hex Win Proof?
Posted:
Mar 22, 2004 1:52 AM
|
|
swmeyers@fuse.net (Steven Meyers) wrote in message news:<b1d340a7.0403210514.3fdb5469@posting.google.com>...
> gcrhoads@yahoo.com (Glenn C. Rhoads) wrote in message news:<3396efc6.0403201232.221c2e9d@posting.google.com>...
> > gcrhoads@yahoo.com (Glenn C. Rhoads) wrote in message news:<3396efc6.0403200010.aab22a4@posting.google.com>...
> > > w.taylor@math.canterbury.ac.nz (Bill Taylor) wrote in message news:<716e06f5.0403181938.72a82f90@posting.google.com>...
> > > >
> > > > It is an old theorem that in Hex, once the board has been completely
> > > > filled in with two colours, there *must* be a winning path for one
> > > > or other of them.
> > > >
> > > > Now, I can prove this easily enough mathematically, but I'm wondering if
> > > > there is a simple proof, or proof outline, that would be understandable
> > > > and reasonably convincing to the intelligent layman.
> > > >
> > > > Can anyone help out please?
> > >
> > > Here's a pretty proof involving a closely related game called Y.
> > > (Don't hesitate about the length of this post; it consists mostly
> > > of descriptions of Y, the relation to Hex, and the definition
> > > of "Y-reduction". The final proof is very short.)
> > >
> > > A Y board consists of a triangular configuration of hexagons. Play is
> > > the same as Hex except that the goal is to build a chain that connects
> > > all three sides (as in Hex, corner hexes belong to both sides).
> > >
> > > Y is a generalization of Hex as illustrated in the following ascii diagram.
> > > (view in a fixed font)
> > >
> > > _
> > > _/*> > > _/*\_/
> > > _/*\_/*> > > _/ \_/*\_/
> > > _/ \_/ \_/*> > > _/ \_/ \_/ \_/
> > > / \_/ \_/ \_/ > > > \_/ \_/ \_/ \_/
> > > \_/ \_/ \_/+> > > \_/ \_/+\_/
> > > \_/+\_/+> > > \_/+\_/
> > > \_/+> > > \_/
> > >
> > >
> > > * are pieces of one player and + are pieces of the other player.
> > >
> > > Playing Y from the above legal position is equivalent to playing
> > > Hex in the unoccupied hexes of this position because a chains wins
> > > for Y if and only if the chain restricted to originally unoccupied
> > > hexes wins for Hex (in the Hex version, player * is connecting the
> > > southwest border up to the northeast). Thus, to prove a completely
> > > filled-in Hex board has a winning chain for one of the two players,
> > > it suffices to prove that a filled-in Y board has a winning chain
> > > for one of the two players.
> > >
> > > The proof makes use of "Y-reduction."
> > >
> > > Y-reduction: From a completely filled-in order n Y-board,construct
> > > a completely filled-in order n-1 Y-board as follows. For each
> > > triangle of three mutually adjacent hexes oriented the same way as
> > > the board, replace it with a single hexagon whose piece color is
> > > that of the majority of the colors in the triangle.
> > > Ex.
> > > _
> > > _/4\
> > > _/3\1/ _/3> > > _/2\1/3\ _/2\1/
> > > /1\1/2\2/ /1\1/2> > > \1/1\2/2\ \1/1\2/
> > > \2/1\3/ \2/1> > > \3/1\ \3/
> > > \4/
> > >
> > >
> > > The triangle of hexes with coordinates
> > > x x+1 x
> > > y y y+1
> > >
> > > on the order-n board corresponds to the hexagon
> > > x
> > > y on the order n-1 board
> > >
> > >
> > > Lemma: If a player has a winning chain on the reduced board, then
> > > that player also has a winning chain on the original board.
> > >
> > > It's easy to verify (but ugly to write up rigorously) that if a player
> > > has a winning chain on the reduced board, then he also has a winning
> > > chain through the corresponding triangles on the original board.
> >
> > Consider two adjacent hexes along the winning chain on the reduced
> > board. Each of corresponding adjacent/overlapping triangles must
> > have at least two pieces of the winning color.
> >
> > Case 1: The unique hex in the overlap is of the winning color.
> > Then both of the other disjoint "truncated triangles" has some
> > piece of the winning color. Both pieces are adjacent to the
> > piece in the overlap and hence must form a chain connecting the
> > corresponding edges.
> >
> > Case 2: The unique hex in the overlap is not of the winning color.
> > Then all four of the remaining hexes are occupied by the winning
> > color. Again these hexes form a chain connecting the corresponding
> > edges. (it helps to draw a diagram).
> >
> > A triangle corresponding to a reduced hex, contains at least two
> > pieces of the same color and thus, each edge of the triangle must
> > contain at least one piece (since each edge contains all but one
> > of the hexes in the triangle). This observation completes the proof.
> >
> > (you need this fact to establish that for any piece connected to the
> > edge of the reduced board, that color must also be connected to the
> > corresponding edge in the original board. This fact also acts as a
> > base case for induction.)
> >
> >
> > > [note: the converse of the lemma is also true but we don't need it.]
>
> > > Thm. One of the player's has a winning chain on a completely filled-in
> > > Y board.
> > >
> > > Proof:
> > > From any completely filled-in Y board, perform a sequence of
> > > Y-reductions to reduce the board to a filled-in order 1 board.
> > > The filled-in order 1 board obviously has a winning chain and
> > > hence by the lemma, each Y board in the sequence has a winning
> > > chain.
> > >
> > >
> > > I wish I could take credit for this proof but it is due to
> > > Ea Ea (his former name was Craige Schensted).
> >
> > Steve Meyers posted a link to a web page containing essentially
> > this same argument. However, this page claims *only* the converse
> > of the above lemma which is not sufficient for the proof; the
> > other direction is what is needed.
>
> Hi Glenn,
>
> I can well believe you're right. I'm not a math professional, so
> sometimes the finer things escape me:(
Well, I'm not right! I double-checked and the site does mention
the correct direction (but it says essentially nothing about why
a winner on an order n-1 board must also win on the order n board).
> I'm delighted to see that you and others have taken an interest in
> this result, and that you seem to appreciate its beauty. For a while
> there I feared almost nobody cared about it. But since there is
> apparently some interest now, I'll go ahead and post how this proof
> came to surface.
>
> In 2000 I got very interested in the game of Hex. I played against
> the computer and against myself hundreds of times, and I began to
> suspect there might be a "pattern" in the game. In fact I thought
> that I was going to be able to solve it. At the time I didn't know
> that Hex was PSPACE-complete, or I probably would never have attempted
> it.
>
> I got nowhere with Hex and in late 2001 switched to Y after realizing
> that Y was more fundamental than Hex; I had always thought the
> reverse. It was already known to some people that Hex was a special
> case of Y, but it came as a surprise to me! In January 2002 I had a
> much bigger surprise: I discovered that with the game of Y, an n game
> (where n is the number of points/cells per side of the board) consists
> of three n-1 games, at least two of which are necessary and sufficient
> to win in order to win the n game; each n-1 game, in turn, consists of
> three n-2 games, at least two of which are necessary and sufficient to
> win in order to win the n-1 game; and so on until n=1, where each
> point/cell is itself a "game."
>
> I immediately notified Mark Thompson of the discovery. He replied the
> same day, saying that the property was very interesting, and he
> suggested that Ea Ea (who was one of Y's co-inventors) be contacted
> about it.
>
> Ea Ea subsequently sent an e-mail to me, in which he said that my
> discovery was very closely related to a discovery he'd made some
> thirty years before. He then proceeded to describe that discovery,
> which is what you called "Y-reduction" in your post. The terminology
> I use for it is "micro-reduction," since it takes the small triangles
> as its starting point. (Unfortunately Ea Ea never published his
> result, so I went ahead and named it.) I called what I found
> "macro-reduction," since it starts at the big triangles. These very
> closely related processes together comprise what I called the "n-1
> property" of the game of Y.
>
> Mark suspected that Y-reduction could not be used to solve a
> moderately complicated Hex position because of the vast number of
> steps required to perform the calculation. I didn't understand this
> at first, but he was right.
>
> I sent the information along to Hex programmer Jack van Ryswyck, who
> made the same observation as Mark. (It was then that I learned about
> Hex's PSPACE-completeness.) Jack came up with the idea to perform the
> reduction probabilistically in order to get a rough but fast estimate
> of which player had the advantage in a given position. (That is, his
> idea was to use Y-reduction not to solve a position but rather as the
> basis of an evaluation function.) Jack's method made use of
> micro-reduction rather than macro-reduction because the former avoids
> unnecessary repetition of steps --- this is also why micro-reduction
> makes for a cleaner no-draw proof than macro-reduction. For more
> information on Jack's programming idea, check his paper "Search and
> Evaluation in Hex," available on his website.
>
> Sorry to be long-winded,
>
> Steve
Thanks for the history.
The term Y-reduction is not mine. I got it from Ryan Hayward
and Jack van Rijswijck's draft "Notes on Hex" which is available
on Ryan Hayward's page (who along with Jack van Rijswijck, is
a member of the University of Alberta's GAMES group). The draft
seems to have been updated this January but curiously, he doesn't
fix the diagram for puzzle 5; Berge's puzzle has white pieces
M7 and N5 and without them his "solution" is invalid (I was a
reviewer for the original draft). I guess I'll have to email
him about it.
Also, Ryan Hayward informed me by email that Jack's idea of using
Y-reduction as an evaluation function for Hex didn't work out
too well.
|
|
