Hex

Status

My thesis on Hex has been approved. Working on it was my reason for writing this website. That means that updates will be even rarer than they were. Thanks to all who helped and showed interest.

Download thesis: [ps], [pdf]

Hex cannot end in a draw

One of the reasons that Hex is a very satisfying game is the property that it cannot end in a draw. Piet Hein stated in his first presentation of the game this property but as an entirely obvious implication of the hexagonal board. The following proves what Hein saw intuitively.

This proof resembles the proof given by David Gale in his article on Hex and the Brouwer Fixed-Point Theorem. It is based on well-known facts of graph theory. A drawing to illustrate some points is coming up.

Let G be a planar 2-connected graph in which all vertices have degree 2 or 3. Each area within G corresponds to a cell on a Hex board. We can assume that all cells are occupied because a game of Hex cannot end before a player wins or no cell is available. Now make a subgraph G' of G created by colouring the edges that separate two areas of different colour on the Hex board.

This G' will consist of vertices of value 0 or 2 because of the fact that no vertex can be visited twice. Exactly four vertices will have a value of 1 namely the corners: a, b, c and d. It is a fact that graphs with vertices of value no more than 2 will consist of isolated vertices, simple cycles and simple paths (where simple means that they do not split). Since G' has exactly 4 vertices of value 1 there must be exactly two of these paths.

It follows easily that the two paths must connect a-b and c-d or a-d and b-c. In the first case white will have won, in the second black.

First player wins

Assuming that there is a winning strategy for one of the players in Hex it is quite easy to show that this must apply to the first player. Unfortunately this is a proof of existence and does not give us any hint about the actual strategy.

The assumption that there is a winning strategy is sound since in all finite games with complete information and no chance events there is a winning strategy if it cannot end in a draw. Sometime soon I will also show here that Hex cannot end in a draw - Rijswijck has done this in his thesis.

The proof was given by John Nash and is a so-called strategy stealing proof. In fact, Nash invented Hex as an example of a game in which first player has a winning strategy.

Assume that there is a winning strategy for the second player. (Obviously there cannot be winning strategies for both players). The first player on his first move occupies an arbitrary cell and in the following pretends to be second player, applying his winning strategy to his own game.

Should this strategy imply occupying a cell already occupied (by one of the player's own pieces) he will make another arbitrary move. Since no cell can be disadvantageous in Hex this strategy will give the first player victory, conflicting with the initial assumption. Thus there must be a winning strategy for the first player.

One necessary property for the proof to be valid is that a move cannot be a disadvantage as is the case in Go. It is intrinsic to Hex that every occupied cell is an advantage or makes no difference at all.

Complexity

The theory of complexity classes was developed during the seventies and succeeded in establishing a common ground for discussing how difficult it would actually be to solve different problems, in terms of necessary time. Edmonds defined good algorithms in a strict sense as those providing an answer in polynomial time, that is within a reasonable amount of time relative to the size of the problem. Thus problem types for which there exist a good algorithm belong to a specific class P (polynomial).

Some problems seem quite hard to solve, but there are cases in which, should one by chance or divine clarity discover a solution, it would be very easy to check its validity. These are for instance the satisfiability problems: In an expression of multiple variables, is it possible to assign each variable a value so that the expression is true? The (general) solution is hard to find, but easy to verify. The problem types that have this property are said to belong to the class NP (non-deterministic polynomial).

For quite a lot of problem types, it seems that there is no good algorithm, even though the solution is so easily verified. In fact, it may be that there actually is a good algorithm in each of these cases but that they are just yet undiscovered. In that case the classes P and NP would be equal, P=NP. This relation has neither been proved nor disproved despite decades of effort and in fact The Clay Mathematics Institute offers a prize of one million dollars for a proof.

In Hex, though, it seems that not even if we know a winning strategy will we be able to verify it without playing through all possible opposition. Due to the great branching factor of Hex described below, this can probably not be done in polynomial time. Thus, Hex may not even belong to NP, but a class of even harder problems called PSPACE, because they can be solved in polynomial space (and unlimited time). Even and Tarjan showed in 1976 that a generalization of Hex to The Shannon Switching Game (which is Hex, played on an arbitrary graph) does belong to PSPACE and that if Hex is solvable in polynomial time, then any problem in PSPACE (and thus also in NP) is solvable in polynomial time.

It is not entirely obvious that proper Hex also belongs to PSPACE. But until someone finds a better way of verifying a possible winning strategy, than by brute force, we must expect Hex to be PSPACE-complete.

Hex is PSPACE-complete

Stefan Reisch wrote the article Hex ist PSPACE-vollständig, published in Acta Informatica in 1981 and as far as I know it is the only account of the PSPACE-completeness of Hex. Even and Tarjan proved it for a generalized version of Hex as mentioned above. This is a summary of Reisch's article.

Reisch makes a number of transformations in order to prove transitional graph games to be PSPACE-hard. His strategy is this:

Deciding wether or not an assignment of variables to a quantified Boolean formula that renders it true exists, is PSPACE-hard. This problem is known as QBF and is the fundamental problem - corresponding to SAT in NP.
- Transform the decision problem above to Geography - a game played on an oriented graph - through a polynomial function.
- Each variable in the QBF is replaced by a subgraph with vertices for both possible truth assignments. These subgraphs are connected in a chain where the start of one is identical to the end of another.
- Disjunctive clauses are replaced by vertices connected to the end of the chain and with edges connecting them to the variables that they contain.
- Via further replacements this graph is made into a planar bipartite graph with each vertex of degree at most 3.
The Geography graph can be polynomially transformed into Graph-Hex which is a specific variant of Hex played on an undirected, "almost planar" graph. Again the transformation is achieved by replacing vertices of Geography by subgraphs. These are divided into different types, namely 'white choice', 'black choice', 'intersection' and 'decision' graphs. The new complete graph can again be made planar by simple replacements.

The 'white choice' graph. White to begin chooses wether to connect the top to the east or to the west. This graph replaces an existentially quantified variable. Some vertices are already occupied by white.
Graph-Hex transforms polynomially into proper Hex by inserting yet more subgraphs to make it planar. Also to render it in the usual layout, edges are replaced by chains of white stones, vertices by empty cells. Using stones of both colours, it is easy to create vertices of arbitrary degree.

The 'white choice' graph transformed to Hex. The white stones with three or more white neighbours correspond to the ones that are occupied in Graph-Hex.
Since QBF is PSPACE-hard, so must the transitions be and thus also Hex. It is easily seen that Hex belongs to PSPACE (since it can be completely solved by a depth-first search requiring approx. n² bits of memory) and so is PSPACE-complete.

The resulting Hex-graph when transforming the Boolean in the top of the image. Each of the three groups in the middle represent a variable. Click for large image.

The size of Hex

It's stated everywhere that Hex is incredibly simple and yet very complex. But how complex is it anyway? Does it come anywhere near Chess, for example?

What makes Chess so difficult to play well is that the player must look many moves ahead. When playing Chess there is (in principle) no upper limit to the number of moves necessary to win a game. In Hex however, there are at most 121 moves on a standard board and only 9 on a 3x3 board. What's the trouble then?

The primary problem is that Hex has a much greater branching factor than Chess and many other games. When opening Chess there are sixteen possible pawn moves and four knight moves - the first level of our Chess game tree has twenty branches. In a standard game of Hex there are 121 possible first moves! The number of options remain somewhat constant in Chess and in Hex decreases with one for each turn. In other words, Chess has a very deep but not too branching game tree whereas Hex's game tree is broad and short.

In order to play Hex well it is of no use just beginning from one end of the game tree searching all branches, it will simply take too long. We will have to make the process more efficient. That is what Jack van Rijswijck and Vadim V. Anshelevich have been trying with their artificial Hex players (see Links).

Counting the complete number of different games for a 3x3 board we will immediately reach 9! = 362,880 (ie 9*8*7*6*5*4*3*2). Half of these however will be duplicates because the board is identical to its 180° rotation. We are also able to remove many positions that are invalid because the game has ended. It is really impossible to determine the size of the exact game tree without counting the final positions one by one.

In an effort to estimate the complexity of the board Cameron Browne counts the number of unique and valid board positions (final or not) finding 2,844 on the 3x3 board and ~2.38*10⁵⁶ on the 11x11 board.

The approach of van Rijswijck is to consider chains, connections and templates as single pieces, measuring connectivity across the board whereas Anshelevich dives deep into a few selected branches of the game tree. So far the latter method has proven the strongest (meaning that I am being flogged by his Hexy) but the attention towards Chess that resulted in Deep Blue has not yet been given to Hex so we can still hope to see refinement and improvements in the future.

Classifying Hex

There are all sorts of games very much like Hex but also lots very different from Hex. These can be divided into classes in a way, so that many results regarding one game will apply to others with a similar structure. In order to understand Hex fully it may be a help to find out which class of games it belongs to.

First of all we must consider the number of players: There are one-player games such as patience and roulette, these are often not very interesting because - in the lack of an opponent - they mostly consist in chance. Games with three or more players are very difficult to discuss mathematically because there is almost always an element of diplomacy and psychology which throws over any predictability. Thus two-player games are considered the most interesting to classify and describe by mathematicians.

Then there are chance events. Backgammon is a popular two-player game that is decided mostly by the dice. Of course there are good and bad players in most dice-games, but even bad players will win now and then - this is probably part of the reason for their popularity. Rock-paper-scissors is an example of a game with no chance events: the players choose all the action.

Wether or not the game can (in principle) be predicted is another important aspect. In a game with complete information, such as chess, both players can predict the effects of their own moves and the winner is often the one who is able to predict most moves. Complete information implies that the players take turns moving.

Finally, games can be finite or not. Chess can in some cases go on forever (unless some time clause is applied). Hex is obviously finite as the board will eventually be full and a winner is found.

There can be different objectives and disguises for the games in a specific category but basically the same mathematics apply. To summarise, Hex belongs to the class of finite two-player games that have complete information and no chance events. To that class also belong the Shannon switching game, go and nim.

In this classification I have ignored physical games such as sports and psychological games such as poker or even love. These are simply too close to chaos for simple mathematics to work.

Having classified Hex in this way enables us to solve the game. It can be proven that any finite two-player game with complete information and no chance events has a saddle point and thus can be solved by maximising and minimising rows and columns in a matrix consisting of all possible strategies and the solution consisting in optimal play for both players resulting in a win for one of them. The trouble is however that this matrix becomes incalculably big for even the standard board - having not mentioned the general form.

The invention of Hex

I have managed to find a few sets of Piet Hein's mostly handwritten notes, one of them being an undated manuscript by Piet Hein which I believe is from his lecture to The Parenthesis, a mathematical association at The University of Copenhagen an evening of 1942. The lecture is well known but the contents are not. A translation of this manuscript is coming.

He says that what he has to present to them is "an outline of a thought as an introduction to a game". The theme of the lecture is "mathematics viewed as a game and this particular game as a simple example of mathematics". His point is that mathematics is different from the empirical sciences, in that it creates models that are manipulated according to rules similar to those of a game - which then are compared with the actual world through empirical methods.

Now, reversing the perspective, Piet Hein tries to set up strict conditions for recognizing games of real value. This amounts to a list of six conditions; a game must be:

Fair
Progressive
Finite
Clear
Strategic
Decisive

Some of these properties are described in the chapter on classification but I may go more into these terms at a later time. At the moment they serve only as a background for the invention of Hex.

In a sketch to the first article in Politiken Piet Hein describes how the complete game of Hex ocurred to him one morning by the combination of the list above with the Four-Colour Theorem:

Suddenly in the half-light of dawn a game awoke, demanding to be born. Today it is ready for release into the world [...] The game builds on the simple geometrical property of a planar surface that two lines within a square each connecting a pair of opposite sides must intersect.

Hein describes how he was working with the Four-Colour Conjecture when having the idea for Hex. He considered four areas in a ring, realising that only one pair of opposite areas can connect to each other across the middle. Had it been possible for both pairs to connect across the middle, then a fifth area encircling and touching the first four would disprove the theorem - actually similar to creating a complete graph with five vertices (K₅) in a plane. This idea leads him to a game in which the players must try to create the connection, a condition that only one of them will be able to achieve.

Building on these ideas Hein says that his game was obvious, only requiring a decision as to how many tiles to use. He chose 11x11 initially but later settled on 12x12 for his wooden board.

Hex's first appearance

Hex was invented by Danish mathematician, designer and author Piet Hein in 1942. He first introduced it to an association of mathematicians called The Parenthesis (and the chess club) at The University of Copenhagen when giving a lecture on the mathematics of games as described above.

The same year Hex appeared in the Danish newspaper Politiken under the name Polygon. Hein introduced the game to the readers on December 26, 1942 and during the following four months gave them a problem each day to begin with - eventually two days a week, on Wednesdays and Saturdays. The solution would always appear in the following column.

Politiken published around 50 problems but strangely it seems no solution is given to the last one, posed on August 1, 1943 - and no explanation either as to why they stopped the series. So we can only speculate: Did the editor find out nobody cared to read it or was it perhaps something to do with the German occupation of Denmark during the Second World War (as we know that Hein was connected to the resistance and had a Jewish wife)?

My thesis will feature a reading of some of the around 50 columns of Hex in Politiken, I will give you a few of the articles here.

December 26, 1942

Would you like to learn Polygon? Piet Hein has constructed a game that can be practised with equal joy by the chess expert and one who is merely able to hold a pencil.

This is how the first article ever about Hex begins. It stresses very much the simplicity of the rules and yet the complexity that not even experienced chess players have been able to see through.

Hein draws attention to the fact that two lines inside a square each connecting their pair of opposing sides must intersect. So it must be possible to create a game that challenges two players to connect opposing sides so that only one can succeed. The chess board will not work, as problems will arise as soon as four or more cells meet at one point so at most three cells are allowed to meet. The solution which is most simple and regular is the hexagonal board and all that remains is to choose an appropriate number of cells.

Having explained the simple rules the article goes on to explain three possible relations between two cells: Contact [adjacent], angle [bridge] and across. The two first being secure connections and the third one unsecure.

The advice is given that playing around the middle of the board is beneficial but certainly not necessary. An example of good opening play is given [this is, however exactly one of the openings that Cameron Browne shows not to be too good].

Concluding the article is a problem along with the promise that the following days will bring new boards, opening moves and problems. There was a prize for the correct solution to problem 1. They are both shown below.

Problem 1: This is the problem that appeared with the first article on Hex on December 27, 1942. The task is to place one white marker on the board which makes a white win inevitable.

Problem 1: This is the problem that appeared with the first article on Hex on December 26, 1942. The task is to place one white marker on the board which makes a white win inevitable. Solution.

December 28, 1942

This day's paragraph shows how a game may begin. We notice a very close opening play resulting in the best position for black with bold numbers.

A possible opening of Hex, Politiken December 28, 1942.

Problem 3 is on a 6x6 board. Again it is white to move and win.

Problem 3: White to move and win. Politiken December 28, 1942. Solution.

January 1, 1943

New Year's day was the day that Politiken announced the winner of the first competition (from December 26) but also made a new one. The new competition was simply to play a game of Hex, number the moves and send it to Politiken. The best game would be awarded - not stating any criteria.

In order to encourage new players the article says that: "Anyone can play Polygon. It is just to hit an empty cell and put one's mark there. It can be done with different talent, yes, but do you know if you do not have that particular ability?"

Due to great interest and numerous requests Politiken decided to make pads with Hex boards. They cost only 0,50 Danish crown and contained 50 games ready to play with a pen or pencil.

January 17, 1943

Some days only featured an advertisement for Hex as this one picturing a couple absorbed in playing Hex in an air-raid shelter and a woman from the civil defence telling them that the All-Clear was sounded.

The text in the middle begins: "Yes, one quite forgets one's surroundings - however disturbing they are - when one absorbes oneself in a game of POLYGON."

Politiken had made pads with hex boards and sold them through bookstores all over the country. "There are 50 games in each pad, enough for a party or a night in the air-raid shelter - should it be so severe!"

Ladies and Gentlemen, the All-Clear was sounded!!

An advertisement from Politiken January 17, 1943. A woman from the civil defence sticks his head into an air-raid shelter saying: "Ladies and Gentlemen, the All-Clear was sounded!!"

Hex's second appearance

The mathematics department at Princeton University had (maybe still has?) a common room at Fine Hall which is the Mathematics building, where students and teachers would meet between classes for tea and discussion. Games were also a popular means for recreation - especially Chess and Go.

John Nash was a graduate student at Princeton in 1949 when he reinvented Hex as and example of a game with a winning strategy for the first player. David Gale who was an older student there describes how Nash told him about the game, Gale immediately realising the playability of the game. Gale thus made the first board and donated it to the common room.

In 1952 Parker Brothers marketed the game for the first time under the name Hex in the United States. David Gale tells that he received a call from Nash in the mid-fifties who had seen the commercial game and accused him of double crossing, selling the game behind his back. Gale maintains that he didn't, but we can assume that Parker Brothers learnt the game from someone at Princeton.

The Hex game that Parker Brothers marketed in the fifties.

Martin Gardner wrote a column on Mathematical Games for Scientific American for 30 years between 1956 and 1986. In 1957 he gave an account of Hex in which he tells that Hein is the inventor. This column, together with a book of reprinted columns, made Hex popular and encouraged some research. Gardner was a close friend of Piet Hein and so was able to describe the initial history quite accurately. The column also contains an outline of Nash' proof of the first player win and a mention of some variants of Hex.

Piet Hein

Piet Hein, courtesy of Piet Hein A/S Piet Hein was born on December 16, 1905 (so this year he would have been 100!) in Denmark. He was from a family of scholars and related to the famous author Karen Blixen. Scientists and artists frequently visited his family and the author Johannes V. Jensen is said to have inspired him to write poetry.

After attending Metropolitanskolen, a prominent high school in Copenhagen, he went to Sweden to become a painter at The Royal University College of Fine Arts. Before finishing his studies he went back to Copenhagen to study theoretical physics under Niels Bohr who was also a friend of his family.

He did not graduate from The University of Copenhagen either but commenced inventing technical wonders and games, writing poetry and agitating for intercultural understanding and cooperation.

During the German occupation of Denmark 1940--1945 Piet Hein was affiliated with the Danish newspaper Politiken. He mainly wrote small poems, in time developing a distinct style, which he called 'grooks'. These are probably what Hein is best known for - in Denmark at least.

Hein also contributed to architecture and design. He is particularly known for his use of the Super Ellipse for a traffic problem in Stockholm as well as a famous table used at the Vietnam conference in Paris 1969.

A number of prizes was awarded to Hein, among others The Alexander Graham Silver Bell in 1968 and an honorary doctorate at Yale University in 1972 and Odense University (now University of Southern Denmark) in 1991.

Piet Hein died on April 17, 1996, 90 years old.

John Forbes Nash

John F. Nash, Jr. Nash was born in West Virginia, USA on June 13, 1928. His father, John Nash senior was an electrical engineer and provided him with an encyclopedia and gadgets to stimulate his scientific interest.

As a young schoolboy he showed great talent for mathematics and chemistry and for a while actually studied chemistry but changed to mathematics towards the end of his undergraduate study. In 1948 at the age of twenty, Nash was accepted into Princeton University as a graduate student of mathematics with very good recommendations.

It took Nash only a little more than a year to finish his 27 pages Ph.D. thesis on non-cooperative games which was later to give him the Nobel prize.

After receiving his degree in 1950 Nash went to Massachusetts Institute of Technology to teach. Having married and expecting his second son, Nash fell victim to a serious case of schizofrenia forcing him to leave his job and a promising academic career for around 25 years.

His contributions to both game theory and geometry had meanwhile increased in significance and in 1994 he was awarded the Nobel prize in economics, sharing with John C. Harsanyi and Reinhard Selten. Nash's mental condition had been improving but the recognition apparently gave him a final push back into the real world. Nash resumed his research at Princeton and has since been working on a mathematical model for the expansion of the universe as well as game theory and geometry.

This biography is mainly based on Nasar and Nash in The Essential John Nash. (Details below)

The decomposition method

As long as a good algorithm does not show up for determining a winning strategy in the general case, there will be a continued effort to improve the tiny knowledge that we have. OHex is building game trees in order to be able to predict outcomes of given board positions.

Jing Yang is a computer scientist at University of Manitoba, Canada who has restricted his search to narrow parts of the board. Yang has succeeded in tracking a winning strategy for a specific opening on the 9x9 board. We already know from Nash's proof that there is a winning strategy and Yang supplies us with one of them.

Yang takes advantage of a main property of Hex, namely what he calls 'sudden death'. This notion refers to the fact that quite a lot of moves in Hex are forced, which means that most of the defender's options will result in a quick loss, thus cutting of large branches of the game tree.

The approach taken by Yang is a method which consists in decomposing a board position into disjoint groups of cells each constituting a secure connection and in conjunction a winning connection. The method is closely related to the development of edge templates but also considers the inner board and allows the opponent's piece when necessary.

The decomposition method is one that most players apply mentally when playing. Experienced players recognize the (simpler) structures, simply remember the local winning strategy and thus saves a number of computations.

Yang has so far applied his method to boards of up to 9x9 manually but it definitely has a potential for automation. The approach is to consider a specific opening and then decomposing the board into two subgames, each connecting the opening piece to a side. In turn, these subgames decompose into subgames of their own.

As an example of the decomposition method, I have made a reconstruction of a winning strategy for the opening D3 on the 5x5-board. Accordingly, this is only 1/25 of the complete solution for this board. I shall post this here shortly.

Notice how easily one follows the strategy and confirms its validity. Having examined and solved a number of local patterns it becomes a lot easier to evaluate a board position. The task is simply to search the local patterns for those that fit on the board. This means a one-level search as opposed to ordinary tree searches.

My 5x5 solution relies on 6 local patterns, whereas the one solution that Yang has developed for 9x9 requires 715 local patterns suggesting that this method, although much more efficient than depth-first search, calls for exponential processing time.

Yang expects to be able to automate the process of developing the local patterns which is necessary as the work of solving them is quite great. However, the ones already developed obviously constitute quite a lot of the ones for the bigger boards.

Links to resources on Hex

On Hex

Google Directory - Games > ... > Hex: Another collection of links
Abstract Games magazine: Review of Hex with strategy written by Cameron Browne.
Wikipedia's article on Hex: Offers a short introduction to history, rules and some strategy.
HexWiki: Resources on rules, history, strategy and theory. Also contains some of Piet Hein's original puzzles.
OHex: Database of 800,000 Hex games played offering hints as to the quality of known moves.
MazeWorks: A very basic introduction to Hex, includes a poor Hex player and two good Q&A's.

Personal Hex pages

Jack van Rijswijck's Hex page: The designer of Queenbee.
Jing Yang's website: Jing Yang has discovered partial solution to Hex on 7x7, 8x8 and 9x9 using decomposition.
Rune Rasmussen's Hex page: Nearly Danish Australian who is researching on artificial intelligence and has contributed to improving existing algorithms (see below).
Jonatan Rydh's Hex page: Swedish physics and computer science student who plays Hex at Kurnik.

Artificial Hex players

Hexy: A very good Hex playing machine by Vadim V. Anshelevich.
Six: Currently the strongest artificial Hex player. Runs on Linux.
Queenbee: A Hex playing machine that I am able to beat but which should offer quite good play against beginners. Also has some opening theory. By Jack van Rijswijck.

Research

Hex Theory and Proofs Project: Collection of lemmas and theorems as well as a library section, by Kevin O'Gorman
An Extension of the H-Search Algorithm for Artificial Hex Players: Written by Rune Rasmussen and Frederic Maire at Queensland University of Technology, Australia.

Terminology

Bridge: Two cells are said to be connected by a bridge when they make this pattern. This is a secure connection that stretches a bit further than adjacent pieces.
Edge template: A pattern of empty cells known to securely connected a piece to the edge. These reduce the board analysis necessary. An example of an edge template that connects row four to the edge, notice how black will have an alternative to any intrusion by white.
Forcing move: A move that forces the other player to play at a certain cell in order to avoid imminent defeat. Occupying one of a bridge's two empty cells will force the owner to occupy the other.
Ladder: A sequence of forcing moves resulting in a line of each player's pieces next to each other. Learning how to force and use a ladder is an enormous advantage against beginners. An arrow indicates the direction that the ladder will form.
Ladder escape: An occupied cell somewhere in the direction of a ladder. A ladder escape will enable the player to jump ahead of the opponent thereby connecting to an edge.
Pivot point or vulnerable point: A cell that is necessary for a connection to succeed. Represented by a dot, this pivot point connects two white pieces.
Strategy: A set of directions telling a player how to move in response to any move the opponent may make.

Bibliography

I'm reading or using the following books for my work:

Beck, Anatole, Bleicher, Michael and Crowe, Donald: Excursions into Mathematics, The Millenium Edition, A.~K.~Peters 2000
Berlekamp, Elwyn et al: Winning Ways - for your mathematical plays, 1982: On games in general and many specific games in particular.
Binmore, Ken: Fun and Games - A Text on Game Theory, 1992: Game theory for economics students. John Nash is mentioned more than once.
Browne, Cameron: Hex Strategy - Making the Right Connections, 2000: Specifically on Hex strategy, gives a thorough description of different moves and formations arising in most games. It is the first book purely on Hex and also the one to get me started on Hex.
Christiansen, Edmund: Elementer af Matematisk Spilteori, 2004: Elements of Mathematical Game Theory, literature for a course on game theory that I took. In Danish.
Even and Tarjan: A Combinatorial Problem which is Complete in Polynomial Space, 1976: The article showing that a generalization of Hex is PSPACE-complete.
Gale, David: The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly 86, 1979: Contains a proof that Hex cannot end in a draw. Gale uses this fact to prove the Brouwer Fixed-Point Theorem.
Gardner, Martin: Mathematical Games, Scientific American 197, 1957: Gardner's original mention of Hex. A popular presentation of Hex that contributed significantly to spreading the game.
Gardner, Martin: The Scientific American Book of Mathematical Puzzles and Diversions, 1959: This book summarises several articles from Scientific American. The one on Hex is revised and extended slightly.
Garey, Michael and Johnson, David: Computers and Intractability, W. H. Freeman and Company 1979: A comprehensive book on NP-completeness.
Hayward, Ryan: Berge and the Art of Hex, 2003
Kuhn, Harold W. and Nasar, Sylvia (ed.): The Essential John Nash, Princeton University Press 2002: A reprint of several of Nash's scientific papers as well as an introduction to Hex by John Milnor.
Reisch, Stefan: Hex ist PSPACE-vollständig, Acta Informatica 15, 1981: Another proof of Hex being PSPACE-complete; German.

About this site

A short list of questions and answers that are not frequently asked - in fact they have not even been asked.

What is this?: I'm making a webpage dealing with the board game Hex as I'm also writing a masters thesis on Hex. With this webpage I hope to show the world what an interesting game Hex is and I would especially like to get in touch with others who are interested.
Who am I?: My name is Thomas Maarup. I'm taking a master of science degree at the University of Southern Denmark, subjects math and philosophy. My thesis on Hex will get me the degree.
What's to expect?: I'm posting minor articles which are close to the chapters that I write for my thesis. When I finish the coming summer I'll upload the complete work. I'd be happy for any response to these as it will help me improve my thesis.

I'd be happy for an e-mail to thomas(at)maarup(dot)net with any questions or comments.