Project 2: Connect Four: Part B Details

Guaranteed Wins

The guaranteed wins in Part B are identical to Part A. This is because using alpha-beta pruning always returns the same results as minimax, except for situations where pruning removes sections of the game tree that will never be encountered during optimal play.

Like in Part A, your program should result in a transposition table with the same number of states, same number of prunings, and the same first player win/second player win/tie information from the two tables below.

Cols → Rows ↓	3	4	5	6	7
3	Tie < 1 sec 206 states 149 prunings	1st player wins < 1 sec 926 states 986 prunings	1st player wins < 1 sec 6792 states 8393 prunings	1st player wins < 1 sec 29559 states 34420 prunings	1st player wins < 1 sec 170295 states 206168 prunings
4	Tie < 1 sec 606 states 522 prunings	1st player wins < 1 sec 4102 states 4619 prunings	1st player wins < 1 sec 32020 states 34919 prunings	1st player wins ~1 sec 192754 states 201936 prunings	1st player wins ~17 sec 1448119 states 1775110 prunings
5	Tie < 1 sec 1465 states 1169 prunings	1st player wins < 1 sec 16224 states 17815 prunings	1st player wins ~1 sec 129471 states 159790 prunings	1st player wins ~15 sec 1000588 states 1183048 prunings
6	Tie < 1 sec 4455 states 4129 prunings	1st player wins < 1 sec 47536 states 50343 prunings	1st player wins < 6 sec 517915 states 636557 prunings

Here are the details of guaranteed wins for Connect-Four for various board sizes.

Cols → Rows ↓	3	4	5	6
3	Tie < 1 sec 106 states 87 prunings	Tie < 1 sec 632 states 694 prunings	Tie < 1 sec 6517 states 11440 prunings	Tie < 1 sec 62907 states 412495 prunings
4	Tie < 1 sec 349 states 292 prunings	Tie < 1 sec 7115 states 9004 prunings	Tie ~5 sec 289554 states 945534 prunings
5	Tie < 1 sec 1021 states 895 prunings	Tie < 1 sec 55040 states 92778 prunings
6	Tie ~1 sec 3118 states 3109 prunings	Tie ~16 sec 535235 states 1886175 prunings

Output

Here is an example of how the program for Part B might look. Your output should include the same information (minimax values, number of prunings, optimal moves, size of the transposition table), but the formatting does not have to match exactly. You do not need to report the search time.

Here is the same first example from the sample output from Part A. This is a situation where MAX will win no matter what, but notice that MIN (the human) picks some suboptimal moves, and each time this triggers a re-run of alpha-beta because the resulting states from each of those moves aren’t in the transposition table. Additionally, notice that the game proceeds in exactly the same fashion: the computer wins in exactly the same way and the minimax values for all states are identical to those in Part A.

Run part A, B, or C? b
Include debugging info? (y/n) n
Enter rows: 4
Enter columns: 5
Enter number in a row to win: 3
Search completed in 0.169 seconds.
Transposition table has 32020 states.
The tree was pruned 34919 times.
First player has a guaranteed win with perfect play.
Who plays first? 1=human, 2=computer: 2

. . . . . 
. . . . . 
. . . . . 
. . . . . 
0 1 2 3 4 
Minimax value for this state: 22222, optimal move: 1
It is MAX's turn!
Computer chooses move: 1

. . . . . 
. . . . . 
. . . . . 
. X . . . 
0 1 2 3 4 
Minimax value for this state: 22222, optimal move: 0
It is MIN's turn!
Enter move: 2

. . . . . 
. . . . . 
. . . . . 
. X O . . 
0 1 2 3 4 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 22222, optimal move: 1
It is MAX's turn!
Computer chooses move: 1

. . . . . 
. . . . . 
. X . . . 
. X O . . 
0 1 2 3 4 
Minimax value for this state: 22222, optimal move: 1
It is MIN's turn!
Enter move: 1

. . . . . 
. O . . . 
. X . . . 
. X O . . 
0 1 2 3 4 
Minimax value for this state: 22222, optimal move: 2
It is MAX's turn!
Computer chooses move: 2

. . . . . 
. O . . . 
. X X . . 
. X O . . 
0 1 2 3 4 
Minimax value for this state: 22222, optimal move: 1
It is MIN's turn!
Enter move: 4

. . . . . 
. O . . . 
. X X . . 
. X O . O 
0 1 2 3 4 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 22222, optimal move: 3
It is MAX's turn!
Computer chooses move: 3

. . . . . 
. O . . . 
. X X . . 
. X O X O 
0 1 2 3 4 
Minimax value for this state: 22222, optimal move: 0
It is MIN's turn!
Enter move: 3

. . . . . 
. O . . . 
. X X O . 
. X O X O 
0 1 2 3 4 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 22222, optimal move: 3
It is MAX's turn!
Computer chooses move: 3
Game over!
. . . . . 
. O . X . 
. X X O . 
. X O X O 
0 1 2 3 4 
The winner is MAX (computer)
Play again? (y/n): n

Same example from Part A, where MAX (the computer) will normally tie if MIN (the user) plays optimally, but the user makes lots of mistakes here and the computer eventually wins.

As above, the computer proceeds in exactly the same fashion and computes the same values as in Part A.

Run part A, B, or C? b
Include debugging info? (y/n) n
Enter rows: 4
Enter columns: 4
Enter number in a row to win: 4
Search completed in 0.064 seconds.
Transposition table has 7115 states.
The tree was pruned 9004 times.
Neither player has a guaranteed win; game will end in tie with perfect play on both sides.
Who plays first? 1=human, 2=computer: 2

. . . . 
. . . . 
. . . . 
. . . . 
0 1 2 3 
Minimax value for this state: 0, optimal move: 0
It is MAX's turn!
Computer chooses move: 0

. . . . 
. . . . 
. . . . 
X . . . 
0 1 2 3 
Minimax value for this state: 0, optimal move: 0
It is MIN's turn!
Enter move: 3

. . . . 
. . . . 
. . . . 
X . . O 
0 1 2 3 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 0, optimal move: 0
It is MAX's turn!
Computer chooses move: 0

. . . . 
. . . . 
X . . . 
X . . O 
0 1 2 3 
Minimax value for this state: 0, optimal move: 0
It is MIN's turn!
Enter move: 0

. . . . 
O . . . 
X . . . 
X . . O 
0 1 2 3 
Minimax value for this state: 0, optimal move: 0
It is MAX's turn!
Computer chooses move: 0

X . . . 
O . . . 
X . . . 
X . . O 
0 1 2 3 
Minimax value for this state: 0, optimal move: 1
It is MIN's turn!
Enter move: 2

X . . . 
O . . . 
X . . . 
X . O O 
0 1 2 3 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 0, optimal move: 1
It is MAX's turn!
Computer chooses move: 1

X . . . 
O . . . 
X . . . 
X X O O 
0 1 2 3 
Minimax value for this state: 0, optimal move: 1
It is MIN's turn!
Enter move: 3

X . . . 
O . . . 
X . . O 
X X O O 
0 1 2 3 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 0, optimal move: 1
It is MAX's turn!
Computer chooses move: 1

X . . . 
O . . . 
X X . O 
X X O O 
0 1 2 3 
Minimax value for this state: 0, optimal move: 1
It is MIN's turn!
Enter move: 3

X . . . 
O . . O 
X X . O 
X X O O 
0 1 2 3 
This is a state that was previously pruned; re-running alpha beta from here.
Minimax value for this state: 10666, optimal move: 3
It is MAX's turn!
Computer chooses move: 3

X . . X 
O . . O 
X X . O 
X X O O 
0 1 2 3 
Minimax value for this state: 10666, optimal move: 1
It is MIN's turn!
Enter move: 1

X . . X 
O O . O 
X X . O 
X X O O 
0 1 2 3 
Minimax value for this state: 10666, optimal move: 1
It is MAX's turn!
Computer chooses move: 1

X X . X 
O O . O 
X X . O 
X X O O 
0 1 2 3 
Minimax value for this state: 10666, optimal move: 2
It is MIN's turn!
Enter move: 2

X X . X 
O O . O 
X X O O 
X X O O 
0 1 2 3 
Minimax value for this state: 10666, optimal move: 2
It is MAX's turn!
Computer chooses move: 2
Game over!
X X . X 
O O X O 
X X O O 
X X O O 
0 1 2 3 
The winner is MAX (computer)
Play again? (y/n): n