# hex

Published on September 18, 2007

Author: FunSchool

Source: authorstream.com

On optimal Play in the Game of Hex:  On optimal Play in the Game of Hex By Chris Senkler and Frank Bergmann Topics:  Topics Short Reminder: What is Hex? History of Hex Optimal Play in the Game of Hex An Automatic Theorem Proving Approach to Game Programming What is Hex?:  What is Hex? Rules The game starts with an empty board of hexagonal tiles. Each player 'owns' 2 opposite sides of the board. Players alternate turns placing pieces on the tiles, one player taking white pieces and the other taking black. The first player to create a string to touching tiles of their color connecting their two sides wins. It is also known that the Game of Hex cannot end in a draw. Nash proved in 1949 that player I always has a winning strategy for symmetric boards. History Of Hex:  History Of Hex The game was first presented in 1959 in Scientific American. Invented in 1942 by Piet Hein. Independently rediscovered by Nash in 1948. Important to Mathematics mostly because of it’s relation to the Brower Fixed Point Theorem. Optimal Play in the Game of Hex:  Optimal Play in the Game of Hex Introduction:  Introduction This part of the presentation will concentrate on two points: What is the shortest path with which player one can guarantee a win? What is the minimal number of moves player one must make to guarantee a win? The Shortest Path:  The Shortest Path Let Hex(n,l) be a Hex game of size n with the added constrain that player one wins only by constructing a path of length less then or equal to l. In such a game a draw is possible. Define λ(n) = min { l | player I has a winning strategy for Hex(n,l) } Instead of determining λ(n) exactly, determine a lower bound for λ(n). Lower bound for λ(n):  Lower bound for λ(n) If λ(n) andgt; n, then λ(n+1) andgt; n+1 Inductive proof: All Hex(n+1,n+1) winning paths for player one must either: Contain a Hex(n,n) winning path for player one through the standard n x n sub-board or Contain both [1,n] and [1,(n+1)] Assume that λ(n) andgt; n, this means that player two can prevent a winning Hex(n,n) path for player one on the n x n sub-board. Whenever I plays on the n x n sub-board II follows his strategy, otherwise he can play on [1,n] or [1,(n+1)].  Player I cant have a winning path in Hex(n+1,n+1) For the initial case consider: λ(4) andgt; 4 Proving λ(4) > 4Categories:  Proving λ(4) andgt; 4 Categories There are up to symmetry four categories of distinct first moves. In order to show λ(4) andgt; 4 each opening move will be considered along with continuing paths. Proving λ(4) > 4Category I:  Proving λ(4) andgt; 4 Category I Blue cannot prevent a connection between the top red edge and the bottom red edge  blue cannot win Hex(4,4) with an opening move from category I Player I = Blue Player II = Red Proving λ(4) > 4Category II:  Proving λ(4) andgt; 4 Category II If blue begins with an opening move in category II, red immediately occupies the corner point and thus eliminated the possibility of any winning path of length 4.  blue cannot win Hex(4,4) with an opening move from category II Player I = Blue Player II = Red Proving λ(4) > 4Category III:  Proving λ(4) andgt; 4 Category III Blue cannot prevent a connection between the top red edge  blue cannot win Hex(4,4) with an opening move from category III Player I = Blue Player II = Red Proving λ(4) > 4Category III:  Proving λ(4) andgt; 4 Category III Blue cannot prevent a connection between the top red edge and the bottom red edge  blue cannot win Hex(4,4) with an opening move from category III Player I = Blue Player II = Red Proving λ(4) > 4Category IV:  Proving λ(4) andgt; 4 Category IV Blue cannot reach the opposite border with a path of length 4  blue cannot win Hex(4,4) with an opening move from category IV  There exists no opening move that allows player one to construct a winning path with length 4 or less. Player I = Blue Player II = Red Minimal number of Counters:  Minimal number of Counters Let Hexd(n) be the game of Hex(n) with the added constraint that player one must win by playing at most d counters. Define: δ(n) = min { d | player one can guarantee a win at Hexd(n) } Again only a lower bound will be established. (A trivial lower bound would be δ(n) ≥ λ(n)) Lower bound for δ(n):  Lower bound for δ(n) δ(n) ≥ n + n/4 Proof: Divide the n x n board into nx4 sub-boards Hk and one n x (n-4n/4 ) sub-board H. In order to win Hex(n) player one must have a winning path across H and each Hk. Player one can complete a path across H with (n-4n/4 ) counters but for each k, player one needs at least 5 counters.  Player one needs at least: 5n/4 + (n-4n/4 ) = n + n/4 counters to complete a winning path in Hex(n) Summary:  Summary A lower bound for the shortest path length and the minimal number of counters could be established for Hex games of size n: Shortest path length: λ(n) andgt; n for all n ≥ 4 Minimal number of counters: δ(n) ≥ n + n/4 The Game of Hex:  The Game of Hex An Automatic Theorem Proving Approach to Game Programming Connections:  Connections Two pieces are connected if they are of the same color and share an edge. These 2 white pieces are 'connected'. The black pieces are not. Virtual Connections:  Virtual Connections These two white pieces are 'virtually connected' because even if it is black’s turn White can connect. If black A, white B, and visa versa A B The Problem:  The Problem Computers evaluate a game tree, which is hard for a game like chess, where there are an average of about 40 legal moves from a given game position. Hex has an average of over 100 on most sizes of board, which makes a complete analysis impossible. Without a concrete way of evaluating a position, a computer has to play out every branch to the end before knowing if it was a good move or not. Common Virtual Connections:  Common Virtual Connections 'Two Bridge' connects 2 stones 'Edge Connection' from fourth row Ladder connection:  Ladder connection Connects either stone to the bottom edge. Why Virtual connections are Good:  Why Virtual connections are Good The computer can reduce the game tree because it no longer has to consider moves at the X points, because the responses to these are wrote. X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X Circuits:  Circuits In order to solve the other problem mentioned earlier we need a concrete way to evaluate game positions in which one player has not yet won. To do this we put the game in terms of something that the computer can understand. We equate it to electrical resistance in a circuit. We apply opposite charges to the sides of the board. We Evaluate the position for Black first, and then for white. For black We assign the value rb(c)=1 if c is empty, rb(c)=0 if c has a black piece, and rb(c)=+infinity if c is occupied by a white piece. For each pair of neighboring cells we associate the electrical link with the resistance rb(c1,c2)=rb(c1)+rb(c2). Virtual Connections are treated as having resistance 0 if they are yours, and infinity if they belong to the other player.:  We apply opposite charges to the sides of the board. We Evaluate the position for Black first, and then for white. For black We assign the value rb(c)=1 if c is empty, rb(c)=0 if c has a black piece, and rb(c)=+infinity if c is occupied by a white piece. For each pair of neighboring cells we associate the electrical link with the resistance rb(c1,c2)=rb(c1)+rb(c2). Virtual Connections are treated as having resistance 0 if they are yours, and infinity if they belong to the other player. X Y We repeat this operation for white, using similar algorithms. The overall position is now given by the formula E=Rb/Rw. If E ever reaches 0, black has a clear path to victory, and if E ever goes to infinity white has a clear path to victory. :  We repeat this operation for white, using similar algorithms. The overall position is now given by the formula E=Rb/Rw. If E ever reaches 0, black has a clear path to victory, and if E ever goes to infinity white has a clear path to victory. X Y Using this algorithm, the computer can::  Using this algorithm, the computer can: Evaluate the current game position Evaluate the relative value of different moves Stop an evaluation of a branch of the game tree once the equation E reaches 0 or infinity. Summary:  Summary In order to make it possible for a computer to play 'intelligently' in hex it is necessary to reduce the branches of the game tree that are analyzed and to evaluate the position of a game even if one player has not yet won. This can be done by the use of 'virtual connections' and by treating the board as an electrical circuit whose positional value is measured as the electrical resistance. References:  References [1] Garikai Campbell, on optimal play in the game of Hex, INTEGERS: Electronic Journal of Combinatorial Number Theory, vol. 4, G2, 2004 [2] Vadim V. Anshelevich, The Game of Hex: An Automatic Theorem Proving Approach to Game Programming, Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), pp.189-194, 2000

18. 06. 2007
0 views

30. 04. 2008
0 views

28. 04. 2008
0 views

22. 04. 2008
0 views

18. 04. 2008
0 views

17. 04. 2008
0 views

16. 04. 2008
0 views

14. 04. 2008
0 views

13. 04. 2008
0 views

10. 04. 2008
0 views

09. 04. 2008
0 views

13. 08. 2007
0 views

19. 10. 2007
0 views

18. 09. 2007
0 views

18. 09. 2007
0 views

18. 09. 2007
0 views

18. 09. 2007
0 views

13. 10. 2007
0 views

15. 10. 2007
0 views

19. 10. 2007
0 views

23. 10. 2007
0 views

15. 10. 2007
0 views

28. 11. 2007
0 views

10. 10. 2007
0 views

16. 10. 2007
0 views

06. 11. 2007
0 views

07. 11. 2007
0 views

23. 10. 2007
0 views

19. 11. 2007
0 views

01. 12. 2007
0 views

10. 12. 2007
0 views

14. 12. 2007
0 views

13. 08. 2007
0 views

13. 08. 2007
0 views

13. 08. 2007
0 views

13. 08. 2007
0 views

13. 08. 2007
0 views

18. 09. 2007
0 views

16. 10. 2007
0 views

15. 11. 2007
0 views

23. 12. 2007
0 views

12. 10. 2007
0 views

04. 01. 2008
0 views

07. 01. 2008
0 views

29. 10. 2007
0 views

02. 11. 2007
0 views

15. 10. 2007
0 views

24. 10. 2007
0 views

18. 09. 2007
0 views

13. 11. 2007
0 views

20. 11. 2007
0 views

21. 11. 2007
0 views

28. 12. 2007
0 views

17. 10. 2007
0 views

09. 10. 2007
0 views

03. 01. 2008
0 views

18. 09. 2007
0 views

26. 10. 2007
0 views

27. 11. 2007
0 views

20. 02. 2008
0 views

26. 02. 2008
0 views

13. 08. 2007
0 views

18. 09. 2007
0 views

28. 09. 2007
0 views

30. 10. 2007
0 views

19. 11. 2007
0 views

12. 10. 2007
0 views

14. 02. 2008
0 views

22. 10. 2007
0 views

11. 03. 2008
0 views

13. 03. 2008
0 views

25. 03. 2008
0 views

15. 10. 2007
0 views

01. 01. 2008
0 views

13. 08. 2007
0 views

07. 10. 2007
0 views

12. 10. 2007
0 views

28. 02. 2008
0 views

29. 10. 2007
0 views

17. 12. 2007
0 views

04. 03. 2008
0 views

08. 10. 2007
0 views

30. 10. 2007
0 views

07. 11. 2007
0 views

27. 03. 2008
0 views

02. 10. 2007
0 views

09. 10. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 06. 2007
0 views

18. 09. 2007
0 views

29. 10. 2007
0 views

21. 10. 2007
0 views

22. 10. 2007
0 views

18. 09. 2007
0 views

03. 10. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

15. 06. 2007
0 views

23. 10. 2007
0 views

18. 09. 2007
0 views

13. 08. 2007
0 views

18. 06. 2007
0 views

18. 09. 2007
0 views

16. 10. 2007
0 views

29. 02. 2008
0 views

18. 09. 2007
0 views

18. 09. 2007
0 views

24. 10. 2007
0 views

24. 02. 2008
0 views

18. 09. 2007
0 views

23. 10. 2007
0 views

18. 10. 2007
0 views

18. 06. 2007
0 views

20. 03. 2008
0 views

31. 12. 2007
0 views

27. 09. 2007
0 views

18. 09. 2007
0 views