Othello with Alpha-Beta Pruning

An interactive Othello (Reversi) game engine that pairs a Prolog-based AI backend with a Python interface. The AI uses alpha-beta pruning over a minimax search tree, with a positional weight heuristic derived from research literature.

Overview

The project is contained in a single Jupyter notebook (othello.ipynb). At runtime, the notebook generates a Prolog source file (othello.pl) containing the core game logic and search algorithm, then interfaces with it through PySwip.

The human player interacts via the notebook's console, entering moves in chess-style notation (e.g., D3, A1). The AI responds with its computed best move, printing the search time and board evaluation score.

Architecture

Prolog Engine (othello.pl, generated at runtime)

• Board representation -- Flat 64-element list encoding an 8x8 grid (0 = empty, 1 = black, 2 = white).
• Move validation and execution -- Checks all eight directions for valid flips, then applies them.
• Position weight matrix -- Assigns strategic values to every square based on known Othello heuristics:
  • Corners: +120 (highest value, permanently stable)
  • X-squares (diagonal to corners): -40 (dangerous, risk giving up corners)
  • C-squares (adjacent to corners): -20
  • Edges: +20 (stable once captured)
  • Center: +3
• Board evaluation function -- Combines three weighted factors:
  • Positional weight difference (x10)
  • Mobility difference, i.e., number of legal moves (x5)
  • Piece count difference (x1)
• Alpha-beta pruning -- Negamax-style minimax with alpha-beta cutoffs. Moves are ordered (corners first, then edges, then interior) to improve pruning efficiency.

Python Interface (Othello class)

• Wraps all Prolog queries behind a clean Python API.
• Handles board display (ASCII art with Unicode disc symbols), coordinate conversion, move input/output, and game state management.
• Supports three difficulty levels that control the search depth:
  • beginner -- depth 1
  • amateur -- depth 3
  • professional -- depth 5

Game Loop (play_othello())

• Manages turn alternation between human and AI.
• Displays valid moves on the board (marked with x) during the human's turn.
• Detects forced passes (no legal moves) and game termination (no moves for either player or two consecutive passes).
• Announces the winner and final score.

Requirements

• Python 3
• SWI-Prolog installed and accessible
• Python packages: pyswip, numpy

On macOS with Homebrew:

brew install swi-prolog
pip install pyswip numpy

On Linux (Debian/Ubuntu):

sudo apt-get install swi-prolog
pip install pyswip numpy

The notebook also runs on Google Colab, where it installs SWI-Prolog and PySwip automatically.

Usage

Open othello.ipynb in Jupyter or VS Code and run all cells. The final cell starts an interactive game:

play_othello(difficulty='beginner', human_color='black')

Parameters:

Parameter	Values	Default
difficulty	'beginner', 'amateur', 'professional'	'amateur'
human_color	'black', 'white'	'black'

Moves are entered in the format <column letter><row number>, e.g., D3. Enter q to quit mid-game.

Board Display

  A B C D E F G H
  ────────────────
1|· · · · · · · ·
2|· · · · · · · ·
3|· · · x · · · ·
4|· · x ● ○ · · ·
5|· · · ○ ● x · ·
6|· · · · x · · ·
7|· · · · · · · ·
8|· · · · · · · ·

• ○ -- Black
• ● -- White
• x -- Valid move for the current player
• · -- Empty square