All time spent in quiescent search - why?

[sje]

I've been attempting to understand these posts, change my code, debug and post back but I've been a little overwhelmed! I've decided to try and respond to each question individually where I can.

Perhaps you should try some less complex positions before attempting debugging. Try a game that starts with all the queenside men missing. Also, print the current variation at the start of each search node and just do a single search iteration.

[mike_bike_kite]

I doubt you treat alpha-beta (even minimax correctness is questionable) properly.

For minmax I just initialise the best score when starting a new level (white gets -2m and black +2m). I then compare the score for each move against the best score held for that level. If it's white's move and score > best or black's move and score < best then the new score becomes the best. The get score below would either be an evaluation of the board or a recursive call to look deeper into the game.

Code: Select all

if white's turn
   best = -2m
else
   best = 2m

for each move
   get score
   if white's turn and score > best or black's turn and score < best
      best = score
return best

For alphabeta it's similar to the above except that, when a new best score is found, I also compare the score to the best score at the level below. If the new score is also better than the best score at the level below then it's an alphabeta cut and I don't explore any further moves at this level.

Code: Select all

if white's turn
   best = -2m
else
   best = 2m

for each move
   get score
   if white's turn and score > best or black's turn and score < best
      best = score
      // alpha beta cut
      if white's turn and score >= level_below_best or blacks's turn and score <= level_below_best
         return best
return best

Both methods will return the same score for the same position (assuming any random influences are turned off) but the alpha beta search just explores fewer nodes and takes less time. This all seems correct to me. Why do you think I'm doing it wrong?

[mike_bike_kite]

Couple of things that I use.

(1) use SEE and do not search captures with SEE < 0, as those are generally bad.

(2) use MVV/LVA ordering, so that you get rid of the queens and rooks first, since they tend to go on feeding forays and drive the search deeper as the queens eat away on opposite sides of the board.

(3) qsearch is always going to be a major part of the tree, because of the exponential shape the tree has. You ALWAYS get to the qsearch at the end of every normal branch you search, and then you add on captures. It only takes a couple to make the q-search examine 90% of the total nodes searched.

SEE is on my list of things to implement but it's a long list. I use MVV/LVA ordering and the moves are done in what appears to be the right order. The qsearch part is killing me at the moment - when I first posted it was extending down to a depth of 30 and was barely completing a full search at depth 2. This has now improved as the qsearch is now around 20 and full search is now at depth 3 but I'm obviously still doing something wrong

[hgm]

Code: Select all

if white's turn
   best = -2m
else
   best = 2m

for each move
   get score
   if white's turn and score > best or black's turn and score < best
      best = score
      // alpha beta cut
      if white's turn and score >= level_below_best or blacks's turn and score <= level_below_best
         return best
return best

It all depends on what 'level_below_best' is, and how you update it. As I pointed out, the very deep line you showed is definitely searching a branch that is totally irrelevant for the root score, and thus should have been pruned by alpha-beta. So either your alpha-beta is not correctly implemeted (e.g. alpha and beta wrongly updated), or your eval scores must be very wrong (which I don't expect). Normally gaining Knight for Pawn should be sufficient to cause a beta cutoff, but it obviously doesn't.

As long as you don't fix that, none of the refinements suggested in the above posts will have much impact. Move ordering is only helpful when alpha-beta works properly...

[mike_bike_kite]

It all depends on what 'level_below_best' is, and how you update it. As I pointed out, the very deep line you showed is definitely searching a branch that is totally irrelevant for the root score, and thus should have been pruned by alpha-beta. So either your alpha-beta is not correctly implemeted (e.g. alpha and beta wrongly updated), or your eval scores must be very wrong (which I don't expect). Normally gaining Knight for Pawn should be sufficient to cause a beta cutoff, but it obviously doesn't.

As long as you don't fix that, none of the refinements suggested in the above posts will have much impact. Move ordering is only helpful when alpha-beta works properly...

This is a better description of my main search function and I hope it describes what I mean by the best score at the level below. It shows what variables I have to play with ie score and BestScore. It doesn't include the stand pat score as we're trying to decide if my alpha beta stuff is ok - I think it is but this should explain it.

Code: Select all

findBestMove( level, max_level ) {
	bestScore[level] = whites_turn ? -2000000 : 2000000

	get moves in MVV/LVA order ie captures first

	// leaf node
	if level > max_level and no_captures_available
		return evaluateBoard();

	// try each move
	for each move
		if level <= max_level or capture_move

			// try move
			putOnMove&#40;)
			swapSides&#40;)
			score = findBestMove&#40; level+1, max_level )
			swapSides&#40;)
			takeOffMove&#40;)

			// minmax
			if whites_turn and score>bestScore&#91;level&#93; or blacks_turn and score<bestScore&#91;level&#93;

				bestScore&#91;level&#93; = score
				bestMove&#91;level&#93; = move
				
	      	// alpha beta cut
				if whites_turn and score>=bestScore&#91;level -1&#93; or blacks_turn and score<=bestScore&#91;level -1&#93;
					return score
	
	return bestScore&#91;level&#93;

Does this look right?

[Don]

It does not look right to me. You are are looking at previous levels to get the equivalent of beta which is ok to do, but it's like you are resetting alpha to -INF at each level. So your program is going to be orders of magnitude slower. Assuming I read this right.

It all depends on what 'level_below_best' is, and how you update it. As I pointed out, the very deep line you showed is definitely searching a branch that is totally irrelevant for the root score, and thus should have been pruned by alpha-beta. So either your alpha-beta is not correctly implemeted (e.g. alpha and beta wrongly updated), or your eval scores must be very wrong (which I don't expect). Normally gaining Knight for Pawn should be sufficient to cause a beta cutoff, but it obviously doesn't.

As long as you don't fix that, none of the refinements suggested in the above posts will have much impact. Move ordering is only helpful when alpha-beta works properly...

This is a better description of my main search function and I hope it describes what I mean by the best score at the level below. It shows what variables I have to play with ie score and BestScore. It doesn't include the stand pat score as we're trying to decide if my alpha beta stuff is ok - I think it is but this should explain it.

Code: Select all

findBestMove( level, max_level ) {
	bestScore[level] = whites_turn ? -2000000 : 2000000

	get moves in MVV/LVA order ie captures first

	// leaf node
	if level > max_level and no_captures_available
		return evaluateBoard();

	// try each move
	for each move
		if level <= max_level or capture_move

			// try move
			putOnMove&#40;)
			swapSides&#40;)
			score = findBestMove&#40; level+1, max_level )
			swapSides&#40;)
			takeOffMove&#40;)

			// minmax
			if whites_turn and score>bestScore&#91;level&#93; or blacks_turn and score<bestScore&#91;level&#93;

				bestScore&#91;level&#93; = score
				bestMove&#91;level&#93; = move
				
	      	// alpha beta cut
				if whites_turn and score>=bestScore&#91;level -1&#93; or blacks_turn and score<=bestScore&#91;level -1&#93;
					return score
	
	return bestScore&#91;level&#93;

Does this look right?

[Don]

It all depends on what 'level_below_best' is, and how you update it. As I pointed out, the very deep line you showed is definitely searching a branch that is totally irrelevant for the root score, and thus should have been pruned by alpha-beta. So either your alpha-beta is not correctly implemeted (e.g. alpha and beta wrongly updated), or your eval scores must be very wrong (which I don't expect). Normally gaining Knight for Pawn should be sufficient to cause a beta cutoff, but it obviously doesn't.

As long as you don't fix that, none of the refinements suggested in the above posts will have much impact. Move ordering is only helpful when alpha-beta works properly...

This is a better description of my main search function and I hope it describes what I mean by the best score at the level below. It shows what variables I have to play with ie score and BestScore. It doesn't include the stand pat score as we're trying to decide if my alpha beta stuff is ok - I think it is but this should explain it.

Code: Select all

findBestMove( level, max_level ) {
	bestScore[level] = whites_turn ? -2000000 : 2000000

	get moves in MVV/LVA order ie captures first

	// leaf node
	if level > max_level and no_captures_available
		return evaluateBoard();

	// try each move
	for each move
		if level <= max_level or capture_move

			// try move
			putOnMove&#40;)
			swapSides&#40;)
			score = findBestMove&#40; level+1, max_level )
			swapSides&#40;)
			takeOffMove&#40;)

			// minmax
			if whites_turn and score>bestScore&#91;level&#93; or blacks_turn and score<bestScore&#91;level&#93;

				bestScore&#91;level&#93; = score
				bestMove&#91;level&#93; = move
				
	      	// alpha beta cut
				if whites_turn and score>=bestScore&#91;level -1&#93; or blacks_turn and score<=bestScore&#91;level -1&#93;
					return score
	
	return bestScore&#91;level&#93;

Does this look right?

What score is returned if there are no captures? It looks like you only return -INF in that case unless it happens to reach the maximum level. That is wrong too.

[hgm]

This is no good. For one, it only allows stand pat when there are no captures, so it would not even return the correct score. Because if there are only losing captures it would think it has to play the least bad of those.

I am not used to alpha-beta in another formulation than negamax, but what you show here looks fishy. I don't see how it would realize deep cutoffs, because the score t the current level gets better than that at level-3, level-5 etc. To avoid having to test for those explicitly, one normally initializes what you call bestScore[level] to bestScore[level-2] rather than -INF.

[Don]

It all depends on what 'level_below_best' is, and how you update it. As I pointed out, the very deep line you showed is definitely searching a branch that is totally irrelevant for the root score, and thus should have been pruned by alpha-beta. So either your alpha-beta is not correctly implemeted (e.g. alpha and beta wrongly updated), or your eval scores must be very wrong (which I don't expect). Normally gaining Knight for Pawn should be sufficient to cause a beta cutoff, but it obviously doesn't.

As long as you don't fix that, none of the refinements suggested in the above posts will have much impact. Move ordering is only helpful when alpha-beta works properly...

This is a better description of my main search function and I hope it describes what I mean by the best score at the level below. It shows what variables I have to play with ie score and BestScore. It doesn't include the stand pat score as we're trying to decide if my alpha beta stuff is ok - I think it is but this should explain it.

Code: Select all

findBestMove( level, max_level ) {
	bestScore[level] = whites_turn ? -2000000 : 2000000

	get moves in MVV/LVA order ie captures first

	// leaf node
	if level > max_level and no_captures_available
		return evaluateBoard();

	// try each move
	for each move
		if level <= max_level or capture_move

			// try move
			putOnMove&#40;)
			swapSides&#40;)
			score = findBestMove&#40; level+1, max_level )
			swapSides&#40;)
			takeOffMove&#40;)

			// minmax
			if whites_turn and score>bestScore&#91;level&#93; or blacks_turn and score<bestScore&#91;level&#93;

				bestScore&#91;level&#93; = score
				bestMove&#91;level&#93; = move
				
	      	// alpha beta cut
				if whites_turn and score>=bestScore&#91;level -1&#93; or blacks_turn and score<=bestScore&#91;level -1&#93;
					return score
	
	return bestScore&#91;level&#93;

Does this look right?

What score is returned if there are no captures? It looks like you only return -INF in that case unless it happens to reach the maximum level. That is wrong too.

I also see that if all captures are losing, you have not choice but to return a losing score which is also wrong.

You can correct some of this by first setting the bestScore at the new level to the same score as the evaluation, not -INF. So if all captures are losing this would become the default score (which is how all modern programs do it) and if there are NO captures this would be returned.

[mike_bike_kite]

It does not look right to me. You are are looking at previous levels to get the equivalent of beta which is ok to do, but it's like you are resetting alpha to -INF at each level. So your program is going to be orders of magnitude slower. Assuming I read this right.

I understand alpha beta cut off as a process but I have no idea what you mean when you refer to alpha and beta as variables. What is -INF? is this the initial value I'm setting it to. Is there a simple explanation of these variables ie is alpha just the current score and beta the current best score. Can I change this code to use your alpha and beta values or do I need to completely rewrite. I have tried reading the chessprogramming wiki pages but they tend to explain each complex process by using other complex processes and I soon give up

I have no doubt that my process can be sped up but is it actually wrong?