I have been thinking about various mathsy topics in tsumego problems.

One was the refutation graph. Given a tsumego problem, draw a graph.

Let the vertices be possible valid first two moves in the problem.

Draw a directed edge from A to B if A as a first move is refuted by B on the second move.

Consider the relation "y follows x" xRy with x,y vertices if y can be reached from x by following these directed edges. This is transitive but not symmetric or reflexive.
Turn this into an equivalence relation by saying x =(R) y if and only if
1) xRy and yRx
or
2) x=y

Then consider the equivalence classes.

There are three types
1) Single nodes {x} where xRx is false, and x is not the right first move, so xRy is true for some y.
2) Single nodes {x} with zero outdegree so xRy is false for all y. This is because x is a correct first move (with no refutation).
3) Clusters with more than one node.

Does anyone think this is interesting/useful?
Has anyone thought about this?
For example
- How does the structure of such graphs depend on the board graph (does 2D cartesian make it special)?
- How does the structure of such graphs relate to good shapes, reading, and strategy?
- What structures are possible?

To add context, I was thinking about this in relation to a discussion between John F and Bill S about strategic ideas such as
"If A is your opponent's good move, try playing there yourself."
"If you cannot win in two moves after your opponent plays A, then to have a chance of killing, you must play A first." This actually requires that A doesn't capture any stones for the commutativity proof to work.

Click Here To Show Diagram Code

[go]$$ Black to play
$$ --------------
$$ | a b c d . . . . .
$$ | e f g h . . . . .
$$ | i j X O O . O O .
$$ | k l X . . . . . .
$$ | m X O . O . . . .
$$ | . O O . O . . . .
$$ | . O . . . . . . .
$$ | . . . . . . . . .[/go]

As an example, this is a classic problem that is very tricky for its size.

f is the unique correct first move, though I think m is ko.

The refutations I could find were
a->f
b->h
c->h
d->h
e->h
g->l
g->m
h->f
i->m
i->f
i->d
j->d
k->f
k->d
l->f
l->d
l->h
m->f

there are plenty more pairs that I haven't mentioned for all the bad moves. It looks like there aren't any clusters, in which case the equivalence relation above is useless. But the graph may still be useful for something.

Instead the key lesson seems to be that g is a bad move for both sides due to missing the key points all around it. It seems that the defender shouldn't play too solidly as that fills in their own eyespace, while the attacker shouldn't leave overconcentrated cutting points as they can be exploited.
d,h,m seem to be key refutation points, on a similar level.

Of course the asymmetry of putting black's moves on the left and white's moves on the right is quite clear. In this shape, stones can get captured, so a good move for one side is not necessarily a good move for the other side.

Do you have an example with a cluster, i.e. a problem with two moves x and y such that xRy and yRx?

I see the following problems:

1. It is very tedious to construct a refutation graph.

2. It would seem that the refutation graph would have many redundant paths.

3. Not including the correct move (the move that can't be refuted) may lead to graphs that are not unique. That is a move may not be in the graph both because it is can't refute or is not a refutation, and simply because it is not a legal move.


I do see a potential use, that would probably need some addressing of the mentioned problems to actually be useful, but maybe it is possible to define similarity measure on graph that is similar to this refutation graph construct and this could then be used to characterizer problems.

Thanks for the feedback.

I think a refutation graph might not be directly useful, but thinking in the most general terms is sometimes helpful, even when dealing with special cases.
I would still be interested to know what the largest possible size of a cluster is though (2 is certainly possible with miai refutations), I have even managed to construct an example with a cluster of 3.

A simpler problem is

Click Here To Show Diagram Code

[go]$$ Black to play
$$ --------------
$$ | . . . . .
$$ | a X O X .
$$ | X O X X .
$$ | b O O X .
$$ | c d e O .
$$ | f X g O .
$$ | . O O . .
$$ | . . . . .[/go]

Hint: This position reverts to the monkey jump! (not completely as 2nd line connects are a bit different but almost)

Compare

Click Here To Show Diagram Code

[go]$$ Black to play
$$ --------------
$$ | . . . . .
$$ | . X X X .
$$ | a - O . .
$$ | b e O . .
$$ | c d . O .
$$ | f X g O .
$$ | . O O . .
$$ | . . . . .[/go]

The correct move is A in both cases. This is because otherwise White can play A or B in sente which is powerful with more follow ups working with the 3-2 cutting stone.

The difference between the two diagrams is that there is a three stone white group separating b and e. It's only other liberty is at d. In addition, in the problem, d is left with only c and e as liberties, but if W plays d, then the stone at d gains the liberty at b (of the three stones, so it still has 3 liberties as in this diagram). And e is adjacent to g.

However, the key point is that after a, b and e are still miai and so are c and d. Most of the main variations are exactly the same, letter by letter.

Other:
- In the monkey jump diagram, the move at e is a viable way to connect and probably best if Black is komaster. However in the problem, in some ways this works better since playing E threatens to capture more stones (so rather ko, it would be unconditional kill). But overall, it is worse since after capturing e with g, the stone you were trying to rescue hasn't got enough liberties to connect.

In order to demonstrate I learnt something, I tried to create a problem where there were some white stones between c and d instead.

Click Here To Show Diagram Code

[go]$$ Black to play
$$ --------------
$$ | . O . . . .
$$ | X X . . . .
$$ | a O X . O .
$$ | b e . X . .
$$ | c O O O d O
$$ | f X X X . .
$$ | . . . . . .
$$ | . X . . . .[/go]

I probably misunderstood something (edit: I did misunderstand completely). Here is problem and its refutation graph (edit: the graph is wrong). Black to live.

Click Here To Show Diagram Code

[go]$$ Black to live
$$ | .......
$$ | .OO....
$$ | aXO....
$$ | bXOOO..
$$ | cXXXO..
$$ | defg...
$$ -------[/go]

There are three equivalence classes (edit: wrong). The equivalence classes AC and GE are clusters, but which type is the equivalence class BDF?

I tried to make the relation symmetric (like markov chains) though I'm not sure it helped.

Using the symmetric relation, B, F, D are each isolated in their own equivalence class since they are not part of a refutation cycle. There is no path from B to B for example.

Note that B, F are refuted by G and A respectively as well.

OK I was completely wrong, so here is the graph



Equivalence classes of type 1: {D}
Equivalence classes of type 2: {B}, {F}
Equivalence classes of type 3: {A,C} and {G,E}.

Yes, we are on the same page now, though I switched type 1 and type 2.

To me this says A and C are working together to make an eye and similarly G and E.

The fact that B is not connected to A or C is a classic pattern which I have been calling notches and nocks (unpublished).

This graph is simple enough that is is suggestive of ideas about "if B is played, black requires another two moves to make pass-alive either at DF, or GE" though I don't yet see a general way to make such inferences.

Perhaps another graph is required in combination such as local domination. For example F is dominated by G in the sense that white F for black G is always a bad exchange except for some quite special cases (notch theory).

Black F is mostly dominated by black G but not completely as it makes a difference to the liberties of D.