Gambler, the next generation

Last summer I've been experimenting a bit with static evaluation in Havannah as I was convinced that a static evaluation can be made that provides a useful approximation of the win chances in a position. It was clear that such an evaluation function would not be a cheap one to execute as it should be able to assess frames and dead structures. I also decided that ringevaluation was not necessary, as the search should be able to deal with the shallow tactics, ignoring the possibility of large ring structures (which would be difficult to find in MC based searches as well). When I had to move to other activities, I had a working prototype, able of doing about 8 evaluations per second on a size 10 board. The resulting evaluation seemed intuitively much better than an MC search of a couple of minutes but further testing was required before putting it to the test in real life games. When RoF appeared I decided to give it one more look, testing it in a few games against RoF, improving things that did not work as planned and the result is now playing here. I hope the change in approach leads to a new playing style where tricking the opponent with lots of ring threats is no longer the main strategy.

That would be an improvement indeed, hope it works out as planned :)

While I believe a decent static evaluation function will be very helpful, I suspect that ignoring ring detection will weaken the algorithm on small boards.

Rings are ignored in static evaluation. But not in search. So when search encounters a ring (which is a solid win/loss) it will be scored as such. Small rings are usually shallow tactics anyway, and a sequence of ring threats will narrow down the search tree. In addition: Even with a sloppy (i.e. non-optimised) implementation, I get about 8-9k evaluations on a base 4 board, 3-4k on a base 5 board. I've watched a few games and it seems it is even using ring-threats now to achieve a strategic advantage (instead of blindly trying rings, hoping the opponent misses one).

Another thing I saw is that it now plays for bridge-tactics instead of rings. I guess that can be called an improvement ...

Yes, if if goes for bridges I think it is an improvement. I believe that bridges should play a much larger role than what is observed in many games.

"I believe that bridges should play a much larger role than what is observed in many games."

The bridge is the oil in the machinery, the soul of the game if you like :)

Does the new Gambler defeat the old Gambler in head-to-head play?

Haven't tried that. I'm still in the phase where the implementation is sub-optimal so I consider those test matches to be a waste of time right now. Perhaps later.

I did just discover an annoying bug in the static eval though which has just been corrected. I'm afraid this invalidates some of the results (scores were way off in some cases as it considered one corner cell to be part of one of the sides). This bug did not exist in the MC version.

Hi Richard, I'm curious -- do you run the static evaluator on all possible moves at each level or do some heuristics-based forward pruning?

As the static eval returns an estimated win-chance, I'm using UCT as the search driver and just replaced an MC playout by the static eval. This means that some of the tricks like RAVE lost its value and I'll need to find something else to initialise all moves in a position. Currently the moves are initialised with value/times 0/0 unless the move finalises a winning structure or prevents the opponent from building one on the next move. This is certainly an area of improvement and I'm already working on it. Running eval on all moves is just too slow.

Thanks for the explanation, Richard! Can you elaborate a bit on the initialization value? What did you mean by value/times 0/0?

Basically it means that the next time this node is visited, a random unplayed move will be chosen (unless there is a known win with another move).

@Richard: "When RoF appeared ..."

I'm glad that my work triggered some progress in the area.

It's fun to watch the size-6 tournament, and the other bot games.

RoF does UCT, and in each leaf node, a static evaluation and some

playouts (a small number, e.g., 10). The value of the node

is a weighted sum of static-eval and playout results.

In the static-eval, I ignore rings (so it misses large-scale ring threats).

Basically I compute the number of stones that white/black must put down

to get a fork/bridge (assuming the opponent passes). Then it's

STATIC = FORK_WEIGHT * (1 / WHITE_FORK - 1 / BLACK_FORK)

+ BRIDGE_WEIGHT * (1 / WHITE_BRIDGE - 1 / BLACK_BRIDGE)

Taking reciprocals because I don't really trust larger numbers.

Currently, FORK_WEIGHT = 1 and BRIDGE_WEIGHT = 0.5

but I am not really sure about this.

I noticed that for BRIDGE_WEIGHT too large, it would play along

the edges only, and this is of course globally wrong.

The result is that RoF now is a bit too confident playing in the center...

In Gambler I'm doing a graph based approach as well, and I'm sure this can be optimised to be faster than it is right now. Gambler values forks and bridges in the same way, but the evaluation is a bit more sophisticated than just calculating the number of missing stones.

I'm building a graph with stone groups (chains, strings or whatever you call it) and empty cells, and give the vector to the neighbours a certain weight. This weight depends on occupation of a cell, but I also take the virtual paths into account as well as blocked paths (which requires to pass through a virtual path) and gates, where you are passing between two cells that are occupied by the opponent and singletons (unoccupied corner cells with bridges). When calculating the shortest path (with a small bonus for the side to move) the static eval seems to be fairly accurate. It completely ignores rings (in static eval, not in search), but well, it seems to do well without that on the smaller boards.

The main problem on the larger boards is that besides the branching factor the evaluation contains a third order algorithm (Floyd-Warshall) which reduces the number of evaluations that can be performed. I'm sure this can be optimised (Floyd-Warshall is overkill but works good enough to demonstrate the viability of the evaluation method, and aggregation of empty cells to reduce the graph size may be an option as well)

In addition to this, my search lacks any move sorting on new UCT nodes as RAVE obviously does not work without an MC search, and initialising the node with evaluations after all moves is not a good idea either, so I'm looking for some new heuristics. Stay tuned ...