Courses/CS 460/Hex
From CSWiki
Contents |
[edit] References
- Wikipedia has a nice entry on the game. That page includes links to a number of other Hex sites, including a Hex Wiki.
- Hex strategy: making the right connections by Cameron Browne
- ICGA-Hex
- Hexy
- Six wins 2003 tournament
- Six
- Rune Rasmussen
- An extension of H-Search or here Rasmussen and Maire, H-search and extension
- Rasmussen's PhD Thesis Resistance discussion
- David King's Hex site
- Kevin O'Gorman's Hex Game database
- Maarup's page (See links toward the bottom.)
- Brendan Smith's senior thesis Queenbee algorithm
- Kahl, et. al. Learning how to play Hex (pdf) H-search with neural nets
- Sensei's library
- More hex links
[edit] ArasHEX
"ArasHEX" (jar) (upload page) is an executable jar file (including src) that Arash created. You should create your own MyPlayer class as a subclass of Player. The MyPlayer class is an example. Insert references to your class in HexGameGui.main( ).
[edit] Analog approach to Hex
Jonathan Berney found this paper (a senior thesis by a student at Middlebury college), which takes an analog approach to Hex. Jonathan continues with these comments.Each node is given a value: 0 if it is occupied by one player, infinity if it is occupied the the other, and a nonzero value (such as 1) if it is unoccupied. The resistance between two nodes is given by the sum of the values of the nodes. Assuming all nodes are connected, the strategy is to find the equivalent resistance of the entire circuit. The equivalent resistance will be 0 if there is already a chain of the first player's nodes between their sides, and infinity if the same is true for the other player. It will be somewhere between for a game state where neither player has yet made a winning connection.
Unfortunately, the strategy for implementing this evaluation function is not sufficiently fleshed out. The author concedes on page 42: "due to a lack of knowledge concerning electrical engineering on the part of the author, these laws will not be explained in any more depth."
I came upon a handful of other papers which go into about the same amount of detail:
- http://home.earthlink.net/~vanshel/VAnshelevich-01.pdf
- http://www.msri.org/publications/books/Book42/files/anshel.pdf
- http://www.cse.iitb.ac.in/~nikhilh/NASH/y-hex.pdf
The following paper was much more illuminating:
Figure 8 on page 18 provides the best illustration I've been able to find of the electric circuit model. Section 6.2.3 on that page describes how to use Kirchoff's Current Law in order to devise a system of equations of multiple variables in order to determine the individual voltage of a node. Given the individual resistances and voltages, we can find the total current flowing through the circuit, and thus the equivalent resistance. …
I've found a linear algebra package for Java called JAMA which is capable of solving the systems of equations that I would be dealing with. Here's an example I found of its use:
[edit] Board representation
The Hex Wiki offers an alternative representation to what we discussed in class. This example shows a 4 x 4 board.
Look at the row and "column" indices. Each cell can be addressed by a row number (1 .. 4) and a column letter (a .. d). The "columns" slope forwards from top to bottom. As an example, consider cell (2, b). It contains a red dot. It has these six neighbors: (1, b), (1, c), (2, a), (2, c), (3, a), and (3, b). Given these conventions there seems to be no reason that the board can't be stored in a traditional 2-dimensional array.
To make this even more traditional let's number the rows and columns starting with 0. The top left cell will be (0, 0) instead of (1, a), and the bottom right cell will be (3, 3) instead of (4, d). Let's use these conventions for addressing the board.
[edit] Strategy
The example above is from the Basic strategies page of the Hex Wiki. It illustrates what's called a bridge. Blue can't stop red from connecting its two pieces. If blue takes one of the separating squares, red will take the other. So red need not waste a move and make the connection immediately. Red can wait until blue takes one of the squares.
The Hex Wiki also points out that the player who goes first has an advantage. So a swap rule is usually played. The second player has a choice of swapping colors (and taking the move that the first player made) or continuing with his initial color. That will encourage the first player to make a weak first move. Since all the border moves—except the two acute corners: (0, 0) and (3, 3)—are considered good first moves (not too strong; not too weak) let's let the referee make the first move of the first player by selecting a cell at random from among the acceptable border cells.
[edit] Other sites
There is a Game Center site that discusses Hex along with numerous other games, including Dots and Boxes, the other game we discussed in class. Wikipedia also has a Dots and Boxes page. The Little Golem site also has Hex as well as a number of other games. (See the FAQ for a list of games and a brief description of each.)
[edit] Down-loadable GUI and player
There is a down-loadable open source Java Hex GUI here. Download and extract the zip file. Start it using either of the .bat files or the .jar file. Once it starts you can attach a computer player by using the "Attach program" entry under the file menu. The default program (six_gtp_engine) plays a good game.
HexGui itself is written in Java. The player is written in C++. Source is included in the download for both. More information here.
If we adopt HexGui as our platform, perhaps we should also adopt its board addressing conventions.
I was able to create an eclipse project and run it. The main class is gui.HGui.main(). When run from eclipse it starts at the Java top level, which is not where the player engine is located. An error message is generated at startup. When attaching the gtp player, you must browse for it.
HexGui seems to have been built with the gtp engine as the intended computer player. There are a great many gtp references. I haven't been able to determine how HexGui asks the gtp engine what its next move is.
It appears that HexGui gets a move from the computer through the method gui.HGui.generateMove(). That seems to interact with gtp.GTP and gui.CommandThread, which interact with the computer player. But I don't know how that interaction works. Perhaps something simpler could be substituted for gui.HGui.generateMove(). That method sends a command to the computer player, which sends back a response. The actual board seems to be kept by gui.HexBoard, and gui.HexBoard.setValue() sets a value. But tracing the link between generateMove() and actually setting the board is not obvious.
