imos/icfpc2015

Team UNAGI Final Submission @ ICFP Contest 2015
===============================================


## Instruction

### Build & Run

As specified in the problem description, invoke `make` and `play_icfp2015` to build and run.

Solutions are written to the standard output. We may also write some messages to the standard error for debugging purpose, which should be ignored.

### Dependency

We checked that, on plain Ubuntu 14.04, all the dependency is automaticaly installed in `Makefile`. Just for in case, we list the main dependent packages.

* The front-end script is written in *PHP*, and requires *PHP*.
* The internal evaluator is written in *C++11*, and thus requires *g++*.
* We use *bazel* for building C++ programs (e.g., the internal evaluator).
* The solvers are written in *Java* and *C#*, so *Java* and *Mono* are also required.



## Description

### Overall Strategy

We developed two solvers named "wata" and "chokudai". Furthermore, solver "wata" has a few variations. None of them overwhelms the other. Therefore, script "play_icfp2015" executes these solveres in parallel, and then the best solution is selected.

### Front-end script

The PHP script `play_icfp2015.php`, which is called from shell script `play_icfp2015`, is our front-end script. It executes our solvers in parallel. It collects the solutions of the solvers, and then selects and outputs the best solution using our internal evaluator.

### Solvers

Both solvers use beam searches, but they use different board evaluation functions, as well as spelling strategies.

* "chokudai" is faster one with wide beam width. It can flexibly adjust its running time by adaptively changing beam width.

* "wata" is slower one with a clever spelling strategy using dynamic programming. "wata" requires ~2GB memory for conducting large dynamic programming.