Project 2: Connect Four: Part A Details
Guaranteed Wins
Here are the details of guaranteed wins for Connect-Three for various board sizes, along with the total number of possible states of the game, and roughly how long it took my computer to run minimax on the state space. My code is in Java on a relatively modern laptop; your code, especially if in Python, may run slower.
Your solution for Part A should result in a transposition table with the same number of states and the same first player win/second player win/tie information from the two tables below.
The links in the table below will let you see the entire transposition table for different board configurations, which may help you debug your code. (I sorted the transposition table states alphabetically to make the table easier to read.)
| Cols → Rows ↓ | 3 | 4 | 5 | 6 |
| 3 | Tie < 1 sec 694 states | 1st player wins < 1 sec 7157 states | 1st player wins < 1 sec 70914 states | 1st player wins ~4 sec 692970 states |
| 4 | Tie < 1 sec 2715 states | 1st player wins < 1 sec 41750 states | 1st player wins ~4 sec 613459 states | |
| 5 | Tie < 1 sec 8789 states | 1st player wins ~1 sec 195472 states | ||
| 6 | Tie < 1 sec 25753 states | 1st player wins ~4 sec 844488 states |
Here are the details of guaranteed wins for Connect-Four for various board sizes.
| Cols → Rows ↓ | 3 | 4 | 5 | 6 |
| 3 | Tie < 1 sec 12031 states | Tie ~1 sec 158911 states | Tie ~23 sec 2087325 states | |
| 4 | Tie < 1 sec 6000 states | Tie ~1 sec 161029 states | ||
| 5 | Tie < 1 sec 38310 states | Tie ~27 sec 1706255 states | ||
| 6 | Tie ~1 sec 235781 states |
Output
Here is an example of how the program for Part A might look. Your output should include the same information (minimax values, 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.
Example where MAX (the computer) will win no matter what:
Run part A, B, or C? A
Include debugging info? (y/n) n
Enter rows: 4
Enter columns: 5
Enter number in a row to win: 3
Search completed in 3.697 seconds.
Transposition table has 613459 states.
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
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
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
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
Example 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:
Run part A, B, or C? A
Include debugging info? (y/n) n
Enter rows: 4
Enter columns: 4
Enter number in a row to win: 4
Search completed in 0.956 seconds.
Transposition table has 161029 states.
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
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
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
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
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