Analyzing the game state using high dimensional lattice walk

[Counting_Zenist]

I want to create heatmaps of sort that indicating which intersections where a cut happened during a game (a transition happen assuming if all the moves survived to the end game, they will have to be connected to a live group), where atari happened (transition happened, but has the potential of one side ended with moves that don’t survive to the end game), where actual capturing happened (where definitely one side has stone(s) not survive to the end game), and where ko happened (also one side already has stones not survive to the end game and can lost even move). It would be nice to check if any of the stones at the end of the game will be considered dead, but only those can be scored in finished games will be easier to find dead stones not yet removed, those ended half way will be hard to judge (so maybe later, which might involve using AI engine to mark potential dead stones halfway). And this would be of quite helpful with some statically data, as an approximation in some theoretically analysis framework (like we can already infer possible legal positions out of total possible positions with a random placement and get a rough ratio, which end up not far from the actual calculation).

There has been visualization of this sort in chess (captured happened and check mate, move to and move from), but it would be very useful in analyzing Go in mid-game I presume. (there are some Go GUI like Sabaki has some functions but cannot be counted or aggregated into heatmaps like or with data points that can be used later, and they often misjudge some moves, like if already a stone on the side of own color, it would call it an extend, not a cut, even if it does cut, and even call a throw in into a tiger’s move a cut, etc). We should be able to categorize them like a transition happened = a cut, or one of the two getting cut in atari, or getting cut stones being captured byt this transition, which will be either a normal capture, or a ko. Did I miss any other possible terminologies?

[Counting_Zenist]

Several basic foundations I want to mention here in order to better understand why detecting transitions is important. The first one is the work by John Tromp, he basically calculated the total number of possible legal moves by using Combinatorics. The basic idea is pretty simple, reduce the Go positions into partial positions on a partial board, and analyze the combinations of the next stone added will create what kind of groups of different Go positions. Each move will be a branch from one position to another, and can be legal or illegal on a board, the beauty is that we don’t have to know what they finally look like, but just to know that for any legal position a stone on a board has to connect to an empty liberty for it to be still alive. And then by dynamic programming trick and combinatorics we can count the groups that are the same or not the same, and how each of them transition to another.

The other work is “high dimension lattice walk”, or more commonly known as “lattice path problem”. There are some theorems which are helpful if we treat each go position like a lattice on a super high N x M dimensions (for 19x19 it would be 361 dimensions, 9x9, 81 dimensions), where each game will be <p1, p2, …, pk> where each element either being <-1, 0, 1> for <white, empty, black>. And every move played is a travelling step like playing a black stone is walking to the next neighboring lattice, with a step like <…, 0, 1, 0, …>, or <…, 0, -1, 0, …> for white. But sometimes when capturing happened, the step will be < …, 1, 1, 1, 1 (a bounch of captured stone), …, 0, 1 (the stone capturing them), 0, …>, since remove the captured stones, will be changing the -1 to 0 (add 1), or 1 to 0 (add -1). Hence any move, if we don’t allow suicide, will be a step with all the element of its “color” (allowing suicide will have the effect of clearing the player own color, which will be an inverse, effectively playing the other players, but we can leave that later for asymmetric turns where one side can play with the others “color” on its own turn). But regardless, the combinatorics of high dimension lattice and lattice walk with steps will be a perfect analyze tool for the game of Go (and as shown by calculating the legal positions)

This will be extremely useful if we start with some very simple Go rule, like pure stone scoring will be a very simple sum(S) operation = sum(P), summation of all the steps will be equal to the final go position, and no tricky definition of territory or stone dead or alive to be considered. And a truly “finished scoring positions” will be those with completely fill out board except eye space and seki points, which is the most ancient Go rule we know of (兩溢 play to full essentially), and almost identical to using group-tax rule. Which only slightly change the game, but much easier in combinatorics analysis. All the trick used to calculated legal moves can be used to check if there are two eyes or seki (maybe first calculating the number of all groups have 2 eyes and their distribution of sum() to get a rough idea, I suspect all positions with seki will be much smaller in portion compared to all living with 2 eyes, just a hypothesis). And in order to apply it, we need to know the “cut” or the moment where transition from a one to one group, to potentially more than 2 (can be 4, or revert to 2, or all get killed and become one). This might help settle and get an analytical answer (or statistical answer using probabilistic combinatorics or simulations) about what are the group sizes and “scores” if just using stone scoring, what are their distributions and why might be the case that near 7 is the magic number for komi (I highly suspected has a lot to do with how groups are split and the first one to play has the extra “transition” right which is always the same regardless of the board size reflecting into the final scoring board combinations)