Go Game Implementation using Data Structures and Algorithms

The assignment is to implement the game Go, a strategy board game played on an 11x11 grid. The objective is to utilize data structures such as lists, queues, stacks, and trees to develop searching and traversal algorithms for traversing these data structures. The implementation should include methods to determine if a board position is captured or not, calculate the current score for each player, check if a proposed move would be a legal move, and allow two players to play the game given specific rules.

Data Structures and Algorithms
Assignment Type: Coding Assignment
Project Title: Implement the game Go
Weighting: Marked out of 100, worth 15%
Feedback Method: Rubric & comment
Learning Outcome: Utilise a variety of data structures available such as lists, queues, stacks and
trees to be able to develop searching and traversal algorithms to traverse through such data
structures, including those designed by other team members.
Assignment Introduction
The game of Go has established itself as the current standard by which to assess the intelligence of a
computer programme surplanting chess. This is due to the fact that brute-force approaches to
searching the board for optimal solutions take too long for Go. This assignment is split into separate
deliverables, building up complexity with each one.
The Game:
Go is a game played on a grid. The grid we will use for this assignment is an 11x11 board. Players
take turns placing stones on the board at specific grid positions, one player plays white stones, the
other black. Only one stone may be placed at a time and once placed its position may not be
changed. Players may choose to skip their turn. The game ends when black followed by white skip a
go.
Stones may be captured. If they are, then they are removed from the board and kept by the capturer
as prisoners. The winner is decided based on amount of
territory and prisoners captured.
Scoring:
Each empty space surrounded by one colour is counted toward
the score along with each prisoner. Each counts as one point.
In the image to the right, a prisoner was taken by black at point
a. Counting the spaces surrounded by black, the top area has 5
captured spaces, the bottom has 9, the space vacated by a is 1,
so that is a count of 15 then we add 1 for the captured piece so
black’s total is 16. White on the other hand has 11 captured
spaces bottom left, and 6 spaces top right, giving it a total of 17
and hence winning the game by 1 point.
Rules:
The following are the rules of the game that we shall use in our implementation
Capturing Stones & Counting Liberties
Data Structures and Algorithms Page 1 of 5

The cardinal directions around a stone are called its liberties. To capture a piece, all of these spaces
must be occupied. A solid connection of pieces of the one colour that are adjacent vertically and/or
horizontally (not diagonally) are collectively called a string. To capture a full string, all of its liberties
must be captured (that is all pieces above, beside and below the string must be filled by the other
colour).
Self Capture
Self capture is not allowed (placing a piece in a position
where it is immediately captured) unless it would result in
capturing the surrounding pieces.
For example, we can place a white piece at i to capture the
black string that surrounds it only because that black string is
surrounded by white on all liberties.
We could place a white piece at j to capture the black string
around it only because the black string’s other liberties are
filled by white. Without those surrounding white pieces we
could not place a white at i or j. Note that we also cannot
place a black piece at either of these locations.
Eyes
A string that has two separated spaces, similar to i and j
above (m and n to the left) cannot be captured. To capture it
would require placing a piece at both m and n
simultaneously. Any string or group of stones which has two
or more eyes is safe from capture.
KO Rule
You may not play a position that recaptures a position that
has just been captured from you. Allowing this could result
in an infinite loop.
All of these rules are fully explained at
http://www.britgo.org/intro/intro2.html There are other rules
at this address, however, you only need to consider those
specified above.
Data Structures and Algorithms Page 2 of 5

Specific Requirements
 You are required to create a Java programme that can do the following:
o take a board state and a board coordinate and return whether that board position is
captured or not (either as territory or as a prisoner) by implementing the following
method:
public boolean isCaptured(int[][] board, int x, int y)
o take a board state and calculate the current score for each player by implementing
the following method:
public int score(int[][] board, int colour)
o take a board state, a board coordinate and a colour and return whether the proposed
move would be a legal move or not by implementing the following method:
public boolean isLegal(int[][] board, int x, int y, int colour)
o allow two players to play the game given the above rules
 This programme should be written using only your own Linked Lists, Stacks and Queues. You
should use Java API classes only for input and output
 Your programme should be able to take in board states from txt files as per the example at
the end of this document, with a 0 indicating an empty space, a 1 indicating a black stone and
a 2 indicating a white stone
 You should include a README file that describes your algorithms, and defines how to
compile and run your code
 Your code should be compilable and runnable from the command line, I should not have to
use an IDE or do any setup work to get your code to compile and run
 You may use Processing (processing.org) to add a graphical front end to your project,
otherwise, the code should be playable on the command line (ie show the game board and
allow for users to input coordinates to play their pieces)
Notes
 Only the code should be submitted along with the README file, no project files or class files
should be uploaded
 This is an individual assignment. It is intended to work on your ability to break a problem
down into small logical steps.
 Do not use code from the internet, 5% will be lost .
Data Structures and Algorithms Page 3 of 5

Marking Scheme Summary (add rows if necessary)
Description Weighting
Code compiles & runs as expected 0 - 5
Logical structure & clarity of code (incl methods, comments) 0 - 10
Captured board position 0 - 20
Current score 0 - 20
Legality of a move 0 - 10
Playable game 0 - 20
Interface 0 - 10
README file 0 - 5
Logic of algorithms:
a few paragraphs here discussing the logic behind your algorithms
Data Structures and Algorithms Page 4 of 5

Sample game board file:
0 0 0 0 0 2 2 0 0
0 2 1 2 2 1 1 2 0
0 1 2 0 2 1 2 1 2
0 2 0 0 2 1 1 1 2
0 0 1 0 0 2 2 2 0
0 1 2 1 0 1 0 0 0
1 2 2 2 2 2 1 0 0
1 2 2 1 1 2 2 1 0
0 1 1 0 0 1 1 0 0
Data Structures and Algorithms Page 5 of 5