This is just a beginning.
Besides the material here, there is a Google Group specifically for the theory of the game. You can access the archives here: To receive emails or to contribute you must become a member, but anyone can browse the archives
|
|
Subscribe to HexTheory | |
| Browse Archives at groups-beta.google.com | ||
The purpose of the Theory and Proofs Project is to collect in one place proofs of all of the major theoretical results concerning the game. If we also wind up proving something new, so much the better.
It is our intent to generate sound and rigorous, albeit informal proofs of a number of known facts which have been proved elsewhere, but in sources that are diverse in accessability, location, and treatment. These include but are not limited to the following:
Lemmas:
A hex game cannot end in a draw.
If one player wins, the other player does not win (a bit stronger than Lemma 1).
A hex game, if play continues long enough, ends in a win for one or the other player (a bit stronger than either of the previous Lemmas.)
Either the first or the second player has a winning strategy on the starting (empty) position.
If a (winning) strategy exists for player A in a given position, a strategy exists for that player in any derived position that differs from the original only in having additional plays by the winning player
If a (winning) strategy exists for player A in a given position, a strategy exists for that player in any derived position that differs from the original only in the deletion of some plays by the losing player
In every finished game (where some side has actually won), the winning path can be reduced to a minimal winning path in which no hex borders more than two other hexes, and the goal edges are touched by exactly one hex apiece from the minimal winning path.
Theorems:
In the absense of a "swap" rule, if the second player has a winning strategy for the starting position, then the first player has a winning strategy for the (same) starting position, contradicting Lemma 2.
In the presence of a "swap" rule, it is the second player who has a winning strategy.
A1 is a losing opening. Proven in Excursions into Mathematics (original 1969 edition, also appears in Millenium Edition).
A2 is a losing reply to A1. Proven in Excursions into Mathematics: The Millenium Edition.
B1 is a losing opening. There is a sketch of the proof.
This collection of documents contains some proofs of the items listed above, as well as other things. It is intended to be a bibliography and direct resource for anyone interested in the theories behind hex, computer programs that play hex, and game analysis in general.
Some documents here are restricted in distribution. Accordingly, they are available only by prior arrangement. You can get access by contacting the Hex Master, indicating your real name and a useable email address, and a desired username (none of which will be used, sold, published, or listed in any other place.) On approval, you will have access to the restricted material here, as well as the latest test build of the OHex database.
Other documents were found on the web or elsewhere with a more permissive copyright notice, or no notice at all; these are readable here without special permission.
Winning Ways for your Mathematical Plays (second edition).
A Combinatorial Problem Which is Complete in Polynomial Space. S.Even and R.E.Tarjan -- Journal of the Association for Computing Machinery, 1976 23(4): 710-719.
Four artices from Proceedings of Computers and Games Conference, 1998
Three artices from Proceedings of Computers and Games Conference, 2000
Five artices from Proceedings of Computers and Games Conference, 2002
Excursions into Mathematics: The Millenium Edition. A. Beck, M.N.Bleicher and D.W.Crowe, eds, A.K.Peters, Natick, MA.
Six Wins Hex Tournament. Gabor Melis and Ryan Hayward -- ICGA Journal, 2003 26(4): cover, 278-280. Part of a report on the 8th Computer Olympiad, covering the hex competition between Six and Mongoose.
Hex is PSPACE-Complete, Stefan Reisch, Acta Informatica 15, 167-191 (1981). This is the original paper, in German. An English translation is listed below.
Union-Connections and Straightforward Winning Strategies in Hex Kohei Noshita – ICGA Journal, 2005 28(1): cover, 3-12. An winning strategy for 8x8 hex.
YLP01 Yang, Liao, Pawlak, 2001, A decomposition method for finding solutions in game Hex 7x7, International Conference on Application and Development of Computer Games in 21st Century.
Ans02 PDF Anshelevich, V. (2002) A Heirarchical Approach to Computer Hex. Arificial Intelligence, 134(1-2): 101-120. There is also a slide presentation.
RIJ02 PDF Rijswijck, J. v.(2002). Search and Evaluation in Hex. Technical report. University of Alberta.
HBJ02 PDF R. Hayward, Y. Björnsson, M. Johanson, M. Kan, N. Po and J. van Rijswijck. Solving 7x7 Hex: Virtual Connections and Game State Reduction Advances in Computer Games 10, Graz, 2003. The underlying data is also available on the web.
YLP02 Yang, Liao, Pawlak, 2002, A new solutions for 7x7 hex game, Proceedings of Computers and Games Conference, 2002. There is a corresponding technical report.
Hay02 Berge and the Art of Hex, a chapter for a book, recounting some history and theory surrounding Hex. Interestingly, "Excursions in Mathematics" is credited with proving B1 is a losing opening, but the book itself does not have that proof, but the slightly weaker one that A2 is a losing reply to A1.
REI81 PDF S. Reisch. Hex is PSPACE-Complete T. Ace translator. From Acta Informatica 15, 167-191 (1981). A formal proof of the complexity of generalized Hex. Original German version available above.
Some years ago, Kevin Walker
(kevin at canyon23.net) exposed an applet version of Jhex on his web
page, with the intent that the community of players could contribute
to solving 7x7 hex. The results of some months of work by some of
the best players of the time is here (click
to download). It was wrong in a number of respects, largely
because of winning moves that were not even tried. Fortunately,
there is no record of the guilty parties, although I'll admit to
having worked out some of the variations on A2 and A3 –
probably all of them wrong.
Corrections are not posted
because they are the topic of an ongoing set of puzzles in the OHex
mailing list.
Last updated 9 June 2005.