In part 1, I used OpenCV and Python to load our game and get to the board data. In part 2, I built the basic mechanics for our AI to make moves.
In this post, I’ll be going over more advanced mechanisms used to allow our AI to make better moves.
Revisiting Detecting Pieces
After allowing our AI agent to detect valid moves and making moves, the issue with getting our game board information for the first move becomes obvious. Take a look at the photo below.
The start of a new game
Due to the color ranges used to detect blue and white pieces, it’ll confuse our algorithm once we classify the color piece on the blue prompts. To avoid this problem, some experimenting was needed to redefine the range of colors that would be searched when classifying some of our pieces. Since the prompts are blue and white, it was necessary to tweak the ranges for these colors.
In the case of white, the color was tweaked on order to get the darker portions of the pieces. Originally, the values used were within the 200s (we’re using BGR colorspace, it’s just the reverse of RGB):
[200, 200, 200] - [255, 255, 255]The new ranges used to get the new colors are as follows:
[145, 145, 145] - [175, 175, 175]In the case of blue, we only needed to reduce the upper bound of our range from 255 to 225. After the tweak, we get the new range:
[128, 128, 0] - [225, 225, 0]With these new values, we now have no problem getting board information regardless of what move we’re making.
Providing Our Agent More Information
It’s great that we now have a program that can play a game of Bejeweled. However, our agent doesn’t have additional information like:
Match type (3-match, 4-match, T-shape, etc.).
Whether two matches will occur in a single move.
Whether a cascade will occur.
Such information would allow our agent to play better.
Determining Match Type
Right now, our agent can only determine whether or not a move exists. 4, 5, T, L, and 3 way matches provide more points than 3-match moves. Those moves also allow us to complete the level faster. How would we go about determining the types of matches to be made?
Before typing the code, we need to figure out how to get the match types. Here’s a diagram of valid matches that can be made when a move is made.
A diagram of valid match types.
From the diagram, the following matches criteria can be made with the red square:
3-match – Made with 2 green squares on one side or a green square on the left and right side but not on top.
4-match – Made with 2 green squares on one side and a green square on the opposite side. The squares on top don’t count.
5-match – Made with 2 green squares on the left and right sides.
T-match – Made with at least one green square on the right and left sides as well as 2 green squares on top.
L-match – Made with 2 green squares on perpendicular sides (left and top or right and top).
3-way – Made with 2 green squares on all sides. This is a special case of the T-match.
Now that the match criteria has been defined, we need to write up some code that’ll mark where the match occurs:
ways = {1: 0, 2: 0, 3: 0}
print("Getting move for ({}, {})".format(x, y))
# Get the number of a color gem in a consecutive line
if d == "U":
c = board[y-1][x]
for i in range(1,3):
# Down
if y+i < 8 and board[y+i][x] == c:
if i == 2 and ways[2] == 0:
continue
ways[2] = i
# Right
if x+i < 8 and board[y][x+i] == c:
if i == 2 and ways[3] == 0:
continue
ways[3] = i
# Left
if x-i >= 0 and board[y][x-i] == c:
if i == 2 and ways[1] == 0:
continue
ways[1] = iWhile this conditional only handles the right swap case, handling the others follows the same logic. We need to determine how many pieces of the same colors are adjacent to the center piece. After the number of adjacent pieces are tracked, we then determine the kind of match that’ll be made.
The following code will do we’re looking for:
theType = None
if ways[1] == 2 and ways[2] == 2 and ways[3] == 2:
theType = "3W"
elif ways[1] > 0 and ways[3] > 0 and ways[2] == 2:
theType = "T"
elif (ways[1] == 2 or ways[3] == 2) and ways[2] == 2:
theType = "L"
elif ways[1] == 2 and ways[3] == 2:
theType = "5M"
elif (ways[1] == 2 and ways[3] == 1) or (ways[1] == 1 and ways[3] == 2):
theType = "4M"
else:
theType = "3M"
return theTypeChecking for Double Match
Some of you may be wondering, why do we care for a double match? Simple, it awards us more points. It also helps us progress through the level a bit faster.
How exactly do we determine a double match? Surprisingly, it’s very simple. You just need to get the move after it was made and check whether that move is in the possible moveset. If so, then the move will cause a double match. As an interesting note, this function is an involution.
The following method can be used to get the list of moves that’ll cause a double match.
def checkDoubleMove(self, moves):
doubles = []
for move in moves:
x = int(move[1])
y = int(move[3])
d = move[-1]
if d == "R":
x += 1
d = "L"
elif d == "L":
x -= 1
d = "R"
elif d == "U":
y -= 1
d = "D"
else:
y += 1
d = "U"
newPos = "({},{}){}".format(x, y, d)
if newPos in moves:
doubles.append(move)
return doublesChecking for Cascade Effect
When a match is made, it can cause a cascade of matches. When a cascade occurs, the amount of points and progress awarded multiplies. This allows you to complete levels faster.
In order to determine a cascade effect, you’ll need to analyze the board state after a move is made. We’ll split this task into three parts.
The first step is to emulate the swap. The code below is pretty straightforward.
d = move[-1]
x = int(move[1])
y = int(move[3])
if d == "R":
tmp = board[y][x + 1]
board[y][x + 1] = board[y][x]
board[y][x] = tmp
elif d == "L":
tmp = board[y][x - 1]
board[y][x - 1] = board[y][x]
board[y][x] = tmp
elif d == "U":
tmp = board[y - 1][x]
board[y-1][x] = board[y][x]
board[y][x] = tmp
else:
tmp = board[y + 1][x]
board[y + 1][x] = board[y][x]
board[y][x] = tmpThe next step is to grab the spots that are part of the match. Note that we store the spot as (y, x) instead of (x,y) coordinates. This is done to make the last easier on us.
We also need to prevent duplicate values from being store in our spot list.
The code below will allow us to get the spots that’ll be part of a match.
spots = []
# Get the spots that are now a match
# Vertical search
for xCur in range(8):
for yCur in range(6):
if board[yCur][xCur] == board[yCur+1][xCur] and \
board[yCur+1][xCur] == board[yCur+2][xCur]:
if (yCur, xCur) not in spots:
spots.append((yCur, xCur))
if (yCur+1, xCur) not in spots:
spots.append((yCur+1, xCur))
if (yCur+2, xCur) not in spots:
spots.append((yCur+2, xCur))
# Horizontal search
for yCur in range(8):
for xCur in range(6):
if board[yCur][xCur] == board[yCur][xCur+1] and \
board[yCur][xCur+1] == board[yCur][xCur+2]:
if (yCur, xCur) not in spots:
spots.append((yCur, xCur))
if (yCur, xCur+1) not in spots:
spots.append((yCur, xCur+1))
if (yCur, xCur+2) not in spots:
spots.append((yCur, xCur+2))The final step is simply moving the pieces to reflect the board state after making the swap.
In the previous step, we made sure to store our spots as (y, x) coordinates. This’ll allow to sort our list of tuples in ascending order for the y-coordinate. Without the sort, we run the risk of incorrectly generating the board state.
As we go through each spot, we move all the pieces down and fill the top most coordinate with a ‘N/A’.
The following code will allow to correctly get the board state.
# Now that we have the matches, predict after effect.
spots.sort()
for curY, curX in spots:
while curY != 0:
board[curY][curX] = board[curY-1][curX]
curY -=1
board[0][curX] = 'N/A'
return boardNote that this algorithm will not account for cascades that can occur with newly generated pieces.
Giving Swap Priority and Putting It Together
Now that we have methods that’ll give much more information, how to we prioritize which move should be made?
For me, I give the following priorities in order:
The match type
Whether two matches will occur in a single move.
Whether a cascade will occur.
To allow for this priority, I ended up using Pandas. Pandas is a Python framework that’s normally used in Data Science.
With Pandas, we need to override the sorting mechanism for match types. We’ll be sorting the match type in descending order:
3-Way
T-Shape
L-Shape
5-Match
4-Match
3-Match
Using the methods and sorting priorities defined, we create the following method to allow our AI agent to pick the best move:
def getBestMove(self, board):
moves = self.processBoard(board)
doubles = self.checkDoubleMove(moves)
moveData = {"move": [], "type": [], "double": [], "reaction":[]}
for move in moves:
theType = self._getMatchType(
board,
int(move[1]),
int(move[3]),
move[-1]
)
isDouble = move in doubles
afterBoard = self.predictAfterMove(move, copy.deepcopy(board))
cascadeAmount = 0
for x in range(8):
for y in range(6):
if afterBoard[y][x] == 'N/A':
continue
if afterBoard[y][x] == afterBoard[y+1][x] and afterBoard[y+1][x] == afterBoard[y+2][x]:
cascadeAmount += 1
for y in range(8):
for x in range(6):
if afterBoard[y][x] == 'N/A':
continue
if afterBoard[y][x] == afterBoard[y][x+1] and afterBoard[y][x+1] == afterBoard[y][x+2]:
cascadeAmount += 1
moveData['move'].append(move)
moveData['type'].append(theType)
moveData['double'].append(isDouble)
moveData['reaction'].append(cascadeAmount)
matchOrdering = ["3W", "T", "L", "5M", "4M", "3M"]
moveInfo = pd.DataFrame(moveData, columns=["move", "type", "double", "reaction"])
moveInfo.type = moveInfo.type.astype("category")
moveInfo.type.cat.set_categories(matchOrdering, inplace=True)
moveInfo.sort_values(["type", "double", "reaction"], ascending=[True, False, False], inplace=True)
print(moveInfo.head(len(moveInfo)))
bestMove = moveInfo.head(1).reset_index(drop=True)["move"][0]
return bestMoveOf course, there are additional ways to measure the best move, but there comes a point when conflicting priorities start to occur.
Conclusion
We finally did it! We went from just launching our application to flat out playing a whole game. There are a few improvements that can be made, but they’re beyond the scope of the project.
The codebase for this project can be found in this github page.
For demonstration purposes, here’s a video for the agent in works.