This project is a Python implementation of the classic Connect Four game where a player can compete against an AI. It employs the Pygame library for the game's interface and control. The AI's decision-making is based on the Monte Carlo tree search algorithm, and the difficulty level is adjustable, allowing players to challenge themselves with smarter AI opponents.
Key Concepts:
Utilizing Pygame for game development.
Implementing the Monte Carlo tree search algorithm for AI decision-making.
ð Preview
ðŊ Tasks
In this project, you will learn:
How to build a game using Pygame
How to implement the Monte Carlo tree search algorithm for AI decision-making
How to customize and enhance the AI's difficulty level
How to create a fun and interactive Connect Four game for human vs. AI battles
ð Achievements
After completing this project, you will be able to:
Develop games using Python and Pygame
Understand the principles of the Monte Carlo tree search algorithm
Tune the difficulty of an AI opponent to create a challenging gaming experience
Enhance user interfaces to make the gaming experience more engaging
Development Preparation
The Four-In-A-Row game is played on a grid of size 7*6. Players take turns to drop their pieces from the top of a column. The piece will fall into the bottommost empty space in that column. The player who connects four pieces in a straight line (horizontal, vertical, or diagonal) wins the game.
Create a file named fourinrow.py in the ~/project directory to store the code for this project. Additionally, we need to install the Pygame library to implement the game's interface and support operations.
cd ~/project
touch fourinrow.py
sudo pip install pygame
You can find the required image resources for this project in the ~/project/images directory.
To better understand the code in this project, it is recommended that you study it alongside the complete solution's code.
The variables used include the width and height of the chessboard (can be modified to design chessboards of different sizes), the difficulty level, the size of the chess pieces, and the setting of some coordinate variables.
In the fourinrow.py file, enter the following code:
import random, copy, sys, pygame
from pygame.locals import *
BOARDWIDTH = 7 ## Number of columns on the game board
BOARDHEIGHT = 6 ## Number of rows on the game board
assert BOARDWIDTH >= 4 and BOARDHEIGHT >= 4, 'Board must be at least 4x4.'
## The python assert statement is used to declare that its given boolean expression must be true.
## If the expression is false, it raises an exception.
DIFFICULTY = 2 ## Difficulty level, number of moves the computer can consider
## Here, 2 means considering 7 possible moves of the opponent and how to respond to those 7 moves
SPACESIZE = 50 ## Size of the chess pieces
FPS = 30 ## Screen refresh rate, 30/s
WINDOWWIDTH = 640 ## Width of the game screen in pixels
WINDOWHEIGHT = 480 ## Height of the game screen in pixels
XMARGIN = int((WINDOWWIDTH - BOARDWIDTH * SPACESIZE) / 2) ## X-coordinate of the left edge of the grid
YMARGIN = int((WINDOWHEIGHT - BOARDHEIGHT * SPACESIZE) / 2) ## Y-coordinate of the top edge of the grid
BRIGHTBLUE = (0, 50, 255) ## Blue color
WHITE = (255, 255, 255) ## White color
BGCOLOR = BRIGHTBLUE
TEXTCOLOR = WHITE
RED = 'red'
BLACK = 'black'
EMPTY = None
HUMAN = 'human'
COMPUTER = 'computer'
In addition, we also need to define some global variables of pygame. These global variables will be called multiple times in various modules later. Many of them are variables that store loaded images, so the preparation work is a bit long, please be patient.
## Initialize pygame modules
pygame.init()
## Create a Clock object
FPSCLOCK = pygame.time.Clock()
## Create the game window
DISPLAYSURF = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT))
## Set the game window title
pygame.display.set_caption(u'four in row')
## Rect(left, top, width, height) is used to define position and size
REDPILERECT = pygame.Rect(int(SPACESIZE / 2), WINDOWHEIGHT - int(3 * SPACESIZE / 2), SPACESIZE, SPACESIZE)
## Create the bottom left and bottom right chess pieces in the window
BLACKPILERECT = pygame.Rect(WINDOWWIDTH - int(3 * SPACESIZE / 2), WINDOWHEIGHT - int(3 * SPACESIZE / 2), SPACESIZE, SPACESIZE)
## Load the red chess piece image
REDTOKENIMG = pygame.image.load('images/4rowred.png')
## Scale the red chess piece image to SPACESIZE
REDTOKENIMG = pygame.transform.smoothscale(REDTOKENIMG, (SPACESIZE, SPACESIZE))
## Load the black chess piece image
BLACKTOKENIMG = pygame.image.load('images/4rowblack.png')
## Scale the black chess piece image to SPACESIZE
BLACKTOKENIMG = pygame.transform.smoothscale(BLACKTOKENIMG, (SPACESIZE, SPACESIZE))
## Load the chessboard image
BOARDIMG = pygame.image.load('images/4rowboard.png')
## Scale the chessboard image to SPACESIZE
BOARDIMG = pygame.transform.smoothscale(BOARDIMG, (SPACESIZE, SPACESIZE))
## Load the human winner image
HUMANWINNERIMG = pygame.image.load('images/4rowhumanwinner.png')
## Load the AI winner image
COMPUTERWINNERIMG = pygame.image.load('images/4rowcomputerwinner.png')
## Load the tie image
TIEWINNERIMG = pygame.image.load('images/4rowtie.png')
## Return a Rect object
WINNERRECT = HUMANWINNERIMG.get_rect()
## Center the winner image on the game window
WINNERRECT.center = (int(WINDOWWIDTH / 2), int(WINDOWHEIGHT / 2))
## Load the arrow image for user instructions
ARROWIMG = pygame.image.load('images/4rowarrow.png')
## Return a Rect object
ARROWRECT = ARROWIMG.get_rect()
## Set the left position of the arrow image
ARROWRECT.left = REDPILERECT.right + 10
## Align the arrow image vertically with the red chess piece below it
ARROWRECT.centery = REDPILERECT.centery
To better understand the code in this project, it is recommended that you study it alongside the complete solution's code.
Initially, clear the two-dimensional list representing the board, and then set the corresponding positions on the board with colors based on the moves of the player and AI.
def drawBoard(board, extraToken=None):
## DISPLAYSURF is our interface, defined in the variable initialization module.
DISPLAYSURF.fill(BGCOLOR) ## Fill the game window background color with blue.
spaceRect = pygame.Rect(0, 0, SPACESIZE, SPACESIZE) ## Create a Rect instance.
for x in range(BOARDWIDTH):
## Determine the top-left position coordinates of each cell in each row of each column.
for y in range(BOARDHEIGHT):
spaceRect.topleft = (XMARGIN + (x * SPACESIZE), YMARGIN + (y * SPACESIZE))
## When x = 0 and y = 0, it is the first cell in the first row of the first column.
if board[x][y] == RED: ## If the cell value is red,
## draw a red token in the game window within spaceRect.
DISPLAYSURF.blit(REDTOKENIMG, spaceRect)
elif board[x][y] == BLACK: ## Otherwise, draw a black token.
DISPLAYSURF.blit(BLACKTOKENIMG, spaceRect)
## extraToken is a variable that contains position information and color information.
## It is used to display a specified token.
if extraToken != None:
if extraToken['color'] == RED:
DISPLAYSURF.blit(REDTOKENIMG, (extraToken['x'], extraToken['y'], SPACESIZE, SPACESIZE))
elif extraToken['color'] == BLACK:
DISPLAYSURF.blit(BLACKTOKENIMG, (extraToken['x'], extraToken['y'], SPACESIZE, SPACESIZE))
## Draw the token panels.
for x in range(BOARDWIDTH):
for y in range(BOARDHEIGHT):
spaceRect.topleft = (XMARGIN + (x * SPACESIZE), YMARGIN + (y * SPACESIZE))
DISPLAYSURF.blit(BOARDIMG, spaceRect)
## Draw the tokens at the bottom left and bottom right of the game window.
DISPLAYSURF.blit(REDTOKENIMG, REDPILERECT) ## Left red token.
DISPLAYSURF.blit(BLACKTOKENIMG, BLACKPILERECT) ## Right black token.
def getNewBoard():
board = []
for x in range(BOARDWIDTH):
board.append([EMPTY] * BOARDHEIGHT)
return board ## Return the board list with BOARDHEIGHT number of None values.
In above code, the drawBoard() function draws the board and the tokens on the board. The getNewBoard() function returns a new board data structure.
Briefly explain the idea of Monte Carlo tree search:
Use the one-dimensional Monte Carlo method to evaluate the Go game board. Specifically, when a specific chessboard situation is given, the program randomly selects a point from all the available points in the current situation and places a chess piece on it. This random selection of available points (roll point) process is repeated until neither side has any available points (the game ends), and then the resulting win or loss of this final state is fed back as the basis for evaluating the current situation.
In this project, the AI continuously chooses different columns and evaluates the results of both sides' victories. The AI will ultimately choose a strategy with a higher evaluation.
Before looking at the pictures and text below, please take a look at the code at the end, and then refer to the corresponding explanations.
Observing the confrontation between AI and player in the figure below:
Some variables in the project can intuitively reflect the process of AI's chess piece operations:
PotentialMoves: Returns a list that represents the possibility of AI winning when moving a chess piece to any column in the list. The values are random numbers from -1 to 1. When the value is negative, it means that the player may win in the next two moves, and the smaller the value, the greater the possibility of the player winning. If the value is 0, it means that the player will not win, and AI will also not win. If the value is 1, it means that AI can win.
bestMoveFitness: Fitness is the maximum value selected from PotentialMoves.
bestMoves: If there are multiple maximum values in PotentialMoves, it means that the player's chances of winning are the smallest when AI moves the chess piece to the columns where these values are located. Therefore, these columns are added to the list bestMoves.
column: When there are multiple values in bestMoves, randomly select one column from bestMoves as AI's movement. If there is only one value, column is this unique value.
In the project, by printing these bestMoveFitness, bestMoves, column, and potentialMoves, we can deduce the parameters of AI's each step in the above figure.
By examining AI's selection in the third step, we can have a better understanding of the algorithm:
The figure below illustrates some of the AI's moves, showing the possible choices for the player if AI places a piece in the first column, and the impact of AI's next move on the player's chances of winning. Through this search and iteration process, the AI can determine the winning situations for both the opponent and itself in the next two steps, and make decisions accordingly.
The figure below is a flowchart of calculating the fitness value for AI. In this project, the difficulty coefficient is 2, and we need to consider 7^4=2041 cases:
From the above flowchart, it is not difficult to find that if AI places its first piece in column 0, 1, 2, 4, 5, or 6, the player can always place the remaining two pieces in column 3 and win. For ease of expression, we use a sequence to represent various combinations, where the first element represents AI's first move, the second number represents the player's response, and the third number represents AI's response. "X" represents any valid move. Therefore, [0,0,x]=0, and it can be deduced that when the sequence is [0,x<>3,x], the player cannot win. Only when the player's second piece is in column 3, and AI's second move is not in column 3, can AI win. Therefore, [0,x=3,x<>3] = -1, and there are 6 such cases. The final result is (0+0+...(43 times)-1*6)/7/7 = -0.12.
By the same reasoning, the results for the other four cases are all -0.12. If AI's first move is in column 3, the player cannot win, and AI cannot win either, so the value is 0. AI chooses the move with the highest fitness value, which means it will place its piece in column 3.
The same analysis can be applied to AI's subsequent moves. In summary, the higher the possibility of the player winning after AI's move, the lower the fitness value for AI, and AI will choose the move with a higher fitness value to prevent the player from winning. Of course, if AI can win itself, it will prioritize the move that leads to its own victory.
def getPotentialMoves(board, tile, lookAhead):
if lookAhead == 0 or isBoardFull(board):
'''
If the difficulty coefficient is 0 or the board is full,
return a list with all values set to 0. This means that
the fitness value is equal to the potential moves for each column.
In this case, AI will drop the piece randomly and lose its intelligence.
'''
return [0] * BOARDWIDTH
## Determine the color of the opponent's piece
if tile == RED:
enemyTile = BLACK
else:
enemyTile = RED
potentialMoves = [0] * BOARDWIDTH
## Initialize a list of potential moves, with all values set to 0
for firstMove in range(BOARDWIDTH):
## Iterate over each column and consider any move by either side as the firstMove
## The move by the other side is then considered as the counterMove
## Here, our firstMove refers to AI's move and the opponent's move is considered as counterMove
## Take a deep copy of the board to prevent mutual influence between board and dupeBoard
dupeBoard = copy.deepcopy(board)
if not isValidMove(dupeBoard, firstMove):
## If the move of placing a black piece in the column specified by firstMove is invalid in dupeBoard
continue
## Continue to the next firstMove
makeMove(dupeBoard, tile, firstMove)
## If it is a valid move, set the corresponding grid color
if isWinner(dupeBoard, tile):
## If AI wins
potentialMoves[firstMove] = 1
## The winning piece automatically gets a high value to indicate its chances of winning
## The larger the value, the higher the chances of winning, and the lower the chances of the opponent winning
break
## Do not interfere with the calculation of other moves
else:
if isBoardFull(dupeBoard):
## If there are no empty grids in dupeBoard
potentialMoves[firstMove] = 0
## It is not possible to move
else:
for counterMove in range(BOARDWIDTH):
## Consider the opponent's move
dupeBoard2 = copy.deepcopy(dupeBoard)
if not isValidMove(dupeBoard2, counterMove):
continue
makeMove(dupeBoard2, enemyTile, counterMove)
if isWinner(dupeBoard2, enemyTile):
potentialMoves[firstMove] = -1
## If the player wins, the fitness value for AI in this column is the lowest
break
else:
## Recursively call getPotentialMoves
results = getPotentialMoves(dupeBoard2, tile, lookAhead - 1)
## Use floating-point representation here for more accurate results
## This ensures that the values in potentialMoves are within the range [-1, 1]
potentialMoves[firstMove] += (sum(results)*1.0 / BOARDWIDTH) / BOARDWIDTH
return potentialMoves
Drag the chess piece, determine the square where the chess piece is located, validate the chess piece, call the chess piece drop function, and complete the operation.
def getHumanMove(board, isFirstMove):
draggingToken = False
tokenx, tokeny = None, None
while True:
## Use pygame.event.get() to handle all events
for event in pygame.event.get():
if event.type == QUIT: ## Stop and exit
pygame.quit()
sys.exit()
elif event.type == MOUSEBUTTONDOWN and not draggingToken and REDPILERECT.collidepoint(event.pos):
## If the event type is mouse button down, draggingToken is True, and the mouse click position is inside REDPILERECT
draggingToken = True
tokenx, tokeny = event.pos
elif event.type == MOUSEMOTION and draggingToken: ## If the red piece is dragged
tokenx, tokeny = event.pos ## Update the position of the dragged piece
elif event.type == MOUSEBUTTONUP and draggingToken:
## If the mouse is released, and the chess piece is dragged
## If the chess piece is dragged directly above the board
if tokeny < YMARGIN and tokenx > XMARGIN and tokenx < WINDOWWIDTH - XMARGIN:
column = int((tokenx - XMARGIN) / SPACESIZE) ## Determine the column where the chess piece will drop based on the x coordinate of the chess piece (0,1...6)
if isValidMove(board, column): ## If the chess piece move is valid
"""
Drop into the corresponding empty square,
This function only shows the dropping effect
The chess piece filling the square can also be achieved without this function by the following code
"""
animateDroppingToken(board, column, RED)
## Set the bottom most square in the empty column to red
board[column][getLowestEmptySpace(board, column)] = RED
drawBoard(board) ## Draw the red chess piece in the dropped square
pygame.display.update() ## Window update
return
tokenx, tokeny = None, None
draggingToken = False
if tokenx != None and tokeny != None: ## If a chess piece is dragged, display the dragged chess piece
drawBoard(board, {'x':tokenx - int(SPACESIZE / 2), 'y':tokeny - int(SPACESIZE / 2), 'color':RED})
## Adjust the x, y coordinates so that the mouse is always at the center position of the chess piece during dragging
else:
drawBoard(board) ## When it is an invalid move, after the mouse is released, because all the values in the board are none
## When calling drawBoard, the operations performed are to display the two chess pieces below, which is equivalent to returning the chess piece to the location where it started dragging
if isFirstMove:
DISPLAYSURF.blit(ARROWIMG, ARROWRECT) ## AI moves first, display the hint operation image
pygame.display.update()
FPSCLOCK.tick()
In above code, the getHumanMove() function handles the player's move. The animateDroppingToken() function animates the dropping of the token. The getLowestEmptySpace() function returns the lowest empty space in a column.
Implement the function to animate the computer's movement and landing of AI pieces in the respective positions.
def animateComputerMoving(board, column):
x = BLACKPILERECT.left ## The left coordinate of the black piece at the bottom
y = BLACKPILERECT.top ## The top coordinate of the black piece at the bottom
speed = 1.0
while y > (YMARGIN - SPACESIZE): ## When y has a larger value, indicating that the piece is below the window
y -= int(speed) ## Decrease y continuously, which means the piece moves up
speed += 0.5 ## Increase the speed at which y decreases
drawBoard(board, {'x':x, 'y':y, 'color':BLACK})
## y keeps changing, continuously drawing the black piece, creating an effect of continuous ascent
pygame.display.update()
FPSCLOCK.tick()
## When the piece ascends to the top of the board
y = YMARGIN - SPACESIZE ## Reset y, so that the bottom of the piece is aligned with the top of the board
speed = 1.0
while x > (XMARGIN + column * SPACESIZE): ## When x is greater than the x coordinate of the desired column
x -= int(speed) ## Decrease x continuously, which means the piece moves to the left
speed += 0.5
drawBoard(board, {'x':x, 'y':y, 'color':BLACK})
## At this point, the y coordinate remains unchanged, which means the piece moves horizontally to the column
pygame.display.update()
FPSCLOCK.tick()
## The black piece lands on the calculated empty space
animateDroppingToken(board, column, BLACK)
Select the highest number from the list of potentialMoves returned, as the fitness value, and randomly choose from those columns with high fitness values as the final movement target.
def getComputerMove(board):
potentialMoves = getPotentialMoves(board, BLACK, DIFFICULTY) ## Potential moves, a list with BOARDWIDTH values
## The values in the list are related to the difficulty level set
bestMoves = [] ## Create an empty bestMoves list
bestMoveFitness = -1 ## Since the minimum value in potentialMoves is -1, it serves as the lower limit
print(bestMoveFitness)
for i in range(len(potentialMoves)):
if potentialMoves[i] > bestMoveFitness and isValidMove(board, i):
bestMoveFitness = potentialMoves[i] ## Continuously update bestMoves, so that each value in bestMoves is the largest
## while ensuring that the move is valid.
for i in range(len(potentialMoves)):
if potentialMoves[i] == bestMoveFitness and isValidMove(board, i):
bestMoves.append(i) ## List all the columns where the piece can be moved to. This list may be empty, contain
## only one value, or multiple values.
print(bestMoves)
return random.choice(bestMoves) ## Randomly choose one of the columns where the piece can be moved to as the target move.
By continuously changing the corresponding coordinates of the pieces, achieve the animation effect of falling.
def getLowestEmptySpace(board, column):
## Return the lowest empty space in a column
for y in range(BOARDHEIGHT-1, -1, -1):
if board[column][y] == EMPTY:
return y
return -1
def makeMove(board, player, column):
lowest = getLowestEmptySpace(board, column)
if lowest != -1:
board[column][lowest] = player
'''
Assign the player (red/black) to the lowest empty space in the column.
Because the piece is dropped in the lowest empty space in a column,
it is considered as the color of that space.
'''
def animateDroppingToken(board, column, color):
x = XMARGIN + column * SPACESIZE
y = YMARGIN - SPACESIZE
dropSpeed = 1.0
lowestEmptySpace = getLowestEmptySpace(board, column)
while True:
y += int(dropSpeed)
dropSpeed += 0.5
if int((y - YMARGIN) / SPACESIZE) >= lowestEmptySpace:
return
drawBoard(board, {'x':x, 'y':y, 'color':color})
pygame.display.update()
FPSCLOCK.tick()
In above code, the makeMove() function makes a move on the board. The animateDroppingToken() function animates the dropping of the token. The getLowestEmptySpace() function returns the lowest empty space in a column.
Judge the validity of a piece's move, judge if there are still empty spaces on the chessboard.
def isValidMove(board, column):
## Judge the validity of a piece's move
if column < 0 or column >= (BOARDWIDTH) or board[column][0] != EMPTY:
## If the column is less than 0 or greater than BOARDWIDTH, or there is no empty space in the column
return False
## Then it is an invalid move, otherwise it is valid
return True
def isBoardFull(board):
## If there are no empty spaces in the grid, return True
for x in range(BOARDWIDTH):
for y in range(BOARDHEIGHT):
if board[x][y] == EMPTY:
return False
return True
In above code, the isValidMove() function returns True if the move is valid. The isBoardFull() function returns True if the board is full.
Several diagrams are provided for easy understanding of the four winning conditions. The positions shown in the diagram correspond to the extreme values ââof x and y.
def isWinner(board, tile):
## Check for horizontal situation of pieces
for x in range(BOARDWIDTH - 3): ## x takes on the values 0, 1, 2, 3
for y in range(BOARDHEIGHT): ## iterate through all rows
## If x = 0, check if the first four pieces in the yth row are all the same tile. This can be used to traverse all horizontal situations of pieces connecting four in a row. If any x, y is true, it can be determined as a win
if board[x][y] == tile and board[x+1][y] == tile and board[x+2][y] == tile and board[x+3][y] == tile:
return True
## Check for vertical situation of pieces, similar to the horizontal situation
for x in range(BOARDWIDTH):
for y in range(BOARDHEIGHT - 3):
if board[x][y] == tile and board[x][y+1] == tile and board[x][y+2] == tile and board[x][y+3] == tile:
return True
## Check for left-leaning diagonal situation of pieces
for x in range(BOARDWIDTH - 3): ## x takes on the values 0, 1, 2, 3
for y in range(3, BOARDHEIGHT): ## because when forming a left-leaning diagonal four in a row, the bottom-most piece must be at least four squares away from the top, i.e. y >= 3
if board[x][y] == tile and board[x+1][y-1] == tile and board[x+2][y-2] == tile and board[x+3][y-3] == tile: ## determine if the left-leaning diagonal four pieces are the same color
return True
## Check for right-leaning diagonal situation of pieces, similar to the left-leaning diagonal situation
for x in range(BOARDWIDTH - 3):
for y in range(BOARDHEIGHT - 3):
if board[x][y] == tile and board[x+1][y+1] == tile and board[x+2][y+2] == tile and board[x+3][y+3] == tile:
return True
return False
Finally, we create the game main loop to keep the game running continuously.
def main():
## Exsiting code omitted
isFirstGame = True ## Initialize isFirstGame
while True: ## Keep the game running continuously
runGame(isFirstGame)
isFirstGame = False
def runGame(isFirstGame):
if isFirstGame:
## At the start of the first game
## Let the AI make the first move so that players can watch how the game is played
turn = COMPUTER
showHelp = True
else:
## For the second game and onwards, assign turns randomly
if random.randint(0, 1) == 0:
turn = COMPUTER
else:
turn = HUMAN
showHelp = False
mainBoard = getNewBoard() ## Set up the initial empty board structure
while True: ## Game main loop
if turn == HUMAN: ## If it's the player's turn
getHumanMove(mainBoard, showHelp) ## Call the method for player's move, see getHumanMove method for details
if showHelp:
## If there's a hint image, turn off the hint after AI makes the first move
showHelp = False
if isWinner(mainBoard, RED): ## If red chip (player) wins
winnerImg = HUMANWINNERIMG ## Load the player winning image
break ## Exit the loop
turn = COMPUTER ## Hand over the first move to the AI
else:
## If it's the AI's turn
column = getComputerMove(mainBoard) ## Call the method for AI's move, see getComputerMove method for details
print(column)
animateComputerMoving(mainBoard, column) ## Move the black chip
makeMove(mainBoard, BLACK, column) ## Set the bottom-most empty slot in the column as black
if isWinner(mainBoard, BLACK):
winnerImg = COMPUTERWINNERIMG
break
turn = HUMAN ## Switch to the player's turn
if isBoardFull(mainBoard):
## If the board is full, it's a tie
winnerImg = TIEWINNERIMG
break
Based on the Monte Carlo algorithm, this project implemented a human-vs-AI chess game using Python with the Pygame module. The project allowed us to become familiar with the basics of creating instances and moving objects in Pygame, and also gave us a preliminary understanding of the specific application of the Monte Carlo algorithm.
We use cookies for a number of reasons, such as keeping the website reliable and secure, to improve your experience on our website and to see how you interact with it. By accepting, you agree to our use of such cookies. Privacy Policy
