Foundations of Artificial Intelligence
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSCI-561 Foundations of Artificial Intelligence
Homework
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.
- Example 2. The 3 white stones are captured as a connected group.
- Example 3. The two groups of white stones are captured.
- Example 4 (Special example). This example illustrates the rule that a capturing stone need not
have liberty until the captured stones are removed.
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.
3. Academic Honesty and Integrity
All homework material is checked vigorously for dishonesty using some advanced AI and Data Mining
agents and almost all coping pieces of evidence, no matter how they are hidden, would be detected.
These agents compare the submissions with previous semesters and similar codes on the internet
including GitHub and other similar places. All detected violations of academic honesty are forwarded to
the Office of Student Judicial Affairs. To be safe, you are urged to err on the side of caution. Do not copy
work from another student or off the web. Keep in mind that sanctions for dishonesty are reflected in
your permanent record and can negatively impact your future success. As a general guide:
Do not copy code or written material from another student. Even single lines of code should
not be copied.
Do not collaborate on this assignment. The assignment is to be solved individually.
Do not copy code off the web. This is easier to detect than you may think.
Do not share any custom test cases you may create to check your program’s behavior in more
complex scenarios than the simplistic ones that are given.
Do not copy code from past students. We keep copies of past work to check for this. Even
though this project differs from those of previous years, do not try to copy from homeworks of
previous years.
Do not ask on Piazza how to implement some function for this homework, or how to calculate
something needed for this homework.
Do not post code on Piazza asking whether or not it is correct. This is a violation of academic
integrity because it biases other students who may read your post.
Do not post test cases on Piazza asking for what the correct solution should be.
Do ask the professor or TAs if you are unsure about whether certain actions constitute
dishonesty. It is better to be safe than sorry.