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)