Examples of Code

Below are some examples of source code for programs that I have written. They play the game called Hex, which was introduced to me by Tom Hayes, a graduate student and one of the best Hex players on the internet. One version, hexIIRandom , has been converted to an applet.

Hex is played on a square grid of hexagons. One player, in the case of these programs the computer, wins by connecting the top to the bottom with his pieces. The other player, the opponent of the computer, wins by connecting the left hand side to the right hand side. Only one player can win, and, in fact, someone must win.

The following programs all have the same interface. The game starts by the player picking a size for the grid. This number is for the dimension of one side. Then one plays a move by entering its coordinate. Then the computer responds, and so on, until the game finishes.

Each of the programs use a probabilistic method to choose a move. The distribution is based on the fact that each players will play the same number of moves, with the same number of choices, no matter what choices are made. Perhaps rethinking this assumption will lead to better results. Still, I think it is surprising how intelligently, if not well, they play.

The program hexRandom uses an evaluation as the probability of winning in a random continuation, and looks ahead one move using this evaluation. The program takes about the order of n^4, in time, where n is the size of the grid, to make a move. A version exists in C++:

• Makefile
• hexRandom.cc
• hex_board.h
• hex_board.cc
• testSquare.h
• testSquare.cc
• Move.h
• Move.cc
• MoveList.h
• MoveList.cc
• occupantType.h
• occupantType.cc
• coords.h
• coords.cc
• RandomAnalysis.h
• RandomAnalysis.cc

and a version in Java: hexRandom.java with hexBoard.java .

The program hexIIRandom simply picks the move that occurs in the most wins after random continuation. It takes about the order of n^2 log n to make a move. It seems unlikely that the n^2 barrier can be broken since the program should need to know what has been played on all of the squares. Perhaps a parallel computation, or even a cellular automaton or quantum computation, could do this. There is a version in Java: hexIIRandom.java with hexBoard.java .

Soon to come is an applet version of the Java programs.