Data Structures and Algorithms | Assignment

Added on - 13 Sep 2019

  • Dissertation

    type

  • 5

    pages

  • 1300

    words

  • 75

    views

  • 0

    downloads

Showing pages 1 to 2 of 5 pages
Data Structures and AlgorithmsAssignment Type:Coding AssignmentProject Title:Implement the game GoWeighting:Marked out of 100, worth 15%Feedback Method:Rubric & commentLearning Outcome:Utilise a variety of data structures available such as lists, queues, stacks andtrees to be able to develop searching and traversal algorithms to traverse through such datastructures, including those designed by other team members.Assignment IntroductionThe game of Go has established itself as the current standard by which to assess the intelligence of acomputer programme surplanting chess. This is due to the fact that brute-force approaches tosearching the board for optimal solutions take too long for Go. This assignment is split into separatedeliverables, 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. Playerstake turns placing stones on the board at specific grid positions, one player plays white stones, theother black. Only one stone may be placed at a time and once placed its position may not bechanged. Players may choose to skip their turn. The game ends when black followed by white skip ago.Stones may be captured. If they are, then they are removed from the board and kept by the captureras prisoners. The winner is decided based on amount ofterritory and prisoners captured.Scoring:Each empty space surrounded by one colour is counted towardthe score along with each prisoner. Each counts as one point.In the image to the right, a prisoner was taken by black at pointa. Counting the spaces surrounded by black, the top area has 5captured 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 soblack’s total is 16. White on the other hand has 11 capturedspaces bottom left, and 6 spaces top right, giving it a total of 17and hence winning the game by 1 point.Rules:The following are the rules of the game that we shall use in our implementationCapturing Stones & Counting LibertiesThe cardinal directions around a stone are called itsliberties. To capture a piece, all of these spacesmust be occupied. A solid connection of pieces of the one colour that are adjacent vertically and/orData Structures and AlgorithmsPage1of5
horizontally (not diagonally) are collectively called astring. To capture a full string, all of its libertiesmust be captured (that is all pieces above, beside and below the string must be filled by the othercolour).Self CaptureSelf capture is not allowed (placing a piece in a positionwhere it is immediately captured) unless it would result incapturing the surrounding pieces.For example, we can place a white piece at i to capture theblack string that surrounds it only because that black string issurrounded by white on all liberties.We could place a white piece at j to capture the black stringaround it only because the black string’s other liberties arefilled by white. Without those surrounding white pieces wecould not place a white at i or j. Note that we also cannotplace a black piece at either of these locations.EyesA string that has two separated spaces, similar to i and jabove (m and n to the left) cannot be captured. To capture itwould require placing a piece at both m and nsimultaneously. Any string or group of stones which has twoor more eyes is safe from capture.KO RuleYou may not play a position that recaptures a position thathas just been captured from you. Allowing this could resultin an infinite loop.All of these rules are fully explained athttp://www.britgo.org/intro/intro2.htmlThere are other rules at this address,however, you only need to consider those specified above.Data Structures and AlgorithmsPage2of5
desklib-logo
You’re reading a preview
card-image

To View Complete Document

Become a Desklib Library Member.
Subscribe to our plans

Unlock This Document