Artificial Intelligence is a hot topic right now. Heralded by many to shape all aspects of the future, the expectations have been set sky high.
Games have offered the challenges that lead to AI breakthroughs. New cutting-edge techniques have been developed, refined and tested on classic games, long before the wider applications have been considered. And for many games now, the machines have exceeded the limits of human intelligence. There is no greater example of this than DeepMind AlphGo’s match of Go, against 18 time world champion Lee Sedol. AlphaGo, a program primarily using neural network and tree based algorithms was able to win the match 4-1. This was a breakthrough that people thought was still at least 10 years away, showcasing the extent of the rapid development and research in AI
Go is an extremely complex game, which required an entire team several years to devise and create. So let’s take a more simple game, Connect Four and see how well we can create an Artificial Intelligence that can learn by itself to beat human players.
Rules of the Game:
Moves in the game consist of each player playing a counter. Counters are dropped through the top of a 6 x 7 board and occupy the next available space in each column, from the bottom up. So a player has a choice of which of the 7 columns to play their next counter.
A player wins the game by being the first to form a run of 4 counters in any direction.
Storing and manipulating the board:
The possible counter positions form a nice 6 x 7 layout, making a matrix the natural data structure to manage the board.
Each position can be in three states: empty, yellow counter or red counter; we can store a 0, 1 or 2 in the matrix to represent each state respectively.
playGrid = np.zeros((6, 7), dtype=int)
We can define a variable called “turn” that alternates between 1 and 2 to represent each player’s turn
turn = 1
One more handy thing to keep track of is the height of the variables in each column. As the matrix’s 0,0 point is the top left hand corner, we start with all columns at 6 and decrement by 1 each time a counter is played in a particular column
gridCounterHeights = [6]*7
Checking for a win:
The benefits of using the matrix data structure is that we can formulate an extremely elegant way to check for a win. Given a particular move , all we need to do is send each possible line that includes that counter into a function that checks for a four in a row.
def checkWinInRow(line, turn):
count = 0
for c in range(len(line)):
if line[c] == turn:
count += 1
if count >= 4:
return True
else:
count = 0
return False
And have the main function which sends each line into it, given the current playGrid, turn, column and row of the move.
def checkWin(grid, col, row, turn):
return (checkWinInRow(grid[row, :], turn)
or checkWinInRow(grid[:, col], turn)
or checkWinInRow(np.diagonal(grid, offset=col-row), turn)
or checkWinInRow(np.diagonal(np.fliplr(grid), offset=6-(col+row)), turn))
(Extra): Picking out each line
The first two handle the horizontal and vertical lines by simple slicing.
The two diagonals are much more tricky. The numpy package comes with a useful diagonal function to handle the ” down” diagonal. You can send in an offset parameter to indicate which diagonal to take, referenced from the main diagonal. Positive integers are diagonals above the main diagonal, negative are diagonals below the main. Each diagonal can surprisingly be uniquely identified by col – row.
For the “up” diagonal, we sneakily flip the entire grid around (an operation that is only O(1) for those about to freak out about performance) and use the same diagonal function. I encourage you to do what I did and draw out the transformation to derive why the offset becomes 6 – (col + row).
Full Code:
The above gives the tough parts of the code required to make the Connect Four game. Most of the extra code is GUI and handling of input. I use the pygame module to handle the visuals and event inputs.
Note that the way this is coded will generalize to any number of column, rows and win amount defined (which will be interesting for later work!)
import pygame
import sys
import time
from pygame.locals import *
import numpy as np
COLUMNS = 7
ROWS = 6
WINAMOUNT = 4
WINDOWWIDTH = 800
WINDOWHEIGHT = 600
COUNTERDIAMETER = 50
PLAYWIDTH = COLUMNS*(COUNTERDIAMETER+25)+25
PLAYHEIGHT = ROWS*(COUNTERDIAMETER+25)+25
PLAYX = 50
PLAYY = 25
COLGAP = (PLAYWIDTH - COLUMNS*COUNTERDIAMETER) / (COLUMNS+1)
ROWGAP = (PLAYHEIGHT - ROWS*COUNTERDIAMETER) / (ROWS+1)
DISPLAYSURF = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT))
pygame.init()
running = True
playing = True
playGrid = np.zeros((ROWS, COLUMNS), dtype=int)
gridCounterHeights = [ROWS-1]*COLUMNS
turn = 1
def checkWin(grid, col, row, turn, winAmount):
return (checkWinInRow(grid[row, :], turn, winAmount) or checkWinInRow(grid[:, col], turn, winAmount)
or checkWinInRow(np.diagonal(grid, offset=col-row), turn, winAmount)
or checkWinInRow(np.diagonal(np.fliplr(grid), offset=COLUMNS-1-(col+row)), turn, winAmount))
def checkWinInRow(line, turn, winAmount):
count = 0
for c in range(len(line)):
if line[c] == turn:
count += 1
if count >= winAmount:
return True
else:
count = 0
return False
while running:
mouseX, mouseY = pygame.mouse.get_pos()
for event in pygame.event.get():
if event.type == QUIT:
pygame.quit()
sys.exit()
if event.type == MOUSEBUTTONUP and playing:
for col in range(COLUMNS):
refX = PLAYX + col*COUNTERDIAMETER + (col+1)*COLGAP
if refX < mouseX < refX + COUNTERDIAMETER and PLAYY < mouseY < PLAYY + PLAYHEIGHT:
if gridCounterHeights[col] >= 0:
playGrid[gridCounterHeights[col],col] = turn
winBool = checkWin(playGrid, col, gridCounterHeights[col], turn, WINAMOUNT)
gridCounterHeights[col] -= 1
turn = turn % 2 + 1
if winBool:
playing = False
print("Player: " + str(turn) + " wins!")
DISPLAYSURF.fill((255, 255, 255))
pygame.draw.rect(DISPLAYSURF, (0, 0, 255), (PLAYX, PLAYY, PLAYWIDTH,PLAYHEIGHT), 0)
DISPLAYSURF.blit(mouseText, (10, 10))
for row in range(ROWS):
for col in range(COLUMNS):
dcol = int(PLAYX + COUNTERDIAMETER * col + COLGAP *(col+1) + COUNTERDIAMETER/2)
drow = int(PLAYY + COUNTERDIAMETER * row + ROWGAP * (row+1) + COUNTERDIAMETER/2)
if playGrid[row][col] == 0:
pygame.draw.circle(DISPLAYSURF, (255, 255, 255), (dcol,drow) ,int(COUNTERDIAMETER/2),0)
elif playGrid[row][col] == 1:
pygame.draw.circle(DISPLAYSURF, (255, 0, 0), (dcol,drow),int(COUNTERDIAMETER/2))
else:
pygame.draw.circle(DISPLAYSURF, (255, 255, 0), (dcol,drow),int(COUNTERDIAMETER/2))
pygame.display.update()
time.sleep(0.20)
