Usage: python3 <_FILE_NAME_>.py board1.txt board2.txt depth [-h] [--print_board [print_board]]

Generates the next move for the White/Black player using MiniMax and Alpha-Beta Pruning algorithms

positional arguments:
  board1.txt            Input File Name
  board2.txt            Output File Name
  depth                 Depth of the search tree

optional arguments:
  -h, --help            show this help message and exit
  --print_board [print_board]
                        Print the board

• The program should be run in the following manner

  ╰─ cat board1.txt
  xxxxxxxxxxxxxxxxxxxxx
  ╰─ python3 MiniMaxOpening.py board1.txt board2.txt 2
  Board Position: Wxxxxxxxxxxxxxxxxxxxx.
  Positions evaluated by static estimation: 420.
  MINIMAX estimate: 0.
  

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

  ╰─ cat board1.txt
  xxxxxxxxxxxxxxxxxxxxx
  ╰─ python3 MiniMaxOpening.py board1.txt board2.txt 2 --print_board
  Input Board:
  x--------x--------x
  |        |        |
  |  x-----x-----x  |
  |  |     |     |  |
  |  |  x--x--x  |  |
  |  |  |     |  |  |
  x--x--x     x--x--x
  |  |  |     |  |  |
  |  |  x-----x  |  |
  |  |           |  |
  |  x-----------x  |
  |                 |
  x-----------------x
  Output Board:
  x--------x--------x
  |        |        |
  |  x-----x-----x  |
  |  |     |     |  |
  |  |  x--x--x  |  |
  |  |  |     |  |  |
  x--x--x     x--x--x
  |  |  |     |  |  |
  |  |  x-----x  |  |
  |  |           |  |
  |  x-----------x  |
  |                 |
  W-----------------x
  Board Position: Wxxxxxxxxxxxxxxxxxxxx.
  Positions evaluated by static estimation: 420.
  MINIMAX estimate: 0.
  

• 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.

Input Board:
B--------x--------x
|        |        |
|  W-----x-----W  |
|  |     |     |  |
|  |  x--x--x  |  |
|  |  |     |  |  |
W--W--B     W--B--x
|  |  |     |  |  |
|  |  W-----B  |  |
|  |           |  |
|  W-----------B  |
|                 |
W-----------------B
Output Board:
B--------x--------x
|        |        |
|  W-----B-----W  |
|  |     |     |  |
|  |  x--x--x  |  |
|  |  |     |  |  |
W--W--B     W--B--x
|  |  |     |  |  |
|  |  W-----B  |  |
|  |           |  |
|  W-----------B  |
|                 |
W-----------------B
Board Position: WBWBWBWWBWBxxxxWBWBxx.
Positions evaluated by static estimation: 78.
MINIMAX estimate: 2.

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

╰─ cat board1.txt
xBWBxWBBxxBBxWxWxBBWW
╰─ python3 MiniMaxGame.py board1.txt board2.txt 2 --print_board
Input Board:
B--------W--------W
|        |        |
|  W-----x-----B  |
|  |     |     |  |
|  |  x--W--x  |  |
|  |  |     |  |  |
B--B--x     x--B--B
|  |  |     |  |  |
|  |  x-----W  |  |
|  |           |  |
|  W-----------B  |
|                 |
x-----------------B
Output Board:
B--------W--------W
|        |        |
|  x-----W-----B  |
|  |     |     |  |
|  |  x--W--x  |  |
|  |  |     |  |  |
B--B--x     x--B--B
|  |  |     |  |  |
|  |  x-----W  |  |
|  |           |  |
|  W-----------B  |
|                 |
x-----------------x
Board Position: xxWBxWBBxxBBxWxxWBBWW.
Positions evaluated by static estimation: 90.
MINIMAX estimate: -1017.

• 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.

╰─ cat board1.txt
xxWBxBxxxxxWxxWxBxWxx
╰─ python3 MiniMaxOpening.py board1.txt board2.txt 3 --print_board
Input Board:
W--------x--------x
|        |        |
|  x-----B-----x  |
|  |     |     |  |
|  |  x--x--W  |  |
|  |  |     |  |  |
x--x--x     x--x--W
|  |  |     |  |  |
|  |  x-----B  |  |
|  |           |  |
|  W-----------B  |
|                 |
x-----------------x
Output Board:
W--------x--------W
|        |        |
|  x-----B-----x  |
|  |     |     |  |
|  |  x--x--W  |  |
|  |  |     |  |  |
x--x--x     x--x--W
|  |  |     |  |  |
|  |  x-----B  |  |
|  |           |  |
|  W-----------B  |
|                 |
x-----------------x
  
-------- MiniMax Algorithm --------
Board Position: xxWBxBxxxxxWxxWxBxWxW.
Positions evaluated by static estimation: 2616.
MINIMAX estimate: 3.
  
-------- Alpha-Beta Pruning --------
Board Position: xxWBxBxxxxxWxxWxBxWxW.
Positions evaluated by static estimation: 875.
MINIMAX estimate: 3.

• 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.

╰─ cat board1.txt
BBWWWxWBBxxxWWBWWBxBB
╰─ python3 ABGame.py board1.txt board2.txt 5 --print_board
Input Board:
x--------B--------B
|        |        |
|  W-----W-----B  |
|  |     |     |  |
|  |  W--W--B  |  |
|  |  |     |  |  |
W--B--B     x--x--x
|  |  |     |  |  |
|  |  W-----x  |  |
|  |           |  |
|  W-----------W  |
|                 |
B-----------------B
Output Board:
x--------B--------B
|        |        |
|  W-----W-----B  |
|  |     |     |  |
|  |  W--W--B  |  |
|  |  |     |  |  |
W--B--B     x--W--x
|  |  |     |  |  |
|  |  W-----x  |  |
|  |           |  |
|  W-----------x  |
|                 |
B-----------------B
  
-------- MiniMax Algorithm --------
Board Position: BBWxWxWBBxWxWWBWWBxBB.
Positions evaluated by static estimation: 4643.
MINIMAX estimate: -1010.
  
-------- Alpha-Beta Pruning --------
Board Position: BBWxWxWBBxWxWWBWWBxBB.
Positions evaluated by static estimation: 360.
MINIMAX estimate: -1010.

• 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.

╰─ python3 MiniMaxOpeningImproved.py board1.txt board2.txt 2 --print_board
Input Board:
x--------x--------x
|        |        |
|  W----[x]----x  |
|  |     |     |  |
|  |  x--W--x  |  |
|  |  |     |  |  |
x--x--x     x--x--x
|  |  |     |  |  |
|  |  x-----x  |  |
|  |           |  |
|  x-----------x  |
|                 |
B-----------------B
Output Board:
x--------x--------x
|        |        |
|  W----[W]----x  |
|  |     |     |  |
|  |  x--W--x  |  |
|  |  |     |  |  |
x--x--x     x--x--x
|  |  |     |  |  |
|  |  x-----x  |  |
|  |           |  |
|  x-----------x  |
|                 |
B-----------------B
Board Position: BBxxxxxxxxxxxWxWWxxxx.
Positions evaluated by static estimation: 272.
MINIMAX estimate: 3.