Connect 4 is played on a wide matrix. There are more than 4 trillion possible game states, so brute forcing of the game isn’t computationally viable. Wikipedia says that minimax and negamax are applicable algorithms to use.
For the ECE244 lab, we play on a square matrix.