AlphaBeta all returning the same number

[SrcEngine]

I am very new to chess programming... my engine already has a method of fetching principle variations, but I now needed the second best moves in positions as well. I thought this would be very easy to implement:

Code: Select all

int AlphaBeta(){
...
int Score=-INFINITY;
int BestScore=-INFINITY;
int secondBestScore=-INFINITY;
for(all moves in position)
{
	...
	Score=-AlphaBeta();
	if(Score>BestScore) //this if statement finds the best move in the position
	{
		
		BestScore=Score;
		...
		if(Score>alpha)
		{
			...
			alpha=Score;
		}
		continue; //skips the if statement check below
	}
	if(Score>secondBestScore) //this if statement, combined with the 'continue' from above, finds the second best move
				secondBestScore=Score;
}
...
loads the best move and second best move to the tables. 
return BestScore;
}

The code would work, except that all moves are returning the exact same Score. I did some debugging with

Code: Select all

printf("move is %s score is %d ", PrMove(list->moves[MoveNum].move), Score);

, and I got
I have no idea why this is happening, as I am returning BestScore for each AlphaBeta. This is not expected behavior, right? If so, how would I obtain the second best moves in positions?

[jorose]

I think given the information you have provided we cannot say for certain what is going on.

It should be noted however, that there might not be anything wrong at all. I you have a fail-hard framework, then moves will not return a static score below your lower bound. This means, if you search the best move first, all moves will return the same score!

[hgm]

This is expected behavior. Alpha-beta search is 'lazy'; the reason it is so efficient is that it makes no attempt at all to prove how much worse a score is than what you already have. As soon as it is >= beta, you take a cutoff.

So once you found a move with score s, as soon as for subsequent moves it has proved the score will be <= s, it leaves it at that. In a tree a few ply deep this usually means the score will be at s, or very close to it. All these 'scores' are in fact upper limits. So there is no way to figure out which of them is the second best. Only in QS it sometimes happes that you get scores far below alpha, e.g. because the daughter directly returns the evaluation, or the only way to get above beta at all there is to capture something big that is hanging.

[SrcEngine]

How do engines like Stockfish find moves other than the best moves, then? Are there resources I can use to read on this?

[Henk]

Maybe they use an excluded movelist. Not very easy to implement for you easily overlook something.

Once I implemented late move pruning by (re)searching first N best moves of previous iteration and then quit search.
But too slow and only made it play worse.

[abulmo2]

How do engines like Stockfish find moves other than the best moves, then? Are there resources I can use to read on this?

There are grossly two ways to do this:
1) do not update the alpha bound at the root node. That way all the score of each moves will be correct.
2) redo the search with the best moves found so far excluded. This is the usual method to do a multipv search.

[emadsen]

How do engines like Stockfish find moves other than the best moves, then? Are there resources I can use to read on this?

In my main search loop, I don't update Alpha at the root (Depth == 0) if MultiPV > 1. (Ignore _scoreError for now. That's used to weaken the engine.) For this to work correctly you need an aspiration window that's large enough to accommodate MultiPV moves. For example, if MultiPV is 4, you need an aspiration window large enough to include 4 moves. The size of this window depends on the position. In some positions only a single good move exists. In others many good moves exist with roughly the same score. To keep your code simple, you can use an infinite aspiration window (-Score.Max to +Score.Max) when MultiPV > 1.

This is not the only possible technique. Others have suggested doing multiple root searches, each time excluding another best move (so the 4th search excludes the 3 previous best moves). That certainly would work. However, in my engine I simply open the aspiration window so MultiPV moves fit within it.

[hgm]

My engines usually do Multi-PV by a score margin rather than by a number. (After all, when the second-best move is a Queen worse than the best, I am not very much interested in how bad it exactly is.) What I do in the root is raise alpha to bestScore - MultiPvMargin, instead of to BestScore. And then I print the PV of any move that scores above this alpha. Took only one statement in the search, plus two lines to recognize setting of the option in the protocol driver.