The AlphaBeta class inherits from the ChineseCheckers class and provides an implementation of the alpha-beta algorithm with various optimizations for playing Chinese Checkers. The class provides several methods for evaluating the heuristic value of a position, ordering moves, and storing the results of previous searches in a transposition table. More...

#include <AlphaBeta.hpp>

Inheritance diagram for AlphaBeta:

Public Member Functions
	AlphaBeta ()

	AlphaBeta (const std::vector< double > &player_to_win_value_, const std::vector< double > &player_to_lose_value_)

ListOfPositionType	getMove (const int &depth, const double &alpha, const double &beta)

uint_fast64_t	getMove64 (const int &depth)

void	availableMoves (std::set< uint_fast64_t, decltype(comp_move_)> &result)

void	tensorflowSortMoves (std::set< uint_fast64_t, decltype(comp_move_)> &possible_moves)

const double	AlphaBetaEval (const int &depth, double alpha, double beta, const bool &maximizingPlayer, const bool &keepMove, uint_fast64_t hash)

bool	isHuman ()

void	loadOpenings ()

Player	getMaximizingPlayer () const

std::vector< double >	getPlayerToLoseValue ()

std::vector< double >	getPlayerToWinValue ()

void	setPlayerToLoseValue (const std::vector< double > &player_to_lose_value_)

void	setPlayerToWinValue (const std::vector< double > &player_to_win_value_)

Public Member Functions inherited from ChineseCheckers
	ChineseCheckers ()

void	newGame ()

bool	move (const Player &player, const ListOfPositionType &list_moves)

Result	stateOfGame ()

void	moveWithoutVerification (const uint_fast64_t &move)

Player	getWhoIsToPlay () const

uint_fast64_t	getBitBoardWhite () const

uint_fast64_t	getBitBoardBlack () const

void	printGrid () const

void	printWhoIsToPlay () const

Public Attributes
std::function< bool(const uint_fast64_t &, const uint_fast64_t &)>	comp_move_

std::function< bool(const uint_fast64_t &, const uint_fast64_t &)>	comp_move_black_

std::function< bool(const uint_fast64_t &, const uint_fast64_t &)>	comp_move_white_

Protected Member Functions
double	heuristicValue ()

void	updateHeuristicValue (const uint_fast64_t &move)

void	updateHeuristicValueBack (const uint_fast64_t &move)

std::vector< uint8_t >	bitBoardsAsVector (const bitBoards_t &bb)

ListOfPositionType	retrieveMoves (const uint_fast64_t &move)

Protected Member Functions inherited from ChineseCheckers
MoveType	elementaryMove (const PositionType &original_position, const PositionType &arrival_position) const

bool	isPositionIllegal () const

int	cantorPairingFunction (const int &x, const int &y) const

boost::unordered_map< uint32_t, bool >	loadIllegalPositions () const

void	generateZobristKeys ()

void	computeAndSetZobristHash ()

Protected Attributes
std::vector< double >	player_to_win_value_

std::vector< double >	player_to_lose_value_

Player	maximizing_player_

uint_fast64_t	best_move_

boost::unordered_map< uint_fast64_t, std::pair< double, int > >	transposition_table_

boost::unordered_map< uint_fast64_t, std::pair< double, int > >::iterator	it_transposition_table_

std::array< boost::unordered_map< bitBoards_t, uint_fast64_t, bitBoardsHasher, bitBoardsEqual >, 2 >	opening_

cppflow::model *	model = new cppflow::model("model")

std::unordered_map< uint_fast64_t, double >	result_tensorFlow_

double	heuristic_value_

int	fullDepth_

std::array< bool, 2 >	won_ = {false, false}

Protected Attributes inherited from ChineseCheckers
const uint_fast64_t	un_64_ = static_cast<uint_fast64_t>(1)

Player	who_is_to_play_ = 0

bitBoards_t	bit_boards_

uint_fast64_t	zobrist_hash_

std::array< boost::unordered_map< uint_fast64_t, uint_fast64_t >, 2 >	zobrist_keys_

std::array< boost::unordered_map< uint_fast64_t, uint_fast64_t >, 2 >	zobrist_keys_moves_

boost::unordered_map< uint64_t, int >	number_of_times_seen_

std::vector< uint64_t >	positions_seen_

const uint_fast64_t	winning_positions_white_ = 0xF0E0C08000000000

const uint_fast64_t	winning_positions_black_ = 0x000000000103070F

const boost::unordered_map< uint32_t, bool >	illegal_positions_

const std::array< std::array< uint32_t, 8 >, 8 >	cantor_pairing_

const std::vector< std::vector< int > >	valid_lines

const std::vector< std::vector< int > >	valid_lines_illegal

const std::array< std::pair< int, int >, 64 >	uint64_to_pair_

const std::array< std::array< uint_fast64_t, 8 >, 8 >	int_to_uint64_

const std::array< std::vector< uint_fast64_t >, 64 >	direct_neighbours_

const std::array< std::vector< std::vector< std::pair< std::pair< uint_fast64_t, uint_fast64_t >, uint_fast64_t > > >, 64 >	k_neighbours_

Detailed Description

The AlphaBeta class inherits from the ChineseCheckers class and provides an implementation of the alpha-beta algorithm with various optimizations for playing Chinese Checkers. The class provides several methods for evaluating the heuristic value of a position, ordering moves, and storing the results of previous searches in a transposition table.

Constructor & Destructor Documentation

◆ AlphaBeta() [1/2]

AlphaBeta::AlphaBeta ( )

Construct the object.

See also: AlphaBeta(const std::vector< std::vector<double> > &player_to_win_value_, const std::vector< std::vector<double> > &player_to_lose_value_)

◆ AlphaBeta() [2/2]

AlphaBeta::AlphaBeta	(	const std::vector< double > &	player_to_win_value_,
		const std::vector< double > &	player_to_lose_value_
	)

Construct the object.

Parameters

player_to_win_value_
player_to_lose_value_

See also: AlphaBeta()

Member Function Documentation

◆ AlphaBetaEval()

const double AlphaBeta::AlphaBetaEval	(	const int &	depth,
		double	alpha,
		double	beta,
		const bool &	maximizingPlayer,
		const bool &	keepMove,
		uint_fast64_t	hash
	)

This methode performs an Alpha-Beta search in the game tree to find the best move for a given game state. It evaluates each possible move and calls the AlphaBetaEval function recursively on the next depth level in the game tree. The code updates the game state and calculates the heuristic value for the new position. It also updates the Zobrist hash and checks for an illegal position.

Parameters

depth	Indicates how deep we should explore the tree.
alpha	Check the Alpha-Beta algorithm to know what this is.
beta	Check the Alpha-Beta algorithm to know what this is.
maximizingPlayer	Indicates if the current player if the maximizing player.
keepMove	indicates if the best move from the current depth should be kept.

See also: getMove; getMove64; availableMoves; heuristicValue

Returns: The value computed by the alpha beta algorithm. Sets best_move_ if asked to.

◆ availableMoves()

void AlphaBeta::availableMoves ( std::set< uint_fast64_t, decltype(comp_move_)> & result )

This function calculates all available moves for the current player and stores them in the result vector. The result vector is passed as a reference so that it can be modified inside the function.

See also: getMove; tensorflowOrderMoves

◆ bitBoardsAsVector()

std::vector< uint8_t > AlphaBeta::bitBoardsAsVector ( const bitBoards_t & bb )

protected

Returns a representation of a given bit board as a vector.

Parameters

bb	The bit boards considered.

Returns: A representation of bb as a vector.

◆ getMaximizingPlayer()

Player AlphaBeta::getMaximizingPlayer ( ) const

Returns maximizing_player_.

Returns: maximizing_player_.

◆ getMove()

ListOfPositionType AlphaBeta::getMove	(	const int &	depth,
		const double &	alpha,
		const double &	beta
	)

This is a method that returns the best move the AI agent can make at a given depth in the game tree using the alpha-beta pruning algorithm. The first check in the method is to see if the current game state is part of the opening book. If so, the method retrieves the pre-calculated moves for this position. Otherwise, it calls the getMove64 method to calculate the best move at the given depth using the alpha-beta pruning algorithm. Once the best move has been determined, the method calls retrieveMoves to convert the bitboard representation of the move into a more human-readable format before returning the result.

Parameters

depth	Indicates how deep we should explore the tree.
alpha	Check the Alpha-Beta algorithm to know what this is.
beta	Check the Alpha-Beta algorithm to know what this is.

See also: getMove64; AlphaBetaEval; availableMoves; heuristicValue; updateHeuristicValue; updateHeuristicValueBack

Returns: The best move according to the alpha beta algorithm.

◆ getMove64()

uint_fast64_t AlphaBeta::getMove64 ( const int & depth )

This is a method that returns the best move the AI agent can make at a given depth in the game tree using the alpha-beta pruning algorithm. This function implements the Alpha-Beta search algorithm to find the best move in a game state. It uses of zero width windows heuristic when a sure win has been detected which makes the end-game faster and improves a lot the quality of the player.

Parameters

depth Indicates how deep we should explore the tree.

See also: getMove; AlphaBetaEval; availableMoves; heuristicValue; updateHeuristicValue; updateHeuristicValueBack

Returns: The best move according to the alpha beta algorithm.

◆ getPlayerToLoseValue()

std::vector< double > AlphaBeta::getPlayerToLoseValue ( )

Returns player_to_lose_value_.

Returns: player_to_lose_value_.

◆ getPlayerToWinValue()

std::vector< double > AlphaBeta::getPlayerToWinValue ( )

Returns player_to_win_value_.

Returns: player_to_win_value_.

◆ heuristicValue()

double AlphaBeta::heuristicValue ( )

protected

The function computes a heuristic value for the current game state by evaluating the positions of the pawns on the board. This value is computed using a linear function generated by genetic evolution.

See also: tensorflowOrderMoves

Returns: The heuristic value of the current position.

◆ isHuman()

bool AlphaBeta::isHuman ( )

inline

A helper function for the python connexion

◆ loadOpenings()

void AlphaBeta::loadOpenings ( )

This function loads the pre-calculated opening moves from a file and stores them in the opening_ map for later use in the alpha-beta algorithm.

◆ retrieveMoves()

ListOfPositionType AlphaBeta::retrieveMoves ( const uint_fast64_t & move )

protected

Compute the full path of a move from a simple bit mask.

Parameters

move

Returns: the full path of a move.

◆ setPlayerToLoseValue()

void AlphaBeta::setPlayerToLoseValue ( const std::vector< double > & player_to_lose_value_ )

Sets player_to_lose_value_.

Parameters

player_to_lose_value_ The value to set.

◆ setPlayerToWinValue()

void AlphaBeta::setPlayerToWinValue ( const std::vector< double > & player_to_win_value_ )

Sets player_to_win_value_.

Parameters

player_to_win_value_ The value to set.

◆ tensorflowSortMoves()

void AlphaBeta::tensorflowSortMoves ( std::set< uint_fast64_t, decltype(comp_move_)> & possible_moves )

The moves are ordered using a tensorflow model that estimates the value that the alpha-beta algorithm would assign to each move.

Parameters

possible_moves The list of moves we could play.

See also: heuristicValue; availableMoves

◆ updateHeuristicValue()

void AlphaBeta::updateHeuristicValue ( const uint_fast64_t & move )

inlineprotected

This function updates the heuristic value of the current game state by adding or subtracting the value of the pawn moved in the last move.

Parameters

move	Said move.

◆ updateHeuristicValueBack()

void AlphaBeta::updateHeuristicValueBack ( const uint_fast64_t & move )

inlineprotected

This function updates the heuristic value of the current game state by adding or subtracting the value of the pawn moved in the last move.

Parameters

move	Said move.

Member Data Documentation

◆ best_move_

uint_fast64_t AlphaBeta::best_move_

protected

Contains the best move we found so far.

◆ comp_move_

std::function<bool(const uint_fast64_t&, const uint_fast64_t&)> AlphaBeta::comp_move_

Initial value:

=
            [this](const uint_fast64_t &a,
                   const uint_fast64_t &b){
                if (who_is_to_play_) {
                    return player_to_win_value_[__builtin_ctzll(a & ~bit_boards_.Black)]
                           + player_to_win_value_[__builtin_ctzll(b & bit_boards_.Black)]
                           < player_to_win_value_[__builtin_ctzll(b & ~bit_boards_.Black)]
                             + player_to_win_value_[__builtin_ctzll(a & bit_boards_.Black)];
                } else {
                    return player_to_win_value_[63 - __builtin_ctzll(a & ~bit_boards_.White)]
                           + player_to_win_value_[63 - __builtin_ctzll(b & bit_boards_.White)]
                           < player_to_win_value_[63 - __builtin_ctzll(b & ~bit_boards_.White)]
                             + player_to_win_value_[63 - __builtin_ctzll(a & bit_boards_.White)];
                }
            }

Function used to compare moves for sorting.

◆ comp_move_black_

std::function<bool(const uint_fast64_t&, const uint_fast64_t&)> AlphaBeta::comp_move_black_

Initial value:

=
            [&](const uint_fast64_t &a, const uint_fast64_t &b) {
                return result_tensorFlow_[a] > result_tensorFlow_[b];
            }

Function used to compare moves for sorting.

◆ comp_move_white_

std::function<bool(const uint_fast64_t&, const uint_fast64_t&)> AlphaBeta::comp_move_white_

Initial value:

=
            [&](const uint_fast64_t &a, const uint_fast64_t &b) {
                return result_tensorFlow_[a] < result_tensorFlow_[b];
            }

Function used to compare moves for sorting.

◆ fullDepth_

int AlphaBeta::fullDepth_

protected

The depth asked for.

◆ heuristic_value_

double AlphaBeta::heuristic_value_

protected

The current heuristic value. It avoids to compute it from scratch at each terminating node.

◆ it_transposition_table_

boost::unordered_map<uint_fast64_t,std::pair<double,int>>::iterator AlphaBeta::it_transposition_table_

protected

Iterator used to find elements through the transposition table.

◆ maximizing_player_

Player AlphaBeta::maximizing_player_

protected

Indicates which player we are playing for.

◆ model

cppflow::model* AlphaBeta::model = new cppflow::model("model")

protected

Tensorflow model used by tensorflowOrderMoves.

◆ opening_

std::array<boost::unordered_map<bitBoards_t, uint_fast64_t , bitBoardsHasher, bitBoardsEqual>, 2> AlphaBeta::opening_

protected

Map of pre-computed optimal openings.

◆ player_to_lose_value_

std::vector<double> AlphaBeta::player_to_lose_value_

protected

This matrix indicates the values we will assign to each pawns when we compute the heuristic value for the player we are playing for.

◆ player_to_win_value_

std::vector<double> AlphaBeta::player_to_win_value_

protected

This matrix indicates the values we will assign to each pawns when we compute the heuristic value for the player we are playing for.

◆ result_tensorFlow_

std::unordered_map<uint_fast64_t, double> AlphaBeta::result_tensorFlow_

protected

Result of the evaluation of the moes from tensorFlow

◆ transposition_table_

boost::unordered_map<uint_fast64_t, std::pair<double, int> > AlphaBeta::transposition_table_

protected

Transposition table used to store the results of previous searches.

◆ won_

std::array<bool, 2> AlphaBeta::won_ = {false, false}

protected

Indicates if according to previous searches, a player can be sure to win. It is used to compute shortest path to win in late game.

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

solvers/AlphaBeta/include/AlphaBeta.hpp
solvers/AlphaBeta/src/AlphaBeta.cpp

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ AlphaBeta() [1/2]

◆ AlphaBeta() [2/2]

Member Function Documentation

◆ AlphaBetaEval()

◆ availableMoves()

◆ bitBoardsAsVector()

◆ getMaximizingPlayer()

◆ getMove()

◆ getMove64()

◆ getPlayerToLoseValue()

◆ getPlayerToWinValue()

◆ heuristicValue()

◆ isHuman()

◆ loadOpenings()

◆ retrieveMoves()

◆ setPlayerToLoseValue()

◆ setPlayerToWinValue()

◆ tensorflowSortMoves()

◆ updateHeuristicValue()

◆ updateHeuristicValueBack()

Member Data Documentation

◆ best_move_

◆ comp_move_

◆ comp_move_black_

◆ comp_move_white_

◆ fullDepth_

◆ heuristic_value_

◆ it_transposition_table_

◆ maximizing_player_

◆ model

◆ opening_

◆ player_to_lose_value_

◆ player_to_win_value_

◆ result_tensorFlow_

◆ transposition_table_

◆ won_