How to solve life&death or tsumego problems by BadukAI?

[HackYardo]

I can solve those problems by shrinking the size of chessboard through Sabaki on my laptop. But how to solve those problems on my Android phone?

[aki65]

You can already restrict the search to a rectangle, but only for the next move not for continuations. So there is no good way to solve tsumego at the moment. But I will add the continuation restriction in version 0.19. Furthermore I will add KataGo's parameter to widen the search which might be useful if the tsumego solution is a very "unusual" move and therefore has a low policy value.
According to my experiments these two additions should provide very good tsumego results except for ko situations (Due to the "shrinking" of the board KataGo will "see" only local threats. So if there aren't any, he might regard a move, which wins by taking a ko first, as equally good as a move, which wins unconditionally).

[HackYardo]

@aki65
Surviving by elsewhere's ko? I remember Schrödinger's Cat, it is both alive and dead. Maybe we can use a mirror or a clone, however, the results are not good:

Here are some web pages about solving tsumego:
https://github.com/d180cf/tsumego.js
https://github.com/cameron-martin/tsumego-solver
lightvector/KataGo#261

[aki65]

Nice problem to test with. I still remember when I saw it first about two years ago: took me ages to figure it out ...

The good news is that it's really "only" the ko issue: I altered the position slightly (without mirror) adding a white stone at Q4 and a black stone at L4. Then white is still normally solid on the outside, but black has a local ko threat at M4. In this position the current development version of BadukAI (with the two additions from my last post) finds the correct solution.

Regarding the ko I have an idea but it's not tested yet ...

[aki65]

I added some features for this in version 0.19. Please refer to https://www.lifein19x19.com/viewtopic.php?p=261999#p261999 for an explanation how to use them. For your sample problem I had to use all the "tips" mentioned there (balancing the position, solidifying the outside, adding ko threat) and arrived at the position attached. KG still needs a few thousand playouts to find T2, but it finally does.
tuned_problem.sgf.txt

[HackYardo]

I set noise=0.03, insidemoves=30, outsidemoves=A17, A18, and run over 900k visits, but the moves after T2 are not good, and the black doesn't choose S1.
Maybe the answer of this question, T2 S3 S1 T1 A17 A18 S1 T3 P1, is not correct? In China, 1400 players dislike the answer and 800 players like it.
https://www.101weiqi.com/q/3063/

[aki65]

In my opinion the answer T2 S3 S1 T1 A17 A18 S1 T3 P1 is correct.

Solving with BadukAI does not work as expected here because of the choice of the rectangle. It is my fault, I should have told more about how to choose it. So I add this here: The rectangle has to include all relevant points for the problem, that is not only the correct solution, but also all refutations of deviations from the correct line. Otherwise KataGo may regard a wrong sequence as successful just because its refutation can't be played.

In this position this means:
a) B may start with P1 which is wrong, but W must be allowed to play O1 to kill. So O1 must be included.
b) B may start with S3 which is a little more tricky, but can still be refuted by W playing T1. But afterwards B can play T3 threatening to capture with T2. W can prevent this by playing S4 ... but only if he is allowed to. So S4 must be included.
c) If S4 is included, B may take it too (after S3 T1) aiming at T3 and T2 to capture in the corner. To stop this, W has to take a liberty at some point with S5. So the rectangle must include the 5th line.
So we arrive at a rectangle from O5 (inclusive) to the corner. And that's it. Anything even further away clearly doesn't play any role. This is the rectangle I used and it worked.

Of course, normally you solve a problem whose solution you don't know, so you don't know such details. But you also don't need to. In my experience you are always on the safe side by following these two rules of thumb:

1. If one side is completely enclosed, make the rectangle include all the inside
2. Otherwise (such as here where we have a "backdoor") include one line "leeway" around the problem.

If you can reduce this "maximal" rectangle safely by general go logic, do so (it saves playouts).

[HackYardo]

It finally does!


But how to let KataGo know the number of inside moves and the rectangle of O5 to corner? How to solve problems automatically?

To my surprise, so many people around the world were focusing on how to solve Go problems by AI since 2016. I need some time to get out of the mess. Here are several webpages:
http://www.xuanxuango.com/solver.htm
search in appstore: katago
https://sahwal.com/
https://github.com/geovens/AQ-PS
https://pandanet-igs.com/communities/pandanet/445
https://blog.janestreet.com/deep-learning-the-hardest-go-problem-in-the-world/

At last, could BadukAI add GTP CLI?The sahwal solves ko-tsumego problems by changing the ko-rule, if we have CLI, we could change rule too.

[HackYardo]

It's my fault to change KoRule like the sahwal. It can not be realized just because KataGo doesn't support recapture of a single stone.
https://lightvector.github.io/KataGo/rules.html

And although there are many webpages about solving tsumego by AI, they all can't solve all tsumego at my first glance. I need some time to try out a new idea.

[HackYardo]

A bit hard rock and long time no good idea, so I close it.