Henry Herzfeld, Michael Keller, and Yuri Villanueva
Why are artificial intelligence researchers obsessed with games? Maybe it’s simply because games are fun. Indeed, the cover art of Sean Gerrish’s book, How Smart Machines Think, shows a clever play on a Space Invaders theme, where the aliens to be shot down are robots, self-driving cars, neurons, and movies--topics of interest in the book.
We chose to do this project on the game Connect Four, because we thought, at first, that the problem would be tractable. Maybe it’s also because we remember playing the game as children and we wanted to see if we could get an AI to solve it.
Connect Four is a solved game. The first solutions were published in 1988 by James Allen [1], and independently by Victor Allis. [2] At the time, it was not practical to solve the game by brute force. If we were to create a state-action pair cube database similar to the one used by the golf-playing agent in chapter 7 of the Gerrish book, it would have been over 4 terabytes. Since then, the game has been solved with brute force methods, starting with John Tromp’s 8-ply database in 1995. [3] More recently, Kaggle has published a database of all final states. [4] Our team had considered using these labeled datasets to train an agent. Given more time, it might be possible to include it in a future project.
We also considered implementing a “perfect player” using the strategies of the solved game. One of us started work on a minimax algorithm with alpha-beta pruning. One of our ideas was to use this player as the perfect adversary for training learning agents using other approaches.
Deep Mind's Atari-playing agent, however, was praised because it became the perfect Space Invaders player without any human supervision. Just give the machine a reward for getting a high score, and let it figure out by itself the best way to play the game. We focused on this approach with Connect Four.
Recall that our objective is to train a Connect 4 agent that is able to perform at the level of or better than human players. Thus, we assign it positive or negative rewards based on whether it wins or loses a match. The reward for winning is 1, the reward for playing to a draw is 0, and the reward for losing is -1.
At first, these were the only heuristics upon which we assigned rewards. However, when after some training we noticed that the agent tended to attempt to win by stacking 4 of its pieces vertically in the same column, we introduced a new heuristic to give it more help. This heurisitc gave it a higher positive reward for blocking an opponent that is one move away from winning.
When updating Q-values, we introduce a decay value between 0 and 1 to give previous Q-values more or less weight or importance.
Since the state space of Connect 4 is quite large (4.5 trillion possible legal states) it becomes more difficult to compute the Q-values of a move using regular q-learning. Thus, in this report we use a neural network to approximate the Q-value of each move.
In our implementation, first we simulate n matches of Connect 4 between an untrained agent and a random agent that makes random moves unless it sees a winning move. If it sees a winning move, it will take it. The non-random agent uses an epsilon-greedy approach to moves where it takes the action with the highest Q-value (best utility) with probability 1-epsilon (exploitation) and takes a random action with probability epsilon (exploration). For the first iteration, we choose the untrained agent's epsilon to be 1 (full exploration, effectively random). We also set the decay value to 0.9. This produces training data for our neural network.
Each successive iteration of training will pit the current trained agent against a new untrained agent and generate training data from those matches again in batches of 10000. Each new untrained agent will have a decay value and an epsilon value decreased by 0.1 from the last iteration.
To approximate q-values, we use a four-layer neural network. The first layer flattens the network input, which is an array of two 7x6 matrices. The first matrix represents the moves of the first player, and the second matrix represents the moves of the second player. Hence, the output of our first layer is a set of 84 values which represent the values of board slots.
The next layer is a Dense layer with 42 nodes and a relu activation function. The third layer is a Dense layer with 21 nodes an a relu activation function. Finally, we have a Dense output layer with 7 nodes and a linear activation function. We chose a linear activation function over relu because we are performing linear regression on the board state, attempting to use it to approximate the q-values. Making our output layer's activation function linear allows for negative output values, which is necessary to represent negative q-values which correspond to actions which may eventually produce a negative reward. A visualization of our network architecure is included in the TensorBoard integration later in this report.
Having the agent learn only from the rules and rewards didn’t get it very far. As a positive, it learned how to win, but it often did so by repeatedly stacking its pieces in the same column, even after its opponent had stopped it from winning. It also failed to block its opponent once its opponent had a chance to win. So, 10,000 games and 100 training epochs might not be enough. The number of states possible in Connect Four is much, much larger. We know we don't need perfect q-values, but rather a good enough approximation of the q-value function. At least one of us suspects that millions of games for training are needed to get this.
To help our agent get a good head start on the learning, we programmed it with some rules: e.g., block the opponent if it can win on the next move, make random moves unless you see a winning move. If you do, take that move. This solution, unfortunately, needs human input.
To give us a hint that our approach works, maybe we should scale down the game to Connect Three on a 4x4 grid, and see if our zero-heuristic reinforcement-learning agent can produce a competent player with fewer training examples and games.
[1] Allen, James D., Expert Play in Connect-Four, 1990, https://tromp.github.io/c4.html
[2] Allis, Victor, A Knowledge-based Approach of Connect-Four, Vrije Universiteit, October 1988, http://www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf
[3] "John's Connect Four Playground". Homepages. May 25, 2010, http://www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf
[4] Kaggle Connect-4 dataset: https://www.kaggle.com/tbrewer/connect-4
[5] Deep Tic-Tac-Toe Implementation: https://zackakil.github.io/deep-tic-tac-toe/
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from random import randrange, choice, random
import tensorflow as tf
from tensorflow.keras.models import Sequential
from tensorflow.keras.layers import Dense, Flatten
from copy import deepcopy
from datetime import datetime
def fill_col(grid, col_idx, val):
h = 6
idx = [i for i, pos in enumerate(grid[col_idx][::-1]) if not pos]
if idx:
grid[col_idx][h - idx.pop() - 1] = val
return grid
def check_consecutive(grid, consecutive):
w, h = 7, 6
for player in [1,2]:
# testing vertically
for col in grid:
for idx in range(h - consecutive + 1):
if (col[idx:idx + consecutive] == player).all():
return player
# testing horizontally
for col in grid.T:
for idx in range(w - consecutive + 1):
if (col[idx:idx + consecutive] == player).all():
return player
# testing diagonals
for k in range(-3, 3):
for idx in range(h - consecutive):
rl_diag = np.diag(grid, k=k)[idx:idx + consecutive]
lr_diag = np.diag(np.fliplr(grid), k=k)[idx:idx + consecutive]
if (rl_diag == player).all() or (lr_diag == player).all()\
and len(rl_diag) == consecutive:
return player
Below defines the code where rewards given for a particular game state are propogated into previous choices. The function takes a reward, a decay parameter and a complete history of predictions made for the currently simulated match.
def q_learn(reward, predictions, decay=0.5):
output = deepcopy(predictions)[::-1]
q_reward = reward
for pred, move in output:
pred[move] = pred[move] + q_reward
q_reward *= decay
return [m[0] for m in output]
Here is where we define our environment, called Board. Board's state is kept legal through the use of a number of helper functions, creating the appropriate environment for agents to learn.
The step function resolves the game logic during simulations as well as determining the appropriate reward as given by winning, losing and blocking heuristics.
class Board:
def __init__(self, render, log=False):
self.grid = np.zeros((7,6))
self.history = []
self.full = np.array([False, False, False, False, False, False, False])
self.w, self.h = self.grid.shape
self.consecutive = 4
self.players = [-1, 1]
self.render = render
self.turn = self.players[0]
self.end = False
self.opponent_method = self.random_move
self.win_col = None
self.log = log
def reset_board(self):
self.grid = np.zeros((7,6))
self.full = np.array([False, False, False, False, False, False, False])
self.end = False
self.history = []
self.turn = -1
def available_moves(self):
return np.where(self.full == False)[0]
def fill_col(self, col_idx, val):
idx = [i for i, pos in enumerate(self.grid[col_idx][::-1]) if not pos]
if idx:
self.grid[col_idx][self.h - idx.pop() - 1] = val
def check_consecutive(self, consecutive):
for player in self.players:
# testing vertically
for col in self.grid:
for idx in range(self.h - consecutive + 1):
if (col[idx:idx + consecutive] == player).all():
if self.log: print("vert", player)
return player
# testing horizontally
for col in self.grid.T:
for idx in range(self.w - consecutive + 1):
if (col[idx:idx + consecutive] == player).all():
if self.log: print("hori", player)
return player
# testing diagonals
for k in range(-3, 3):
for idx in range(self.h - consecutive):
rl_diag = np.diag(self.grid, k=k)[idx:idx + consecutive]
lr_diag = np.diag(np.fliplr(self.grid), k=k)[idx:idx + consecutive]
if (rl_diag == player).all() or (lr_diag == player).all()\
and len(rl_diag) == consecutive:
if self.log: print("dia", player)
return player
def check_full(self):
for idx, col in enumerate(self.grid):
if (col != 0).all():
self.full[idx] = True
def move(self, col_idx, player):
if self.available_moves().any() and self.turn == player:
self.fill_col(col_idx, player)
self.turn = player * -1
else:
print("invalid move attempted or out of order move attempted")
def random_move(self, grid_base):
for col_idx, _ in enumerate(grid_base):
grid = deepcopy(grid_base)
grid = fill_col(grid, col_idx, 1)
if check_consecutive(grid, 4) == 1:
return col_idx, _
else:
return choice(self.available_moves()), _
def find_win_col(self, grid_base):
for col_idx, _ in enumerate(grid_base):
grid = deepcopy(grid_base)
grid = fill_col(grid, col_idx, 1)
if check_consecutive(grid, 4) == 1:
return col_idx
def step(self, move):
self.check_full()
self.history.append((self.grid, move))
if move == self.find_win_col(self.grid):
if self.log: print("win blocked")
reward = 5
else:
reward = 0
self.move(move, -1)
if self.check_consecutive(4) == -1:
if self.log: print("first player won")
reward = 1
self.end = True
elif not self.available_moves().any():
if self.log: print("first player ended match")
reward = 0
self.end = True
if self.end:
return reward, self.grid
# other players turn
move, pred = self.opponent_method(self.grid)
self.move(move, 1)
self.check_full()
if self.check_consecutive(4) == 1:
if self.log: print("second player wins")
reward = -1
self.end = True
if not self.available_moves().any():
if self.log: print("second player ended game")
reward = 0
self.end = True
return reward, self.grid
def render_board(self):
if self.render:
sns.heatmap(np.rot90(self.grid), linewidth=1, vmin=-1, vmax=1)
plt.show()
def simulate(self, agent, opponent=None, n=1, epsilon=0.3, decay=0.5):
memory = []
if opponent:
self.opponent_method = opponent.decide_move
else:
self.opponent_method = self.random_move
for i in range(n):
print(f"game {i}")
predictions = []
while self.available_moves().any() and not self.end:
move, pred = agent.decide_move(self.grid)
if random() < epsilon:
move = choice(self.available_moves())
predictions.append([pred, move])
reward, state = self.step(move)
self.render_board()
# q learning update
updated_q = q_learn(reward, predictions, decay=decay)
for j in range(len(self.history)):
memory.append((self.history[j], updated_q[j], predictions[j]))
self.reset_board()
return memory
Here we define our agents. Note that the random agent is built into the Board environment
class Agent:
def __init__(self, id):
self.id = id
self.model = self.create_model()
def decide_move(self, grid, valid=True):
model_input = np.zeros([1,7,6,2])
model_input[0,:,:,0] = grid == -1
model_input[0,:,:,1] = grid == 1
pred = np.squeeze(self.model.predict(model_input))
if valid:
invalid = [i for i, col in enumerate(grid) if np.all(col)]
for idx in invalid:
pred[idx] = 0
return pred.argmax(), pred
def create_model(self):
model = Sequential()
model.add(Flatten(input_shape=[7,6,2]))
model.add(Dense(42, activation='relu'))
model.add(Dense(21, activation='relu'))
model.add(Dense(7, activation='linear'))
model.compile(loss='mae', optimizer='adadelta')
return model
class Human:
def __init__(self, id):
self.id = id
def decide_move(self, grid):
return int(input()), _
b = Board(render=False)
a1 = Agent(1)
b.reset_board()
The simulation method drives all exploration for the agent, taking in a number of parameters to facilitate the agent games.
Here we simulate our first agent against a "random" agent. This "random" agent will place a token in a column randomly if there is no winning move immediately available. Epsilon serves as the parameter for exploitation vs. exploration, where an epsilon of one (as used below) will ensure every move is a random choice.
memory_a1 = b.simulate(a1, opponent=None, n=10000, epsilon=1, decay=0.9)
_X_1 = np.array([m[0][0] for m in memory_a1])
X_1 = np.zeros([*_X_1.shape,2])
X_1[:,:,:,0] = (_X_1 == -1)
X_1[:,:,:,1] = (_X_1 == 1)
y_1 = np.array([m[1] for m in memory_a1])
print(X_1.shape, y_1.shape)
Below we train a neural network on states with modified q-value vectors as labels. The vectors have had the rewards as learnt through simulations propogated into them, encouraging the desired game-winning behavior.
Thus the network, given a game state, predicts the q_values for each action choice. We visualize the first round of training with Tensorboard:
#mc=tf.keras.callbacks.ModelCheckpoint('c4_model.hdf5', save_best_only=True, monitor='loss')
logdir="logs/fit/" + datetime.now().strftime("%Y%m%d-%H%M%S")
tensorboard_callback = tf.keras.callbacks.TensorBoard(log_dir=logdir)
hist_a1 = a1.model.fit(X_1, y_1, epochs=75, batch_size=1024, callbacks=[tensorboard_callback])
%load_ext tensorboard
%tensorboard --logdir logs
In the second round of simulations, a new agent is trained not against a "random" agent but against the first previously trained one.
a2=Agent(2)
b.reset_board()
memory_a2=b.simulate(a2, opponent=a1, n=10000, epsilon=0.9, decay=0.8)
_X_2 = np.array([m[0][0] for m in memory_a2])
X_2 = np.zeros([*_X_2.shape,2])
X_2[:,:,:,0] = (_X_2 == -1)
X_2[:,:,:,1] = (_X_2 == 1)
y_2 = np.array([m[1] for m in memory_a2])
hist_a2 = a2.model.fit(X_2, y_2, epochs=75, batch_size=1024)
a3=Agent(3)
b.reset_board()
memory_a3=b.simulate(a3, opponent=a2, n=10000, epsilon=.8, decay=0.7)
_X_3 = np.array([m[0][0] for m in memory_a3])
X_3 = np.zeros([*_X_3.shape,2])
X_3[:,:,:,0] = (_X_3 == -1)
X_3[:,:,:,1] = (_X_3== -1)
y_3 = np.array([m[1] for m in memory_a3])
hist_a3 = a3.model.fit(X_3, y_3, epochs=75, batch_size=1024)
Play against the AI
b = Board(render=True)
opponent=a1
while not b.end and b.available_moves().any():
move, pred = opponent.decide_move(b.grid, valid=True)
print(pred)
b.move(move, b.turn)
b.render_board()
winner = b.check_consecutive(4)
if winner:
b.end = True
if not b.end and b.available_moves().any():
move = int(input())
if move not in b.available_moves():
print("column is full")
move = int(input())
b.move(move, b.turn)
b.render_board()
else:
b.end = True
Below is a link to a web app where the reader can play the agent that we have trained in real-time. It was written in Javascript with Tensorflow.js.