Introduction
Go is an ancient Chinese game. It was created a long time ago! I was initiated by my sister’s boyfriend simply by playing a game. Me having only Hikaru no Go1 knowledge of the game, I lost of course. The rules of the game of go are pretty simple (eg. rules).
The next day I trained, and because I like to combine hobbies and passion, I challenged myself to create a “engine” for go. Which would contain the rules, a virtual board and an API that would allow it to be used in a graphical interface or an AI.
I have chosen rust, because it’s a language I enjoy, and It guarantees some speed ;)
The rules
Go is a game that is played differently in many countries ! Each country have its own ruleset, the most popular is maybe the Japanese. Like many go programs, I choose the Tromp-taylor rules in order to implement the game. These rules are the basic rules of go. They are divided in 10 parts, I’m gonna explain my implementation of each part.
1. Go is played on a 19x19 square grid of points, by two players called Black and White.
First step is choosing a struct to represent the goban (the name of the game
board). First idea was using an array [0u8;19*19] but due to the fact that in rust we cannot
actually get an iterator per value from an array, pushed me for using a vector.
We will not simulate a matrix (like Vec<Vec<>>_) for the sake of simplicity,
instead, we will allocate a vector with 361 size let v: Vec<u8> = vec![0;19*19],
to access values stored, we will use a row major policy2.
Now we are ready to create our struct representing a goban !
type Coord = (usize,usize)
type Color = u8
struct Goban {
tab : Vec<Color>
}
impl Index<Coord> for Goban {
type Output = Color
fn index(i: (usize,usize)){
tab[i.0*tab.len()+i.1]
}
}
It’s all we need, next !
2. Each point on the grid may be colored black, white or empty.
Well in game of Go you have two colors of stones, and you must save empty spaces too. We’ll create an Enum representing the color of a stone.
#[repr(u8)]
enum Color {
Black,
White,
Empty
}
With that enum we don’t need type Color=u8.
Finally we create an struct Stone, we will need it.
struct Stone {
coord: Coord,
color: Color
}
3. A point P, not colored C, is said to reach C, if there is a path of (vertically or horizontally) adjacent points of P’s color from P to a point of color C.
We have to handle connection of stones ! First, we need the coordinates of the stones that may be connected.
pub fn neighbors_coords(coord: &Coord) -> Vec<Coord> {
vec![
(coord.0.wrapping_add(1), coord.1),
(coord.0.wrapping_sub(1), coord.1),
(coord.0, coord.1.wrapping_add(1)),
(coord.0, coord.1.wrapping_sub(1))
]
}
Nice, with that we can do :
///
/// Get all the neighbors to the coordinate
///
#[inline]
pub fn get_neighbors(&self, coord: &Coord) -> impl Iterator<Item=Stone> + '_ {
neighbors_coords(coord)
.into_iter()
.filter(move |x| self.coord_valid(x))
.map(move |x| Stone { coord: x, color: self[x] })
}
And get all the the neighbors to a stone (empty stones too). the function
coord_valid() returns true if the coordinate is in the goban. So to only get
the stones connected to a single stone, we only have to add a filter ! I chose
to create another function in order to see where are the “blank” stones and to
be able to calculate liberties later.
#[inline]
pub fn get_neighbors_stones(&self, coord: &Coord) -> impl Iterator<Item=Stone> + '_ {
self.get_neighbors(coord)
.filter(|s| s.color != Color::None)
}
With that function we get an iterator of neighbors of a stone. This function will be very important in the future.
To know if a point P can reach a color C, I used and Bread First Search because the goban is like a graph. Stones are connected vertically and horizontally.
///
/// Get the string of stones connected to a stone. with a Breadth First Search,
/// works for Empty stones too.
/// Ex: Passing a point to this will return all the points of same color connected to
/// the point.
///
pub fn bfs(&self, point: &Stone) -> HashSet<Stone> {
let mut explored: HashSet<Stone> = HashSet::new();
explored.insert(point.clone());
let mut to_explore: Vec<Stone> = self.get_neighbors(&point.coord)
.filter(|p| p.color == point.color)
.collect(); // Acquiring all the neighbors
while let Some(stone_to_explore) = to_explore.pop() { // exploring the graph
explored.insert(stone_to_explore.clone());
self.get_neighbors(&stone_to_explore.coord)
.filter(|p| p.color == point.color && !explored.contains(p))
.for_each(|s| to_explore.push(s));
}
explored
}
This returns a group connected to the stone passed to the function, so if we want to know if the stone passed as parameter can reach C, we only have to iterate on the set returned by the function and filter by C.
let s = Stone{color:Color::Black,coord:(2,4))}
bfs(s).iter().flat_map(|s|get_neighbors(s.coord)).any(s.color == Color::White) // true or false
Now we know how to get the groups of stones connected.
Next !
4. Clearing a color is the process of emptying all points of that color that don’t reach empty
So in Go when a player cuts the last liberty of an opponent group3, the group is removed from the board. You need to know which stones are in that group, and if a group doesn’t reach an empty stone that means we are clearing his stones.
///
/// Test if a group of stones is dead.
///
/// "a group of stones is dead if it doesn't have liberties"
///
pub fn is_string_dead(&self, stones: &HashSet<Stone>) -> bool {
!stones // If there is one stone connected who has liberties, they are not captured.
.iter()
.any(|s| self.has_liberties(s))
}
With that function we can know if a group of connected stones is dead or not. Then we need to clear groups that are dead.
Our code is beginning to grow ! So we have to structure it, We have to find a
place for functions and methods that aren’t dependent with the struct Goban.
We are going to need another struct containing the rules, Goban was the
vocabulary now we need semantic ! Let’s call it Game
struct Game{}
In the impl of game we are gonna put the function to clear up dead stones.
Because it’s not analogous to Goban.
///
/// Removes the dead stones from the goban by specifying a player.
/// Returns the number of stones removed from the goban.
///
fn remove_captured_stones_turn(&mut self, turn: Player) -> usize {
let mut number_of_stones_captured = 0;
for groups_of_stones in self
.goban
.get_groups_of_stones_color_without_liberties(turn.get_stone_color())
// get a vector of set of stones connected and without lib.
{
if self.goban.is_string_dead(&groups_of_stones) {
self.goban.push_many(
groups_of_stones.iter().map(|point| &point.coord),
Color::None,
);
number_of_stones_captured += groups_of_stones.len();
}
}
number_of_stones_captured
}
This rule is finished, next!
5.Starting with an empty grid, the players alternate turns, starting with Black.
We need to add 1 variable to our game struct, something to handle the player turn.
enum Player {
White,
Black
}
/// impl Neg for Player etc ...
struct Game{
turn: Player
}
then in a method called play we are gonna handle the turn of a player, I
implemented trait Neg to the enum Player. So we can do !self.turn and return
the other player like a boolean.
///
/// Method to play on the goban or pass.
/// (0,0) is in the top left corner of the goban.
///
pub fn play(&mut self, play: &Move) {
match play {
Move::Pass => {
self.turn = !self.turn;
self.passes += 1;
}
Move::Play(x, y) => {
self.goban.push(x, y , self.turn.get_stone_color());
self.turn = !self.turn;
}
Move::Resign => {
self.resigned = Some(self.turn);
}
}
And of course the method play is in impl Game. Don’t mind the play: &Move
it’s explained in the next part.
6. A turn is either a pass; or a move that doesn’t repeat an earlier grid coloring.
Another easy one, and you might already understood how to achieve this thanks to
match play in play.
So to fulfill this rule we have to create an enum Move who stores each of the
actions of the players.
enum Move {
Play(x,y), // the coordinates
Pass, // passing
Resign // bonus handling resign
}
Then you add a history in the Game struct, like a Vec<Goban> and you check
if the new goban is not in the vec. If the goban already is in the collection,
then the move is illegal.
fn is_board_uniq(board : Goban) -> bool {
!self.history.contains(board)
}
We want a nice API for our Game struct, so there is draft:
- a method
legals(&self)which returns an iterator of legal moves - a method
play(&Move)that plays the move, we already have - maybe a
play_with_verifications(&Move)to verify is the play is good
Why play() don’t do verifications ? Because legals() do ! I don’t want to
check a move two times.
7. A move consists of coloring an empty point one’s own color; then clearing the opponent color, and then clearing one’s own color.
If I reformulate this rule, “For each move we remove enemy stones who don’t have liberties, then I remove my stones who don’t have liberties”. So it’s kind of easy, the last part where I remove my own stones, it’s called a suicide4.
So I present you the final play method, who will fulfill the requirements. There are another features not presented here, but you can checkout my repo at the end of the article.
pub fn play(&mut self, play: Move) -> &mut Self {
match play {
Move::Pass => {
self.turn = !self.turn;
self.passes += 1; // handling passes
self
}
Move::Play(x, y) => {
let stone_color: Color = self.turn.get_stone_color(); // getting the color of the turn
self.goban.push((x, y), stone_color).expect(&format!( // "coloring an empty point ..."
"Put the stone in ({},{}) of color {}",
x, y, stone_color
));
self.remove_captured_stones(); // removes stones enemies then mine (if suicide is enable in the rule)
self.plays.push(self.goban.clone()); // history for avoid same dispositions
self.turn = !self.turn; // handling turn
self.passes = 0; // handling passes
self
}
Move::Resign(player) => {
self.outcome = Some(EndGame::WinnerByResign(player));
self
}
}
}
8. The game ends after two consecutive passes.
Here we need to handle the endgame, if there is 2 passes then the game is over
(normally it can be resumed), so we add a variable passes: u8 to Game, we will also
create an enum to represent kind of endgames.
enum EndGame{
WinnerByPoints(Player, f32)
WinnerByResign(Player)
Draw
}
As you could see in the play() we increment passes when a player pass, if
passes == 2 then we can conclude the game is finished. The trick is to reset
passes when a play is made.
Next we are gonna add a method to Game to know when the game is finished, we
are gonna call it is_over()-> bool
fn is_over(&self)-> bool {
if passes == 2 {
true
}else {
false
}
}
9. A player’s score is the number of points of her color, plus the number of empty points that reach only her color.
We have already done this, it’s the same technique as concluding that a group had no liberties. Don’t worry, it’s not complicated at all. So for the first part of the rule it’s easy, we only have to count the number of stones of each color, for the second part it’s also easy. Because we can do a BFS on each empty point as for stones. So for each group of blank points, if they reach only one color of stone then add the count of empty points to the player. For the empty points that reach two colors, don’t do nothing.
Here is the code:
/// Returns the territory of each player in a tuple
pub fn get_territories(&self) -> (impl Iterator<Item = Stone>, impl Iterator<Item = Stone>) {
// as you can see get_stones_by_color was used in rule four
let empty_strings = self.get_strings_from_stones(self.get_stones_by_color(Color::None)); // gets a list of groups
let mut white_territory = Vec::new();
let mut black_territory = Vec::new();
for group in empty_strings {
let mut neutral = (false, false);
for empty_intersection in &group {
for stone in self.get_neighbors(empty_intersection.coordinates) {
if stone.color == Color::White {
neutral.1 = true; // found white stone
}
if stone.color == Color::Black {
neutral.0 = true; // found black stone
}
}
}
if neutral.0 && !neutral.1 {
black_territory.extend(group.into_iter())
} else if !neutral.0 && neutral.1 {
white_territory.extend(group.into_iter())
}
}
(black_territory.into_iter(), white_territory.into_iter())
}
So there it is we can count territories, well this function returns two
iterators of points, we just need to .count() on them.
10. The player with the higher score at the end of the game is the winner. Equal scores result in a tie.
Last rule for this we just need to add a function that return an EndGame
Here is the implementation :
///
/// Returns the endgame.
/// None if the game is not finished
///
#[inline]
pub fn outcome(&self) -> Option<EndGame> {
if !self.is_over() {
None
} else if self.outcome.is_some() {
self.outcome
} else {
// wrapper for scoring, all it does is getting territories and counting them.
let scores = self.rule.count_points(&self);
if (scores.0 - scores.1).abs() < std::f32::EPSILON { // standard for comparing floats
Some(Draw)
} else if scores.0 > scores.1 {
Some(WinnerByScore(Black, scores.0 - scores.1))
} else {
Some(WinnerByScore(White, scores.1 - scores.0))
}
}
}
The end + next to do
So there it is, you have a Go board, but you haven’t an AI ;).
There is some improvements you can do:
- For Ko detection you can use zobrist hashing
- Not using breadh first search for calculate liberties
- implement others rules like Japanese, or AGA
- Implement an AI
If you want to look to my implementation there is my repo.