Minimax is a popular AI algorithm used to play adversarial games such as Tic-Tac-Toe or Chess against a machine. The concept behind Minimax is to increase (or maximize) the rewards for the machine and decreasing (or minimizing) the losses in response to the player's moves.

In this program, written for Dr. Haim Schweitzer's AI class at UT Dallas, the Minimax algorithm is used to play a game called Jumpy.

The game starts out with a board like this:

White has two pieces on the leftmost boxes numbered 1 and 2, and Black has two pieces on the rightmost boxes numbered 7 and 8. The initial game state is denoted by 1278, where the two left numbers indicate where the White pieces are on the board and the right numbers indicate where the Black pieces are on the board.

The objective of both the players is to get both their respective pieces out of the opposite side of the board. Meaning, White needs to move the pieces beyond box 8 by moving to the right. Outside the box for white is denoted by "9". Black, on the other hand needs to move both its pieces beyond box 1 by moving to the left. Outside the box for black is denoted by "0".

Each player is allowed to jump over consecutive pieces, however if a piece jumps over a singular piece from the opponent, the opponent's piece must be pushed back on the farthest available box on its starting side. For example, if the board is 1528 and its White's turn where the White piece on box 1 jumps over the Black piece on Box 2 and lands on Box 3, the resulting game state would be 3578, since the farthest available box for Black to be pushed back on would be Box 7 (since 8 is occupied).

The Minimax algorithm is written for both White and Black players. Functions generate moves for respective players using a simple decision tree. A third Minimax algorithm is written using an improved Static Estimate Function than the one provided by the instructor. The improved Static Estimate Function heavily rewards reaching the end of the respective player's side, jumping over the opponent, and jumping over multiple pieces over making singular moves. Alpha Beta Pruning is an algorithm that produces the same moves as generated by MiniMax, but it visits less nodes, essentially reducing the amount of space and memory used.

The input file is board1.txt where the intial game state is passed. The output file is board2.txt where the program writes the response according to which program is run and produces a new game state. The game state, static estimate function visiting the number of nodes, and the Minimax/Alpha-Beta estimate is printed to console.