Project1.docx

Project 1 – Minimax Search with Alpha-Beta Pruning

In this project, you will write a Python program for a miniature “Isolation” game on a 3-by-3 board. Your program should make a suggestion about the best possible move for Player 1 (the player represented by Max nodes on the Min-Max search tree), and once Player makes his move, make the best move for Player 2 (the player represented by Min nodes on the Min-Max search tree), and iteratively enter rounds of moves till the end of game, in which one player cannot move and thus become the loser.

In the game of isolation, at the beginning, Player 1 gets to place his piece anywhere on the game board, and Player 2 can place his piece anywhere remaining. From then on, two players move like queens in chess, i.e., for the next move either player can go any square that's horizontal or vertical or diagonal from the current position, except that one can't move through the opponent’s piece. Also, squares between the start and the end position remain obtainable for future moves. In other words, it's just where the piece lands that becomes unobtainable for future moves. Moreover, players do not attack each other. The players cannot go outside the boundaries of the game board, nor through a position that is currently or was previously occupied.

The objective of the game is to be the last player to move. The first player to get isolated (i.e., unable to move on their turn), loses.

You are given a Python program for a tic-tac-toe game on a 3-by-3 board. You need to modify the program such that it plays the isolation game.

Thoroughly test your program to make sure it works correctly in every situation. Submit your program file (the Python source codes in .py or .ipynb format).