[Suggestion] Visualize the counting process like on a real board

Feedback Suggestions
1

I just wanted to put it out there, I think it would be a fantastic learning tool if there was an option for OGS to move the stones around for counting at the end of a game, the same as is done on a real Go board.

The purpose being to simulate the traditional counting method, as a cultural artifact, as a learning aid, and because it looks cool. I think it would be a great resource to see how counting actually works and make it easier for people to transition to in-person Go boards.

Accurately capturing the traditional method in an algorithm is tricky, since it’s a matter of style. Personally I feel that Japanese-style counting would be most clear, but I’m not a programmer!

12 Likes
2

You want an AI to move the stones around to make rectangle zones?

That’s actually a pretty cool idea. But probably a project outside the scope of OGS.

If someone successfully makes such an AI and it is open-source, then it will time to suggest to incorporate the feature on OGS :slight_smile:

3 Likes
3

I don’t think it is an “AI”, just an algorithm for going around the board picking up stones, putting them down, and making areas in each surrounded territory. I do not enjoy programming in my free time, but people in discord seemed to like the idea so I just wanted to put it out there.

4 Likes
4

AI or not, a proof of concept would be a good idea. (As someone who does enjoy programming, I’m still not really sure how would be a good way to implement this)

1 Like
5

From my limited knowledge, I would say something like:

  • Pick up all the dead stones
  • Divide each distinct group that surrounds territory
  • Set it up as a constrained optimization problem to create separate zones that are as square/rectangular as possible

I am not sure how the movement of stones would work, that seems like the hard part to program. Maybe the first step is a problem to draw lines where the minimum territorial borders are, and then the next step is to move stones around.

2 Likes
6

This sounds complicated, but like a really neat programming problem. I’m super interested to see a proposed solution.

It’s certainly far out of the scope of my abilities - if I can’t do it with for loops and nested if statements, I won’t bother even trying :joy:

3 Likes
7

The “AI” might simply solve an optimisation problem, as follows.

Step 0. Start with a go position after both players have passed. Remove the dead stones.

Step 1. Mark every intersection of the board with one of the following five labels:
White stone, Black stone, White territory, Black territory, or Dame.
If using Japanese rules, if there is a seki on the board, then all intersections involved in the seki must be marked as Dame as well, including the stones and eyes.

Step 2. A “solution” of the optimisation problems consists in changing the labels of any number of intersections, with the following rules:

  • A black stone or territory cannot become a white stone or territory, nor vice versa;
  • The number of black stones that become black territories plus the number of stones captured by white must be equal to the number of black territories that become black stones;
  • The number of white stones that become white territories plus the number of stones captured by black must be equal to the number of white territories that become white stones;

These rules guarantee that the score of the game is unaffected.

Then, the optimal solution is the solution that

  • maximises the “rectangularness” of the territories, while at the same time
  • minimises the number of changed labels.
3 Likes
8

Sounds like a very good exercise in constrained optimization! Those rules are a very nice step to understanding and phrasing the problem.

1 Like
9

Doesn’t seem easy. You may need to split a territory into several rectangles, among other problems.

ScreenShot_08_08_2022_19_47_27

3 Likes
10

Minimising the number of changed labels is easy to formulate. Maximising the rectangularness is the harder part.

Idea 1
“Maximising the rectangularness” might be reworded as “minimising the perimeter”. Now we just need to find a good definition for perimeter of a territory.

We can define “perimeter” as follows:

  • Every intersection contributes between 0 and 4 to the perimeter of a territory.
  • An intersection which does not belong to a territory contributes 0 to the perimeter of that territory.
  • An intersection which belongs to a territory contributes 1 for each adjacent intersection which does not belong to that territory.
  • An intersection which belongs to a territory also contributes 1 for each adjacent side of the board.

Idea 2
A territory is a rectangle if and only if it is convex. So we can add penalties for every concavity in a territory. A concavity is an intersection which is not in the territory, but is adjacent to at least two intersections which are in the same territory.

2 Likes
11

Not sure if this is worth noting, but there’s another “axis” on which go players tend to maximize during the scoring phase: “round numbers/multiples of 10s/5s” that’s why you see stuff like:

OOOOOO
O----O
O-OO-O
O----O
OOOOOO
5 Likes