Hamiltonian Maker-Breaker games on small graphs - The computer program

(Supplement to original work available on arxiv.org: https://arxiv.org/abs/1708.07579)

On this page you can find all relevant information on how to run and use our computer program which solves Hamiltonicity game, Hamiltonian Path game and Fixed Hamiltonian Path game on small (finite) boards.

Our computer program is implemented in Java programming language, source code along with runnable JAR files can be downloaded here: ham.zip in form of a ZIP archive. At this point, there are two options, you can either opt to execute runnable JAR files or you can import the project into Eclipse IDE and run the code from there. Both options are explained in more detail below.

Eclipse IDE option

Prerequisites:

1. Java SE Development Kit (JDK) 7 or newer: http://www.oracle.com/technetwork/java/javase/downloads/,
2. Eclipse Java IDE: https://eclipse.org/ide/,
3. Apache Maven: https://maven.apache.org.

ham.zip contains Eclipse project, so you should import the contents of ham.zip into your Eclipse workspace. Project relies on one third party library (Trove) and dependency management is implemented using Apache Maven so you should now run the following commands from the command line, in the root folder of the project in order to download these dependencies, build the project and generate Eclipse project files:

1. mvn clean install
2. mvn eclipse:eclipse

Now you are ready to run the program, and here is a brief overview of Java packages found in the project.

Overview of Java packages:

• rs.dmi.master.game.base - package containing abstract base classes for game solver programs. There are two implementations, one based on Set and one based on BitSet data structure.
• rs.dmi.master.game.hamiltonian - this is the main package, it contains all the classes related to solving Hamiltonicity game, Hamiltonian Path game and Fixed Hamiltonian Path game.
• rs.dmi.master.game.hamiltonian.bitsetbased - package containing the most efficient implementation of programs which solve Hamiltonicity game, Hamiltonian Path game and Fixed Hamiltonian Path game. There are three classes in this package, one for each of the games, and all three need to be executed with four command line arguments, "n c d p", which have the following meaning:
  • n - number of vertices of the complete graph representing the game board.
  • c - critical number of transposition table entries, soon after number of entries goes over this value table will be partially emptied.
  • d - represents depth in the game tree. When cleaning the transposition table all entries related to depths in the game tree larger than d will be removed.
  • p - player which starts the game, use 'm' for Maker and 'b' for Breaker.
• rs.dmi.master.isomorphism - package that contains implementation of Brendan McKay's canonical labeling algorithm.
• rs.dmi.master.lookuptable - package containing various implementations of transposition table (i.e. lookup table). Main interface is LookupTable.
• rs.dmi.master.pathcollection - package containing various implementations of winning set collections. Main interface is PathCollection.

Runnable JAR option

Prerequisites:

1. Java SE Runtime Environment (JRE) 7 or newer: http://www.oracle.com/technetwork/java/javase/downloads/.

There are three runnable JAR files: ham-cycle.jar, ham-path.jar and fix-ham-path.jar, one related to each of the games. Each of these three JAR files basically runs the corresponding class from rs.dmi.master.game.hamiltonian.bitsetbased package. This means that these JAR files accept the same command line arguments as explained above.

Example: "java -jar ham-cycle.jar 5 10000000 20 m".

Memory considerations

It is worth noting that our program will usually require large amounts of computer memory in order to be able to efficiently solve the game and store desired number of entries in the transpostion table. We were mostly providing Java VM with 2GB to 14GB of RAM memory. This is specified using "-Xmx" Java command line argument, both when using Eclipse IDE and running Java from command line.

Example: "java -Xmx2G -jar ham-cycle.jar 5 10000000 20 m".

For all the additional information, suggestions and comments about this project you can contact us on: nikola (dot) trkulja (at) dmi.uns.ac.rs.