$24
Intro to AI Homework 2 Solution
Search [50 points]
s
4
2
a
1
b
n
h(n)
2
6
3
s
5
1
5
a
2
b
3
c
t
d
c
1
d
4
Figure 1: The graph.
t
0
Table 1: The heuristics.
Using the graph in Figure 1 and the heuristic function in Table 1, search for the path from node s to node t using the following algorithms:
Breadth-First Search [7 points] Uniform-Cost Search [12 points] Depth-First Search [7 points]
Greedy Best-First Search [12 points]
A* [12 points]
To order the nodes to visit, when there is ambiguity, solve it using alphabetical ordering. For each algorithm, report
The list of visited nodes in the order of visit; The best path found from s to t;
CS4341: Intro to AI—Homework 2
2
The complete work table as shown below. If you make correction to the table while calculating it, just report the nal version.
Breadth-First Search
Uniform-Cost Search
node
came from
visited?
node
came from
g(n)
visited?
s
s
a
a
b
b
c
c
d
d
t
t
Depth-First Search
Greedy Best-First Search
node
came from
visited?
node
came from
h(n)
visited?
s
s
a
a
b
b
c
c
d
d
t
t
A*
node
came from
g(n)
f(n)
visited?
s
a
b
c
d
t
Adversarial Search [50 points]
2.1 Introduction
This is a 2-weeks project that will span HW2 and HW3. For this weekly homework, we ask you to provide the design of your solution. The graded deliverable is a description of your design. The deliverable of HW3 will be the implementation of your design. It is strongly suggested that you start your implementation early, and engage with the professor and the TAs to make sure you’re on the right path.
The aim of this project is to make an AI for the game Connect-N, which is a more general version of Connect-4. If you don’t know Connect-4, try it out here: https://www.gimu.org/connect-four-js/ jQuery/alphabeta/index.html.
2.2 The Game Code
The code is stored in a GitHub repository: https://github.com/NESTLab/CS4341-projects/. You can download it from the command line with the following command:
$ git clone https :// github . com / NESTLab / CS4341 - projects /
The code for this project is located in CS4341-projects/ConnectN. There are ve les:
run.py: the main script that creates and executes a game;
game.py: de nes the Game class, which manages the board and the players and declares the winner;
board.py: de nes the Board class, which contains the state of the board;
agent.py: de nes the Agent class, along with two sample agents that you can use to test your AI: RandomAgent, which picks a move completely at random, and InteractiveAgent, which allows a human to play the game;
alpha_beta_agent.py: de nes the AlphaBetaAgent class, which you must implement to complete this project.
Bug bounty: This code was made by the professor on purpose for this project, mostly by night and fueled by co ee. There might be bugs. For each bug you might nd, submit a GitHub pull request with the x and you will get 5 extra points on your HW3 grade. The extra points will be awarded only to the rst one to nd a speci c bug and provide a solution.
2.3 Your Task
Your task is to complete the AlphaBetaAgent class, whose de nition is as follows:
import math
import agent
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# Alpha - Beta Search Agent #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
class A l p h a B e t a A g e n t ( agent . Agent ):
""" Agent that uses alpha - beta search """
def __init__ ( self , name , m ax _de pt h ):
super (). __init__ ( name )
self . m ax _d ept h = m ax _d ep th
def go ( self , brd ):
""" Search for the best move ( choice of column for the token ) """
# Your code here
def g e t _ s u c c e s s o r s ( self , brd ):
Returns the re ac ha ble boards from the given board brd .
The return value is a tuple ( new board state , column number where last token was added ). """
freecols = brd . f re e_c ol s ()
if not freecols :
return []
succ = []
for col in freecols :
nb = brd . copy ()
nb . a dd _t oke n ( col )
succ . append (( nb , col ))
return succ
As you can see, you must implement the AlphaBetaAgent.go() method. This method must perform a minimax search with alpha-beta pruning, as explained in class.
To help you with the implementation, the method AlphaBetaAgent.get_successors() is already written: this method, given a Board object, goes through all the legal moves for the current player and returns a list of tuples. Each tuple has, as rst element, a new board and, as second element, the action performed to get to that board. If the board given as input is full, i.e., no more tokens can be added, AlphaBetaAgent.get_successors() returns an empty list.
You can modify AlphaBetaAgent in any way you want. For instance, you can rewrite AlphaBetaAgent.get_successors() if you prefer a di erent de nition. However, do not modify the other les we provide. Those must remain the same, because we will set up a tournament after the deadline of HW3.
In the tournament, we will limit the time to pick a move to 15 seconds. If your AI takes more than 15 seconds to return a move, it will lose the game. Your AI will lose the game also if it returns a wrong move.
2.4 Finding a Good Evaluation Function
The main challenge in your work will be to devise a good evaluation function for non-terminal boards. In other words, given a board in which no player has already won, who is most likely to win?
You can get some ideas from these websites, which focus on Connect-4 rather than Connect-N:
http://tromp.github.io/c4/c4.html http://blog.gamesolver.org/
https://www.gimu.org/connect-four-js/
You are encouraged to look on the Internet for research, inspiration, and tips. Also, engage with the professor and the TAs about your approach.
Deliverables
The deliverable. Your main deliverable is a document, either in electronic format (preferred) or neatly hand-written (if we can’t read something, we’ll consider it not done). In this document, report both your solution for Exercise 1 and the solution design for Exercise 2.
About Exercise 2. Regarding Exercise 2, describe the design of your solution. Do not summarize the purpose of the project. Rather, explain clearly the following design choices:
Code structure: the methods you plan to add to AlphaBetaAgent, any extra class you want to create (provide a UML diagram if you plan on adding classes), etc.
Evaluation function: describe your evaluation function, along with pseudocode and/or a Python implementation if you already have one. If you have multiple ideas about evaluation functions, discuss them all, and comment on their feasibility.
Make sure to add references to the websites/documents you used.
Submitting. The nal deliverable is a single PDF le submitted on Canvas. If you have Python code to show, do not add extra les; rather, report the code in the document.
What’s next? The actual code for Connect-N will be the deliverable of HW3. We strongly suggest you to start your implementation early, because this project is harder than it looks. In HW3, we will also ask you to try your AI against RandomAgent 10 times for N = f4; 5g, and report on how many times your AI won against it. If you have multiple evaluation functions and want to try them against each other, you’ll be awarded 25 extra points for each evaluation function.
