If you are reading this notebook on the GitHub, please go to README and follow installation instructions to set everything up locally, it’s an interactive notebook and you need a local setup to execute the cells.¶
Welcome to Assignment 2 – Impact Isolation!¶
Your task is to create an AI that can play and win a game of Impact Isolation. Your AI will be tested against several pre-baked AIs as well as your peers’ AI systems. You will implement your AI in Python 3.7, using our provided code as a starting point.
In case we haven’t got this into your heads enough: start early!!! It is entirely possible, and probably likely, that a large part of your next 2 weeks will be devoted to this assignment, but we hope that it is worth it and you will really enjoy the assignment!
Good luck!
Table of contents¶
About the Game
Important Files
The Assignment
Submissions & Grading
Exporting the notebook
Coding time!
Section1a checkpoint!
Section1b checkpoint!
Section1c checkpoint!
Bot fight!)
About the Game¶
The rules of Impact Isolation are a variation of the original Isolation game. In the original form of the game there are two players, each with their own game piece, and a 7-by-7 grid of squares. At the beginning of the game, the first player places their piece on any square. The second player follows suit, and places their piece on any one of the available squares. From that point on, the players alternate turns moving their piece like a queen in chess (any number of open squares vertically, horizontally, or diagonally). When the piece is moved, the square that was previously occupied is blocked, and cannot be used for the remainder of the game. The first player who is unable to move their queen loses.
In this variant called Impact Isolation, each player’s piece creats an impact crater around itself when it moves more than one block in any direction. This impact crater blocks 4 locations (North, South, East, West) around the location the queen moves to, effectively reducing the queen’s mobility to that of a bishop the next turn. We start with a 9-by-9 grid in this variation. Neither players can move on or through squares blocked by this impact. For clarity, examine the scenario below:
Q1 places their queen on the board, and Q2 follows suit.
Q1 moves horizontally to the right for 4 blocks and creates an impact around it, consequently blocking some of Q2’s potential future moves. The previous location of Q1 is also blocked along with the “impact”ed locations
Q2 makes a single unit block thus not creating any impact but simply blocking the previously held location.
Q1 moves diagonally southwest.
The game will continue in a similar fashion until either of the queens has no cells left to move.
For more clarity, You can try playing the game against the Random Player or yourself using the interactive tool below¶
In [ ]:
%run helpers/verify_config.py # verify the environment setup
In [ ]:
# Following two lines make sure anything imported from .py scripts
# is automatically reloaded if edited & saved (e.g. local unit tests or players)
%load_ext autoreload
%autoreload 2
from board_viz import ReplayGame, InteractiveGame
from isolation import Board
from test_players import RandomPlayer
In [ ]:
# replace RandomPlayer() with None if you want to play for both players
#ig = InteractiveGame(RandomPlayer(), show_legal_moves=True)
ig = InteractiveGame(None, show_legal_moves=True)
One other thing you can do is simulate a game between two players and replay it.¶
Run the next cell, click inside the text input box right above the slider and press Up or Down.
In [ ]:
# Here is an example of how to visualise a game replay of 2 random players
game = Board(RandomPlayer(), RandomPlayer(), 9, 9)
winner, move_history, termination = game.play_isolation(time_limit=1000, print_moves=False)
bg = ReplayGame(game, move_history, show_legal_moves=True)
bg.show_board()
Important Files¶
While you’ll only have to edit notebook.ipynb and submit the exported submission.py, there are a number of notable files:
isolation.py: Includes the Board class and a function for printing out a game as text. Do NOT change contents of this file. We have the same file on the server’s side, so any changes will not be accounted for.
notebook.ipynb: Where you’ll implement the required methods for your agents.
player_submission_tests.py: Sample tests to validate your agents locally.
test_players.py: Contains 2 player types for you to test agents locally: RandomPlayer – chooses a legal move randomly from among the available legal moves
HumanPlayer – allows YOU to play against the AI in terminal (else use InteractiveGame in jupyter)
Additionally, we’ve included a number of local unit tests to help you test your player and evaluation function as well as to give you an idea of how the classes are used. Feel free to play around with them and add more.
The Assignment¶
In this assignment you will need to implement evaluation functions and game playing methods. Your goal is to implement the following parts of the notebook:
Evaluation functions (OpenMoveEvalFn and CustomEvalFn if you wish to use the latter)
The minimax algorithm (minimax)
Alpha-beta pruning (alphabeta)
Adjust the move() according to section you are trying to work on.
Evaluation Functions¶
These functions will inform the value judgements your AI will make when choosing moves. There are 2 classes:
OpenMoveEvalFn – Returns the number of available moves open for your player minus the number of moves available for opponent player. All baseline tests will use this function. This is mandatory
CustomEvalFn – You are encouraged to create your own evaluation function here.
Notes on these classes¶
You may write additional code within each class. However, we will only be invoking the score() function. You may not change the signature of this function.
When writing additional code please try not to copy the existing cells since they contain #export comments that is used for converting the notebook to submission.py file.
CustomPlayer¶
This is the meat of the assignment. A few notes about the class:
You are permitted to change the default values within the function signatures provided. In fact, when you have your custom evaluation function, you are encouraged to change the default values for __init__ to use the new eval function.
You are free change the contents of each of the provided methods. When you are ready with alphabeta(), for example, you should update move() to use that function instead.
You are free to add more methods to the class.
You may not create additional external functions and classes that are referenced from within this class.
Your agent will have a limited amount of time to act each turn (1 second). We will call these functions directly so don’t modify the function names and their parameter order.
We have divided the tests into three sections (mentioned in details in next grading section below), each with their own submission limit.
These are the bare minimum requirements for your AI, and the rest is up to you. You will be scored according to how well your AI performs against some baseline AIs that we provide (see Grading). If you want to improve over the base performance, here are a few suggestions:
Use partition techniques.
Store the evaluation scores for past moves.
Modify your evaluation function to account for “killer moves”.
Optimize functions that are called often.
Order nodes to maximize pruning.
Submissions & Grading¶
The grade you receive for the assignment will be determined as follows:
Section Points Condition
1a 5 points You write an evaluation function, OpenMoveEval, which returns the number of moves that the AI minus the number of moves opponent can make, and your evaluation function performs correctly on some sample boards we provide.
1a 30 points Your AI defeats a random player >= 80% of the time.
1b 20 points Your AI defeats an agent with OpenMoveEval function that uses minimax to level 2 >= 80% of the times.
1b 20 points Your AI defeats an agent with OpenMoveEval function that uses alphabeta to level 4 >= 70% of the times.
1c 20 points Your AI defeats an agent with OpenMoveEval function that uses iterative deepening and alpha-beta pruning >= 70% of the time.
1c 5 points (Extra Credit) Your AI defeats an agent with Peter’s secret evaluation function that uses iterative deepening and alpha-beta pruning and optimizes various aspects of the game player >= 80% of the time
We have changed the last 5 points to Extra Credit this semester, so the assignment will be graded out ot 95. As you can see from the table there are three autograded sections, each having the following submission frequency restrictions:
Section 1a – 1 submission per 30 minutes.
Section 1b – 3 submissions per 360 minutes.
Section 1c – 3 submissions per 360 minutes.
We will provide you checkpoints and instructions below once you are ready to submit for each of these sections.
Exporting the notebook¶
In order to do get your submission file ready you will need to make sure have saved your notebook and run:
In [ ]:
# %run helpers/notebook2script section1a
Once execution is complete open autogenerated submission.py and verify that it contains all of the imports, functions and classes you are required to implement. Only then you can proceed to the Gradescope for submission.
Do NOT erase the #export at the top of any cells as it is used by notebook2script.py to extract cells for submission.
Coding time!¶
Importing External Modules¶
In [ ]:
# Following two lines make sure anything imported from .py scripts
# is automatically reloaded if edited & saved (e.g. local unit tests or players)
%load_ext autoreload
%autoreload 2
import player_submission_tests as tests
from test_players import HumanPlayer, RandomPlayer
In [ ]:
#export
import time
from isolation import Board
If you have discussed this assignment at a whiteboard level, got help from Piazza or have used external resources (not provided by the instructors) that you may want to cite, please do so in the cell below as a python comment! (no need to cite python or included packages documentation)
In [ ]:
#export
# Credits if any
# 1)
# 2)
# 3)
OpenMoveEvalFn¶
This is where you write your evaluation function to evaluate the state of the board.
The test cases below the code are expected to pass locally before you make a submission.
Hints: Remember when calling the below helpful methods that you do need to inform both methods of who your player is (consult those methods’ docstrings for more information).
Here are a couple methods you might find useful to implement OpenMoveEvalFn():
In [ ]:
Board.get_player_moves??
In [ ]:
Board.get_opponent_moves??
In [ ]:
#export
class OpenMoveEvalFn:
def score(self, game, my_player=None):
“””Score the current game state
Evaluation function that outputs a score equal to how many
moves are open for AI player on the board minus how many moves
are open for Opponent’s player on the board.
Note:
If you think of better evaluation function, do it in CustomEvalFn below.
Args
game (Board): The board and game state.
my_player (Player object): This specifies which player you are.
Returns:
float: The current state’s score. MyMoves-OppMoves.
“””
# TODO: finish this function!
raise NotImplementedError
######################################################################
########## DON’T WRITE ANY CODE OUTSIDE THE FUNCTION! ################
######## IF YOU WANT TO CALL OR TEST IT CREATE A NEW CELL ############
######################################################################
##### CODE BELOW IS USED FOR RUNNING LOCAL TEST DON’T MODIFY IT ######
tests.correctOpenEvalFn(OpenMoveEvalFn)
################ END OF LOCAL TEST CODE SECTION ######################
About the local test above¶
You should look at the test in player_submission_tests.py to verify that your evaluation function is correct. If you want to edit the test (which you most definitely can), then edit the source code back in player_submission_tests.py.
CustomPlayer¶
CustomPlayer is the player object that will be used to play the game of isolation.
The move() method will be used to pass over to you the current state of the game board.
The content of the move() method will be changed by you according to the section you are attempting to pass. While you can use Iterative Deepening & Alpha-Beta (ID+AB) to beat our agents in all of the sections, going directly for ID+AB is error prone. As such, we highly recommend you to start with MiniMax (MM), then implement Alpha-Beta (AB), and only then go for ID+AB.
By default, right now move() calls minimax() as you can see below.
You are not allowed to modify the function signatures or class signatures we provide. However, in case you want to have an additonal parameter you can do it at the very end of parameter list (see examples below). However, it must have a default value and you shouldn’t expect it to be passed on the server-side (i.e. Gradescope). Thus, Gradescope will be using the default value.
Originally:
def move(self, game, time_left):
…
Adding a new argument with default parameter.
def move(self, game, time_left, new_parameter=default_value):
…
Don’t do this, you will get an error in the auto-grader and lose your submission:
def move(self, game, time_left, new_parameter):
…
def move(self, new_parameter, game, time_left):
…
In [ ]:
#export
class CustomPlayer:
# TODO: finish this class!
“””Player that chooses a move using your evaluation function
and a minimax algorithm with alpha-beta pruning.
You must finish and test this player to make sure it properly
uses minimax and alpha-beta to return a good move.”””
def __init__(self, search_depth=2, eval_fn=OpenMoveEvalFn()):
“””Initializes your player.
if you find yourself with a superior eval function, update the default
value of `eval_fn` to `CustomEvalFn()`
Args:
search_depth (int): The depth to which your agent will search
eval_fn (function): Evaluation function used by your agent
“””
self.eval_fn = eval_fn
self.search_depth = search_depth
def move(self, game, time_left):
“””Called to determine one move by your agent
Note:
1. Do NOT change the name of this ‘move’ function. We are going to call
this function directly.
2. Call alphabeta instead of minimax once implemented.
Args:
game (Board): The board and game state.
time_left (function): Used to determine time left before timeout
Returns:
tuple: (int,int): Your best move
“””
best_move, utility = minimax(self, game, time_left, depth=self.search_depth)
return best_move
def utility(self, game, my_turn):
“””You can handle special cases here (e.g. endgame)”””
return self.eval_fn.score(game, self)
###################################################################
########## DON’T WRITE ANY CODE OUTSIDE THE CLASS! ################
###### IF YOU WANT TO CALL OR TEST IT CREATE A NEW CELL ###########
###################################################################
Minimax¶
This is where you will implement the minimax algorithm. The final output of your minimax should come from this method and this is the only method that Gradescope will call when testing minimax.
With MM implemented you are expected to pass: Defeat a Random Player >=90% of the time.
Useful functions: The useful methods will probably all come from isolation.py. A couple of particularly interesting ones could be forecast_move() and your score() method from OpenMoveEvalFn. Remember the double question mark trick from Assignment 0 if you feel you are flipping between files too much!
In [ ]:
#export
def minimax(player, game, time_left, depth, my_turn=True):
“””Implementation of the minimax algorithm.
Args:
player (CustomPlayer): This is the instantiation of CustomPlayer()
that represents your agent. It is used to call anything you
need from the CustomPlayer class (the utility() method, for example,
or any class variables that belong to CustomPlayer()).
game (Board): A board and game state.
time_left (function): Used to determine time left before timeout
depth: Used to track how deep you are in the search tree
my_turn (bool): True if you are computing scores during your turn.
Returns:
(tuple, int): best_move, val
“””
# TODO: finish this function!
raise NotImplementedError
######################################################################
########## DON’T WRITE ANY CODE OUTSIDE THE FUNCTION! ################
######## IF YOU WANT TO CALL OR TEST IT CREATE A NEW CELL ############
######################################################################
##### CODE BELOW IS USED FOR RUNNING LOCAL TEST DON’T MODIFY IT ######
tests.beatRandom(CustomPlayer)
tests.minimaxTest(CustomPlayer, minimax)
################ END OF LOCAL TEST CODE SECTION ######################
Section 1a Checkpoint¶
Now it’s a good time to submit for Section1a – See Exporting the notebook¶
In case you want to submit please uncomment and run the cell below.
Your code will be generated in the folder named section1a, please upload submission.py file to Gradescope
In [ ]:
# %run helpers/notebook2script section1a
AlphaBeta¶
This is where you will implement the alphabeta algorithm. The final output of your alphabeta should come from this method.
With A/B implemented you are expected to pass: Minimax level 2 >= 70% of the time
Useful functions: The useful methods will probably all come from isolation.py. A couple of particularly interesting ones could be forecast_move() and your score() method from OpenMoveEvalFn. Remember the double question mark trick from Assignment 0 if you feel you are flipping between files too much!
In [ ]:
#export
def alphabeta(player, game, time_left, depth, alpha=float(“-inf”), beta=float(“inf”), my_turn=True):
“””Implementation of the alphabeta algorithm.
Args:
player (CustomPlayer): This is the instantiation of CustomPlayer()
that represents your agent. It is used to call anything you need
from the CustomPlayer class (the utility() method, for example,
or any class variables that belong to CustomPlayer())
game (Board): A board and game state.
time_left (function): Used to determine time left before timeout
depth: Used to track how deep you are in the search tree
alpha (float): Alpha value for pruning
beta (float): Beta value for pruning
my_turn (bool): True if you are computing scores during your turn.
Returns:
(tuple, int): best_move, val
“””
# TODO: finish this function!
raise NotImplementedError
######################################################################
########## DON’T WRITE ANY CODE OUTSIDE THE FUNCTION! ################
######## IF YOU WANT TO CALL OR TEST IT CREATE A NEW CELL ############
######################################################################
##### CODE BELOW IS USED FOR RUNNING LOCAL TEST DON’T MODIFY IT ######
# tests.name_of_the_test #you can uncomment this line to run your test
################ END OF LOCAL TEST CODE SECTION ######################
About the lack of a local test above¶
Notice that we do not have any code here. We want you to learn to write your own test cases, so feel free to get creative! You can always create the test in player_submission_tests.py and then run it over here in a manner identical to how local tests have been run so far.
IMPORTANT
Now remember that the server (i.e. Gradescope) uses move() to interface with your code. So now you will need to update the move() method (which you saw earlier in the CustomPlayer class) to call alphabeta() so as to return the best move.
Section 1b Checkpoint¶
Now it’s a good time to submit for Section1b – See Exporting the notebook¶
In case you want to submit please uncomment and run the cell below.
Your code will be generated in the folder named section1b. Please upload submission.py file to Gradescope
In [ ]:
# %run helpers/notebook2script section1b
That does not cover all 100 points though!¶
You’re right, and that’s on purpose. Each of the bullets below try to walk you through how you may want to think about beating the remaining agents.
First up is the alphabeta agent. Vanilla alphabeta (that is, alphabeta with no optimization) may not do so well against this agent. However, any agent that searches deeper with the same algorithm probably has a bigger advantage. You may learn about a method that allows your algorithm to search in such a way that you can find the maximum search depth without running out of time. This will probably come up in class or you can read through the book to find out what you are looking for.
Next to beat is the agent with iterative deepening. This one is a little harder to think about, given that you may have used all the tools that you may think of to try a make a “better” agent. But you may have just implemented the evaluation function that was discussed in class. Maybe we can do better – like checking for winning moves and prioritizing those! Or if you are feeling really creative, you can always try editing the CustomEvalFn below this cell and come up with an awesome idea of your own.
Now to Peter’s agent with the secret evaluation function (Extra Credit). Here we have nothing to tell you. Use everything in your toolbox and within the class rules to defeat it. This is by far the hardest 5 points to get! Good luck and have fun!
Remember that you may want to edit the methods in the cell with the CustomPlayer class to try and implement some of the above. You are certainly free to as long as you adhere to the general rules about editing provided code (which can be found by reading the cell above the CustomPlayer code).
CustomEvalFn¶
Edit the below to come up with your very own improved evaluation function. The typical rules about how you can and cannot edit the code we have given (namely, the function signature rules) apply here.
IMPORTANT: There’s one big thing to keep in mind when the below is exported to submission.py. When the export happens, your resulting submission.py is parsed top-down, so you may have errors when trying to run that file with a custom evaluation function. The fix is to make sure this does not happen is to follow these steps: Use “Edit->Move Cell Up” to move the below cell to just above the first time you call CustomEvalFn (probably in CustomPlayer) -> Now run helpers/notebook.ipynb -> Submit the resulting submission.py to Gradescope to test your submission.
In [ ]:
#export
class CustomEvalFn:
def __init__(self):
pass
def score(self, game, my_player=None):
“””Score the current game state.
Custom evaluation function that acts however you think it should. This
is not required but highly encouraged if you want to build the best
AI possible.
Args:
game (Board): The board and game state.
my_player (Player object): This specifies which player you are.
Returns:
float: The current state’s score, based on your own heuristic.
“””
# TODO: finish this function!
raise NotImplementedError
######################################################################
############ DON’T WRITE ANY CODE OUTSIDE THE CLASS! #################
######## IF YOU WANT TO CALL OR TEST IT CREATE A NEW CELL ############
######################################################################
Now you may need to change the move() method again in the CustomPlayer class. In addition, you may also need to edit eval_fn() in CustomPlayer to have your agent use the above custom evaluation function when it is playing against the test agents.
Section 1c Checkpoint¶
Now it’s a good time to submit for Section1c – See Exporting the notebook¶
In case you want to submit please uncomment and run the cell below.
Your code will be generated in the folder named section1c. Please upload submission.py file to Gradescope
In [ ]:
# %run helpers/notebook2script section1c
Botfight (Extra Credit)¶
In addition to the basic assignment, you will have the option to compete against your peers for the glory of being the Spring 2023 AI-Game-Playing champ. We’ll set up a system to pit your AI against others, and we’ll be handing out extra credit for the top players. May the odds be ever in your favor.
If you compete in the AI tournament and your agent finishes in the top 10, you will receive bonus points for this assignment (bonus points are added to the grades of each assignment. Not to final score. ):
: 12 bonus points added to the assignment score.
Second Best: 10 bonus points.
Third Best: 7 bonus points.
Fourth to Tenth Best: 5 bonus points.
To make your submission simply upload a file called submission.py (similar to what you have been doing so far) with your best agent implementation to Canvas.
Contribute to the class¶
If you find any typos and/or have some issues or suggestions on how to improve this or any future assignments, please feel free to create a Pull Request or make a Piazza post.