Regarding Alpha-beta Search

[StackFish5]

I have already added the alpha-beta search (using negamax) to my work-in-progress chess engine, but I'm still confused about one thing. How would I properly implement the alpha-beta search to find the best move available. I couldn't find anything about it on CPW. Any help is appreciated.

Thanks.

[expositor]

Assuming I understand your question properly: there are a few ways that I can think of.

The first is to have a separate function (let's call it root_negamax) that looks just like your negamax function but that also keeps track which move last raised alpha (i.e. the best move, the one that led to the highest score). The root_negamax function calls negamax to get the score of child nodes, just like negamax does, but its return signature is the pair (move, score) rather than just score.

Another way is to modify negamax to always return (move, score). The negamax function would simply ignore the move returned by the recursive calls of negamax, but whoever is calling negamax on the root node would pay attention – the move returned there is what the engine should emit.

The last way is to keep track of the entire principal variation, or PV (the sequence of moves that the engine considers best play from both sides – the best move to make in the current situation as well as the expectation of what the opponent will play, its intended response after that, and so on). The negamax function in this case returns the pair (pv, score). It does this by 1 keeping track of which move last raised alpha (the best_move) as well as the PV that follows from playing the best move (best_pv, which is the PV returned by negamax called on that child node) and then 2 returning the two concatenated together (e.g. [best_move] + best_pv if we were writing this in python). To get the move that should be played at the root position, you simply look at the head (zeroth element) of the PV returned by the negamax call on the root node.

I'd personally recommend the last way, since it's usually very handy to know the PV. For instance, if the engine plays a strange move, the PV tells you what the engine believed would happen in response to it playing that move, which might either reveal a problem or convince you that the strange move is actually reasonable.

[algerbrex]

I have already added the alpha-beta search (using negamax) to my work-in-progress chess engine, but I'm still confused about one thing. How would I properly implement the alpha-beta search to find the best move available. I couldn't find anything about it on CPW. Any help is appreciated.

Thanks.

Hi, you have a couple of options.

The approach I took for a while was to have two alpha-beta search routines. One called rootNegamax and one called negamax. Negamax was always called at depth-1 and just returned a score, whereas the rootNegamax routine keep track of a best move and best score.

The approach I use now is to just collect the principal variation, and then use the first move from the principal variation to get the best move.

[hgm]

The best move is the first move of the PV.

Normally you would (in every node of the tree) remember the move that increased alpha but did not cause a beta cutoff, (this would be the new PV move), and return it to the caller. To allow the negamax function to return multiple data items, you could have it return a struct, or pass it a pointer to a struct whare it can store the data it wants to return. That is better programming practice than storing the data to be returned in a global variable for the caller to pick it up.

The PV would be one of the variables the negamax function should return to its caller, in addition to the score of the node. The first move of the PV would be the last move that raised alpha, and the PV returned by the search of that move should be appended to it. E.g.

Code: Select all

typedef struct {
// passed to daughter:
int depth;
int alpha
int beta;
// returned to caller:
int score;
Move pv[MAXDEPTH];
} Stairway;

void
Negamax(Stairway *ps)
{
   Stairway s;
   Move m;
   ps->pv[0] = 0; // initialize empty PV to return
   int myAlpha = ps->alpha; // better not to mess with original alpha (IID!)
   
   ...
     s->depth = ps->depth - 1;
     s ->alpha = -ps->beta;
     s->beta = -myAlpha
     MakeMove(m);
     Negamax(&s);
     UnMake(m);
     s->score = -s->score; // negamax sign flip. (You could of course already return it flipped instead)
     if(s->score > myAlpha) {
       myAlpha = s->score;
       if(s->score >= ps->beta) { // beta cutoff
         ps->score = ps->beta;
         return;
       }
       ps->pv[0] = m; // first move of new PV
       int i = 1;  while((ps->pv[i] = s->pv[i-1])) i++; // copy tail of PV
     }
     ...
     ps->score = myAlpha;
}

The Stairway struct that you passed to the root would contain the move the engine should play in pv[0]. (And the ponder move in pv[1].)

[StackFish5]

And for clarification, here the the code I have for search so far. I am wondering if any of my functions are incorrect as odd numbered depths behave much worse for select_move() than even depths. Thanks.

Code: Select all

int quiescence(int alpha, int beta, Legal_Moves &board) {
  int stand_pat = board.static_evaluation();
	int score;
    if(stand_pat >= beta)
        return beta;
    if(alpha < stand_pat)
        alpha = stand_pat;
		std::vector <int> board_moves;
		board.legal_captures(board_moves);
    for(int move : board_moves) {
        board.push_move(move);
        score = -quiescence(-beta, -alpha, board);
        board.pop_move(move);
        if(score >= beta)
            return beta;
        if(score > alpha)
           alpha = score;
    }
    return alpha;
}

int alphabeta(int alpha, int beta, int depth, Legal_Moves &board){
	if (depth == 0){
    return quiescence(alpha, beta, board);
	}
	std::vector <int> board_moves;
	board.legal_moves(board_moves);
  for(int move : board_moves){
    board.push_move(move);
    int score = -alphabeta(-beta, -alpha, depth - 1, board);
    board.pop_move(move);
    if (score >= beta){
      return beta;
		}
    if (score > alpha){
      alpha = score;
		}
	}
	return alpha;
}

int select_move(int depth, Legal_Moves &board){
	int best_score = -49999;
	std::vector <int> board_moves;
	board.legal_moves(board_moves);
	int best_move;
	int alpha = -50000;
  for(int move : board_moves){
    board.push_move(move);
    int score = -alphabeta(alpha, 50000, depth - 1, board);
    board.pop_move(move);
		if (score > alpha){
			alpha = score;
			best_move = move;
		}
	}
	
	return best_move;
}

[expositor]

From a very cursory glance, I noticed in your quiescing function that the side to move is always allowed to stand pat. Typically, you do not allow the side to move to stand pat if the side to move is in check.

[StackFish5]

From a very cursory glance, I noticed in your quiescing function that the side to move is always allowed to stand pat. Typically, you do not allow the side to move to stand pat if the side to move is in check.

If the side to stand pat is in check, how should I proceed with the quiescence search?

[algerbrex]

From a very cursory glance, I noticed in your quiescing function that the side to move is always allowed to stand pat. Typically, you do not allow the side to move to stand pat if the side to move is in check.

If the side to stand pat is in check, how should I proceed with the quiescence search?

Different engines handle it differently. For a long time I actually took the approach of not even considering checks in quiescence search, which probably isn't necessarily the best design, but coupled with check extensions in the main search it worked worked practically. Now in the latest versions I use a compromise. Instead of worrying about every check in quiescence search, which would slow things down too much, I only consider checks within the first three plies of the quiescence search. If I encounter a check within those first three plies, I won't allow stand pat, and will generate all moves: https://github.com/algerbrex/blunder/bl ... ch.go#L672

This worked a little better for me when testing than just always ignoring checks.

[StackFish5]

From a very cursory glance, I noticed in your quiescing function that the side to move is always allowed to stand pat. Typically, you do not allow the side to move to stand pat if the side to move is in check.

If the side to stand pat is in check, how should I proceed with the quiescence search?

So other than the quiescence search, there is nothing wrong with my code for the move selection and alpha-beta?