Date: Mar 22, 2004 1:52 AM Author: Glenn C. Rhoads Subject: Re: Hex Win Proof?

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.