AI to solve life and death problems

I was wondering how Leela Zero or similar AI engines could help with life and death problems.

I haven’t tried yet, but basically to get the AI’s best move I would fill the rest of the board with a position where the only way to win is to kill (or survive).

Does this make sense? And is there a better way than pretending to play a full game?

2 Likes

Well, there’s GoTools, which is freely available now. I tried small problems on a 9x9 grid and it’s complex to use, restrictive and from my pov, kinda slow. Maybe I’m doing something wrong, but yah.

3 Likes

I believe most traditional tools rely on ‘fencing off’ the problem and doing a slightly smart brute force method (in the end brute force will be necessary to prove a problem has been solved, n.b. this is important regarding neural approaches, see below). This confines the solvers to small problems (small in the sense of board space), so it can’t solve complex problems that require a lot of space.

I’m not sure if a Leela Zero approach would work, since neural networks basically play with ‘intuition’ instead of certainty. They instinctively know which move is the best, but a smart tsumego problem could be very counter intuitive even for a program like Leela (for example because it’s a situation that you would never encounter in a real game). Actually I bet that whichever (current) network you use, there is a problem it will fail on. They are smart because they know where to play without finishing a whole search tree (and hence fast), not because they are certain their move is the best (hence the ladder failures).

There are situations where mathematics (game theory) can solve a very complex situation that usually cannot be solved with go intuition. Even most professional players probably fail at these mathematical endgame problems. Note however that the author of these problems was convinced that computer victory over humans would be totally impossible in the near future (he was wrong). I’m actually quite curious how well Leela would fare against these problems. My bet is that she will fail just like the rest of the professionals.


To elaborate a little on why a perfect tsumego solver is a lot harder than a program that plays go well: winning from humans is an enormously difficult task in go because of the huge search space of a go game. That’s why we need artificial intelligence to fill in the lack of computational power. The computer ‘instinctively’ knows where to play from its training, and that’s why it plays so well. However, for a tsumego solver, we need to prove that a certain set of moves is a perfect solution. The only way to prove this is by using brute force (playing out all of the possible variations) or by using logical reasoning. The first means that we would go back exactly to the original problem of playing go against humans: the number of possible moves is simply to big to explore. The second means we need an AI that is capable of constructing proofs or reasoning logically / semantically. This is something that has not been tackled yet (even sligtly), and is closer to the development of artificial general intelligence (an AI that outperforms humans on any task).

In essence neural networks, like AlphaGo and Leela, are very dependant on computational power. They need a large set of training data and a lot of computation to develop their networks. This is one of the reasons why these programs only recently have been developed: deep neural networks existed in the 90’s already, but the computational power was too low to ever be of any practical use.

Since tsumego in the end will need a way to prove that the solution is right, we need either a brute-force algorithm (slow on large problems) or a reasoning algorithm (which would be a break through even larger than the AlphaGo one).

4 Likes

Thanks for the useful replies. I didn’t know dedicated problem solving programs were available.

Maybe I’ll still give Leela Zero a try. I hear what you’re saying @Vsotvep, but at the same time the tree for a tsumego is so much smaller than a full game that I would expect AI to do an exhaustive exploration - my noob view on things AI related.

2 Likes

There is a try on modifying recent go AI for promblem solving: https://github.com/geovens/AQ-PS
But it’s not good, only useful to a 15kyu or something.

3 Likes