In this paper, we introduce a formal grammar for playing Go that fundaments an automated Go-player. Go-tactics such as eyes, ladders, mutual life and nets are properly modeled and tested. As well as Go-strategies to offensive or defensive purpose are introduced and their performance is tested throughout Go matches against humans or previous well-known automated Goplayers like GNUGo. Results and a comparison analysis are reported and discussed on the perspective of current state of the art on Go automation.
Originated more than 2,000 years ago, Go is a two-person perfect information game,
and is one of the most complex board games. Writing computer programs to play Go
is one of the grand challenges of Computational Intelligence nowadays. Each player’s
goal of the game is to control a larger area than the opponent’s one on the board; the
challenge for Go game automation is due to the simplicity of the pieces and rules to
play it, hence the way to achieve the most board area control is a very open
procedure, and the combinations for doing it have an exponential growth. Actually,
the Go’s search space of solutions is huger –very much– than the one of Chess [
The Go game is played on a board shaped with 19 horizontal and vertical lines
commonly, see Figure 1, where alternating, each player places a stone of his own
color on an empty intersection on the board, with black playing first [
In [
Bounzy [
GNUGo is a free Go program that is able to play the Go games from board sizes of
5x5 to 19x19 [
Description of the paper, it begins with a brief introduction to the formal rules of Go, in Section 2; we make a description of Go game simulator, in Section 3; the experimental stage, in Section 4 and conclusion; Ending with a discussion about future work. 2
A Go game can be represented as a tree, with each node corresponding to a particular
board position. The root node is the position at the beginning of the game. The
children of each node are the positions reachable in one move. A strategy for a player
indicates how the player responds to any board position. A complete strategy for Go,
even on the 9x9 board, would be astronomically large. The disarming simplicity of
the rules of Go, however, conceals a formidable combinatorial complexity [
The player with the black stones is allowed to play first. It is only allowed to play one stone at the time, which is placed on one of the empty intersections. A stone, once played, is not to be moved unless if it is captured. If a stone or multiple stones of the same color are surrounded by the other color, such that no direct adjacent intersection is empty, and then the stone(s) is (are) captured. Adjacent empty intersections are also referred to as liberties. A liberty is an empty point adjacent to a group of stone. Any group that has no liberties is said to be dead and they have to be removed from board. From the capturing rule for multiple stones it can be seen that stones are connected which are positioned on directly neighboring intersections. Diagonal neighboring intersections are not connected as there is no direct line between them. Stones which are connected are also called a chain –a single stone is also a chain. The goal of the game is to control as much territory as possible. The player who has the largest territory at the end of the game is the winner.
The tactics in Go game are local conditions to deal with immediate fighting
between stones [
The strategies deal with global influence [
In the next diagram and table, we show how the simulator works. In Figure 2 describes the process flow in the algorithm and in Table 1 the algorithm steps. 1. Initializes the board 2. Player makes a move 3. If the move is possible go to step 5, otherwise go to step 4 4. Pass go to step 7 5. Put stone 6. Change turn go to step 2 7. If both players pass go to step 8 8. Calculate the scores and end game
Go Formal grammar. For the Go game, we proposed a simple formal grammar to help us to develop a Go game simulator and it is the following: • V is the alphabet (terminals and non-terminals symbols). • ∑ ⊆ V is the set of terminals. • B ∈V - ∑ is the initial symbol. • V - ∑, the set of non-terminal elements. • R ⊆ (V - ∑) × V* is the set of rules.
∑ = {play (player, x, y, t)}, where • player є {black, white}, x є {0… 18}, y є {0…18} • t is the tactics/strategies to apply. • end is the end of game.
Non-terminal symbols: • G is the initial symbol. • J is the play. • T is the position played. • Pass-black is when a player black pass. • Pass-white is when a player white pass.
• G → J. • J → T | Pass-black Pass-white end | Pass-white Pass-black end | Pass-black T |
Pass-white T. • T → play (player, x, y, t).
The Go game simulator is in Java and uses a graphic interfaces human – computer. Simulator is a heuristic method based on a formal grammar having a degree of variability by execution, sometimes giving an optimal result. 4
In this section, we present some experiments of simulator, when each player plays with others; the experiments are the following: 1) random player (RP) vs. RP, 2) RP vs. smart player (SP), 3) RP vs. GnuGo player (GP), 4) SP vs. SP and 5) SP vs. GP. Nowadays thirty tests per experiment were made hence certain confidence was got. Additional more exhaustive tests will be made.
This paper has explored the diversity of tactics and strategies in the game of Go. We developed a simulator which is capable of playing competitive with the most traditional and powerful simulator of Go. From results is showed that when RP played with RP, both won at the same percentage, see Table 2; when RP played with SP, there was a clearly advantage to favor of SP, see Table 3; when RP played with GP, the first won more times than GP, see Table 4; when SP played with SP, both won at the same percentage, see Table 5; when SP played with GP, the SP won more times than GP did, see Table 6. We tested our simulator with GP and obtained a huge advantage to our simulator.
Random (black) Random (white) 1 2 3 28 29 30
Random player (black) 55 46 48
Random (black) Smart (white) Random (black) Gnu-go (white)
Smart (black) Smart (white) 1 2 3
Smart (black) Gnu-go (white)
Conclusion: A formal grammar for modeling the Go game is introduced; the flow diagram and context-free grammar fundament the automated Go player algorithms. The deployed Go player mostly beat the well-known GnuGo, as well as to humans Go medium level of expertise or other automated Go players. The reason of the advantage is due to the application of offensive, territorial and defensive strategies introduced. The algorithmic implementation of these strategies, it supports the agile response by our automated Go player during the matches. Further test are required to assess the automated Go player performance.
Ongoing work: The introduction of artificial neural network (NN) for patterns recognition allow acquire more information about the state of board game and what the enemy is doing. By segmenting the board game into 3 x 3 and 5 x 5 windows allows detect eyes, ladders, and net patterns. NN usage improves offensive/defensive tactics and strategies application for playing Go game. Moreover, for learning on the usage of tactics and strategies, given specific game circumstances. Formal grammar models the moves of the player and whole Go game, but still lacking for represent specific tactics and strategies, what we are working on.