Legal Move Checking in Go Game
Last month I attended two coding dojo sessions in Singapore Scala Programmers group. We had a kata for writing a Go Game program that can determine whether a move is legal. In this post I will share with you my implementation of the Go’s board as well as the move checking. To understand about Go Game as well as its rule, you can read it on Wikipedia or the kata’s description on GitHub.
Piece
sealed abstract class Piece {
val opponentPiece: Piece = Empty
}
case object Empty extends Piece
case object BlackPiece extends Piece {
override val opponentPiece = WhitePiece
}
case object WhitePiece extends Piece {
override val opponentPiece = BlackPiece
}
I defined an abstract Piece class with 3 case objects: Empty (for representing unoccupied positions), BlackPiece and WhitePiece. These classes all have opponentPiece function, but mostly used by BlackPiece and WhitePiece to get each other piece.
Move
case class Move(x: Int, y: Int, piece: Piece) {
require(piece != Empty, "Invalid Piece, only BlackPiece or WhitePiece")
}
The Move class’s constructor has 3 paramters, x and y represent the row and column coordinate on the board respectively, piece represents which player plays the move. Note that piece cannot be an Empty type.
GoGame
With Piece and Move classes above, I wrote a GoGameDef trait which defines logics of a go game:
trait GoGameDef {
val rowCount: Int
val colCount: Int
type Positions = Vector[Vector[Piece]]
case class Board(positions: Positions = Vector.fill(rowCount, colCount)(Empty),
nextPiece: Piece = BlackPiece) {
require(positions.length == rowCount && positions.head.length == colCount,
"Invalid positions length")
}
/**
* A record of boards of the game.
* The Stream.head is the current board
*/
type BoardRecord = Stream[Board]
def isLegalMove(move: Move, boardRecord: BoardRecord): Boolean = ???
/**
* Given a move and board record, play a move on the board, capture no-liberty opponent's pieces
* If a move is illegal, an IllegalArgumentException exception will be thrown
* @return a new board record
*/
def playMove(move: Move, boardRecord: BoardRecord): BoardRecord = ???
rowCount and colCount are for defining the size of the board. A standard Go board has the size of 19×19. 13×13 and 9×9 boards are popular choices to teach beginners.
The Positions type is a 2D Vector of Piece objects which represents the state of all positions of a board, whether it is unoccupied Empty, occupied by BlackPiece or WhitePiece. Next we have a Board class which has a positions to hold the state of the board and nextPiece to indicate which player is going to play next. I define a BoardRecord type which is a Stream of Board objects to record all Board states of a Go Game after each move.
Given a Move and a BoardRecord, the isLegalMove method returns true if the move is legal, false otherwise. I also have playMove method which simulate playing a move and returns a new BoardRecord. Our kata’s objective is implementing the isLegalMove method.
Test Cases
Before implementing the isLegalMove method, I wrote ScalaTest specs so that the method needs to check for all rules of a move. To define a board game easily, I wrote a StringParserGoGame which helps to parse a Board object from ASCII string:
/**
* This trait implements a parser to define a board state from a ASCII string.
*
* When mixing in this trait, we can get the `initialBoardRecord`
* by defining the field `boardASCII` in the following form:
*
* val boardASCII =
* """x
* |-----
* |--o--
* |--x--
* |-----""".stripMargin
*
* - The first line will have one character `x` or `o` denotes
* the next piece
* - The following lines represent the board's position
* - The `-` character denotes empty positions
* - `x` denotes positions which are occupied by black
* - `o` denotes positions which are occupied by white
*
*/
trait StringParserGoGame extends GoGameDef {
val boardASCII: String
lazy val rowCount = positions.length
lazy val colCount = positions.head.length
private lazy val positions: Positions = {
parseBoardPositions(boardASCII)
}
protected lazy val initialBoardRecord: BoardRecord = {
val newBoard = {
val nextPiece = if (boardASCII.charAt(0) == 'o') WhitePiece else BlackPiece
Board(positions, nextPiece)
}
Stream(newBoard)
}
protected def parseBoardPositions(boardStr: String): Positions = {
def charToPiece(c: Char) = {
if (c == 'x') BlackPiece
else if (c == 'o') WhitePiece
else Empty
}
Vector(boardASCII.split("\n").drop(1).map(str => Vector(str: _*)
.map(c => charToPiece(c))): _*)
}
}
Here are test cases for isLegalMove method:
Test for correct move’s turn
class GoGameDefSpec extends WordSpec {
trait NewGoGame5x5 extends GoGameDef {
val rowCount = 5
val colCount = 5
val initialBoardRecord = Stream(Board())
}
"isLegalMove()" when {
"at the start of the game" should {
"be true if black's move" in {
new NewGoGame5x5 {
isLegalMove(Move(0, 0, BlackPiece), initialBoardRecord)
}
}
"be false if white's move" in {
new NewGoGame5x5 {
assert(!isLegalMove(Move(0, 0, WhitePiece), initialBoardRecord))
}
}
}
...
}
}
Test for moves with a coordinate outside of the board
"the move is outside the board's coordinate" must {
"be false" in {
new NewGoGame5x5 {
assert(!isLegalMove(Move(-1, 2, BlackPiece), initialBoardRecord))
assert(!isLegalMove(Move(3, -1, BlackPiece), initialBoardRecord))
assert(!isLegalMove(Move(5, 1, BlackPiece), initialBoardRecord))
assert(!isLegalMove(Move(4, 5, BlackPiece), initialBoardRecord))
}
}
}
Test for moves on occupied positions
trait SelfCaptureGame1 extends StringParserGoGame {
val boardASCII =
"""o
|-x---
|x----
|-----
|-----
|-----
""".stripMargin
}
"the move is on occupied position" must {
"be false" in {
new SelfCaptureGame1 {
assert(!isLegalMove(Move(0, 1, WhitePiece), initialBoardRecord))
}
}
}
Test for Suicide rule
"the move has no liberties (self-capturing)" must {
"be false" in {
new SelfCaptureGame1 {
assert(!isLegalMove(Move(0, 0, WhitePiece), initialBoardRecord))
}
}
}
trait SelfCaptureGame2 extends StringParserGoGame {
val boardASCII =
"""o
|-xx--
|x-ox-
|xoox-
|-xx--
|-----
""".stripMargin
}
"the move causes its connected group has no liberties (self-capturing)" must {
"be false" in {
new SelfCaptureGame2 {
assert(!isLegalMove(Move(1, 1, WhitePiece), initialBoardRecord))
}
}
}
trait KoRuleGame extends StringParserGoGame {
val boardASCII =
"""o
|-----
|-xo--
|x-xo-
|-xo--
|-----
""".stripMargin
}
"the move captures enemy's positions, even its position has no liberties" should {
"be true" in {
new KoRuleGame {
assert(isLegalMove(Move(2, 1, WhitePiece), initialBoardRecord))
}
}
}
Test for ko rule
"the move causes the board state return to previous position" must {
"be false" in {
new KoRuleGame {
val newBoardRecord = playMove(Move(2, 1, WhitePiece), initialBoardRecord)
assert(!isLegalMove(Move(2, 2, BlackPiece), newBoardRecord))
}
}
}
Implementation
For rule 1-3, I have a straightforward implementation:
def isLegalMove(move: Move, boardRecord: BoardRecord): Boolean = {
require(boardRecord.nonEmpty)
val currentBoard = boardRecord.head
def isNextMove = move.piece == currentBoard.nextPiece
def isOccupiedPos = currentBoard.positions(move.x)(move.y) != Empty
def isSelfCapture: Boolean = ???
def isSameAsPreviousState: Boolean = ???
isNextMove && isInsideBoard(move.x, move.y) && !isOccupiedPos &&
!isSelfCapture && !isSameAsPreviousState
}
protected def isInsideBoard(x: Int, y: Int): Boolean = {
0 <= x && x < rowCount && 0 <= y && y < colCount
}
To check for suicide (or self-capture) rule, we need to determine whether a move causes its group to be captured. Thus I implement a function, called getCapturedPieces, which returns a set of captured positions of a type Piece, given a Position board:
/**
+ Given a board position, get all the captured pieces
+ which are same type of the input piece
+ @return A set contains positions of captured piece
*/
protected def getCapturedPieces(positions: Positions, piece: Piece): Set[(Int, Int)] = {
require(piece != Empty)
/**
+ Given a position (x, y), returns list of its neighbor positions
*/
def neighbors(x: Int, y: Int): List[(Int, Int)] = {
val neighborDisplacement = List((-1, 0), (1, 0), (0, -1), (0, 1))
neighborDisplacement.map({ case (dx, dy) => (x + dx, y + dy)})
.filter({ case (i, j) => isInsideBoard(i, j) })
}
/**
+ Get all groups which are same type of the input piece
*/
def getGroups: Set[Set[(Int, Int)]] = {
/**
+ Find the group where piece at (x, y) belongs to
*/
def findGroup(x: Int, y: Int) : Set[(Int, Int)] = {
def visit(toVisit: Seq[(Int, Int)], visited: Set[(Int, Int)], group: Set[(Int, Int)]): Set[(Int, Int)] = {
if (toVisit.isEmpty) group
else {
val pos = toVisit.head
val toVisitFriendNeighbors = neighbors(pos._1, pos._2).toSeq.filter {
case(i, j) => !visited.contains((i, j)) && positions(i)(j) == positions(pos._1)(pos._2)
}
visit(toVisit.tail ++ toVisitFriendNeighbors, visited + pos, group + pos)
}
}
visit(Seq((x, y)), Set.empty, Set.empty)
}
def iterPos(x: Int, y: Int, visited: Set[(Int, Int)], groups: Set[Set[(Int, Int)]]): Set[Set[(Int, Int)]] = {
def nextPos(x: Int, y: Int): (Int, Int) = {
if (y < colCount - 1) (x, y + 1)
else if (x < rowCount - 1) (x + 1, 0)
else null
}
val group = {
if (positions(x)(y) == piece && !visited.contains((x, y))) findGroup(x, y)
else Set.empty[(Int, Int)]
}
nextPos(x, y) match {
case (i, j) => iterPos(i, j, visited ++ group, groups + group)
case _ => groups + group
}
}
iterPos(0, 0, Set.empty, Set.empty)
}
/**
+ Whether a group is surrounded by enemy
*/
def isSurrounded(group: Set[(Int, Int)]): Boolean = {
def hasEmptyNeighbor(x: Int, y: Int): Boolean = {
neighbors(x, y) exists {
case (i, j) => positions(i)(j) == Empty }
}
!(group exists { case(x, y) => hasEmptyNeighbor(x, y) })
}
getGroups.filter(isSurrounded).flatten
}
The getGroups function uses a breadth-first search to find all connected-pieces or groups. The isSurrounded function tells us whether a group is surrouded by checking whether it has any Empty piece connected to it.
With the help of this function, we can implement the isSelfCapture function easily:
def isSelfCapture = {
val canCaptureOpponent = getCapturedPieces(positionsWithMovePiece, move.piece.opponentPiece).nonEmpty
if (canCaptureOpponent) false
else {
// if there is any captured piece of move.piece -> self-capture move
val capturedOwnPieces = getCapturedPieces(positionsWithMovePiece, move.piece)
capturedOwnPieces.nonEmpty
}
}
lazy val positionsWithMovePiece = positionsWhenPlaceMove(move, currentBoard.positions)
First it checks whether the move can capture opponent’s pieces. If yes, it means its groups will not be surrounded as there will be empty positions after taking out captured opponent’s pieces. Otherwise, we check whether there is any captured group of the move’s piece. If yes, it means the move is a sucide (or self-capture) move. The positionsWhenPlaceMove helper function returns a new board’s position by simply placing the move’s piece into its coordination.
To check for ko rule, I check the boardRecord for the previous state and check it with the board position after playing the move.
def isSameAsPreviousState: Boolean = boardRecord match {
case (current#::previous#::xs) =>
val newPosition = removeCapturedPieces(positionsWithMovePiece, move.piece.opponentPiece)
previous.positions == newPosition
case _ => false
}
The removeCapturedPieces helper function will take out captured pieces and return new board’s position.
That is my implementation for a legal move checking in Go Game. For more details of the code, please visit its repository on my GitHub.
Discussion, links, and tweets
Tweet
Follow @luugiathuy