alphabeta issue

[Sven]

Here's some pseudo code to help you understand what the most minimalistic search should do:

Fully agreed, only one element is missing in that pseudo code, the updating of alpha, as shown below:

Code: Select all

		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
		if (best_score > alpha)
			alpha = best_score	// raise alpha

Sven

According to http://chessprogramming.wikispaces.com/Alpha-Beta that is incorrect: if best_score >= beta, one should return beta, not best_score.

it's not wrong or right. there are two ways of doing alpha beta, one is called fail hard (what you describe) and the other is called fail soft.
fail soft is what all good engines do nowadays, but you can try with fail hard if you like. or try both and compare the node counts... and introduce a hash table in there. food for thoughts

Actually the link you give also describes fail soft.

Hi Lucas,

after looking a second time on your pseudo code some posts above I noticed that my previous correction (add code to update alpha) was suboptimal. Only after your last post I got aware of your intention to use fail-soft. But instead of raising alpha (which is redundant since best_score is already raised on an improved score) it is required to pass "-max(alpha, best_score)" instead of "-alpha" to the recursive search call. That ensures that the window is at most of size (alpha,beta) but can become tighter as soon as best_score exceeds alpha.

Regarding fail-hard vs. fail-soft, since the slight improvement of fail-soft can only be seen when using aspiration windows or other advanced search techniques, I would always recommend to an alpha-beta beginner to start with fail-hard.

Sven

[lucasart]

Here's some pseudo code to help you understand what the most minimalistic search should do:

Fully agreed, only one element is missing in that pseudo code, the updating of alpha, as shown below:

Code: Select all

		best_score = max(best_score, score)
		if (best_score >= beta)
			return best_score	// beta cutoff
		if (best_score > alpha)
			alpha = best_score	// raise alpha

Sven

According to http://chessprogramming.wikispaces.com/Alpha-Beta that is incorrect: if best_score >= beta, one should return beta, not best_score.

it's not wrong or right. there are two ways of doing alpha beta, one is called fail hard (what you describe) and the other is called fail soft.
fail soft is what all good engines do nowadays, but you can try with fail hard if you like. or try both and compare the node counts... and introduce a hash table in there. food for thoughts

Actually the link you give also describes fail soft.

Hi Lucas,

after looking a second time on your pseudo code some posts above I noticed that my previous correction (add code to update alpha) was suboptimal. Only after your last post I got aware of your intention to use fail-soft. But instead of raising alpha (which is redundant since best_score is already raised on an improved score) it is required to pass "-max(alpha, best_score)" instead of "-alpha" to the recursive search call. That ensures that the window is at most of size (alpha,beta) but can become tighter as soon as best_score exceeds alpha.

Regarding fail-hard vs. fail-soft, since the slight improvement of fail-soft can only be seen when using aspiration windows or other advanced search techniques, I would always recommend to an alpha-beta beginner to start with fail-hard.

Sven

At what point in my code does max(alpha,best_score) not equal alpha when calling the search recusrively ?
Note that best_score is initialized with -inf which is always <= alpha