Connect Four
Tech Stack: Python, GoogleColab.
What is connect four?
Connect Four is a game where two players take turns placing coins in a 6 x 7 game board. The first player to get their coins 4 in a row wins. They can get 4 in a row horizontally, vertically and diagonally. The board is upright so you have to put the coins in coin slots and they goto the bottom of the board. For example player 1 placed a "coin" in column 0 and it slides down the slot to the bottom and player two's is placed in row 2 and goes to the bottom.
[[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 0.]
[1. 0. 2. 0. 0. 0. 0.]]
Making an AI to play connect 4 with.
To keep this relatively simple I am not using any graphics and playing in the terminal. The player goes first and the computer goes next. To make the computer "smarter" and not just choose random columns. I will implement minimax algorithm and alpha beta pruning.
Minimax Algorithm
The below pseudocode is from Wikipedia.
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
Alpha-beta Pruning
The following pseudocode is from Wikipedia.
function alphabeta(node, depth, α, β, maximizingPlayer) is
if depth == 0 or node is terminal then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
if value > β then
break (* β cutoff *)
α := max(α, value)
return value
else
value := +∞
for each child of node do
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
if value < α then
break (* α cutoff *)
β := min(β, value)
return value
Solution
You can see the code below or click on the link to try playing yourself.