Opening the Game of Hex - Case Study Example

Introduction Piet Hein a Danish poet, mathematician and scientist is accredited for being the first person to invent the game of Hex in 1942 (Eckmann pp. 385). The game was re-discovered by John Nash at Princeton. Rediscovery of this game by Nash made it popular to graduate students at Princeton. Given a perfect play, the game is always won by the first player. Hex never ends in a tie; there must always be a winner (Gale pp. 1). The Hex theorem is believed to be intuitive but it requires invoking complicated topological results to prove it. Hex theorem was proved by John Nash but he never went ahead to publish his proof (Weinberger pp. 380). A simple graphical proof of the theorem showing equivalence between Brouwer Fixed Point Theorem and Hex Theorem was provided by David Gale. Hex Theorem To show that the first player wins Hex, two players A and B participate in the game. A is the first player and B is the second player. Just to contradict the situation it is assumed that the second player B has the strategy of emerging the winner. Player A then plays a random move at any part on the board. B turns out to be the first player when he plays. This makes A who was the original first player become the second player and for the rest of the game can play the winning strategy. Lemma 1 which indicates that possessing random/extra pieces of your own does not hurt, player A is not hurt by having an additional piece from the initial random move. Given that the winning strategy has been stolen from player B by player A the second Lemma comes in play which states that Hex cannot end in a draw since B cannot win. This then proves that Hex must be won by the first player (Gale pp. 2). FIGURE 1 Proving the Hex Theorem We begin with a graph lemma to prove the Hex theorem. Finite graphs with vertices having degrees at most two is the combination of subgraphs that are disjointed, each with either, isolated node (i), a simple cycle (ii) and a simple path (iii). To prove this, the numbers of edges in a graph are inducted. A graph g with N nodes is considered. Every node has a degree at most two which means that g will have not more than N edges. In that regard, a graph with k edges is denoted as gk.All the nodes are isolated in the base case g0. An edge is randomly picked and removed (called u,v) if the graph has n+1 edges. The degrees for nodes u and v are at most 1 because they had a degree at most two prior to removal of edge u and v. This implies that u and v are not on any cycle. Gn is assumed to be the combination of disjoint simple paths, simple cycles and isolated nodes. U and v are now added into the graph. The addition of (u, v) does not in any way change the subgraphs which had been disjointed from u and v in gn. The nodes u and v are now either on the same cycle or simple path. This means that gn+1 is the combination of the disjoint simple paths, simple cycles and isolated nodes. This implies that the lemma is true for all gk with0≤k ≤N. The white and black colors in the game are substituted with o’s and x’s respectively. The game board is represented as a graph G=(V,E), where Vis a set of nodes and E a set of edges. Every side of the hexagonal board is an edge represented by X and every vertex is represented by node V. Four additional nodes are created one linked to every corner of the core graph. These new nodes are denoted as u1,u2, u3, and u4 while the edges that link them to the core graph are denoted e1,e2,e3, and e4. X-face is one of the sections marked as X orXᶦ or just x and an O-face represent a section marked as O or Oᶦ or just o. It is therefore evident that edges e1,e2,e3, and e4 lie between O-face and X-face because the sections O,Oᶦ,X and Xᶦ are also regarded as faces. It shows that a simple path links two vertices out of u1,u2,u3 and u4. A winning chain is contained in the hexagonal tiles traced out by the simple path (Eckmann pp. 390). Theorem 4.2 This theorem indicates that in case each tile of the Hex board is depicted as either o or x, then it is presumed that a x-path exists which connects sections X and Xᶦ and an o path which links sections O and Oᶦ. To prove this, a subgraph Gᶦ=(V,Eᶦ) of G is constructed with the same nodes but the edges are a subset. The edge is defined to belong to Eᶦ in case it is between O-face and X-face. E1, e2 e3 and e4 will be part of Eᶦ. u1,u2,u3and u4 nodes have degree one. In case all three hexagons surrounding a node have the same mark, the node will be isolated in Gᶦ and its degree is zero. If two hexagons of one pattern and a single hexagon of the other pattern surround a node, the nodes possess two incident edges. Every node in the core graph will have degree two or zero. Figure two shows a Hex board with O and X notation. Gᶦ is a combination of separate subgraphs because it has nodes with degrees at most two. Each subgraphs is a simple path, simple cycle or isolated node. u1,u2,u3 and u4 nodes depict the end of some paths since they have degree 1. Subgraphs G’s disjointness makes sure that the paths do not cycle. It therefore means that two simple paths exist in Gᶦ with every path linking two of u1,u2,u3 and u4 nodes. Despite the winner depending on the path’s orientation, a winning chain of hexagons is traced by the paths. In this regard, for any arbitrary configuration of the Hex board, one of the player’s winning path always exist. An example in figure two, the darkened vertices and edges belong to Gᶦ. two simple paths exist one connecting u2 and u3 and the other connecting u1 and u4. A winning chain for the O-player is marked out. John Nash used the Hex Theorem to prove that the first player possesses a strategy of winning. The strategy is a simple stealing argument (Gale pp.5). Equivalence of Brouwer’s Fit Point and Hex Theorems. To make it simple, the representation of Hex board is changed once again in this section. Lattice points of Rnare denoted by Zn . For x ≠y Ɛ Rn, we let │x – y │= maxi (xi - yi ); x < y if xi ≤ yi for all i. if x < y or y < x then the points x and y are comparable. The Hex board with two dimensions and of size k called Bkrefers to a graphwhose apexes is the set of all z Ɛ Z2 with (1,1) ≤ z ≤ (k, k). zᶦ and z apexes are adjacent ( implies that an edge Bklinks zᶦ and z) if │z - zᶦ│ = 1 and zᶦ and z can be compared. FIGURE 3 showing a Hex board of size 5 The edges of the board are labeled by the cardinal directions E, W, N, S. for a k size board, the boundary’s vertices are all z= (z1,z2) which fulfill z2= k, z1 =0, z1 =k, z2 =0, respectively. Rather than the o and x player, we can regard them as vertical and horizontal players. The He Theorem can now be restated with the new board representation. Theorem 5.1 Let Bkbe covered by two sets V and H. Then either V contains a linked set meeting Sand N or H contains a linked set meeting W and E.The main target of this is to prove that Hex Theorem is the same to Brouwer Fixed-Point Theorem which states that Let f be a continuous mapping from the unit square I2 into itself. X Ɛ I2 exists such that f (x) = x The proof is to show that the Brouwer Theory is implied by the Hex Theorem. Let f:I2 –I2 be represented as f(x) =(f1(x),f2(x). Given that set I2 is compact, it clearly indicates that for any Ɛ > 0, x Ɛ I2 exists in which │f(x)-x│< £.I2 compactness also indicates the uniform continuity of f, it is therefore known that given £>0, d >0 exists such that in case │x-xᶦ│< d, it implies that │f(x) –f(xᶦ)│£) V+ = (z│f2(z/k)-z2/k>£) V- = (z│z2/k-f2(z/k)>£) The aim of this is to prove that the four sets don’t cover Bk. The desired fixed points are the points not covered by the four sets(given that z does not lie on any of them. This implies that │f(z/k)-z/k│£ as well as Zᶦ1/k-f1(zᶦ/k)>£ When the two equations are added; 5.1 F1(z/k)-f1(zᶦ/k) +zᶦ1/k-z1/k>2£ Assuming that z’ and z are adjacent, and k’s choice such that 1/k Read More