Othello game solution algorithms and GNN

About the Othello game

The game of Othello (Othello) is a board game played between two players using black and white discs, with the basic rule of competition being that players place a disc of their own colour and change it to their own colour by flipping it between their opponent’s discs.

The Othello board layout is an 8×8 grid, as shown in the diagram above, with two white and two black discs placed crosswise in the four central squares in the initial layout. The order of play is usually the black player first, taking it in turns to place his or her discs, and if, when placing a disc, he or she is able to pinch an opponent’s disc that has already been placed with his or her own disc, then all of his or her discs will change to his or her own colour. The disc can be placed vertically, horizontally or diagonally. If there is no place to place a disc on your turn, you must pass, and the game ends when both players pass in succession, and also when the board is completely filled or when both players have no more places to place a disc. The player with more discs of his or her own colour at that point wins.

Othello game solution algorithm

Despite its simple rules, Othello is a very strategic game, with the following basic strategies

• Take the corners: placing a disc on a corner is a powerful position because the disc is difficult to flip over, and in the early stages of the game it is important to be careful not to let your opponent take the corner.
• Keep the edges: the edges of the board are less likely to be pinched, so controlling the edges is also advantageous.
• Don’t turn over unnecessarily: the more discs you turn over, the higher the risk that your opponent will turn them over. One important strategy is to avoid flipping over too many discs unnecessarily and to prevent your opponent from making advantageous moves.

Approaches to solving the game of Othello by machine have been considered for a long time, and the game is classified as a two-player zero-sum finite-confirmation complete information game, with a 6-0 record in 1997 in a six-round game against a human. The game tree complexity of Othello is about 10 to the 58th power and has not been fully analysed by computers, but on 30 October 2023, a pre-peer-reviewed paper was published on the arXiv by Takumi Takizawa of Preferred Networks, Japan, claiming to have proved that 8×8 Othello is a draw in a best progression ‘Othello is Solved’.

The classical solution algorithm for solving Othello would be as follows.

1. Minimax Algorithm: The Minimax Algorithm, described in ‘Minimax Algorithm Overview, Algorithm and Implementation Examples’, is a method for selecting the best move by exploring the Othello game tree. The search is recursive, with each player choosing his or her best move and the opposing player choosing the best move for that best move. As the computational complexity increases with the depth of the game tree, when the search is limited in depth, the evaluation function is used to calculate the evaluation value of the current board and the move that maximises (own move) or minimises (opponent’s move) the evaluation value is selected.
2. Alpha-Beta Pruning: alpha-beta pruning is a method for reducing the search space in minimax methods. It prunes unnecessary branches during the search to make the search more efficient. Specifically, the search can be terminated when it is established that the evaluation value of the player who chooses the best move (the maximising player) exceeds the current best evaluation value.
3. Evaluation Function: the evaluation function is a function for calculating the current evaluation value of the board, which in the case of Othello takes into account factors such as the placement of stones on the board, the number of stones and the securing of corners. The evaluation function is designed so that the player has a high evaluation value for the advantageous state of the board, and empirical knowledge and heuristic methods are utilised in the design of the evaluation function.
4. Monte Carlo Tree Search (MCTS): MCTS, also described in ‘Overview of Monte Carlo Tree Search, Algorithms and Examples of Implementations’, uses probabilistic methods to simulate multiple moves and select the most promising move among them. In complex games such as Othello, where it is difficult to explore all possible moves, MCTS is useful, especially in the endgame, to evaluate which moves are the best by using computational resources to play out many random playouts (simulation of the game).

In recent years, deep reinforcement learning approaches have also been used, as described in ‘Board games and AI: Why Alpha Go beat humans’ reading notes.

Othello game solution algorithms and GNNs

In solving Othello games, the use of graph neural networks (GNNs) is a powerful approach for efficiently modelling the board state and evaluating complex game phases.

The Othello game board consists of a grid of 64 squares (8 x 8), which can be modelled as a graph. By treating each square as a node and defining the neighbouring squares (top, bottom, left, right and diagonal) as edges, the entire Othello board can be viewed as a graph GNNs utilise this graph structure to learn the state of each node (square) and to predict the next move.

It has the following characteristics.

1. modelling the Othello board as a graph: each square is represented as a node with three states – black, white and blank – and each node is influenced by the states of its surrounding nodes (neighbouring squares); the GNN can learn this dependency between nodes and capture strategic patterns in the game

2. efficient game evaluation: a GNN can learn the entire board at once and evaluate several moves at the same time. This has the advantage over traditional algorithms (minimax method and Monte Carlo tree search) of being more efficient in the evaluation of each game board.

3. learning spatial dependencies: in Othello, certain locations on the board are strategically very important, such as the strategy of taking corners or the importance of squares close to the edges, etc. GNN can naturally learn such spatial dependencies and is a very advantageous approach when predicting next moves based on the evaluation of the entire board.

4. combination with reinforcement learning: GNNs can be combined with Reinforcement Learning (RL) to further enhance Othello’s solution algorithms. Reinforcement learning agents use GNNs to learn optimal moves by inputting board states and obtaining rewards; compared to traditional convolutional neural networks (CNNs), GNNs capture local features and overall strategies simultaneously, making decision-making in complex boards such as Othello more efficient more efficiently on complex boards such as Othello.

The specific algorithm using GNNs is as follows.

1. graph definition: define a graph with 64 nodes (squares of the board), each node connected by its own colour (black, white or blank) and by edges to neighbouring nodes (up, down, left, right and diagonal).

2. construction of a GNN: using the state of each node (colour and position) as input features, the GNN is used to learn the dependencies between nodes; the output of the GNN can be a prediction of what will happen next to each node (square) and a score of which square the disc should be placed in.

3. reinforcement learning agent: based on the output of the GNN, the reinforcement learning agent learns which move to choose; the GNN captures the features of each phase of Othello and can therefore assess the importance of each move with high accuracy.

4. training and data generation: an Othello AI using GNNs is trained on historical game data and simulations. Generating large amounts of new board data using generative AI and training the GNN and reinforcement learning agents on it is key to creating more powerful AI players.

GNN can also be used in conjunction with conventional algorithms such as the minimax method and MCTS. For example, when searching with the minimax method, GNN can be used as a function of the phase evaluation to calculate the degree of promise of each phase, which allows the selection of more accurate moves, and to make α-β branch pruning more efficient, GNN can also be used to narrow down in advance the number of possible phases to be explored.

implementation example

Below is an overview of an example implementation of GNN applied to Othello and the steps involved.

1. preparation and dependent libraries: first, the GNN implementation requires a library that supports the processing of graph data. Typical libraries include PyTorch Geometric and DGL (Deep Graph Library). An example implementation using PyTorch Geometric is shown here.

# Install the required libraries.
pip install torch
pip install torch-geometric

2. graphical modelling of an Othello board: the Othello board consists of 64 nodes (8×8 squares) and the nodes adjacent to each square are connected by edges. The state of the nodes (black, white or empty) is represented as a feature vector.

import torch
import torch_geometric
from torch_geometric.data import Data

# 8x8 board modelled as 64 nodes
def create_othello_graph(board):
    # Representation of the characteristics of each node (square) (empty is 0, black is 1, white is -1)
    node_features = []
    for row in board:
        for cell in row:
            if cell == 'black':
                node_features.append([1])
            elif cell == 'white':
                node_features.append([-1])
            else:
                node_features.append([0])

    node_features = torch.tensor(node_features, dtype=torch.float)

    # Create edge lists of neighbouring nodes (top, bottom, left, right and diagonal)
    edges = []
    for i in range(8):
        for j in range(8):
            node_id = i * 8 + j
            # Create edges on surrounding nodes (diagonally, up, down, left, right).
            for di in [-1, 0, 1]:
                for dj in [-1, 0, 1]:
                    if 0 <= i + di < 8 and 0 <= j + dj < 8 and (di != 0 or dj != 0):
                        neighbor_id = (i + di) * 8 + (j + dj)
                        edges.append([node_id, neighbor_id])
    
    edge_index = torch.tensor(edges, dtype=torch.long).t().contiguous()

    # Converted to PyTorch Geometric data objects.
    graph_data = Data(x=node_features, edge_index=edge_index)
    return graph_data

# Othello board in its initial state
initial_board = [
    ['empty'] * 8 for _ in range(8)
]
initial_board[3][3] = 'white'
initial_board[4][4] = 'white'
initial_board[3][4] = 'black'
initial_board[4][3] = 'black'

othello_graph = create_othello_graph(initial_board)
print(othello_graph)

3. defining the GNN model: next, the GNN model is defined. In this section, a simple GNN layer is used to create a model that predicts the next state of each node (mass).

import torch.nn as nn
from torch_geometric.nn import GCNConv  # GCNConv is a graph convolution layer

# Definition of the GNN model
class OthelloGNN(nn.Module):
    def __init__(self, input_dim, hidden_dim, output_dim):
        super(OthelloGNN, self).__init__()
        self.conv1 = GCNConv(input_dim, hidden_dim)
        self.conv2 = GCNConv(hidden_dim, hidden_dim)
        self.fc = nn.Linear(hidden_dim, output_dim)  # Finally, full connection.

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        # Graph convolution of the first layer
        x = self.conv1(x, edge_index)
        x = torch.relu(x)
        # Graph convolution of the second layer
        x = self.conv2(x, edge_index)
        x = torch.relu(x)
        # Finally, predict the next state of affairs.
        x = self.fc(x)
        return x

# Create an instance of the model
model = OthelloGNN(input_dim=1, hidden_dim=64, output_dim=1)

4. implementation of the learning process: to train the model, historical game data (board states and the best moves against them) are used. A simple example here is the prediction of the next state (black, white or empty).

# Create training data as an example (in practice, a large amount of game data is required)
train_data = [
    (create_othello_graph(initial_board), torch.tensor([0]*64))  # Labels indicate the state of the next turn.
]

# learning loop
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)
loss_fn = nn.MSELoss()

def train(model, train_data, epochs=100):
    model.train()
    for epoch in range(epochs):
        total_loss = 0
        for data, target in train_data:
            optimizer.zero_grad()
            output = model(data)
            loss = loss_fn(output.view(-1), target.float())
            loss.backward()
            optimizer.step()
            total_loss += loss.item()
        print(f'Epoch {epoch+1}, Loss: {total_loss}')

train(model, train_data)

5. execution and prediction: after the training has been completed, the next optimal move can be predicted by inputting the state of the Othello board. The following is an example of a prediction.

# Predicting the next move for a new Othello board
new_board = [
    ['empty'] * 8 for _ in range(8)
]
new_board[3][3] = 'white'
new_board[4][4] = 'white'
new_board[3][4] = 'black'
new_board[4][3] = 'black'
new_board[2][4] = 'black'

test_graph = create_othello_graph(new_board)
model.eval()
with torch.no_grad():
    prediction = model(test_graph)
    print("Prediction for next move:")
    print(prediction.view(8, 8))

Reference information and reference books

This section describes books related to graph neural networks (GNNs), game theory and Othello algorithms. These books are useful for understanding the basics and applications of GNNs and game solving algorithms.

1. related to graph neural networks (GNNs)

– Graph Representation Learning by William L. Hamilton
– A comprehensive overview of the theory and practice of representation learning and GNNs for graphical data, covering the basic concepts of learning GNNs as well as practical applications.

– Deep Learning on Graphs by Yao Ma and Jiliang Tang
– It contains detailed information on state-of-the-art techniques and applications of graph neural networks. In particular, it focuses on the application of machine learning to graph structures.

2. game theory and algorithm-related
– Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig
– Widely known as a textbook on AI, it details game-solving algorithms such as the minimax method, alpha-beta branch pruning and Monte Carlo tree search.

– Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto
– The book covers the basics and applications of reinforcement learning. It provides a basic approach to the application of reinforcement learning to games such as Othello.

– Algorithms and Networking for Computer Games by Jouni Smed and Harri Hakonen
– It describes the algorithms and networking techniques used in computer games. It teaches how game theory and AI techniques can be applied to game development.

3. books dedicated to the game of Othello

– The Art of Computer Game Design by Chris Crawford
– There is a wealth of discussion of design and algorithms in computer games in general, which is useful for designing strategy games such as Othello.