Connect4 Python AI

All the code for this connect4 Python AI is available here on GitHub.

Why Connect4?

Chess has been the focus of extensive research in the domain of Artificial Intelligence for many years. It is complex and yet it meets a specific set of rules which make it easy to define:

  • Its rules have not ambiguity
  • You can easily make a human play against a computer
  • Many people play chess

The only problem with building a chess AI is that it requires a lot of brain power to build (which I don’t have). There are, on the other hand, two other games which come to mind which meet the above criteria and are easier to implement: Tic-Tac-Toe, which I have previously covered and Connect4 which I shall cover now!

I recommend that you read this tutorial on Tic-Tac-Toe first

Introduction

A bit of nomenclature

To be able to write this tutorial on Connect4 I will need to be very specific about the terms I use I’d rather spend a little time explaining them here than repeating myself later on. I will refer to the 7 columns as a, b, c up to g and the rows will be numbered 1 through 6. I will talk about a-column and row-1. To specify a line of squares I will use the notation and will call it a streak.

Connect4 statistics

According to calculations, there are in between 1.6 ∗ 1013 and 7.1 ∗ 1013 possible boards which means that computing them all is definitely out of question. The OEISA212693 has actually calculated that there are 4531985219092 possible games. If you would like a more in-depth explanation I definitely recommend watching this video by numberphile:

Because there are so many possible games, our minimax algorithm even with alpha-beta pruning would take hundreds of thousands of years to run! We are going to have to add a depth limit meaning that after a certain recursion depth even if we haven’t won, lost or tied the game we will stop. This means that we will need to create a function to evaluate the board. If I give you two different connect4 boards, how can you tell which one is better?

Connect4 evaluation function

I used the following criteria to evaluate the game:

It turns out that the following simple evaluation function for Connect Four (based on R. L. Rivest, Game Tree Searching by Min/Max Approximation, AI 34 [1988], pp. 77-96) performs surprisingly well:

  • a win by X has a value of +512,
  • a win by O has avalue of -512,
  • a draw has a value of 0,

otherwise, take all possible straight segments on the grid (defined as a set of four slots in a line–horizontal, vertical, or diagonal; see Figure 2), evaluate each of them according to the rules below, and return the sum of the values over all segments, plus a move bonus depending on whose turn it is to play (+16 for X, -16 for O). The rules for evaluating segments are as follows:

  • -50 for three Os, no Xs,
  • -10 for two Os, no Xs,
  • – 1 for one O, no Xs,
  • 0 for no tokens, or mixed Xs and Os,
  • 1 for one X, no Os,
  • 10 for two Xs, no Os,
  • 50 for three Xs, no Os.

taken from this Harvard paper.

Game environment

The game environment I use is very similar to the one I used for my Tic-Tac-Toe AI. I definitely recommend reading the explanation of that environment first.

Here’s the connect4 environment stored in environment.py:

WIN = 512
LOSE = -WIN

#self.board environment class
class Board(object):
""" Game Environment Class"""

def __init__(self, board=[]):
""" Initialize the environment variables """
# Generate a newself.board if the passedself.board is empty
if len(board) == 0:
self.board = [[' ' for row in range(6)] for column in range(7)]

# Set newself.board as oldself.board
else:
self.board = self.board

self.width = 7
self.height = 6

def __str__(self):
""" Return the board"""
string = ''
# Print Column numbers
string += "\ 1 2 3 4 5 6 7\n"

# 0-5 (6 Rows)
for row in range(6):
# Print Row number
string += str(row+1) + ' '
# 0-6 (7 Columns)
for column in range(7):
# Print Square at index [Column][Row]
string += self.board[column][row] + ' '
# New line
string += '\n'
return string

def legal_moves(self):
""" Get the empty spaces """
return self.get_columns(' ')

def leaf(self):
""" Is theself.board full or has someone won the game """
if self.full():
return True
if self.winner() != None:
return True
return False

def full(self):
for column in range(self.width):
if self.board[column][0] == ' ':
return False
return True

def X_won(self):
""" Did player X win """
return self.winner() == 'X'

def O_won(self):
""" Did player O win """
return self.winner() == 'O'

def tied(self):
""" Is the game a tie? """
return self.leaf() == True and self.winner() is None

def score(self, one, two, three, four, man):
o_man = get_opponent(man)
score = 0
if(one != o_man and two != o_man and three != o_man and four != o_man):
count = 0
if one == man:
count += 1
if two == man:
count += 1
if three == man:
count += 1
if four == man:
count += 1

if count == 4:
score += WIN
elif count == 3:
score += 50
elif count == 2:
score += 10
elif count == 1:
score += 1
return score

def evaluate(self, man):
o_man = get_opponent(man)
score = 0
for column in range(self.width):
for row in range(self.height):
# Horizonatal - evaluation
try:
t_score = self.score(self.board[column][row], self.board[column+1][row], self.board[column+2][row], self.board[column+3][row], man)
if t_score >= WIN:
return WIN
score += t_score
t_score = self.score(self.board[column][row], self.board[column+1][row], self.board[column+2][row], self.board[column+3][row], o_man)
if t_score >= WIN:
return LOSE
score -= t_score
except:
pass
# Vertical | evaluation
try:
t_score = self.score(self.board[column][row], self.board[column][row+1], self.board[column][row+2], self.board[column][row+3], man)
if t_score >= WIN:
return WIN
score += t_score
t_score = self.score(self.board[column][row], self.board[column][row+1], self.board[column][row+2], self.board[column][row+3], o_man)
if t_score >= WIN:
return LOSE
score -= t_score
except:
pass
# Diagonal \ evaluation
try:
t_score = self.score(self.board[column][row], self.board[column+1][row+1], self.board[column+2][row+2], self.board[column+3][row+3], man)
if t_score >= WIN:
return WIN
score += t_score
t_score = self.score(self.board[column][row], self.board[column+1][row+1], self.board[column+2][row+2], self.board[column+3][row+3], o_man)
if t_score >= WIN:
return LOSE
score -= t_score

except:
pass
# Diagonal / evaluation
try:
t_score = self.score(self.board[column][row], self.board[column-1][row+1], self.board[column-2][row+2], self.board[column-3][row+3], man)
if t_score >= WIN:
return WIN
score += t_score
t_score = self.score(self.board[column][row], self.board[column-1][row+1], self.board[column-2][row+2], self.board[column-3][row+3], o_man)
if t_score >= WIN:
return LOSE
score -= t_score
except:
pass
if man == 'O':
score += 16
else:
score -= 16
return score

def winner(self):
""" Get the winner of the board """
score = self.evaluate('X')
if score >= WIN:
return 'X'
elif score <= LOSE:
return 'O'
else:
return None

def get_columns(self, player):
""" Get a list of all squares taken by a certain player """
return [column for column in range(self.width) if self.board[column][0] == player]

def move(self, column, player, delete=False):
""" Move player to position """
# Get Row to play at
for row in range(self.height):
if self.board[column][row] != ' ':
if not(delete):
row -= 1
break

# Set Square at index [column-1][row-1] to passed Square value
#print("Column: ",column+1," Row: ",row+1)
self.board[column][row] = player

def get_opponent(player):
""" Gives us the opponent of player """
if player == 'O':
return 'X'
else:
return 'O'

Simple AI

Let’s create a simple AI to test our environment.

We need:

  • A function to get the player’s move
  • A function to get the computer’s move
  • A function to decide who plays when and draws the board

The computer’s move function will:

  1. Check if it can win, if so it will play there
  2. Check if the opponent can win, if so it will play there
  3. Pick a random move in all the available moves

Here are the three functions which we will store in connect4.py:

from environment import *
import random
from copy import deepcopy

COMPUTER = 'O'

def player_move(board, text):
""" Get a player's move"""
print('\n-------')
print(text)
move = None
while move not in board.legal_moves():
move = int(input('Select square to play at: '))-1
return move

def computer_move(board, computer):
""" Get the stupod computer's move """
board = deepcopy(board) # Copy board as we will be changing it
best_moves = [0,1,2,3,4,5,6]
player = get_opponent(computer)

<h1>If computer can win: play there</h1>

for move in board.legal_moves():
board.move(move, computer)
if board.winner() == computer:
print('Computer will play at square: {}'.format(move+1))
return move

<h1>Undo the move</h1>

board.move(move, ' ', True)

<h1>If player can win: block the move</h1>

for move in board.legal_moves():
board.move(move, player)
if board.winner() == player:
print('Computer will block at square: {}'.format(move+1))
return move

<h1>Undo the move</h1>

board.move(move, ' ', True)

<h1>Else pick the best empty square</h1>

return random.choice(board.legal_moves)

def computer_play():
""" Play Tic-Tac-Toe against a (perfect) computer"""
board = Board()
print(board)
player1 = input("What are you called? ")
player2 = "Computer"
print('{} is X and {} is O'.format(player1,player2))
player = None
while player not in ['X','O']:
player = input('Who goes first?(X or O) ').capitalize()

while not board.leaf():
if player == 'X':
move = player_move(board, '{}\'s turn'.format(player1))
board.move(move, player)
else:
move = computer_move(board, player)
board.move(move, player)
print(board)
player = get_opponent(player)

if board.X_won():
print("{} won!".format(player1))
elif board.O_won():
print("{} won!".format(player2))
else:
print("It's a tie!")

Obviously, we can beat this “AI” fairly easily so let’s create an even better AI using the minimax algorithm with alpha-beta pruning. Once again, for more information read this post.

Minimax algorithm

Connect4 Minimax AI

Our algorithm will be the simple minimax algorithm with  a little extra added:

  • If the computer can win immediately it will play there
  • If the opponent can win immediately it will play there

Here is the wrapper function and the minimax algorithm also stored in connect4.py:

# Minimax
def minimax(node, player, alpha, beta, depth):
if node.leaf() or depth == 0:
return node.evaluate('O')

for move in node.legal_moves():
node.move(move, player)
score = minimax(node, get_opponent(player), alpha, beta, depth-1)
node.move(move, ' ', True)
if player == 'O':
if score > alpha:
alpha = score
if alpha >= beta:
return beta
else:
if score < beta:
beta = score
if beta <= alpha: return alpha if player == 'O': return alpha else: return beta def computer_move2(board, player): best_moves = [0,1,2,3,4,5,6] o_player = get_opponent(player) # If computer can win: play there for move in board.legal_moves(): board.move(move, player) if board.winner() == player: print('Computer will play at square: {}'.format(move+1)) return move # Undo the move board.move(move, ' ', True) # If player can win: block the move for move in board.legal_moves(): board.move(move, o_player) if board.winner() == o_player: print('Computer will block at square: {}'.format(move+1)) return move # Undo the move board.move(move, ' ', True) best = LOSE-1 choices = [] if len(board.legal_moves()) == 9: return random.choice([0,2,6,8]) for move in board.legal_moves(): board.move(move, player) score = minimax(board, get_opponent(player), LOSE+1, WIN+1, 6) board.move(move, ' ', True) print("Move: ",move+1," has a score of: ",score) if score > best:
best = score
choices = [move]
elif score == best:
choices.append(move)
choice = random.choice(choices)
print("[+] Selected move: ",choice+1)
return choice

def computer_play():
""" Play Tic-Tac-Toe against a (perfect) computer"""
board = Board()
print(board)
player1 = input("What are you called? ")
player2 = "Computer"
print('{} is X and {} is O'.format(player1,player2))
player = None
while player not in ['X','O']:
player = input('Who goes first?(X or O) ').capitalize()

while not board.leaf():
if player == 'X':
move = player_move(board, '{}\'s turn'.format(player1))
board.move(move, player)
else:
move = computer_move2(board, player)
board.move(move, player)
print(board)
player = get_opponent(player)

if board.X_won():
print("{} won!".format(player1))
elif board.O_won():
print("{} won!".format(player2))
else:
print("It's a tie!")

I really hope that you enjoyed this tutorial. As making this tutorial really required a lot of work it would be much appreciated if you left a comment to show your support!

Don’t forget to subscribe to our email list to get notified when we post more amazing content.

[sp-form formid=377]

Leave a Reply