Legal Moves in Go

• Given a Go board, determine the legal moves of the next player.
• Definition: The Liberty of a connected black or white group of stones is the number of empty fields adjacent to it.
• If after the placement of a new stone the liberty of any group of stones is zero, the whole group dies.
• A move is legal, if it kills at least one enemy group.
• A move is also legal, if it doesn't kill any group.
• A move is illegal, if it kills an own group, but no enemy group.

How to solve it

• If any adjacent field of X is empty, the move was legal.
• So from now on we assume that all adjacent fields of X are occupied.
• For each adjacent white stone, determine the liberty of the group this stone belongs to. If any of these liberties is 0, the move was legal.
• If we are still not sure whether the move was legal, we determine the liberty of the group X belongs to. If it is 0, the move was illegal, otherwise legal.

How do we determine the liberty of a group?

• Depth-First Search
• Start the search on field X. Let's assume X is black.
• If any adjacent field is empty, return positive.
• If all adjacent fields are white, return zero.
• If all adjacent fields are occupied, but some (or all) of them are black, recursively search the adjacent black fields.
• If any of the recursive calls returns positive, return positive.
• If all recursive calls return zero, return zero.

Preventing an infinite loop

• Before searching the adjacent fields recursively, mark the current field as visited!
• Only search the adjacent fields that haven't been visited yet.

Preventing an Array-Index-Out-Of-Bound Error

char board[MAX_SIZE][MAX_SIZE];

char get_color (int i, int j, char default)
  if (i>=0 && i<n && j>=0 && j<0) {
    return board[i][j];
  } else {
    return default;
  }
}

• The default color is always the opponent's color.
• Example: If we are determining the liberty of a white group, we consider the board surrounded by black.

Last modified 2001-02-20