Calculate the score of the game "GO"

Question

Does anyone know how to calculate the score in the game of Go programmatically? I have an array of 19x19 and each element of this array can be 0 (empty point), 1 (black stone) or 2 (white stone). I don't understand how can I check the region to belong to any color.

Answer 1

This is a non-trivial question because usually a Go game ends before players make all of the moves necessary to make it obvious what the "true" score/value of the game is. And sometimes it's possible that the value of the game will be different assuming that one player played suboptimally (e.g. letting opponent finish establishing a set of stones that has life in opponent's territory, even though it's provably possible to kill the set of stones). Counting raw un-intruded territory is fairly obvious, just check whether each space is "cut off" in each possible combination of directions (positive and negative horizontal and vertical) by either the edges of the board or pieces of one color. You can do this more efficiently by starting a breadth first search starting at an empty spot, and keep track of which colors are encountered in the process (not traversing BFS from an occupied spot), and once no more empty spots can be found then if the colored pieces found are all one color, then all the empty spaces found belong to that color, otherwise they don't belong to anyone. Then continue the breadth first search with the next unexplored empty spot, removing all previously explored empty spots. However, if the opponent has one piece in established territory, that piece should ideally be ignored in calculating territory, and in fact even be considered captured. The situation is the same if it is obvious that a group of opponent's pieces in a player's territory will "eventually" be captured if they play it out without making mistakes. The situation is even more delicate if the two players get into a situation where they each have a group of pieces adjacent to the other's pieces, such that the pieces have "mutual life", i.e. if one player tries to make a move in an effort to kill the other's pieces then the opponent will be able to kill the original player's pieces, and vice versa.