email@example.com (Steven Meyers) wrote in message news:<firstname.lastname@example.org>... > email@example.com (Glenn C. Rhoads) wrote in message news:<firstname.lastname@example.org>... > > email@example.com (Glenn C. Rhoads) wrote in message news:<firstname.lastname@example.org>... > > > email@example.com (Bill Taylor) wrote in message news:<firstname.lastname@example.org>... > > > > > > > > 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.