Description
Question
The campus of USC is home to two large families of squirrels, the
Leavey Ninja Squirrels from the north, and the Viterbi Fluffy
Hackers from the west. They are constantly battling for territories
with the highest yield of pine nuts (or whatever nuts they desire).
The family patriarch of Viterbi Fluffy Hackers, Master Yoda, after
“attending” many years of CSCI561 outside the classroom
window, finally realized this is the key to the glory of his family. He
requested you, the Chosen One (who apparently knows how to
communicate with a squirrel), to be his strategy advisor. As a member of greater Viterbi family,
you feel obliged to help your fluffy brethren, using the power of the Force (a.k.a. Artificial
Intelligence).
As the wise Master Yoda has told you, the squirrel war on USC campus
can be simulated as a game with the following rules:
1. The game board is a 5×5 grid representing territories the squirrel
warriors will trample.
2. Each player takes turns as in chess or tictactoe. That is, the first
player takes a move, then the second player, then back to the first player
and so forth.
3. Each square has a fixed point value between 1 and 99, based upon its
yield of nuts.
4. The values of the squares can be changed for each game, but remain
constant within a game.
5. The objective of the game for each player is to score the most points, i.e. the total point
value of all his or her occupied squares. Thus, one wants to capture the squares worth the
most points.
6. The game ends when all the squares are occupied, because no more moves are left.
7. On each turn, a player can make one of two moves:
Raid – You can take over any unoccupied square that is adjacent to one of your current pieces
(horizontally or vertically, but not diagonally). You place a new piece in the taken over square.
Also, any enemy pieces adjacent to your new piece (horizontally or vertically, but not diagonally)
are conquered and replaced by your own pieces. You can Raid a square even if there are no
enemy pieces adjacent to it to be conquered. Once you have made this move, your turn is over.
Figure 1. This is a Raid. Green raids D3 and conquers the blue piece in D2 since it is touching
the new green piece in D3. A Raid always creates at least one new piece (in the square being
raided), but it may not always conquer any of the other player’s pieces. Thus, another valid
move might have been to have raided E4. Then the green player would own D4 and E4 but
would have conquered none of blue’s pieces. Note, the total value of each side before the raid
was green 16 : blue 54, but afterwards is green 28 : blue 43. These values will be used in the
evaluation function as explained later.
Figure 2. Here blue raids C3. In the process green’s pieces at D3 and D4 are conquered
because they touch C3. Notice that in its next move, green will not be able to conquer any of
blue’s pieces, because it can raid only D5 and E4.
Sneak – You can take any unoccupied square on the board that is not next to your existing
pieces. This will create a new piece on the board. Unlike Raid which is an aggressive move,
Sneak is a covert operation, so it won’t conquer any enemy pieces. It simply allows one to place
a piece at an unoccupied square that is not reachable by Raid.
Notice that a space that can be Raided cannot be Sneaked(your squirrel warriors are
always more aggressive when near home territory). Once you have done a Sneak, your turn is
complete.
Figure 3. This is a Sneak. In this case, green drops a new piece on square B3. This square is
worth 48, which is a higher number, meaning that it contains some important resources (e.g. a
large pine tree). A Sneak could have been carried out on any squares except for C2 since blue
already occupies it. In the next move, blue can Raid B2, C1, C3 or D2, or it can Sneak any other
square, except for B3 and C2, which are already occupied.
8. Again, the Raid operation has two effects: (1) A new piece is created in the target square,
and (2) any enemy pieces adjacent to the target square are turned to the player’s side. On the
other hand, Sneak has only effect (1).
9. Any unoccupied square can be taken with either Raid or Sneak, but they are
mutuallyexclusive. If the square is horizontally or vertically adjacent to an existing selfowned
piece, it’s a Raid. Otherwise it’s a Sneak.
10. Anytime adjacency is checked (e.g. Raid validity, conquering enemy pieces), it’s always
checking vertical and horizontal neighbors, but never diagonal. In other words, a diagonal
neighbor is never considered adjacent.
Assignment
PART 1: You will write a program to determine the next move by implementing the following
algorithms:
● Greedy Bestfirst Search (30%);
● Minimax (30%);
● AlphaBeta Pruning (30%).
PART 2:
You will simulate several battles by applying the above algorithms as two players (10%).
Evaluation Function
As introduced, each grid on the game board has different strategic value. The evaluation
function of a game board state can be computed by:
E(s) = Total_Value_Player Total_Value_Opponent
For example, the board on the left side of Figure 2 for the blue player has an evaluated value of:
E(s) = (1+32+2+8)(11+1+10+6) = 15
Note: The leaf node values are always calculated from this evaluation function. Although there
might be a better evaluation function, you should comply with this rule for simplicity.
Expand Order and Tie Breaking
The positional order on Figure 4(b) decides the next move among multiple candidates with the
same evaluated value. For example, if some legal moves (B4, C3, C5, D3, E3, E4) have the
same evaluated values, the program must pick C3 according to the tie breaker rule.
Your traverse and expand order must be in the positional order as well. For example, your
program will traverse on C3, D3, E3, B4, E4, C5 branch in order.
(The wise Master Yoda explained why this positional order is passed on from a long time ago: When
choosing territories with the same yield of nuts, the brave Viterbi Fluffy Hackers always prioritize those
closer to their enemy’s home North / Up for attack, then consider those closer to their own home West /
Left for defence. The Leavey Ninja Squirrels follow the same two rules, but they are more conservative and
prefer defence over attack, thus they end up with the same positional priority order.)
(a) (b)
Figure 4. Illustration of tie breaking positional order for traverse and expand.
Your expand and traverse orders don’t need to differentiate between Raid or Sneak, because
each square is valid for only one type of move. When expanding a node for a square, you must
perform the correct move to compute the next board state.
Pseudocode
1. Greedy Bestfirst Search: AIMA section 3.5.1 (Greedy bestfirst search) The cutoff depth is
always 1. Thus, the algorithm is very simple. You only need to pick the action which has the
highest evaluation value.
2. Minimax: AIMA Figure 5.3 (Minimax without cutoff) and section 5.4.2 (Explanation of
Cutting off search)
3. AlphaBeta Pruning: AIMA Figure 5.7 (AlphaBeta without cutoff) and section 5.4.2
(Explanation of Cutting off search)
PART 1
Drawing upon the Force, you must skillfully manipulate three algorithms as powers to guide your
squirrel warriors’ next move.
Input:
For each test case, you are provided with an input file that describes the current state of the
game. In the input and output files, the two sides will be represented as X and O.
