Homework 2

1. Overview

In this programming assignment, you will develop your own AI agents based on some of the AI techniques for Search, Game Playing, and Reinforcement Learning that you have learned in class to play a small version of the Go game, called Go-5x5 or Little-Go, that has a reduced board size of 5x5. Your agent will play this Little-Go game against some basic as well as more advanced AI agents. Your agents will be graded based on their performance in these online game “tournaments” on Vocareum.com. Your objective is to develop and train your AI agents to play this Little-Go game as best as possible.

2. Game Description

Go is an abstract strategy board game for two players, in which the aim is to surround more territory than the opponent. The basic concepts of Go (Little-Go) are very simple:

• Players: Go is played by two players, called Black and White.
• Board: The Go board is a grid of horizontal and vertical lines. The standard size of the board is 19x19, but in this homework, the board size will be 5x5.
• Point: The lines of the board have intersections wherever they cross or touch each other. Each intersection is called a point. Intersections at the four corners and the edges of the board are also called points. Go is played on the points of the board, not on the squares.
• Stones: Black uses black stones. White uses white stones.

The basic process of playing the Go (Little-Go) game is also very simple:

• It starts with an empty board,
• Two players take turns placing stones on the board, one stone at a time,
• The players may choose any unoccupied point to play on (except for those forbidden by the “KO” and “no-suicide” rules).
• Once played, a stone can never be moved and can be taken off the board only if it is captured. The entire game of Go (Little-Go) is played based on two simple rules: Liberty (No-Suicide) and KO. The definitions of these rules are outlined as follows:

Rule1: The Liberty Rule

Every stone remaining on the board must have at least one open point, called a liberty, directly orthogonally adjacent (up, down, left, or right), or must be part of a connected group that has at least one such open point (liberty) next to it. Stones or groups of stones which lose their last liberty are removed from the board (called captured). Based on the rule of liberty, players are NOT allowed to play any “suicide” moves. That is, a player cannot place a stone such that the played stone or its connected group has no liberties, unless doing so immediately deprives an enemy group of its final liberty. In the latter case, the enemy group is captured, leaving the new stone with at least one liberty.

Examples of capturing:

• Example 1. The white stone is captured after Black plays at position 1, because its directly orthogonally adjacent points are occupied.

Rule 2: The “KO” Rule

For the position shown on the left board above, Black can capture the stone by a play at position a. The resulting position is shown on the right board above. Without a KO rule, in this position White could recapture the stone at position b, reverting to the position shown on the left, and then Black could also recapture. If neither player gave way, then we would have Black a, White b, Black a, White b, ..., repeated ad infinitum, stalling the progress of the game. This situation is known as KO. The KO rule resolves the situation: If one player captures the KO, the opponent is prohibited from recapturing the KO immediately.

• Example. Given the initial status on the left below, the white player puts a stone at position 1, which captures a black stone. Black stone cannot be placed at position 2 immediately after it’s captured at this position. Black must play at a different position this turn. Black can play at position 2 the next turn if this position is still not occupied.
• More examples. KOs need not occur only in the center of the board. They can also show up at the sides or corners of the board, as shown in the diagram below.

Komi

Because Black has the advantage of playing the first move, awarding White some compensation is called Komi. This is in the form of giving White a compensation of score at the end of the game. In this homework (a board size of 5x5), Komi for the White player is set to be 5/2 = 2.5.

Passing

A player may waive his/her right to make a move, called passing, when determining that the game offers no further opportunities for profitable play. A player may pass his/her turn at any time. Usually, passing is beneficial only at the end of the game, when further moves would be useless or maybe even harmful to a player's position.

End of Game

A game ends when it reaches one of the four conditions:

• When a player’s time for a single move exceeds the time limit (See Section 6. Notes and Hints).
• When a player makes an invalid move (invalid stone placement, suicide, violation of KO rule).
• When both players waive their rights to move. Namely, two consecutive passes end the game.
• When the game has reached the maximum number of steps allowed. In this homework (a board size of 5x5), the maximum number of steps allowed is (5*5)-1 = 24.

Winning Condition

There are various scoring rules and winning criteria for Go. But we will adopt the following rules for the scope of this Little-Go project.

• “Partial” Area Scoring: A player's partial area score is the number of stones that the player has occupied on the board.
• Final Scoring: The Black player’s final score is the partial area score, while the White player’s final score is the sum of the partial area score plus the score of compensation (Komi).
• Winning Criteria:
  • If a player’s time for a single move exceeds the time limit (See Section 6. Notes and Hints), s/he loses the game.
  • If a player makes an invalid move (invalid stone placement, suicide, violation of KO rule), s/he loses the game.
  • If the game reaches the maximum number of steps allowed or if both players waive their rights to move, the winner is the player that has a higher final score at the end of the game. For example, in the following board at the end of a game, White’s partial area score is 10 and Black’s partial area score is 12. White is the winner because 10 + 2. 5 = 12. 5 > 12.

Clarification of the Game Rules

The particular set of rules that have been adopted in this assignment references several popular rule sets around the world, but some changes have been made to best adapt to this project. For example, “Full” Area Scoring is usually used in the 19x19 Go game, which counts the number of stones that the player has on the board plus the number of empty intersections enclosed by that player's stones, but we do not use this rule in our assignment. Go is a very interesting and sophisticated game. Please do some more research if you’re interested. ...