a1_solutions

CS 486/686 Assignment 1 (100 marks) Jesse Hoey & Josh Jung Due Date: February 5, 2024; Time: AOE Instructions Submit any written solutions in a file named writeup.pdf to the A1 Dropbox on Learn . If your written submission on Learn does not contain one file named writeup.pdf , we will deduct 5 marks from your final assignment mark. Submit any code to Marmoset at https://marmoset.student.cs.uwaterloo.ca/ . Use the latest Python 3.12 No late assignment will be accepted. This assignment is to be done individually. The Due Date is February 5, 2024, “Anywhere On Earth”: if it is Februrary 6, 2024 wherever you are, the deadline has passed. Lead TAs: – Jess Gano (jgano) – Shuhui Zhu (s223zhu) The TAs’ office hours will be scheduled on Piazza. 1

CS 486/686 Winter 2024 Assignment 1 1 Shortest Route to Waterloo (30 points) Suppose that you want to drive to Waterloo from Toronto. You are conscious of your carbon footprint; therefore, you are seeking the shortest path to Waterloo. Below is a graph indicating the driving distances between various cities surrounding Toronto and Waterloo. All distances are given in kilometres. Waterloo Mississauga Kitchener Cambridge Guelph Toronto Milton Oakville Hamilton 28 21 33 44 30 30 42 46 24 25 22 3 29 You would like to apply A* search to identify the shortest route to Waterloo from Toronto. Below are the components of the search problem formulation: States: Each city is the state. We will identify each state by the first 3 letters of its name. For example, the “Guelph” node is denoted as Gue . Initial state: Tor Goal state: Wat Successor function: State B is a successor of state A if and only if there exists an edge on the above graph connecting city B and city A. Cost function: The cost of an edge connecting two states is the distance between the cities that the states correspond to. Your decide to use Euclidean distance as a heuristic function. That is, h is the Euclidean distance from a city to Waterloo (in kilometres). That is, if ( x C , y C ) is city C ’s longitude and latitude coordinates, h ( C ) = p ( x C − x Wat ) 2 + ( y C − y Wat ) 2 . On the diagram below, the red text number to each city indicates its Euclidean distance to Waterloo. v1.3 Page 2 of 9

CS 486/686 Winter 2024 Assignment 1 what order. You do not need to write out the frontier, but the tree must show all paths expanded after removing a node from the frontier. Break any F -value ties using alphabetical order. For example, “Milton” precedes “Mis- sissauga” and should be expanded first if the F values for both nodes are the same. We recommend using https://app.diagrams.net/ to draw the search tree. SOLUTION : See the example search tree below. The blue numbers indicate the set and ordering of the nodes expanded. Ties were broken using alphabetical ordering, as suggested. Tor Mis 2 Mil Oak Mis Gue Cam Gue Ham Kit Mil Cam Kit Mil Wat Cam Gue Wat Ham Mil Mis 0+94=94 28+72=100 58+52=110 49+67=116 104+20=124 100+24=124 88+72=160 88+67=155 82+57=139 79+52=131 70+72=142 128+24=152 148+57=205 126+3=129 150+52=202 124+20=144 142+52=194 125+3=128 129+0=129 147+20=167 150+24=174 128+0=128 1 3 4 5 6 7 8 Tor Oak 56+94=150 Steps are listed below (students do not have to list the steps): 1) Expand Tor with f = 94. 2) Mis has the smallest f value with f = 100. Expand Mis . 3) Mil has the smallest f value with f = 110. Expand Mil . 4) Oak has the smallest f value with f = 116. Expand Oak . 5) Cam and Gue are tied for the smallest f value with f = 124. We break ties by using alphabetical order and expand Cam next. 6) Gue has the smallest f value with f = 124. Expand Gue . 7) Kit has the smallest f value with f = 128. Expand Kit . 8) Wat has the smallest f value with f = 128. Wat is a goal node, so we are done. v1.3 Page 4 of 9

CS 486/686 Winter 2024 Assignment 1 2 Minimax and Connect Four (50 points) For this question, you will be programming Minimax agents to play Connect Four. Connect Four is an adversarial game in which two players, one ‘x’ and one ‘o’, take turns dropping their pieces into the top of a vertical grid with 6 rows and 7 columns. To play a move, a player must select one of the 7 columns into which to drop a piece. The piece then falls downward through the grid, staying in the same column and stopping when it reaches the bottom, or when the square below it is already occupied by another piece. If a column is completely full, it may no longer be selected. In this way, pieces may be stacked on top of each other until either one player is able to get four of their pieces in a row (vertically, horizontally, or diagonally), or the grid becomes completely full. If one player achieves four- in-a-row, that player wins, but if the board fills up before either player has done so, the game is a draw. In Python, we represent the board as a two-dimensional list, where the first index references the column, and the second references the row. Both are indexed from 0, where (0,0) is the bottom-leftmost square. In the example below, the ‘x’ player plays into column 4, it descends to row 1, and ’x’ wins the game via a diagonal four-in-a-row. +---------------+ +---------------+ | . . x . . . . | | . . x . . . . | | . . o . . . . | | . . o . . . . | | . . x . . . . | x into column 4 | . . x . . . . | | . . x x . x . | --------------> | . . x x . x . | | o o o x . o . | | o o o x x o . | | x o x o o x o | | x o x o o x o | +---------------+ +---------------+ Information on the Provided Code We have provided two files: connect_four.py and agents.py on Learn. You will need to complete the minimax and my_heuristic functions in agents.py , and then submit agents.py on Marmoset . You may submit agents.py as many times as you wish until the deadline. Marmoset will evaluate your program for its correctness and efficiency. Writ- ten answers should be submitted on Learn. connect_four.py contains the Connect Four game implementation, including the State class that contains game state information and provides functions for querying and advancing the game state. You will need to call some of these functions in your own code. agents.py contains a few example heuristics, as well as the MinimaxNode class, which you must use to build a tree in the minimax function. v1.3 Page 5 of 9

CS 486/686 Winter 2024 Assignment 1 Describe your heuristic function as concisely as possible. Why should it outperform three_line_heur ? SOLUTION : Give a reasonable-sounding description of a heuristic. (E.g. Same as three line heur, but only counts a line if there is an empty space at the end.)Marks are deducted if it doesn’t make sense or if there is no attempt to explain why it is better than three line heur. (d) [10 pts] Fill out the table below by recording the results of games between the agents specified. For each table row, run at least 10 games. Record wins and losses from the perspective of Agent 1. (For games that specify a depth of 5, you may decrease to a depth of 4 if games are taking more than 10 seconds to terminate.) You can write code to automate this process and add it to agents.py if you wish. Agent 1 Agent 2 Wins Draws Losses MinimaxPlayer, depth 3, RandomPlayer three line heur MinimaxPlayer, depth 3, RandomPlayer my heuristic MinimaxPlayer, depth 5, MinimaxPlayer, depth 2, three line heur three line heur MinimaxPlayer, depth 5, MinimaxPlayer, depth 2, my heuristic my heuristic MinimaxPlayer, depth 5, MinimaxPlayer, depth 5, my heuristic three line heur SOLUTION : Full marks if every table row records the results of at least 5 games. No deduction if my heuristic doesn’t actually outperform three line heur. (e) Bonus (10% on assignment grade) On Marmoset, we will run MinimaxPlayer using your version of my_heuristic vs. another MinimaxPlayer using our own secret heuris- tics. There are five trials consisting of different heuristics. Each is a public test (meaning that you will be shown the results for each of your submissions). For each trial, your agent must win a best of five (i.e. win more games than it loses). For each trial passed, you will receive a 2% bonus on this assignment. Trials will be run at depth 4, and will time out (fail) after 10 seconds. You may assume that your agent can use half of that time. If you think you got unlucky, you can always resubmit. SOLUTION : The bonus is evaluated by Marmoset. There are 5 tests (all public) that are worth 2 points each. v1.3 Page 7 of 9

CS 486/686 Winter 2024 Assignment 1 3 Constraint Satisfaction (20 points) The N-Queens problem is to place N Queens on an N × N chessboard (grid) so that no Queen can attack any other Queen. Queens can attack one another if they are on the same row, same column, or same diagonal. Thus, a solution to the N-Queens problem has N Queens on an N × N chessboard with no two Queens on the same row, same column, or same diagonal. 1. [10 pts] Formulate the N-Queens problem as a constraint satisfaction problem (CSP) by giving the variables, their domains, and the constraints. Formulate the constraints mathematically so they are as precise as possible. SOLUTION : The variables are usually the position of the Queens on the rows (or columns), and the constraints are between each pair of Queens that they do not lie on the same column (or row) or diagonal. Variables: Q 1 , Q 2 , ...Q N where Q i = r means that the Queen on row i is in column r Domains: Q i has domain D i = { 1 , 2 , ..., N } Constraints: For any i ̸ = j , Q i ̸ = Q j and | Q i − Q j | ̸ = | i − j | 2. [10 pts] Like the N-Queens problem, the N-Octopi problem is to place N Octopi on an N × N chessboard so that no Octopus can attack any other Octopus. However, Octopi attack in a slightly different way than Queens. Octopi cannot attack on a diagonal, but can attack if they are on the same row or column. Furthermore, Octopi can attack each other if they are within one of the M × M blocks that make up the N × N grid, where M is integer, M ≥ 2, N = M 2 , and the M 2 blocks completely fill the N × N grid (so they are all aligned and adjacent). This is shown below for M = 2 (a 4 × 4 grid) and M = 3 (a 9 × 9 grid): the darker lines delineate the blocks , the top left block is shaded, and Octopi are shown in positions from which they cannot attack each other. If two Octopi were in the same block, or on the same row or on the same column, they could attack one another. Formulate the N-Octopi problem as a constraint satisfaction problem (CSP) by giving the variables, their domains, and the constraints. SOLUTION : In this case, the variables are again the positions of the Octopi on the rows (or columns, or blocks), and the constraints are between each pair of Octopi that they do not lie on the same row/column/block. The best formulation is one where the variables are the positions of Octopi within a block. In this case, there are fewer constraints since the diagonally positioned Octopi do not constrain each other. Variables: S 1 , S 2 , ..., S N where S i = r means that the Octopi on row i is in column r . Domains: S i has domain D i = { 1 , 2 , ..., N } v1.3 Page 8 of 9