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. <task#> Greedy Bestfirst Search = 1, MiniMax = 2, Alphabeta Pruning = 3 X or O Cutoff depth started from the root. Positive integers from 1 99 5 in each row separated with a space, 5 total rows *: Unoccupied X: Player 1 O: Player 2 5 in each row, no space in between, 5 total rows The ordering corresponds with the board values. Input Example (board state as Figure 5): 2 X 2 20 16 1 32 30 20 12 2 11 8 28 48 9 1 1 20 12 10 6 2 25 30 23 21 10 **XX* **XOX ***O* **OO* Figure 5 ***** NOTES: ● The input file is a text file ending with .txt extension. ● The input file given to your program will not contain any formatting errors, so it is not necessary to check for those. Output: For each test case, your program should output a file named “next_state.txt” showing the next state of the board after the move. For Minimax and AlphaBeta Pruning, your program should output another file named “traverse_log.txt” showing the traverse log of your program in the following format. There is no need to output “traverse_log.txt” for Greedy Bestfirst Search. The format of “next_state.txt” should be: *: Unoccupied X: Player 1 O: Player 2 5 in each row, no space in between, 5 total rows For example: **XX* **XOX *X*O* **OO* ***** The format of “traverse_log.txt” for Minimax traverse log requires 3 columns. Each column is separated by “,” (a single comma). Three columns are Node, Depth and Value. Everything shown here is case sensitive. For example: Node,Depth,Value root,0,Infinity A1,1,Infinity B1,2,19 A1,1,19 E1,2,5 A1,1,5 A2,2,15 A1,1,5 B2,2,23 A1,1,5 A3,2,7 A1,1,5 B3,2,13 A1,1,13 C3,2,22 …… “Node”: is the node name which refers to the move that is made by the agent. For example, the blue player places a piece at the position “D3”. The node name is D3 and has depth 1. Then, the green player places a piece at the position “C3” and has depth 2. There is special node named “root” which is the name for the root node. “Depth”: is the depth of the node. The root node has depth zero. “Value”: is the value of the node. The value is initialized to “Infinity” for the max node (your agent is always max) and “Infinity” for the min (your agent’s opponent) node. The value will be updated when its children return the value to the node. The value of leaf nodes is the evaluated value, for example, C3,2,3 The algorithm traverses from the root node. The log should show both when: 1. The algorithm traverses down to the node. 2. The value of the node is updated from its children. For example, the log shows the value of the node “D3” when traversing from the root. The log shows the node “D3” again when the node is updated from its children “C3”, “E3” and so on. The leaf nodes have no children. Thus, the log shows only once when the algorithm traverses a leaf node and the value is the evaluated value, for example, C3,2,3. where 3 is the evaluated value. The format of “traverse_log.txt” for AlphaBeta traverse log requires 5 columns. Each column is separated by “,” (a single comma). The five columns are node, depth, value, alpha, and beta. The description is same as with the MiniMax log. However, you need to show the alpha and beta values in the AlphaBeta traverse log. For example: Node,Depth,Value,Alpha,Beta root,0,Infinity,Infinity,Infinity A1,1,Infinity,Infinity,Infinity B1,2,19,Infinity,Infinity A1,1,19,Infinity,19 E1,2,5,Infinity,19 A1,1,5,Infinity,5 A2,2,15,Infinity,5 A1,1,5,Infinity,5 B2,2,23,Infinity,5 A1,1,5,Infinity,5 A3,2,7,Infinity,5 A1,1,5,Infinity,5 B3,2,13,Infinity,5 A1,1,13,Infinity,13 C3,2,22,Infinity,13 …… NOTES: ● The output examples above are based on input as in figure 5. They are provided here to demonstrate file format specification, and they only show a small part of the full traverse log (the full log can be found in the samples provided). ● Your program should stop searching when there’s no valid move, even if the preset cutoff depth is not reached yet. ● For any test case, it will be marked as correct only if both next state and traverse log are correct. (For Greedy Bestfirst Search only next state will be checked). ● With the given description, we don’t believe that multiple outputs are possible for any test case. If you are able to think of any such case, please let us know and we will make the necessary changes in the grading guidelines. ● The final test cases will be different from the sample test cases provided. Your assignment will be graded based on the performance on the final test cases only. PART 2 Masterfully controlling the three algorithm powers, you are now ready to wage a fullscale squirrel war. To the wonderland of nuts!! Input You are provided with an input file that describes the current state of the game. Your agent should be able to identify one more task. <task#> Battle simulation = 4 X or O. The first player always moves first Greedy Bestfirst Search = 1, MiniMax = 2, Alphabeta Pruning = 3 X or O Greedy Bestfirst Search = 1, MiniMax = 2, Alphabeta Pruning = 3 Positive integers from 1 99 5 in each row separated with a space, 5 total rows *: Unoccupied X: Player 1 O: Player 2 5 in each row, no space in between, 5 total rows The ordering corresponds with the board values. For example: Greedy Bestfirst Search(cutoff depth is always 1) vs. Minimax(with cutoff depth: 2) 4 X 1 1 O 2 2 20 16 1 32 30 20 12 2 11 8 28 48 9 1 1 20 12 10 6 2 25 30 23 21 10 **XX* **XOX ***O* **OO* ***** NOTES: ● The first player always moves first. ● The input file is a text file ending with .txt extension. ● The input file given to your program will not contain any formatting errors, so it is not necessary to check for those. Output: For each test case, your program should output a file named “trace_state.txt” tracing every state of the game until it ends. The game ends when all the squares are occupied (See Rule 6 on Page 1). The format of “trace_state.txt” should be: … For example: **XX* **X*X ***** **OO* ***** **XX* **XXX ***** **OO* ***** **XX* **XOX ***O* **OO* ***** … NOTES: ● Your program should stop searching when there’s no valid move, even if the preset cutoff depth is not reached yet. Grading Notice: ● Please follow the instructions carefully. Any deviations from the instructions will lead your grade to be zero for the assignment. If you have any doubts, please use the discussion board. Do not assume anything that is not explicitly stated. ● You must use PYTHON (Python 2.7) to implement your code. ● You need to create a file named “hw1cs561s16.py”. The command to run your program would be as follows: (When you submit the homework on labs.vocareum.com, the following commands will be executed.) python hw1cs561s16.py –i inputFile ● You will use labs.vocareum.com to submit your code. Please refer to http://help.vocareum.com/article/30gettingstartedstudents to get started with the system. Please only upload your code to the “/work” directory. Don’t create any subfolder or upload any other files. ● If we are unable to execute your code successfully, you will not receive any credits. You are allowed to use standard libraries only. You have to implement any other functions or methods by yourself. ● You will get partial credit based on the percentage of test cases that your program gets right for each task. ● Your program should handle all test cases within a reasonable time (not more than a few seconds for each sample test case). The complexity of test cases is similar to, but not necessarily the same as, the ones provided in the homework. ● The deadline for this assignment is Feb 8, 2016 at 11:59 PM PST. No late homework will be accepted. Any late submission will not be graded. Any email for late submission will be ignored.
