Perfect-play Connect-4 solver. More...

#include <BitBully.h>

Public Member Functions
	BitBully (const std::filesystem::path &bookPath="")
	Construct a solver, optionally loading an opening book.
bool	isBookLoaded () const
	Was an opening book successfully loaded?
void	resetBook ()
	Discard the currently loaded opening book (if any).
bool	loadBook (const std::filesystem::path &bookPath="")
	Load an opening book from disk.
int	mtdf (const Board &b, const int firstGuess, const int maxDepth=-1) noexcept
	Solve a position using the MTD(f) driver.
int	nullWindow (const Board &b, const int maxDepth=-1) noexcept
	Alternative driver based on a binary search of zero-width windows.
void	resetTranspositionTable ()
	Discard the contents of the transposition table.
auto	getNodeCounter () const
	Number of nodes visited since resetNodeCounter().
void	resetNodeCounter ()
	Reset the visited-node counter to zero.
int	negamax (Board b, int alpha, int beta, const int depth, const int maxDepth=-1) noexcept
	Negamax search with alpha-beta pruning, transposition table and opening book consultation.
auto	scoreMove (const Board &b, const int column, const int firstGuess, const int maxDepth=-1)
	Evaluate the move that drops a stone in `column`.
auto	scoreMoves (const Board &b, const int maxDepth=-1)
	Evaluate every column move from `b`.

Static Public Member Functions
static int	scoreToMovesLeft (const int score, const Board &b) noexcept
	Convert a solver score to the number of moves until the game ends.
static int	rollout (Board b) noexcept
	Cheap evaluation: play out the game using safe heuristic moves.

Detailed Description

Perfect-play Connect-4 solver.

Maintains a transposition table and (optionally) an opening book between searches so that subsequent calls reuse previously computed information. Scores returned by the engine follow the convention introduced by Pascal Pons:

a positive score s means the player to move wins on ply 2 * s - 1 from the current position,
a negative score s means the player to move loses on ply 2 * |s|,
a score of 0 indicates a draw.

The helper scoreToMovesLeft converts these compact scores back into the actual number of plies remaining.

Examples: quick_solve.cpp, score_all_moves.cpp, and with_opening_book.cpp.

Definition at line 45 of file BitBully.h.

Constructor & Destructor Documentation

◆ BitBully()

BitBully::BitBully::BitBully ( const std::filesystem::path & bookPath = "" )

inlineexplicit

Construct a solver, optionally loading an opening book.

Parameters

bookPath Path to a binary opening-book file. If empty, no book is loaded and isBookLoaded() returns false.

Definition at line 64 of file BitBully.h.

Here is the call graph for this function:

Member Function Documentation

◆ getNodeCounter()

auto BitBully::BitBully::getNodeCounter ( ) const

inlinenodiscard

Number of nodes visited since resetNodeCounter().

Definition at line 248 of file BitBully.h.

Here is the caller graph for this function:

◆ isBookLoaded()

bool BitBully::BitBully::isBookLoaded ( ) const

inline

Was an opening book successfully loaded?

Examples: with_opening_book.cpp.

Definition at line 72 of file BitBully.h.

Here is the caller graph for this function:

◆ loadBook()

bool BitBully::BitBully::loadBook ( const std::filesystem::path & bookPath = "" )

inline

Load an opening book from disk.

The database type (8-ply vs. 12-ply, with or without distance information) is inferred from the file size.

Parameters

bookPath Path to the book file. Empty paths are a no-op.

Returns: true if a new book is now loaded; false if a book was already loaded or bookPath is empty.

Definition at line 87 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mtdf()

int BitBully::BitBully::mtdf	(	const Board &	b,
		const int	firstGuess,
		const int	maxDepth = -1 )

inlinenoexcept

Solve a position using the MTD(f) driver.

MTD(f) repeatedly invokes negamax() with zero-width ([beta-1, beta]) windows, tightening the upper and lower bounds until they meet. The firstGuess parameter seeds the initial test value: a good guess (e.g. from a previous shallow search) drastically reduces the number of re-searches.

Parameters

b	Position to evaluate.
firstGuess	Initial guess for the position's score.
maxDepth	Maximum search depth in plies, or `-1` for unlimited search (full perfect-play resolution).

Returns: Exact score of b (or a depth-limited approximation when maxDepth ≥ 0).

See also: [plaat96]

Examples: quick_solve.cpp, and with_opening_book.cpp.

Definition at line 188 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ negamax()

int BitBully::BitBully::negamax	(	Board	b,
		int	alpha,
		int	beta,
		const int	depth,
		const int	maxDepth = -1 )

inlinenoexcept

Negamax search with alpha-beta pruning, transposition table and opening book consultation.

The function combines several enhancements:

move ordering through Board::sortMoves(),
transposition cutoffs (EXACT / LOWER / UPPER) keyed on the position's Board::uid(),
Enhanced Transposition Cutoffs (ETC) at low depths,
mirror-symmetry lookups,
opening-book consultation when the configured ply depth is reached,
depth-limited rollouts via rollout() once maxDepth is hit.

Parameters

b	Position to evaluate (passed by value — recursion mutates a local copy).
alpha	Current lower bound of the search window.
beta	Current upper bound of the search window.
depth	Plies played from the search root.
maxDepth	Maximum total search depth, or `-1` for unlimited.

Returns: Score of b in the active player's perspective.

Definition at line 274 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nullWindow()

int BitBully::BitBully::nullWindow	(	const Board &	b,
		const int	maxDepth = -1 )

inlinenoexcept

Alternative driver based on a binary search of zero-width windows.

Empirically slower than mtdf() in this codebase but useful for cross-checking results.

Parameters

b	Position to evaluate.
maxDepth	Maximum search depth in plies, or `-1` for unlimited search.

Returns: Exact score of b.

Definition at line 221 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ resetBook()

void BitBully::BitBully::resetBook ( )

inline

Discard the currently loaded opening book (if any).

Definition at line 75 of file BitBully.h.

Here is the caller graph for this function:

◆ resetNodeCounter()

void BitBully::BitBully::resetNodeCounter ( )

inline

Reset the visited-node counter to zero.

Definition at line 251 of file BitBully.h.

Here is the caller graph for this function:

◆ resetTranspositionTable()

void BitBully::BitBully::resetTranspositionTable ( )

inline

Discard the contents of the transposition table.

Definition at line 242 of file BitBully.h.

Here is the caller graph for this function:

◆ rollout()

int BitBully::BitBully::rollout ( Board b )

inlinestaticnoexcept

Cheap evaluation: play out the game using safe heuristic moves.

Both players use Board::generateNonLosingMoves() to avoid immediate losses; among multiple non-losing moves the centre-priority heuristic Board::nextMove() picks the next ply. The function terminates as soon as a side reaches a winning position or runs out of non-losing replies.

Parameters

b	Position to evaluate. Passed by value because the rollout mutates a local copy.

Returns: Solver score from the perspective of the side to move in b.

Definition at line 139 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scoreMove()

auto BitBully::BitBully::scoreMove	(	const Board &	b,
		const int	column,
		const int	firstGuess,
		const int	maxDepth = -1 )

inline

Evaluate the move that drops a stone in column.

Plays the move on a copy of b and runs mtdf() on the resulting position, then negates the score so that it is reported from the perspective of the player to move in b.

Parameters

b	Current position.
column	Column index of the move to evaluate.
firstGuess	Seed value for MTD(f).
maxDepth	Search depth limit, or `-1` for unlimited search.

Returns: Score of the resulting position, or -1000 if column is not a legal move.

Definition at line 476 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scoreMoves()

auto BitBully::BitBully::scoreMoves	(	const Board &	b,
		const int	maxDepth = -1 )

inline

Evaluate every column move from b.

Calls scoreMove() for each of the N_COLUMNS columns. Illegal moves are reported with the sentinel score -1000.

Parameters

b	Current position.
maxDepth	Search depth limit, or `-1` for unlimited search.

Returns: Per-column scores indexed by column number.

Examples: score_all_moves.cpp.

Definition at line 499 of file BitBully.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scoreToMovesLeft()

int BitBully::BitBully::scoreToMovesLeft	(	const int	score,
		const Board &	b )

inlinestaticnoexcept

Convert a solver score to the number of moves until the game ends.

Parameters

score	The solver score (positive = current player wins, negative = current player loses, 0 = draw).
b	The board state for which the score was computed.

Returns: Number of moves until the game concludes under perfect play.

The encoding maps the absolute score to a final-ply count:

\[ \text{plies\_left}(s, b) = \begin{cases} \text{movesLeft}(b) & s = 0 \\ \text{movesLeft}(b) - \bigl(2(|s| - 1) + \delta\bigr) & s \ne 0 \end{cases} \]

where \(\delta \in \{0, 1\}\) accounts for the parity of the side to move (winning move falls on an even or odd ply).

Examples: quick_solve.cpp.

Definition at line 115 of file BitBully.h.

Here is the caller graph for this function:

The documentation for this class was generated from the following file:

src/BitBully.h

	BitBully 0.0.78 A fast, perfect-play Connect-4 engine in modern C++

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ BitBully()

Member Function Documentation

◆ getNodeCounter()

◆ isBookLoaded()

◆ loadBook()

◆ mtdf()

◆ negamax()

◆ nullWindow()

◆ resetBook()

◆ resetNodeCounter()

◆ resetTranspositionTable()

◆ rollout()

◆ scoreMove()

◆ scoreMoves()

◆ scoreToMovesLeft()