As a casual attempt to accomplish a Grand Assignment, I created a Reversi game with Python. The project is open-source on GitHub and you can view it with the link above.
The game implements the following functionality:
- Graphical User Interface (GUI), using PyQt5
- Built-in AI implemented as a heuristic searching (and evaluation) algorithm
The core functionality of the game is pretty simple, and should be easy for anyone familiar with the Reverso game. The code is in
It’s the GUI and the AI part that differentiates implementations of the Reversi game. Since GUI isn’t very hard to create with Qt, I’ll focus on the AI algorithm here.
As a general (and relatively easy) way to create an AI for the game, heuristic searching well balances between coding complexity and the competence of the resulting algorithm. Heuristic searching is basically a complete searching tree at limited depth, equipped with a heuristic evaluation function that determines the situation of the game board.
From my previous experiences in playing Reversi with others, I’ve learnt that it’s important to occupy side grids and corner grids, while avoiding the opponent to occupy them. With some research and calculation, this boils down to a predefined weight table:
SCORE = [ [ 500, -150, 30, 10, 10, 30, -150, 500], [ -150, -250, 0, 0, 0, 0, -250, -150], [ 30, 0, 1, 2, 2, 1, 0, 30], [ 10, 0, 2, 16, 16, 2, 0, 30], [ 10, 0, 2, 16, 16, 2, 0, 30], [ 30, 0, 1, 2, 2, 1, 0, 30], [ -150, -250, 0, 0, 0, 0, -250, -150], [ 500, -150, 30, 10, 10, 30, -150, 500] ]
This is a good start but may not be sufficient in complicated scenarios. While it’s good to try to occupy sides and corners, it’d be of little value when they’re easily captured by the opponent.
Given the idea above, I came up with this “chess liberty” solution. The score will be decreased if a chess is “too liberated”.
for dx in [-1, 0, 1]: for dy in [-1, 0, 1]: tx, ty = x + dx, y + dy if 0 <= tx < BS and 0 <= ty < BS and board[tx][ty] == EMPTY: liberty += 1 if chess == BLACK: c1 += 1 s1 += SCORE[x][y] - liberty * LIBERTY else: c2 += 1 s2 += SCORE[x][y] - liberty * LIBERTY
s1 is the score for the black side, and
s2 is the score for the white side.
The final part is the side chess check (code). It checks if a corner may be occupied by the opponent (having own chess around), and if it’s occupied, add additional score if there are more chesses of the same color.
A plain searching algorithm would be really plain. The black side wants the score to be as high as possible, while the white side wants the exact opposite.
A pseudo-code of the algorithm is given below:
MAX = 999999 function heuristicSearch(game, side, depth) if depth <= 0 return null, heuristicScore(game) want_max = (side == BLACK) bestMove = null if want_max bestScore = -MAX - 1 else bestScore = +MAX + 1 for move in game.availableMoves game.perform move // Recurse subMove, subScore = heuristicSearch(game, side, depth - 1) game.undo if want_max if subScore > bestScore bestScore = subScore bestMove = move else if subScore < bestScore bestScore = subScore bestMove = move return bestMove, bestScore
That’s the abstract of the searching procedure. There are a few things to do before it’s fully working.
- Handle the case where the game has ended already
- Handle the case where the current player has no moves available
Both cases aren’t too complex to be handled with a few lines of codes. And then, there’s a performance concern: Why bother searching deeper when one move is bad enough that subsequent moves can’t perform any better?