
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 "Yreduction". 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 > > > filledin Hex board has a winning chain for one of the two players, > > > it suffices to prove that a filledin Y board has a winning chain > > > for one of the two players. > > > > > > The proof makes use of "Yreduction." > > > > > > Yreduction: From a completely filledin order n Yboard,construct > > > a completely filledin order n1 Yboard 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 ordern board corresponds to the hexagon > > > x > > > y on the order n1 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 filledin > > > Y board. > > > > > > Proof: > > > From any completely filledin Y board, perform a sequence of > > > Yreductions to reduce the board to a filledin order 1 board. > > > The filledin 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 doublechecked and the site does mention the correct direction (but it says essentially nothing about why a winner on an order n1 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 PSPACEcomplete, 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 n1 games, at least two of which are necessary and sufficient > to win in order to win the n game; each n1 game, in turn, consists of > three n2 games, at least two of which are necessary and sufficient to > win in order to win the n1 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 coinventors) be contacted > about it. > > Ea Ea subsequently sent an email 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 "Yreduction" in your post. The terminology > I use for it is "microreduction," 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 > "macroreduction," since it starts at the big triangles. These very > closely related processes together comprise what I called the "n1 > property" of the game of Y. > > Mark suspected that Yreduction 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 PSPACEcompleteness.) 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 Yreduction not to solve a position but rather as the > basis of an evaluation function.) Jack's method made use of > microreduction rather than macroreduction because the former avoids > unnecessary repetition of steps  this is also why microreduction > makes for a cleaner nodraw proof than macroreduction. For more > information on Jack's programming idea, check his paper "Search and > Evaluation in Hex," available on his website. > > Sorry to be longwinded, > > Steve
Thanks for the history.
The term Yreduction 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 Yreduction as an evaluation function for Hex didn't work out too well.

