chiark / gitweb /
Improve the Flood solver.
authorSimon Tatham <anakin@pobox.com>
Thu, 15 Jan 2015 20:21:05 +0000 (20:21 +0000)
committerSimon Tatham <anakin@pobox.com>
Thu, 15 Jan 2015 20:36:19 +0000 (20:36 +0000)
commitcca302c01b7b331c280ec885d783d673a0c951c3
tree6eb7e7507a690da2eb06a6708f8bcb9ff401e273
parent202e7fecfdac09b791b204cde464f09f9165f55b
Improve the Flood solver.

Previously it simply chose every move based on the static evaluation
function 'minimise the pair (longest shortest-path to any square,
number of squares at that distance)'. Now it looks three moves ahead
recursively, and I've also adjusted the evaluation function to tie-
break based on the number of squares brought to distance zero (i.e.
actually in control).

The result isn't an unconditional improvement on the old solver; in a
test run based on 'flood --generate 1000 12x12c6m0#12345' I found that
57 out of 1000 grids tested now had longer solutions. However, about
three quarters had shorter ones, and solutions are more than a move
shorter on average.
flood.c