If you are reading this notebook on the GitHub, please go to README and follow installation instructions to set everything up locally, its an interactive notebook and you need a local setup to execute the cells.
Welcome to Assignment 1 Trailblazer Isolation!
Your task is to create an AI that can play and win a game of Trailblazer Isolation. Your AI will be tested against several prebaked 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 havent 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
1. About the Game
2. Important Files
3. The Assignment
4. Submissions Grading
5. Exporting the notebook
6. Coding time!
7. Section1a checkpoint!
8. Section1b checkpoint!
9. Section1c checkpoint!
10. Bot fight!
About the Game
The rules of Trailblazer Isolation are a simple variation of the original Isolation. In the original form of the game there are two players, each with their own game piece, and a 7by7 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 Trailblazer variant, each player leaves behind a temporary trail when they move their queen. This trail places a temporary block in every square the queen passes through. The opponent cannot move on or through squares blocked by this trail, but once the opponent makes a move the trail will disappear. For clarity, examine the scenario below:
Q1 places their queen on the board, and Q2 follows suit.
Q1 makes a diagonal move across the board and leaves behind a temporary trail, blocking some of Q2s potential moves.
Q2 makes a move, leaving behind her own trail. After Q2 makes this move, the trail left by Q1 in the turn prior vanishes.
You can try playing the game against the Random Player or yourself using the interactive tool below.
In:
run helpersverifyconfig.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
loadext autoreload
autoreload 2
from boardviz import ReplayGame, InteractiveGame
from isolation import Board
from testplayers import RandomPlayer
In:
replace RandomPlayer with None if you want to play for both players
ig InteractiveGameRandomPlayer, showlegalmovesTrue
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 BoardRandomPlayer, RandomPlayer, 7, 7
winner, movehistory, termination game.playisolationtimelimit1000, printmovesFalse
bg ReplayGamegame, movehistory, showlegalmovesTrue
bg.showboard
Important Files
While youll only have to edit notebook.ipynb and submit the exported submission.py, there are a number of notable files:
1. 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 servers side, so any changes will not be accounted for.
2. notebook.ipynb: Where youll implement the required methods for your agents.
3. playersubmissiontests.py: Sample tests to validate your agents locally.
4. testplayers.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, weve 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:
1. Evaluation functions OpenMoveEvalFn and CustomEvalFn if you wish to use the latter
2. The minimax algorithm minimax
3. Alphabeta pruning alphabeta
4. 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
1. 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.
2. 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 dont 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 90 of the time.
1b
20 points
Your AI defeats an agent with OpenMoveEval function that uses minimax to level 2 70 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 alphabeta pruning 70 of the time.
1c
5 points
Your AI defeats an agent with Peters secret evaluation function that uses iterative deepening and alphabeta pruning and optimizes various aspects of the game player 80 of the time
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 helpersnotebook2script 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
loadext autoreload
autoreload 2
import playersubmissiontests as tests
from testplayers 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.getplayermoves??
In:
Board.getopponentmoves??
In:
export
class OpenMoveEvalFn:
def scoreself, game, myplayerNone:
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 Opponents 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.
myplayer Player object: This specifies which player you are.
Returns:
float: The current states score. MyMovesOppMoves.
TODO: finish this function!
raise NotImplementedError
DONT 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 DONT MODIFY IT
tests.correctOpenEvalFnOpenMoveEvalFn
END OF LOCAL TEST CODE SECTION
About the local test above
If you want to edit the test which you most definitely can, then edit the source code back in playersubmissiontests.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 AlphaBeta IDAB to beat our agents in all of the sections, going directly for IDAB is error prone. As such, we highly recommend you to start with MiniMax MM, then implement AlphaBeta AB, and only then go for IDAB.
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 shouldnt expect it to be passed on the serverside i.e. Gradescope. Thus, Gradescope will be using the default value.
Originally:
def moveself, game, timeleft:
…
Adding a new argument with default parameter.
def moveself, game, timeleft, newparameterdefaultvalue:
…
Dont do this, you will get an error in the autograder and lose your submission:
def moveself, game, timeleft, newparameter:
…
def moveself, newparameter, game, timeleft:
…
In:
export
class CustomPlayer:
TODO: finish this class!
Player that chooses a move using your evaluation function
and a minimax algorithm with alphabeta pruning.
You must finish and test this player to make sure it properly
uses minimax and alphabeta to return a good move.
def initself, searchdepth3, evalfnOpenMoveEvalFn:
Initializes your player.
if you find yourself with a superior eval function, update the default
value of evalfn to CustomEvalFn
Args:
searchdepth int: The depth to which your agent will search
evalfn function: Evaluation function used by your agent
self.evalfn evalfn
self.searchdepth searchdepth
def moveself, game, timeleft:
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.
timeleft function: Used to determine time left before timeout
Returns:
tuple: int,int: Your best move
bestmove, utility minimaxself, game, timeleft, depthself.searchdepth
return bestmove
def utilityself, game, myturn:
You can handle special cases here e.g. endgame
return self.evalfn.scoregame, self
DONT 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 forecastmove 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 minimaxplayer, game, timeleft, depth, myturnTrue:
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.
timeleft function: Used to determine time left before timeout
depth: Used to track how deep you are in the search tree
myturn bool: True if you are computing scores during your turn.
Returns:
tuple, int: bestmove, val
TODO: finish this function!
raise NotImplementedError
return bestmove, bestval
DONT 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 DONT MODIFY IT
tests.beatRandomCustomPlayer
tests.minimaxTestCustomPlayer, minimax
END OF LOCAL TEST CODE SECTION
Section 1a Checkpoint
Now its 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 helpersnotebook2script section1a
AlphaBeta
This is where you will implement the alphabeta algorithm. The final output of your alphabeta should come from this method.
With AB 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 forecastmove 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 alphabetaplayer, game, timeleft, depth, alphafloatinf, betafloatinf, myturnTrue:
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.
timeleft 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
myturn bool: True if you are computing scores during your turn.
Returns:
tuple, int: bestmove, val
TODO: finish this function!
raise NotImplementedError
return bestmove, val
DONT 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 DONT MODIFY IT
tests.nameofthetest 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 playersubmissiontests.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 its 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 helpersnotebook2script section1b
That does not cover all 100 points though!
Youre right, and thats 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 Peters agent with the secret evaluation function. 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: Theres 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 topdown, 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 EditMove Cell Up to move the below cell to just above the first time you call CustomEvalFn probably in CustomPlayer Now run helpersnotebook.ipynb Submit the resulting submission.py to Gradescope to test your submission.
In:
export
class CustomEvalFn:
def initself:
pass
def scoreself, game, myplayerNone:
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.
myplayer Player object: This specifies which player you are.
Returns:
float: The current states score, based on your own heuristic.
TODO: finish this function!
raise NotImplementedError
DONT 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 evalfn in CustomPlayer to have your agent use the above custom evaluation function when it is playing against the test agents.
Section 1c Checkpoint
Now its 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 helpersnotebook2script 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 2020 AIGamePlaying champ. Well set up a system to pit your AI against others, and well 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. :
Best Overall: 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 andor 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.