Getting potential points in Tsumegos, for MCTS

[Fry_hunter]

Hi guys,

First of all, sorry for possible mistakes with my english. It's not my native language.

I'm doing an AI for playing basic Tsumegos, with Monte Carlo Tree Search algorithm. Right now, I've implemented it with light playouts. It's my bachelor final project. If I have time I'll implement with heavy playouts . My question is about getting potential points of a Tsumego. Right now, I take all the empty points inside and surrounding the Tsumego as potential points to evaluate. As you can imagine, Monte Carlo takes a long time to make all required simulations, in some cases.

It would be nice to get the truly potential points, to get a better performance. However I don't know how to get this points. Some kind of heuristic maybe? Any kind of help will be appreciated.

Best regards.

[xed_over]

Tsumego don't really have points, per se. Not without taking the rest of the board into context.

And maximizing the points is usually not the goal. In fact, living with 2 points in sente might be worth more than living with 3 or 4 points (or more) in gote -- again, depending on the whole board context.

The game of Go is about offering a trade, and which player can better judge the value of that trade. Tsumego is just a small half of that equation. Often in a game, its not about being able to kill or live, but it might be more about the threat to do so, and the potential compensation for one result or the other.

[HermanHiddema]

@xed_over: Fry_hunter is talking about intersections to consider, not points scored.

[xed_over]

@xed_over: Fry_hunter is talking about intersections to consider, not points scored.

ah, that makes more sense then.

[Mike Novack]

While your algorithm might have to consider all of the points (intersections) you might try the heuristic of giving the points suggested by the "proverbs" (if any) a head start in the tree. You'd have to play around with how much of a head start that should be to optimize performance for a given amount of time.

a) There is murder in the hane.
b) Play at the center of symmetry (if there is one)
c) In the corner, magic happens at the 1-2 points. Also in the corner consider the 2-2 point.

Note that you will need "detectors" for "ko" (and especially "double ko") and "seki". Also probably some definition of "got out" though in a real game situation that would depend on what was already out there whether a true escape.

[leichtloeslich]

Hm, I read the post as asking for common "vital points" in tsumegos.

I guess there are a couple of standard techniques that any strong player just knows, like white 1 in response to the triangled stones:

$$W
$$ . . . . . . .
$$ . O O O O , .
$$ . X X X O . .
$$ . . . . Y O .
$$ . . 1 . Y . .
$$ -------------

Click Here To Show Diagram Code

[go]$$W
$$ . . . . . . .
$$ . O O O O , .
$$ . X X X O . .
$$ . . . . Y O .
$$ . . 1 . Y . .
$$ -------------[/go]

This is basically a forcing move that white has to answer if he doesn't want to lose the triangled stones, so the breadth of the variations is very managable. There are a couple of these inside peeps, placements etc. that would be considered "vital points" in tsumegos, but I'm not sure how awesome hardcoding these kinds of shapes will perform in MCTS.


In general, one can already use existing MCTS bots to solve tsumego, and I have to say, I am not impressed. While the strength of pachi on 9x9 on my hardware surely is >KGS 4d, it fails at simple SDK/low dan tsumegos:

$$B
$$ +-------------------+
$$ | . . . . X . . O O |
$$ | . . . O . O . . O |
$$ | . X X O O X O O O |
$$ | . X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X . X . X |
$$ +-------------------+

Click Here To Show Diagram Code

[go]$$B
$$ +-------------------+
$$ | . . . . X . . O O |
$$ | . . . O . O . . O |
$$ | . X X O O X O O O |
$$ | . X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X X X X X |
$$ | X X X X X . X . X |
$$ +-------------------+[/go]

Black to play, chinese rules, white gets 80 komi (it's a 9x9 board).

So obviously the bot needs to kill white here. And it resigns instead.
When I play the first move for black and let it play white it resigns two moves later (after I kill it). This makes me wonder how well MCTS is suited to solve tsumegos. But maybe pachi can be tweaked somehow to perform better at these kinds of problems, I don't know.


Also, Mike makes a good point about ko and double ko detection. MCTS algorithms can go a bit ballistic when encountering these. And double ko can be double ko death or double ko life, and some kos are completely irrelevant for the life of a group, so it seems slightly nontrivial.

As for escaping into the center: maybe you could create immortal groups on the outside that the inside group can connect to. Then you only have to worry about detecting "connections" between groups (which sounds easier to do than the vaguely defined term "getting out").

[Fry_hunter]

Thas was truly helpful. Thanks to all for the answers!