Directory

Every repository should have a directory for files describing the structure of the repository and a high-level overview of the contents

repo
│
└─── data
│   │
│   └───freeplay_boards : data sampled from ThinkAloud
|   |
│   └───peak_boards : peak data
|   |
│   └───jeroen_puzzle.json : Jeroen's Puzzles
│
└─── log : directory for storing results
│
└─── src
│   │
│   └───pattern_detector
|   |     |
│   |     └───wd2.jl : 2-move win detector
|   |     |
│   |     └───wd3.jl : 3-move win detector
│   │
│   └───consts.jl : constant numbers for wd2/wd3/solvers
│   │
│   └───utils.jl : initialization and other utilization functions
│   │
│   └───win_detector.jl : tools to determine whether the board has a forced-win strategy
│   │
│   └───solver.jl : main function of the solver 
|
└─── scripts
│   │
│   └───setup.jl : script for installing required packages
|   |
│   └───test_solver_[DATA].jl : testing scripts for the corresponding data
|
└─── run
│   │
│   └───run_test_solver_[DATA].sbatch : SLURM submission commands used in HPC
│
│   README.md 
│

Installation

To use the solver, you should install Julia (http://julialang.org/downloads/) first.

After installing Julia, you should delete the first line of scripts/setup.jl to use default path or specific to your preferred path. run julia scripts/setup.jl to install required packages.

Usage

To use the solver, run solver_log = Solver.solve(black, white, find_one_solution, find_all_win, max_steps, find_optimal), where

• black and white : The list of black and white piece indexes from 0 to 35.
• find_one_solution : If placed true, the solver will stop searching as soon as it find a solution but the solution could be suboptimal. Otherwise, the solver will find all solutions (forced-win first moves). By default, find_one_solution=true.
• find_all_win : If placed true, the solver will find all the wining path for each opponent's move. Don't recommend to do that with large max_steps, it will be extremly time-consuming. By default, find_all_win=false, the solver will return only one forced-win path for each opponent's move.
• max_steps : Max search depth. The solver will search for at most max_steps player's moves and max_steps - 1 opponent's moves. If the solver cannot determine the board state with the given depth constraint, it will return unknown. By default, max_steps=100, which means, the solver doesn't have a depth constraint.
• find_optimal : If placed true, all the solutions should be optimal solutions. By default, find_optimal=true.

The return is a dictionary:

solver_log 
│   
└───log
|   |
|   └───board state : whether the board is a win/loss/draw board
|   |        |
|   |        └───win : the player has forced-win strategies
|   |        |
|   |        └───loss : the opponent has forced-win strategies
|   |        |
|   |        └───draw : Neither the player nor the opponent has forced-win strategies
│   │
│   └───path : if the board is a win board, then the value is a list of paths to win, otherwise a empty list
|   |
|   └───solutions : a list of forced-win first move indexes (0-35)
│   |
│   └───num win steps : shortest wining length specifics to the first moves in "solutions"
│   │
│   └───time cost : time to find the solution (seconds)
|   |
|   └───storage cost : maximum storage usage in the solving process (bytes) 
|   |
|   └───num nodes : number of nodes in the tree-search process
|   |
|   └───num iterations : number of searched first moves, i.e., number of nodes in the top level
|   |
|   └───num call wd2 : number of the times calling 2-move win detector
|   |
|   └───num find wd2 : number of the times finding a 2-move win moves
|   |
|   └───num call wd3 : number of the times calling 3-move win detector
|   |
|   └───num find wd3 : number of the times finding a 3-move win moves
│
└───black : black piece indexes (0-35)
|
└───white : white piece indexes (0-35)

Run on HPC

1. Run ```module load julia/1.6.1``` 
2. Change the path in the first line of ```scripts/setup.jl``` (```ENV["JULIA_DEPOT_PATH"] = "/scratch/sl9315/.julia_depot"```) to your path. Or delete this line to use default path. It depends on the file number quota of your '''home''' directory.
3. Set up the environment by ```julia scripts/setup.jl```
4. Change the task parameters in ```run/run_test_solver_[DATA].sbatch```
4. Submit by ```sbatch run/run_test_solver_[DATA].sbatch```

Authors and Acknowledgements

Codes: Jieyu Peak Data: Yotam Freeplay Data: Shucheng Jeroen's Puzzles: Jeroen

License

Contact lab about licensing code