David Wilson's "All Critical Moves As First"

Several years ago, during 2004 and 2005, David B. Wilson

wrote a very nice computer program which plays the games

Random-turn Hex and Random-turn Y almost perfectly.

Ideas from his bot may also be used in MCTS programs

for "normal" Hex or other board filling games.

3-Hirn Verlag -- Games section

See more text in the computer-go mailing list in

this posting.

Sorry for the line with "3-Hirn Verlag";

simply ignore it.

I made a mistake in formating the text.

Ingo.

How widespread is that property of Random-turn Hex? E.g., does MCTS also approach perfection for Random-turn Havannah?

Of course. But MCTS is not necessary in such games.

Pure MC alone is sufficient.

The only question might be if MCTS converges (much)

faster to perfection.

Hmm, would there be many critical moves in Havannah? In Hex the winning formations by their very nature are mutually exclusive because they have to cross. A handful of stones, if switched, would help cross the board in the opposite direction. In havannah though, the winning conditions are not mutually exclusive, and often in separate areas of the board. Clearly sometimes there would be critical stones, but my guess is that it'd be far more rare than in Hex.

Right. Havannah is not a traditional board filling games.

One might define pseudo-criticality: The (random) game

stopps when one winning condition is fulfilled, and

in that position all stones which can not be deleted

without giving the win away are called pseudo-critical.

I am not sure if this would be of much value.

I seem to remember Wanderer using only those moves for its rave implementation. This is quite different than Castro, which uses all moves for rave. I haven't tested it, but I think Richard found it to be better.

Hi,

I tried such moves in my havannah bot a long time ago, but as far as I remember it was not better than all moves for rave.

MCTS?

MCTS stands for "Monte Carlo Tree Search":

in contrast to "pure Monte Carlo" the random games

do not all start at the successors of the root.

Instead a tree is built up (in some way), and only at

the current leaves of this tree Monte-Carlo runs are

started.

Ingo.

OK, thanks. I wouldn't have thought that was a significant-enough change to be worth giving its own acronym. It's like thinking that a squeegee on the end of a stick is significantly different from a squeegee not on the end of a stick. Do the nodes that invoke MC even know that they're not top-level nodes?

Hi Phil,

> I wouldn't have thought that was a significant-enough change

> to be worth giving its own acronym.

The difference in performance is tremendous.

Try Wilson's pure MC program for normal Hex (with alternating

turns). Even a 2-year old child would be able to beat the program

after some 10-minute introduction when it (the child) gets the

first move.

And putting "tree" in the name MCTS is absolutely normal and informative.

> Do the nodes that invoke MC even know that they're not top-level nodes?

A difficult question. MCTS is a colletive name for game algorithms that both

use Monte Carlo runs and tree building. I think, in most MCTS-bots there is

made a difference between direct succersors of the root and all the other

nodes. And I know of at least one MCTS bot where almost each node in the tree

has "its own personality".

Another example:

Hanfried for instance, one of the competitors in the Computer Olympiad for Ewn,

is doing iterative deepening with minimax, running something between 10 and 100

random games for each leaf (the detailed number will not be given before the

Tilburg Olympiad has taken place).

Cheers, Ingo.

Is the difference that MC collects statistics only for the immediate (1-ply) children of the root while MCTS in contrast collects statistics for all nodes of a growing tree of descendents of the root, a tree whose direction of growth is determined by those statistics?

In the "tree" of game states that may follow the root state, how important is it to recognize transpositions? I.e. most games have a lattice, not strictly a tree, of states that can follow a given state.

Slither would introduce quandaries into an AMAF plan since by the time a random game is won, a cell may have had several transitions among Empty, Black and White. If ACMAF examines only the final position, then those transitions become moot.

Or does AMAF also look only at the final position, rather than the series of moves that lead to it?

> Is the difference that MC collects statistics only for the immediate (1-ply)

> children of the root while MCTS in contrast collects statistics for all nodes

> of a growing tree of descendents of the root, a tree whose direction of growth

> is determined by those statistics?

Yes.

> In the "tree" of game states that may follow the root state, how important

> is it to recognize transpositions?

Important. Problem not well solved so far.

> Slither would introduce quandaries into an AMAF plan since by the time

> a random game is won, a cell may have had several transitions among Empty,

> Black and White.

Hmm, Slither seems to be complicated.

What do AMAF and ACMAF stand for?

AMAF = All moves as first, and ACMAF = All critical moves as first.