Volcano

[ddyer]

Volcano has the potential to be a good intermediate level problem for AI developers. I have implemented
a basic robot for Boardspace.net, based on the generate/alpha-beta/evaluate model. It plays decently enough
to beat beginners, but it will obviously not be strong enough to qualify as expert.

for reference, here are the rules: http://boardspace.net/volcano/english/rules.html

The reason this simple model will never be expert is that a player's turn can include an unlimited number
of moves of the "volcano caps" which manouver them into the desired position to complete the turn. It is routine
for sequences of 20 or more of these moves to precede the final move of the turn. There's no way a simple alpha-beta
will be able to reach that depth in a reasonable play time. There are lots of potential tricks and optimizations to
improve on this brute force approach, which make it an interesting problem.

One approach might be to make the robot actually play a somewhat related game, where you can
position two volcano caps anywhere before causing an eruption. The robot that plays this game would use
an expert "pathfinder", conceptually in parallel, which would figure out if, and how, the configurations needed by the
imaginary game can be reached in the real game.

[Rémi Coulom]

Hi Dave

I took a look at Volcano.

I noticed a few problems with the rule page, by the way: html title is "Rules for Fanorona". Links to translations either do not work (français) or automatically translates the rules of Fanorona. Also, you may wish to add at the beginning of the text of the rules that each pyramid is a stack of (2?) pyramids of the same color. It took me some time to figure it out, since it is not obvious on the pictures.

Regarding an alpha-beta implementation, what I would do is this: consider each move of a volcano cap as a move. The recursive call would negate the returned value or not, depending on whether the player to move changed or not. This ways, the branching factor is reasonable.

In order to force players to switch turn during the search, you may need to give a penalty in the static evaluation function if it is called after a cap move without eruption. Maybe a penalty proportional to the number of consecutive cap moves would work. I do not know the game enough to tell.

Rémi

[ddyer]

Hi Dave

Regarding an alpha-beta implementation, what I would do is this: consider each move of a volcano cap as a move. The recursive call would negate the returned value or not, depending on whether the player to move changed or not. This ways, the branching factor is reasonable.

This is standard procedure. A useful consequence of this is that after planning a move a depth N, and making the first move, the robot then plans another move at depth N and so sees a little farther and can make an even better move, if one becomes available.

In order to force players to switch turn during the search, you may need to give a penalty in the static evaluation function if it is called after a cap move without eruption. Maybe a penalty proportional to the number of consecutive cap moves would work. I do not know the game enough to tell.
Rémi

I use a couple tweaks along this line - the search only considers erupting moves after N nonerupting moves, and also on the last ply of the search.

The main point though, is that these tweaks to alpha-beta won't ever get you to a 20 move plan to rearrange caps. Something quite different will be required.