README.md 4.2 KB
Build a Game-Playing Agent
This game-playing agent uses techniques such as Iterative Deepening, Minimax, and Alpha-Beta Pruning to compete in the game of Isolation (a two-player discrete competitive game with perfect information). The different heuristics used are then compared to find the best heuristic.
About
This project is an adversarial search agent to play the game 'Isolation.' Isolation is a deterministic, two-player board game of perfect information in which the players alternate turns moving a single piece from one cell to another. Whenever either player occupies a cell, that cell becomes blocked for the remainder of the game. The first player with no remaining legal moves loses, and the opponent is declared the winner.
This project uses a version of Isolation where each agent is restricted to L-shaped movements (like a knight in chess) on a rectangular grid (like a chessboard). The agents can move to an open cell on the board that is 2-rows and 1-column or 2-columns and 1-row away from their current position on the board. Movements are blocked at the edges of the board (the board does not wrap around). However, the player can "jump" blocked or occupied spaces (just like a knight in chess).
Additionally, agents will have a fixed time limit each turn to search for the best move and respond. If the time limit expires during a player's turn, that player forfeits the match, and the opponent wins.
Requirements
This project requires Python 3. It is recommended to use Anaconda, a pre-packaged Python distribution that contains all of the necessary libraries and software for this project. Try using the environment provided in this folder.
Using the Board Visualization
The isoviz folder contains a modified version of chessboard.js that can animate games played on a 7x7 board. In order to use the board, you must run a local web server by running python -m SimpleHTTPServer 8000 from your project directory (you can replace 8000 with another port number if that one is unavailable), then open your browser to http://localhost:8000 and navigate to the /isoviz/display.html page. Enter the move history of an isolation match (i.e., the array returned by the Board.play() method) into the text area and run the match. Refresh the page to run a different game.
Files
game_agent.py– Contains the code for the game-playing agent (see CustomPlayer class).agent_test.py- Provided by @udacity to unit testgame_agent.pyimplementation.tournament.py- Provided by the @udacity staff to evaluate the performance of the game-playing agent.heuristic_analysis.pdf– Contains the analysis of the various heuristics implemented in the game_agent. The metrics are obtained fromtournament.py.research_review.pdf– Reviews IBM's Deep Blue's seminal paper. A detailed blog post can be read on my blog on [this link]()
Output (tournament.py)
*************************
Evaluating: ID_Improved
*************************
Playing Matches:
----------
Match 1: ID_Improved vs Random Result: 15 to 5
Match 2: ID_Improved vs MM_Null Result: 14 to 6
Match 3: ID_Improved vs MM_Open Result: 16 to 4
Match 4: ID_Improved vs MM_Improved Result: 12 to 8
Match 5: ID_Improved vs AB_Null Result: 14 to 6
Match 6: ID_Improved vs AB_Open Result: 12 to 8
Match 7: ID_Improved vs AB_Improved Result: 11 to 9
Results:
----------
ID_Improved 67.14%
*************************
Evaluating: Student
*************************
Playing Matches:
----------
Match 1: Student vs Random Result: 17 to 3
Match 2: Student vs MM_Null Result: 14 to 6
Match 3: Student vs MM_Open Result: 14 to 6
Match 4: Student vs MM_Improved Result: 13 to 7
Match 5: Student vs AB_Null Result: 18 to 2
Match 6: Student vs AB_Open Result: 13 to 7
Match 7: Student vs AB_Improved Result: 16 to 4
Results:
----------
Student 75.00%