Othello

---

Othello/Reversi game coded in C++, with an ncurses TUI. Can play against an 'AI'.

• Since you're here, I assume you already know how to play... If not, here's a link.
• To play the game, clone the repo, then build and run:

  cmake -B build && cmake --build build
  ./build/main

Dependencies: building from source requires CMake (≥3.16) and ncurses (wide-char build). On macOS: brew install cmake ncurses. The CMakeLists locates ncurses automatically — on Apple it queries brew --prefix ncurses; on Linux the system package is found via the standard search paths.

Disclaimer: the game targets Unix-based systems (macOS/Linux). On Windows you'll need a POSIX-compatible environment like WSL to compile and run it.

---

Game modes

1. Player vs Player
2. Player vs AI
3. AI vs AI
4. Puzzle Mode

---

Features

• Interactive ncurses TUI — the whole game (menus included) runs as a persistently redrawn curses screen: Unicode board with box-drawing borders, a filled ● for White and hollow ○ for Black, valid moves highlighted in green, and the last move played highlighted in red. Falls back to plain ASCII glyphs and/or no color automatically on terminals that don't support Unicode or color.
• Mouse or keyboard, your choice — click any cell to play it, or type the coordinate (e.g. D3) and press Enter. Clicking near a cell's edge is forgiving; a click that lands exactly on the line between two cells is safely rejected (with a message) rather than guessing which one you meant.
• Menus are navigable by arrow keys, j/k (vim-style), mouse click, or number keys — game mode, time limits, disk color, and Puzzle Mode setup are all on-screen selection/entry screens rather than typed prompts.
• AI time limit can be set to any decimal number of seconds (minimum 0.1s), default = 1 (enter 0 to use the default). In AI vs AI mode each side has its own time limit.
• In PvE mode the player can choose their disk color and consequently, who starts first.
• Undo (U) — reverts your last move. In PvE mode, undoes back to the player's own last turn, skipping over the AI's move.
• Resign (R) — immediately concedes the game and awards the win to the opponent.
• Recent-moves log — a persistent panel below the board keeps the last 10 moves/skips visible (including the AI's search score, depth reached, and nodes searched for each of its moves), so fast AI-vs-AI play or turn-skips stay legible instead of flashing past.
• Game-over screen shows the final board position alongside the result, and waits for a keypress before exiting.
• Game log export — at the end of every game, three files are saved to the logs/ folder:
  • .log — raw move sequence on a single line
  • .txt — human-readable log with move history, scores, result, and game settings
  • .csv — one row per AI move (move_number,score,depth,nodes,opening,date,game_mode,player_color,time_limit_b,time_limit_w), for graphing or long-term analysis. nodes is the number of search-tree nodes visited for that move (0 for book moves, since they don't search). opening is whatever was showing in the opening-name display right after that move (blank if none had matched yet)
• Optional score/depth chart — set OTHELLO_GRAPH=1 to also generate a .png chart of AI score and search depth per move (via plot_game.py, requires python3 + matplotlib). Off by default; the game runs with zero extra dependencies otherwise.
• Live opening name — when the game is following a known line from real Othello opening theory, its name (e.g. "Tiger") is shown below the score. See Opening book below.

---

Puzzle Mode

Puzzle Mode lets you load a custom board position and watch the AI play both sides from that state.

Setup (choose via the on-screen menus/text-entry screens):

1. Choose a board input format:
   • FEN-like string — rows separated by /, using B/b (Black), W/w (White), and digits 1–8 for empty cells. Example: 8/8/8/3WB3/3BW3/8/8/8
   • 64-character string — left-to-right, top-to-bottom using B/b, W/w, and . for empty. Example: ...........................WB......BW...........................
2. Specify whose turn it is (B for Black, W for White).
3. Set a time limit for the AI (shared by both sides).

The AI then plays out the game from the given position.

---

Notes on 'AI'

• Board representation: bitboards — the board is two 64-bit integers (one bit per square, one integer per color) instead of a grid. This makes move generation, flipping, and scoring fast bitwise operations instead of cell-by-cell loops.
• Opening book: the first several moves of a game are often looked up instantly instead of searched, drawn from real Othello opening theory — see Opening book below.
• Search: Iterative deepening (IDDFS) with a time limit. The deadline is enforced inside the search (once per node), not just between root moves, so one deep subtree can't silently overrun the budget — timed runs finish within ~1–2% of the requested time.
• Parallel search (Lazy SMP): the AI searches with 4 independent iterative-deepening workers by default, racing each other over one shared transposition table — a subtree one worker finishes can be another worker's TT hit, so the workers collaborate. Each TT entry (key + payload, 16 bytes) travels as a single atomic unit, so a reader can never see a key from one position with another's score; whether that atomic is lock-free is platform-dependent (it is on Apple Silicon and x86-64 with cmpxchg16b, otherwise the standard library falls back to an internal lock, and the build links libatomic where the platform needs it). The deepest completed depth wins. Set --threads N to change the count (capped at 16 and at cores − 2); --threads 1 runs the historical single-threaded search. Fixed-depth --search is always single-threaded so its results stay deterministic. Measured on an Apple M4 (10 cores), midgame position: at a 3s time limit the 4-thread search reaches depth 12 where 1 thread stays at depth 11; at 1s both reach depth 11, the 4-thread search having searched ~4× as many nodes (note this is aggregate across workers — some work is duplicated between them, so it is not a pure 4× speedup).
• Honest depth accounting: the depth reported for a timed search uses the same convention as fixed-depth mode ("depth D" counts the root move as ply 1, i.e. D−1 plies are searched below the root move), so depth numbers in the CSV/log exports are directly comparable across both paths.
• Algorithm: NegaScout (Principal Variation Search) with alpha-beta pruning, sped up by a transposition table — a cache of positions already searched, keyed by a Zobrist hash (a fingerprint of the board that updates incrementally as moves are made, rather than being recomputed from scratch). This lets the AI skip re-searching positions it's already evaluated (which happens often — different move orders can reach the same board) and search noticeably deeper in the same time limit.
• Move ordering: Moves are tried in priority order (corners → edges → inner cells → X-squares) to improve pruning efficiency, with a further boost from replaying whichever move the transposition table says worked best last time.
• Evaluation components:
  • Material: positional weights per square
  • Mobility: relative number of legal moves available
  • Stability: discs that can never be flipped (corners, filled edges, enclosed interior)
  • Frontier: discs adjacent to empty squares (fewer is better) — evaluated with pure bitboard shifts/popcounts rather than a per-cell neighbor scan
• Dynamic danger correction: static penalties for X/C-squares are lifted when the adjacent corner is already owned, since those squares are no longer a liability.
• Time-budget integrity: searches abort cleanly at the deadline and only report a depth that fully completed — an iteration cut off mid-way by the clock is discarded in favor of the last completed depth's result. Input positions where no legal move exists error out gracefully instead of crashing.

---

Opening book

The AI can consult a book of known opening moves instead of searching from scratch, and the game can show you the name of the opening you're currently in (e.g. "Tiger") — both features are driven by the same file: openings.txt.

openings.txt is a plain, human-editable list of 117 named Othello openings — Tiger, Rose, Cow, and many others (some with well-known alternate names, e.g. "Aubrey / Tanaka") — each with its move sequence, curated from real Othello theory (Robert Gatliff's 1995 opening catalogue, the Hong Kong Othello Association's opening list, and independently-corroborated additions from a couple of other established sources). One line per opening:

Tiger|f5 d6 c3 d3 c4

At every program start, the game reads this file, replays each sequence, and builds two things in memory from it: a move-suggestion table (every move of every line, not just the final position) and a name lookup (the name of the position at the end of each named line). There's no separate compiled/generated file — edit openings.txt directly to add, fix, or extend an opening, and it takes effect the next time you run the game. No regeneration step, nothing to keep in sync.

Note: the path is resolved relative to the current working directory (not the binary's location), so run the game from the repo root — or pass an absolute path via --book-dump — for the book to be found.

A few things make the book smarter than a plain move list:

• It's keyed by the position on the board, not the sequence of moves that reached it — so different move orders that land on the same board share one book entry.
• It's keyed by canonical position — the board's 8 rotations/reflections (spin it 90°, flip it, etc.) are recognized as the same entry, so openings.txt only needs one orientation of each opening; the other 3 equivalent first moves and any mirror-image continuation are covered automatically.
• Where different named openings share an early position and then diverge, the book keeps every alternative and picks one at random each time it's used — so the AI doesn't play the exact same opening every single game.

You'll see book moves in the recent-moves log / CSV export as a move with depth -1 — that's the "no search happened, this came straight from the book" marker. The opening name itself is shown as its own line below the score in the TUI: once the position exactly matches a named opening's full sequence (including junction entries like "Tiger Category" that exist precisely to name an early, well-known position), that name is shown. If a position is only partway through a line or consistent with several, nothing new is shown — the display sticks with whatever last resolved unambiguously (it doesn't disappear once you leave a line — the game genuinely did start with that opening).

The book is only ever used from the standard starting position onward — it's silently skipped in Puzzle Mode (a custom position essentially never coincidentally matches a book entry), and it hands off to normal search automatically once a game goes past however many moves openings.txt covers for that particular line.

Adding or editing openings

Just edit openings.txt: add a line Name|moves (lowercase algebraic squares, space-separated, e.g. f5 d6 c3 d3 c4), or fix an existing one. To check the file parses the way you expect (and see exactly what got loaded — position, move, and which line it came from):

./main --book-dump openings.txt

If openings.txt is missing or unreadable, the game just runs without a book or opening names — search happens from the very first move instead, exactly like before either feature existed. No error, no setup required to just play.

---

Running the game without the TUI (developer/testing mode)

Passing certain flags on the command line skips the ncurses screen entirely and runs one specific thing headlessly, printing plain text to the terminal. Useful for testing, benchmarking, or scripting — not needed for normal play.

./build/main --selfplay --time 2                     # play a full AI-vs-AI game, print every move
./build/main --search --time 5                       # get the AI's move for the current position
./build/main --search --fen "8/8/8/3WB3/3BW3/8/8/8" --player B   # ...from a specific position
./build/main --search --time 3 --threads 1           # ...single-threaded (default is 4 Lazy SMP workers)
./build/main --perft 6                                # count reachable positions N moves out (move-generator correctness check)
./build/main --book-dump openings.txt                 # print every entry the opening book parses to (see above)
./build/main --opening-name --64 "<64charboard>" --player B   # look up the opening name for an arbitrary position

Common options across these: --fen <string> / --64 <string> load a starting position (same formats as Puzzle Mode above; defaults to the standard starting position if neither is given), --player B|W sets whose turn it is, --time <seconds> sets the AI's thinking time (decimal seconds accepted, minimum 0.1; 0 = default 1s), and --threads <n> sets the number of Lazy SMP search workers for --search/--selfplay (default 4; 1 restores the single-threaded search; capped at 16 and at cores − 2). A couple of flags exist purely for verifying the engine is behaving correctly and aren't needed day-to-day: --verify-zobrist (with --perft) and --no-tt / --search --fixed-depth <n> (with --search; fixed-depth search is always single-threaded and ignores --threads).

Running ./build/main with none of these flags starts the normal interactive game exactly as before — with one exception from this branch: the AI in every mode now searches with the default 4 Lazy SMP workers (same speedup as headless mode), so it reaches deeper in its time budget.