It is currently Tue Aug 16, 2022 5:45 am

 All times are UTC - 8 hours [ DST ]

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Refutation graph #1 Posted: Fri Oct 15, 2021 5:53 pm
 Lives in gote

Posts: 403
Liked others: 54
Was liked: 261
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
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?
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?

"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.

`[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.

_________________
Give me triangles strong enough and I can measure the universe.

When Venus transits, we can align our clocks to one event. By measuring the angle to flat Earth at two places far apart on Earth, we can compute the distance to Venus and the Sun.

Top

 Post subject: Re: Refutation graph #2 Posted: Fri Oct 15, 2021 11:12 pm
 Gosei

Posts: 1579
Liked others: 141
Was liked: 439
Do you have an example with a cluster, i.e. a problem with two moves x and y such that xRy and yRx?

Top

 Post subject: Re: Refutation graph #3 Posted: Sat Oct 16, 2021 12:48 am
 Lives in gote

Posts: 442
Liked others: 18
Was liked: 59
Rank: panda 5 dan
IGS: kvasir
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.

Top

 Post subject: Re: Refutation graph #4 Posted: Sat Oct 16, 2021 5:38 am
 Lives in gote

Posts: 403
Liked others: 54
Was liked: 261
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
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

`[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

`[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.

`[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]`

_________________
Give me triangles strong enough and I can measure the universe.

When Venus transits, we can align our clocks to one event. By measuring the angle to flat Earth at two places far apart on Earth, we can compute the distance to Venus and the Sun.

Top

 Post subject: Re: Refutation graph #5 Posted: Sat Oct 16, 2021 1:35 pm
 Gosei

Posts: 1579
Liked others: 141
Was liked: 439
I probably misunderstood something (edit: I did misunderstand completely). Here is problem and its refutation graph (edit: the graph is wrong). Black to live.

`[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?

Attachment:

Capture.JPG [ 13.49 KiB | Viewed 1347 times ]

Last edited by jlt on Sun Oct 17, 2021 12:09 am, edited 1 time in total.
Top

 Post subject: Re: Refutation graph #6 Posted: Sat Oct 16, 2021 7:16 pm
 Lives in gote

Posts: 403
Liked others: 54
Was liked: 261
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
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.

_________________
Give me triangles strong enough and I can measure the universe.

When Venus transits, we can align our clocks to one event. By measuring the angle to flat Earth at two places far apart on Earth, we can compute the distance to Venus and the Sun.

Top

 Post subject: Re: Refutation graph #7 Posted: Sun Oct 17, 2021 12:19 am
 Gosei

Posts: 1579
Liked others: 141
Was liked: 439
OK I was completely wrong, so here is the graph

Attachment:

Capture.JPG [ 19.86 KiB | Viewed 1296 times ]

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

Top

 Post subject: Re: Refutation graph #8 Posted: Sun Oct 17, 2021 5:28 am
 Lives in gote

Posts: 403
Liked others: 54
Was liked: 261
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
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.

_________________
Give me triangles strong enough and I can measure the universe.

When Venus transits, we can align our clocks to one event. By measuring the angle to flat Earth at two places far apart on Earth, we can compute the distance to Venus and the Sun.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 8 posts ]

 All times are UTC - 8 hours [ DST ]

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Life In 19x19.com General Topics    Introductions and Guidelines    Off Topic    Announcements    General Go Chat    Beginners    Amateurs    Professionals       Lee Sedol vs Gu Li    Go Rules    Forum/Site Suggestions and Bugs    Creative writing    Tournaments       Ride share to tournaments Improve Your Game    Game Analysis    Study Group    Teachers/Club Leaders       Teacher advertisements    Study Journals L19²GO (Malkovich)    1-on-1 Malkovich games    Big Brother Malkovich games    Rengo Games    Other versions of turn-based games Go Gear    Go Books    Go Book Reviews    Computer Go    Gobans and other equipment    Trading Post    New Products/Upgrades/Sales Go Club Forums    Go Club Discussions       Honinbo Go League    American Go Association Forum       Go Congress 2011 volunteers       AGA volunteers ( non-congress)    Australian Go Association    European Go Federation Forum    Singapore Weiqi Association    KGS    ASR League    IGS    OGS    Tygem    WBaduk    Turn Based Servers    Insei League Events    Kaya.gs       King of the Hill