## What’s The Project About?

OG AI Algorithms like MixMax and AlphaBeta Pruning play a 2000 year old board game - Nine Men’s Morris

GitHub Link: *github.com/vedangwartikar/9-Mens-Morris-using-AI*

## 1. How to execute

### About

### Example

- The program should be run in the following manner

- It can also be run with an optional parameter
*—print_board*for a visual representation of the board after a move has been played

## 2. MiniMax Algorithm

### Opening Phase

- After running the
`opening_simulator.sh`

which simulates the 8 moves using the MiniMax algorithm for White and Black players consecutively, we get the following board. Here we can see that the White player was able to form a (vertical) mill and take out one of the Black player’s pieces. The Black player was also able to block 2 potential mills of the White player.

### Midgame and EndGame

- In the following example, the White player closes a mill by moving its piece and removes a Black piece from the bottom right

## 3. Alpha-Beta Pruning Algorithm

### Opening Phase

- For the following input board, the MiniMax and Alpha-Beta Pruning algorithms (ply 3) smartly place the White player’s piece on the top right corner making it a possibility of at least 1 mill irrespective of the Black player’s next move. The
**positions evaluated by the static estimation function**and the**Minimax estimate**have been compared for both algorithms. We can clearly see that Alpha-Beta Pruning is very efficient in minimizing the unnecessary computations done by the MiniMax algorithm.

### MidGame and Endgame Phase

- For the following input board, the MiniMax and Alpha-Beta Pruning algorithms (ply 5) the White player’s piece at position 3 is moved to the top. The move is fairly simple, but as seen below the positions evaluated by Alpha-Beta Pruning are
**360**and that of MiniMax is**4643**. Therefore,**Alpha-Beta is 13x more efficient that the MiniMax**algorithm in terms if the positions being evaluated.

## 4. Improved MiniMax Algorithm

### Opening Phase

- The static estimation function is tweaked to form a potential double mill at an intersection. The basic MiniMax algorithm for Black player does not consider such scenarios at the intersection and places its pieces in the ascending order.
The formation of a potential mill is highlighted by
**[ ]**in both boards.

Feel free to contribute through a PR or report any issues here.