Computer go programming: Encyclopedia II - Computer go programming - State representation

Computer go programming - State representation

A problem that all Go programs must solve is how to represent the current state of the game. For programs that use extensive searching techniques, this representation needs to be copied and modified for each new hypothetical move considered. This need places the additional constraint that the representation should either be small enough to be copied quickly or flexible enough that a move can be made and undone easily.

The most direct way of representing a board is as a 1 or 2-dimensional array, where each space in the array represents a point on the board, and can take on a value corresponding to a white stone, a black stone, or an empty space. Additional data is needed to store how many stones have been captured, whose turn it is, and which spaces are illegal due to the Ko rule.

Most programs, however, use more than just the raw board information to evaluate positions. Data such as which stones are connected in strings, which strings are associated with each other, which groups of stones are in risk of capture and which groups of stones are effectively dead is necessary to make an accurate evaluation of the position. While this information can be extracted from just the stone positions, much of it can be computed more quickly if it is updated in an incremental, per-move basis. This incremental updating requires more information to be stored as the state of the board, which in turn can make copying the board take longer. This kind of trade-off is very indicative or the problems involved in making fast computer Go programs.

Adapted from the Wikipedia article "State representation", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki