圈圈之地

ejsoon 写了： 用繁體中文翻譯以下文段：

I would like to answer some questions that came up regarding
the solution of Nine Men's Morris.

- How can a draw be reached?

A draw is reached through cyclical play, whereby neither
player can (or will) close a mill. Note that since the proof
was obtained using only the 9-9, 9-8 and 8-8 databases, neither
player need close more than one mill to reach a draw ,thereby
avoiding a loss with less than three stones.

- What is an optimal opening strategy (for humans)?

I must admit that I have not examined the opening moves
for any easily describable patterns.
However, the examination of mid- and endgame databases
has repeatedly shown optimal play to be beyond human
comprehension. Therefore, I very much doubt that any such
simple-to-describe strategy exists.

- Is a paper describing these results available?

I am now working on such a paper. I will send a copy to those
of you who have requested one as soon as it is completed.

There is however a paper describing some initial results
of the retrograde analysis phase of the project:

Gasser, R., "Applying Retrograde Analysis to Nine Men's
Morris", Heuristic Programming in Artificial
Intelligence 2: the Second Computer Olympiad, Levy, D.N.L.
and Beal, D.F. (Eds.), pp. 161-173, Ellis Horwood, London.

- Is the program available?

Making the program available is something of a problem
because of the databases it uses. In total the databases
amount to a few hundred MBytes.

There is of course a program available which plays without
any database (or with a few small db's). While this program
cannot claim to be invincible, it plays quite strongly, having
won a match against the British Champion.

This program was developed under the Smart Game Board and
therefore only runs on Macintosh computers. The program
is shareware and depending on the number of requests, I will
either make it available via ftp or snail mail.

Ralph Gasser (gasser@inf.ethz.ch)
Informatik, ETH
CH-8092 Zurich
Switzerland
Newsgroups: rec.games.abstract
From: colley@qucis.queensu.ca (Paul Colley)
Subject: Re: Nine Men's Morris: More about the draw
Organization: Computing & Information Science, Queen's University at Kingston
Date: Wed, 24 Nov 1993 15:41:54 GMT
In article <1993Nov24.103138.21488@neptune.inf.ethz.ch>
gasser@inf.ethz.ch (Ralph Gasser) writes:

>A draw is reached through cyclical play, whereby neither
>player can (or will) close a mill. Note that since the proof
>was obtained using only the 9-9, 9-8 and 8-8 databases, neither
>player need close more than one mill to reach a draw ,thereby
>avoiding a loss with less than three stones.

This appears to be a mistake. Er, let me rephrase that. "The evidence
supplied does not prove your conclusion."

In building the 9-9 and 9-8 databases, you would have used the smaller
data bases. Retrograde analysis starts from the smallest, and works
up.

Say some position in the 8-7 database is a draw. Then in the 8-8
database, a position where the player may close a mill and reduce to
the drawn 8-7 position gets marked as a draw (assuming there's no
winning move).

You don't need the 8-7 database in doing the opening search, because
you don't need to know why the particular 8-8 position is drawn. This
is NOT the same thing as

>neither player need close more than one mill to reach a draw

The fact that you didn't need the smaller databases in the opening
search just means that no player need close more than one mill *DURING
THE OPENING* to reach a draw. It doesn't mean the player doesn't need
to close a mill during the middle or end game.

The correct statement, based on the evidence you give, is "neither
player need close more than one mill, and only during the opening, to
reach a book draw." Well, now that the initial position of NMM is
solved, we could even say "neither player needs to make a move to reach
a book draw." Of course, if your opponent doesn't agree, you still
have to play out the book draw, and that (may) require the smaller
databases. Or may not require the smaller databases. I have nothing
to contradict your statement. I'm just asking for more support.

ejsoon 写了： 用繁體中文翻譯以下文段：

I would like to answer some questions that came up regarding
the solution of Nine Men's Morris.

- How can a draw be reached?

A draw is reached through cyclical play, whereby neither
player can (or will) close a mill. Note that since the proof
was obtained using only the 9-9, 9-8 and 8-8 databases, neither
player need close more than one mill to reach a draw ,thereby
avoiding a loss with less than three stones.

- What is an optimal opening strategy (for humans)?

I must admit that I have not examined the opening moves
for any easily describable patterns.
However, the examination of mid- and endgame databases
has repeatedly shown optimal play to be beyond human
comprehension. Therefore, I very much doubt that any such
simple-to-describe strategy exists.

ejsoon 写了： 用繁體中文翻譯以下英文：

For the rules of Nine Men’s Morris, see for example
Gasser’s work [6]. There are two points in the rules, for which
there is no consensus. The first question is what should happen
when two mills are closed with one move. The second is
whether a player should be allowed to take a stone from
a mill, when all the opponent’s stones are in mills. Our
implementation followed Gasser’s decisions: mill closure is
always followed by taking exactly one stone. Moreover, we
regard position repetitions as draws.
The main difference between Lasker Morris [7] and the
standard variant is that there are no distinct placement and
movement phases, i.e. the players can decide at every move
whether they want to place a stone on the board or move one
of their stones (as long as they have remaining stones to place).
The other difference is that players can place 10 stones instead
of 9.
Morabaraba differs from the standard variant in the graph
of the game board (see Fig. 3 and Fig. 4), and in the number
of stones the players can place, which is 12. There is also a
special rule: if the board becomes full (because neither player
closed a mill during the opening), the game ends in a draw.
There is no consensus about whether to use the rule or not, so
we implemented both versions. The state space of Morabaraba
is about four times bigger than that of the standard variant.

ejsoon 写了： 用繁體中文翻譯以下文段：

Two points are subject to debate among Nine Men’s Morris enthusiasts. The
first hinges on the observation that in the opening it is possible to close two
mills simultaneously. Should the player then be allowed to remove one or two
opponent’s stones? Our implementation only allows one stone to be removed.
The second point concerns positions where the player to move has just closed a
mill, but all the opponent’s stones are also in mills. May she then remove a stone
or not? In our implementation she may remove any stone. It seems unlikely that
either of these rule variations affect the value of the game.

ejsoon 写了： 用繁體中文翻譯以下文段：


After all stones have been placed, play proceeds to the midgame. Here a
player may slide one of her stones to an adjacent vacant point. If at any time
during the game a player succeeds in arranging three of her stones in a row—this
is known as closing a mill—she may remove any opponent’s stone that is not
part of a mill. In Figure 2, if White closes a mill in the opening by playing to
b6, she can now remove Black’s stone on a1, but not the one on d2.
As soon as a player has only three stones left, the endgame commences. When
it is her turn, the player with three stones may jump one of her stones to any
vacant point on the board.

ejsoon 写了： 用繁體中文翻譯以下文段：

Fig. 3: Game-theoretic values with DTWs of all possible
moves in the starting position of Morabaraba. The optimal
moves are marked with an “!”.

ejsoon 写了： 用繁體中文翻譯以下文段：

Fig. 4: A game-theoretical draw position in the standard or
Lasker variant. White to move. Although White can preserve
his material advantage, he cannot win. This is one of the only
two such positions in the subspace of 8 white and 3 black
stones. The only move here that can keep this stone count
indefinitely is marked with an arrow.

ejsoon 写了： 用繁體中文翻譯以下文段：
We strongly solved Morabaraba, which turned out to be
a win for the first player in 49 moves. We also calculated
extended strong solutions for Nine Men’s Morris, Lasker
Morris, and Morabaraba which provided some insights into
these games (and also confirmed the result of Stahlhacke [8]
that Lasker Morris is a draw).

Furthermore, we developed a multi-valued retrograde anal-
ysis. Then we modified this to have an algorithm which can
solve these games ultra-strongly. This means that the program
has a much higher chance to win a game of Nine Men’s
Morris or Lasker Morris against a fallible opponent instead
of just drawing it, compared to a program which uses only a
strong solution. This is important, because when a program is
playing Nine Men’s Morris based only on the strong solution,
it is surprisingly easy for the opponent to achieve a draw. The
algorithm classifies draws into subclasses based on a heuristic
value of the subspace that can be reached via perfect play. We
investigated two heuristics for the subspace values.
We compared our ultra-strong solution to the strong solution
by having them play against a heuristic (α-β) program, and
against human players, and found that it achieved wins more
often.