Re: [gnugo-devel] Re: Ranked Robot (fwd)

[Gunnar Farnebäck]

Arend wrote:
> I got this question from Bill Shubert. Ideas anyone?
> 
> Lately some clown on KGS has been playing as black, komi -0.5, against
> the gnugo robots, playing tengen as first move followed by mirror go.
> Obviously he wins all his games by 0.5 points. What would be your
> thought on teaching gnugo how to defeat a mirror go game? :-) I think
> the hard part would be noticing mirror go - once it is spotted, a simple
> pattern to force the player to break mirror go (or else lose) would do
> the trick.

Detecting mirror go is hardly difficult, just test whether mirrored
vertices are either both empty or contain one stone of each color. As
for how to counter the strategy, I think it's useful to split between
a couple of cases.

1. Vertical, horizontal, or diagonal mirroring.

Don't bother. There are so many moves which automatically break
symmetry that one will be played reasonably early. In the following
mirroring will always refer to mirroring in tengen, or equivalently by
rotation 180 degrees. 

2. GNU Go plays black, white mirrors

Play tengen within some 10 to 20 moves.

3. GNU Go plays white, black starts at tengen and mirrors, komi > 0.

Don't bother. The longer the mirroring goes on, the more black will
lose of the first move advantage.

4. GNU Go plays white, black starts at tengen and mirrors, komi < 0.

Start a sequence to capture tengen within 10 to 20 moves.


As for implementation, 2 probably needs special casing in genmove.c,
but it shouldn't have to be harder than something like this
(untested):

tengen = POS((board_size - 1) / 2, (board_size - 1) / 2);
if (board_size % 2 == 1
    && board[tengen] == EMPTY
    && color == BLACK
    && stones_on_board(BLACK | WHITE) > 10
    && test_symmetry_after_move(tengen, color))
  set_minimum_move_value(tengen, 50.0);

Implementing 4 shouldn't be difficult either, at least if the board is
reasonably large. Add patterns for the capturing of tengen sequence,
e.g.,

.......  .......  .......  .......  .......  .......
.......  .......  .......  .......  ...*...  ..*O...
.......  ...X...  ..XX...  ..XX*..  ..XXO..  ..XXO..
...X...  ...X...  ...X*..  ..XXO..  ..XXO..  ..XXO..
...*...  ...O*..  ...OO..  ...OO..  ..XOO..  ..XOO..
.......  .......  .......  .......  .......  ...X...
.......  .......  .......  .......  .......  .......

and so on, and make them contingent on a helper which tests that

* The board size is odd.
* A white move is being generated and the komi is less than zero.
* The middle X stone in the pattern is really placed at tengen.
* At least some 10 or so moves have been played.
* The board has a mirror symmetric configuration.

One weakness of this scheme is that it requires an empty 7x7 square
around tengen. It can be slightly improved by reducing the pattern to
5x5 and add constraints to check that the sequence works.

If somebody wants to implement this, feel free. Notice that GNU Go can
be used for testing, with the --mirror option.


What does this not cover?

* Mirror play on even size boards. A "capture something near the
  middle of the board" scheme should work, but the first move must be
  special cased since the pattern matcher can't handle empty patterns.
  Actually I think the special case code earlier is fine if just the
  odd size board test is removed. New capturing patterns would still
  be needed though.
  
* Quasi-mirror play with symmetrically placed handicap stones
  including tengen. This can usually be defeated by capturing tengen
  but also by capturing handicap stones. However, if the handicap
  stones are placed freely with a ponnuki around tengen, more care is
  needed.

* Case 4 above on boards small enough that after 10 moves (remember
  that we control where they are placed) it is unlikely to be an empty
  7x7 or 5x5 square around tengen.

* Quasi-mirror play where black does not play the first move on tengen
  but e.g. on an adjacent vertex, in order to defeat anti-mirroring
  strategies.


What other plausible anti-mirror strategies are there?

* Setting up colliding ladders. This would be really cool if we could
  implement but maybe we should start with something simpler. :-)

* Playing along the edge (first and second row) until the opponent has
  been captured. This has the advantage that those lines are seldom
  occupied early but the drawback that the opponent probably will come
  out better by breaking symmetry when we start playing on the edge.

* If the game is played with superko, multiple kos can be set up and
  the opponent forced to break symmetry or violate the superko rule.

/Gunnar