Basic Alpha/Beta question

[benvining]

I think I understand in principle how alpha/beta search traverses the move tree depth first, but what I'm struggling to connect the dots on is how you actually call it from the root search.

Do you basically run alpha beta for each legal move and pick the one with the best score? Like this:

Code: Select all

Move find_best_move(const Position& pos)
{
        Move bestMove {};
        auto bestScore = -inf;

	for (auto move : generate_moves(pos))
	{
	    Position newPosition {pos};
	    newPosition.make_move(move);
	    
	    auto score = alpha_beta(
	      -inf, inf, newPosition, max_depth);
	      
	    if (score > bestScore) {
	        bestScore = score;
	        bestMove = move;
	    }
	}
	
	return bestMove;
}

[hgm]

In my engines the root search is simply the first node of alpha-beta. So I just call alpha-beta from the command loop of the engine.

If what you want to do in the root is significantly different from what you do in other nodes, you might want to use a separate routine for it. But the basic idea is still the same: you have a search window {alpha, beta} and increase alpha to the best score you found so far.

[benvining]

What I'm confused about is translating the alpha/beta call into actually finding the best move. Am I correct about the basic process of making each legal move and using alpha/beta to evaluate each resulting position to determine the best move?

[hgm]

It depends what parameters alpha and beta you use to call AlphaBeta(). In any node of AlphaBeta() you also (recursively) call AlphaBeta() to evaluate moves, and find the best one. But you call those with window { -beta, -alpha }, where alpha is the maximum of all move scores evaluated so far and the initial alpha. And you stop doing that as soon as alpha >= beta.

So in the root you should do that too. Except that in the root the initial alpha = -INFINITY, and beta = +INFINITY, so that you will never get a beta cutoff, and always search all moves. You won't have a score for all moves, though; for most you will just get an upper limit. You only search them to prove they were worse than the move you already had. (Which usually is the first move you searched.)

Each time you find a score > alpha you increase alpha to that score, and the move that got this score becomes 'best move so far'. After having searched all moves the 'best move so far' is the best move.

[lithander]

Code: Select all

Move best = ???
int depth = N
int alpha = -CheckmateScore
int beta = CheckmateScore

foreach (move in Moves(depth))
{
	Play(move)
	int score = -AlphaBeta(depth - 1, -beta, -alpha)
	if (score > alpha)
	{
		best = move
		alpha = score
	}
}

int AlphaBeta(int depth, int alpha, int beta)
{
	foreach (move in Moves(depth))
	{
		Play(move)
		
		if (depth > 1)
			int score = -AlphaBeta(depth - 1, -beta, -alpha)
		else
			int score = Eval() //or QSearch

		if (score >= beta)
			return beta

		if (score > alpha)
			alpha = score
	}
	return alpha
}

A bit of pseudo-code shows that the search at the root is very similar to the recursive AlphaBeta calls except that there is no beta-cutoff and you don't return just a score but also keep track of the best-move associated with that score.

But if you had the score > beta return beta clause here it also wouldn't hurt because it would never trigger. And maybe you'll want to know the principal variation so there's a good reason why AlphaBeta would also somehow store or return the best move. These similarities inspire some programmers, like hgm suggested, to streamline the code so that you have no dedicated root search. In my engine I use a seperate implementation for root, normal and quiescence search.

[abulmo2]

Personally, I get the bestmove in the alphabeta routine.
To return the besmove from the search I store the list of moves to search at root apart, and sort the best move here.
So When I need to return the bestmove I just return the fist move of root moves.

Here is the pseudocode. The lines with "//<- HERE" are what you want.

Code: Select all

typedef struct Search {
	Board *board;
	Eval eval;
	MoveArray root_moves;   // <- HERE
	int ply;
	...
} Search;

Move search_bestmove(const Search *search) {
	return search->root_moves.move[0];
}

int search_alphabeta(Search *search, int alpha, const int beta, const int depth) {
	int score, bestscore = -SCORE_MATE;
	int move, bestmove;
	MoveArray movearray_;
	MoveArray *movearray = search->ply == 0 ? &search->root_moves : &movearray_; // <- HERE

	if (search_abort(search)) return alpha;

	if (depth <= 0) return search_qs(search, alpha, beta);

	if (search->ply > PLY_MAX) return eval(&search->eval, search->board);

	++search->pvs_nodes;

	movearray_generate(movearray, search->board);

	// loop over all moves
	foreach (move, movearray) {
		search_update(search, move);
			score = -search_alphabeta(search, -beta, -alpha, depth - 1);
		search_restore(search, move);
		if (search->stop) return alpha;
		if (score > bestscore) {
			bestscore = score
			if (score > alpha) {
				alpha = bestscore;
				bestmove = move;
				if (search->ply == 0) movearray_set_best(&search->root_moves, bestmove); // and <-- HERE
				if (alpha >= beta) break;
			}	
		}
	}

	return bestscore;
}

[benvining]

Thanks for all the input everyone, I think I understand better now!

[hgm]

As remarked, other AlphaBeta instances also keep track of the best move, even if just for storing it in the TT when they are done. When you record PV through the 'triangular array' method PV nodes would also store it there (inserted in front of the PV of the daughter). So at game level the best move would just be the first move of the PV.

Note that when you use an aspiration window, you can get beta cutoffs in the root.

My favorite design for passing info between parent and daughter and vice versa has evolved to putting most variables used in AlphaBeta in a struct, and passing a pointer to that struct as only parameter to AlphaBeta. The daughter can then keep track of info that has to be returned directly in the struct of the parent. Parameters that would be the same in all recursive calls (such as side to move or beta) would then have to be set only once in that struct.