Fastest best move

[Jonatan Pettersson]

Might be a silly question but I'm having some trouble with my engine not choosing the fastest line to victory. If it can see a good move 3 plies ahead, it might not do it if there's no way to stop it (like having a pawn close to promotion and not moving it until it's actually at risk of capture).

Mate is not a problem since that's taken care of in my search (lowering the mate value deeper in the search).

Is there a good way of making the engine pick any good line quick, even if it can do it undisturbed further down in the search?

[H.G.Muller]

This is a very general problem, that goes back to the very foundation of the way we make computers play chess. Why is it better to select the short path to victory? You don't get more points if you win in a short number of moves...

On the other hand, it is embarrassing to see your engine postpone the capture of a queen for 49 moves with meaningless checks before the 50-move rule forces him to take the capture or face the draw. We programmers are a lot less patient than our engines. I'm sure if you could ask the engine why he gave the 49 checks he would tell you he was just having a good time and wanted to enjoy it as long as possible...

I reasoned as follows: the score a moves get is based on the current evaluation plus what the search predicts he will gain on top of that by future moves. If the prediction were perfect there is no reason to take the fast path. Unfortunately my engine is far from perfect, and misjudges the future quite often. On the other hand, the present is often obvious. So there is a certain risk involved in relying on a good score that is derived from future gains: the gains might be illusory and evaporate on deeper search. If the advantage is expressed in current evaluation, it is much more real, and evaporates less easily.

So if the total score is higher than the current evaluation (meaning I expect to gain something) I give the score an uncertainty penalty. Variations that postpone a gain for many moves accumulate the penalty as the scores are passed down the tree. The opponent will look, during the sequence, to a score that will be consistently worse than the current evaluation, and will receive no penalty. So at the root such paths look less attractive for the side that postponed the gain.

It does not matter very much if the penalty is a percentage or a fixed value. In my latest engine I subtracted half a pawn for any future gain more than 1.75 pawn, and had the penalty go linearly to zero when the future gains dropped to 0.75 pawn. The corrected score is then still a continuous and monotonous function of the original score.

You have to be very careful with the (alpha,beta) window-limits, though, if you are going to change the score by an amount that you know only afterwards (i.e. after the subtree for the move that you might penalize is searched). If you might subtract (say) 10 points, you should shift up the window by 10 points, so that a move that was not accurately evaluated because it was supposed to produce a cutoff, does not become an accepted (in-window) and score-determining move after subtracting the 10 points. So you have to apply the inverse function to the window limits that you will apply to the result of the move for implemeting the penalty. If you will subtract 10% on positive scores (on the amount above the current evaluation), i.e. multiply the excess with 0.9, you will have to multiply all window limits by 1/0.9 = 1.111111 or 1.111112 in advance. The last digit is significant! Make sure you round in the direction to make the window larger (so oppositely for alpha and beta). If you don't, there is no limit to the stupidity of the moves that your engine will produce, because moves that can at most get equal score as the best so far, and thus are not further investigated for how bad they are because they are not supposed to be chosen, will be chosen after all because of the tiny bit of rounding in the wrong direction. For equal scores, the rounding determines which is chosen, no matter how tiny the difference. My engine overlooked he could be checkmated in one in an 8-ply search because of this.

[Volker Böhm]

Hi,

I agree on the generality of the problem, but not on the way described by H.G. Muller to solve it.

The problem on the idea of H.G. Muller is, that the evaluation is much less accurate than the search result, quite the other way as he described it. The evaluation does not concider tactical gains that are very important for the total evaluation. Additionally in many games the engine does very well to take a solid path to win with some more moves than to try to reach a high risky quick win. The only idea to add the "uncernity effect" that seems good is to count the amount of winning moves in a position and search more if there are only few good moves. The problem is that the typical Alpha-Beta does only know the value of the best move.


IMHO the problem you described is part of the horizon effekt where an engine cannot see the goal because it is too far away to find it in search. The only possible solution is to add terms to your evaluation that "smells" how near it is to the goal. More such terms will lessen your problem. Examples:

1. Give pawns a bonus the nearer they are from promoting. Then pawns will advance even if the search does not see the promotion.

2. In an KQK endgame give a bonus for the side with qeen for the distance between the opponent king and the nearest edge (the nearer the better) and from its king to the opponent king (the nearer the better). You will see your engine promoting the pawn to a queen as fast as possible as the search could easily see that by having the queen it can force the king to get closer to an edge.

3. Give your pieces a bonus if they are placed near the enemy king and your engine will concentrate forces for a king attack.

All engines I know have situations where no eval term is able to "smell" what to do, thus you will never be perfect!


Greetings Volker

[Tord Romstad]

Hi Volker,

Good post!

The only idea to add the "uncernity effect" that seems good is to count the amount of winning moves in a position and search more if there are only few good moves.

This is essentially exactly what multi-cut pruning does. At nodes where you expect a fail high (based on the static eval, a hash table score, a reduced depth search, or whatever), search the first x moves with reduced depth, without allowing a beta cutoff. If at least y of the x first moves produce a score >= beta, return a fail high score without doing a full depth search.

I've tried it in Glaurung a couple of times, without success.

Tord

[H.G.Muller]

Well, Volker, what can I say? You might not agree with the underlying motivation, but the idea works quite satisfactory in practice.

All of the evaluation terms you mention are good to have, as I wrote elsewhere in this forum, the very reason for evaluation is to anticipate what lies beyond the horizon, so that deepening the search does not make the move score vary wildly and unpredictably. But they don't do a thing for the problem Jonatan raises:
If there are multiple paths to equivalent (or even identical) end-leaves of the search tree, why would the computer prefer the shorter one? This problem even exists if the eventual goal (the check-mate) does ly within the horizon. It can of course be solved by some ad hoc trick (e.g. make the score of the check-mate dependent on the move number), but if you don't use a general solution the problem will always come back to haunt you in another form. Such as recapture of a Queen - or even a pawn - in a position where you can also chase the enemy King with pointless checks.

Another example: When I gave bonus points to be close to a bare King with my own, it was not enough to make my program do it, no matter how high the bonus! The reason was that the closest legal distance could be reached in 5 moves from anywhere on the board. Since the program was searching typically 12 ply in such a situation, it could still see that for any other move it started with, it could still force a path to the best position in its search tree. So it never saw any urgency in starting the journey, and postponed it for ever (in KQK), keeping the bare King trapped with his Queen in the corner far away from his own King.

If your program does not suffer from this, you are simply lucky, e.g. because for some completely accidental reason it prefers King's moves over Queen's moves. Or it preserves some move ordering from smaller search depth where the King could not go all the way, setting the choice between moves with otherwise identical score (because they all are aimed at forcing a path to the same end-leave). It is dangerous to rely on such accidental ordering to make the right choice between equally valued moves.

[Volker Böhm]

Hi H.G. Muller,

I agree with the idea to solve this prinzipially and not by eval terms. With the KQK example I don?t see the problem. As once your king is in opposition to the opponent king and the opponent king is at an edge it will be very hard to not see the mate.

But I agree there are allways situation that one cannot solve in eval.

Where I fully disagree is "If the advantage is expressed in current evaluation, it is much more real, and evaporates less easily". This is not at all true in tactical positions.

I am sure, that your algorithm solves the problem descibed but I am allmost sure that it will as well reduce your playing strength.


Nevertheless the approache is very interresting if you use it in special situations. Thus I have some questions about possible search problems.

1. How do you handle extensions? Example you have a gain that could be driven out of horizont by checks of your opponent. Typically you add check extensions to keep the gain inside the horizont. Will you reduced the value of your gain because the opponent can do several useless checks?

2. How do you handle search depth reductions? Will reduced searched positions get a bonus because searching less deep in "very quiet" positions?

3. For hashing the same position sould allways get the same score and return the same score down the tree even if it is reached by different moves or a different arrangement of moves. How do you handle this?


An example I whant to solve with a related algorithm is the position 230 from WAC:
"2b5/1r6/2kBp1p1/p2pP1P1/2pP4/1pP3K1/1R3P2/8 b - - 0 1".

Spike hasn?t got an eval term to see that the position is draw once the black pawn has moved to a4. Black has an advantage and can keep it for 50 moves by just doing useless moves. The only way to win here is to sacrifice the rook (the right move is Rb4) but this is far too deep to be seen by spike.

Greetings.

Volker

[Dann Corbit]

Jeremiah Pennery's wall detection code (found in some Crafty versions) solves WAC.230 by noticing that black is about to form a fortress.

You can also solve it quickly by giving a huge value to passed pawns (besides breaking the fortress wall, you are also trading a rook for a passer), but that solution causes bad game play in general.

[eric_oldre]

Jeremiah Pennery's wall detection code (found in some Crafty versions) solves WAC.230 by noticing that black is about to form a fortress.

You can also solve it quickly by giving a huge value to passed pawns (besides breaking the fortress wall, you are also trading a rook for a passer), but that solution causes bad game play in general.

Dann,
Do you know which file in crafty contains this wall detection code. I can't find the words "DFUTILITY" or "Penery" anywhere beside the comments in main.c. I'd be very interested in seeing the ideas expressed in this code.

* 19.1 changes to the outside passed pawn and outside candidate pawn *
* code to more correctly recognize when one side has a simple end- *
* game position that is easy to win. futility pruning and razoring *
* (Jeremiah Penery) was added. to endable it, you will need to add *
* -DFUTILITY to the Makefile options, otherwise it is disabled by *
* default. EvaluateWinner() had a bug dealing with KR vs KN or *
* KRR vs KRN(B) that has been fixed. *
*

[Dann Corbit]

In here:
ftp://ftp.cis.uab.edu/pub/hyatt/src/crafty-19.20.zip

E:\crafty\c19-20>grepcarl detectdraw *.?
evaluate.c ( 28): #if defined(DETECTDRAW)
evaluate.c ( 53): #if defined(DETECTDRAW)
evaluate.c ( 1173): #if defined(DETECTDRAW)
evaluate.c ( 3764): #if defined(DETECTDRAW)
Makefile ( 48): # -DDETECTDRAW This enables experimental code that detects lots of the

The draw detection code has been removed in version 20. A tragedy for me.

[Uri Blass]

Well, Volker, what can I say? You might not agree with the underlying motivation, but the idea works quite satisfactory in practice.

All of the evaluation terms you mention are good to have, as I wrote elsewhere in this forum, the very reason for evaluation is to anticipate what lies beyond the horizon, so that deepening the search does not make the move score vary wildly and unpredictably. But they don't do a thing for the problem Jonatan raises:
If there are multiple paths to equivalent (or even identical) end-leaves of the search tree, why would the computer prefer the shorter one? This problem even exists if the eventual goal (the check-mate) does ly within the horizon. It can of course be solved by some ad hoc trick (e.g. make the score of the check-mate dependent on the move number), but if you don't use a general solution the problem will always come back to haunt you in another form.

I agree that you need to have different score for mates in order not to delay the mate forever but except different score for mates I do not see
the problem because uually you can win more material by not delaying captures.

Even if you have the same score for all mates I think that the only problem is delaying the mate because at some point you will have to mate to avoid draw by repetition or draw by the 50 move rule and if your program does not mate then it means that it has a bug of evaluating draw line as mating line or you have some bug when you do unsafe pruning by hash when you believe that you have big material advantage when it is really a draw by the 50 move rule.

A program with no bugs will never prune drawing line by hash tables because of some assumption that the line is winning.

Uri

[H.G.Muller]

1. How do you handle extensions? Example you have a gain that could be driven out of horizont by checks of your opponent. Typically you add check extensions to keep the gain inside the horizont. Will you reduced the value of your gain because the opponent can do several useless checks?

2. How do you handle search depth reductions? Will reduced searched positions get a bonus because searching less deep in "very quiet" positions?

3. For hashing the same position sould allways get the same score and return the same score down the tree even if it is reached by different moves or a different arrangement of moves. How do you handle this?

Let me first focus on the specific questions:

1. Yes, the gain is reduced if the opponent can delay it by a number of checks. If this is justified depends on how exactly you do your extensions: do you give both the checking side and the check evasion one extra ply, or just the check evasion? If you just extend the one ply for the check evasion, each intervening check pushes the gain closer to the horizon, and thus makes it less thoroughly tested. The gain might be illusory, but its refutation might be too complicated for the QS+eval to see.

If you would extend two plies for a check, this argument fails. If you would extend three plies, it would reverse (and your search would probably explode). But even in the latter case (if it were feasible) you might argue that you only verified the gain well under the assumption that he would give the check, so depreciating the gain can never hurt: if it would be the best end-leave the opponent can prevent you from getting there by not giving the check. Giving the check only makes sense for him if some of the end-leaves in the non-extended part of the tree evaluated better.

So it is difficult for me to think up an example where a slightly larger depreciation of the gain after the check would hurt. If this is the only way to obtain a similar gain, the program will still do it. Only if there were alternatives to achieve a similar (or only slightly smaller gain) earlier in the tree, it will prefer that.

2. My program does not really do reductions, so I have to be a little careful on that one. Mind that I am not penalizing deep or shallow search per se, I am penalizing the length of the path from the root to the point where the gain materializes. So the difference between reducing and not for a specific gain (occuring at a given number of plies from the root) is that the gain is closer to the horizon in the former case. You might argue that this makes the gain less certain, and that it therefore deserved a higher discount, while in fact it receives the same because only the distance to the root is taken into account. But this ignores the fact that you don't apply reductions randomly, but that there was presumably a good reason for applying it (quiet situation, etc.). If we suppose that the reduction is justified, the reliability of the gain is equal in reduced and unreduced parts of the tree, so it seems reasonable that the 'postponement penalty' does only depend on the distance to the root. If the reduction does not give equally reliable scores, there is a problem with the reduction criteria, not with my algorithm. If the reduction pushes the gain beyond the horizon, the program will dive into the part of the tree that was not reduced, where it can see the gain, independent of my algorithm was used to depreciate it, because it is the only gain it sees.

3. For the hashing it poses no problems. The score is a function of the position only, e.q. if it is a check-mate the position is entered in the hash-table with the one and only check-mate score. When the search hits on such a hashed position deep in the tree, the score is discounted on passing it down to the root. So if there are two paths leading to that same check-mate, (say 5 or 9 ply) the first move of the long path will recieve a lower score than the first move of the short path, and will be selected as the best move. It will thus evaluate the root position as a mate-in-3, not a mate-in-5 (and enter it in the hash table with this score).

So every hash entry will recieve the score it deserves, be it 'mate-in-n' or 'queening-in-n', or 'queen-capture-in-n', the higher n, the lower the score. Later searches that can force a path to such a stored position in m moves (through the quickest path) automatically receive the 'mate-in-(n+m)' score, as they should. In fact, the search just builds a table-base for the best sub-goal it can enforce within its horizon in the hash table. In the KPK end-game, for instance, you see the score first jump to the (delayed) queening value, and very quickly after that jump to the check-mate value, because by the time it has forced the queening most of the TB for KQK is already in the hash table (from variations with stupid play for black, that let the pawn pass straight away).

[mathmoi]

Might be a silly question but I'm having some trouble with my engine not choosing the fastest line to victory. If it can see a good move 3 plies ahead, it might not do it if there's no way to stop it (like having a pawn close to promotion and not moving it until it's actually at risk of capture).

Mate is not a problem since that's taken care of in my search (lowering the mate value deeper in the search).

Is there a good way of making the engine pick any good line quick, even if it can do it undisturbed further down in the search?

Hi,

It seems to me that Iterative deepening will resolve this issue. No ?

Let's say that you do a depth=1 search and you found a good capture. Later you do a depth=3 search using the best move at depth=1 as the first move you search (and you do this for all subsequent search). Even if you can delay the capture at the 3rd ply, your engine won't since he searched the capture move first. If you find an other best move at depth=3 that imply delaying the capture, it is clear that the capture must be delayed.

Not sure regards
Mathieu Pag

[Daniel Mehrmann]

Hi Volker,

Good post!

The only idea to add the "uncernity effect" that seems good is to count the amount of winning moves in a position and search more if there are only few good moves.

This is essentially exactly what multi-cut pruning does. At nodes where you expect a fail high (based on the static eval, a hash table score, a reduced depth search, or whatever), search the first x moves with reduced depth, without allowing a beta cutoff. If at least y of the x first moves produce a score >= beta, return a fail high score without doing a full depth search.

I've tried it in Glaurung a couple of times, without success.

Tord

But works perfectly for Homer. I don't need NullMove or IDD

MC-Pruning doing all me like odering, pruning, IDD and some other stuff.

Best,
Daniel

[H.G.Muller]

It seems to me that Iterative deepening will resolve this issue. No ?

This is what I considered as dangerous: you rely on a non-guaranteed property, that a less deep search will already recognize the move as good. If this works depends on how you do the move sorting (i.e. do you strictly take over the order found by the previous iteration, or do you allow it to be overridden by the discovery of new killer moves at the deeper level?)

A position might first look too good, and get its true, lower (but still best) value only at a deeper search. A long path to that position might leave not enough search depth to get the correct score, making it recieve the over-estimated score, while the shortest path does leave enough search depth. In that iteration the first move of the long path will then replace that of the fast path as first in the move sorting. In the next iteration, both paths search deep enough beyond that position to agree about the (lower) value, but that is not enough to switch the order back, and the long path will be prepared.

This example is for a search without hash tables, but relying on the hash tables is even more dangerous. What happens depends on replacement policy and might be very unpredictable. Sometimes positions are already present in the hash table searched very deep before they become relevant for the score. This happens for instance in the KPK end-game, where stupid defense gives a fast path to promotion (but the search still had to go all the way to promotion to prove that the defense was stupid). A short and a long path to a won position can discover that they are won in the same iteration, not because they reach deeper, but because a position they could already reach in previous searches is suddenly upgraded to 'winning' in the table through an intervening search in an even faster branch (that could not be enforced, but was only faster due to cooperation of the opponent). If you then preserve the order they have from before it was discovered that they both led to queening, it is not better than random. It might, for instance, lead to indecisive behavior with W:Ke4,Pe3; B:Ke6 (black to move), keeping the opposition (i.e. Kd4 after Kd6) in stead of surging forward (... Kf5), because on previous iterations, before it could be seen that Kf5 led to queening, Kd4 was considered better for positional reasons (center, opposition).

[Tony van Roon-Werten]

Hi all,

I've been playing around with this stuff for a while, it looks like I've found a decent solution.

I started with using the 50 move counter, and reducing the score with a percentage depending on that counter.

It didn't work. What the engine did, was fooling around for 10 ply in search and then right before the last ply, making an irreversable move, since then the evaluation would not be punished. But the next iteration, it would just fool around 11 ply and then 12 etc.

So I use the following, wich seems to work OK.

Code: Select all


   if (ply<3) tree->search_data[ply].worst_50moves=board->50moves_cnt;
   else
   {
      tree->search_data[ply].worst_50moves=tree->search_data[ply-1].worst_50moves;
      if (board->50moves_cnt>tree->search_data[ply].worst_50moves) tree->search_data[ply].worst_50moves=board->50moves_cnt;
   }
   board->drawfactor=100;
   if (tree->search_data[ply].worst_50moves>10)
   {
      board->drawfactor=100-((tree->search_data[ply].worst_50moves-10)*2);
      if (board->drawfactor<10) board->drawfactor=10;
   }

score=(score*board->drawfactor)/100;



The idea is that, when searching fe 10 ply, the optimium score will be reached by playing the irreversable move at ply 5, meaning it will search the remaining 5 ply with the consequences of that move (with a lower best score).


Tony

[Daniel Shawul]

Hi Volker,

Good post!

The only idea to add the "uncernity effect" that seems good is to count the amount of winning moves in a position and search more if there are only few good moves.

This is essentially exactly what multi-cut pruning does. At nodes where you expect a fail high (based on the static eval, a hash table score, a reduced depth search, or whatever), search the first x moves with reduced depth, without allowing a beta cutoff. If at least y of the x first moves produce a score >= beta, return a fail high score without doing a full depth search.

I've tried it in Glaurung a couple of times, without success.

Tord

But works perfectly for Homer. I don't need NullMove or IDD

MC-Pruning doing all me like odering, pruning, IDD and some other stuff.

Best,
Daniel

I recently tried MC pruning along with null move, and it works better than using it alone. Many engines use "Fail low" reductions combined with null move and it works. Fail high reductions are same as fail low redcutions, only difference being the point of application. So i think you might get better results if you combine it with null move.
daniel

[Daniel Shawul]

sorry, i was thinking of FH reductions + Nullmove.
MC pruning should be used without Null move.

[Ron Murawski]

Hi all,

I've been playing around with this stuff for a while, it looks like I've found a decent solution.

I started with using the 50 move counter, and reducing the score with a percentage depending on that counter.

It didn't work. What the engine did, was fooling around for 10 ply in search and then right before the last ply, making an irreversable move, since then the evaluation would not be punished. But the next iteration, it would just fool around 11 ply and then 12 etc.

So I use the following, wich seems to work OK.

Code: Select all


   if (ply<3) tree->search_data[ply].worst_50moves=board->50moves_cnt;
   else
   {
      tree->search_data[ply].worst_50moves=tree->search_data[ply-1].worst_50moves;
      if (board->50moves_cnt>tree->search_data[ply].worst_50moves) tree->search_data[ply].worst_50moves=board->50moves_cnt;
   }
   board->drawfactor=100;
   if (tree->search_data[ply].worst_50moves>10)
   {
      board->drawfactor=100-((tree->search_data[ply].worst_50moves-10)*2);
      if (board->drawfactor<10) board->drawfactor=10;
   }

score=(score*board->drawfactor)/100;



The idea is that, when searching fe 10 ply, the optimium score will be reached by playing the irreversable move at ply 5, meaning it will search the remaining 5 ply with the consequences of that move (with a lower best score).


Tony

That's an interesting idea, Tony. Another approach, if you have a spare 5
bits in your hash entry, is to record the 50-move count. In your hash
replacement code, the move with the smaller 50-move count should
replace the larger 50-move count when the scores are equal. I have not
actually tested this idea -- it's on my to-do list.

Ron

[Edsel Apostol]

Hi Dan,

I have tried FH reduction before, I used it as a replacement for the null move forward pruning. It searched much faster at fixed depth, less nodes searched at fixed depth, compared to the null move, but it is weaker. I guess it might be because of my weak evaluation function or maybe null move is just stronger than FH reduction in general.

I just want to ask you, how did you do it, I mean, to combine null move and FH reduction?

Edsel

[Daniel Shawul]

HI edsel
i just used normal FH reduction with little modification.
if the evaluation of the postion is > beta and there is no threat
(material, promotion or mate), redcuce the depth. The modification is
i dont do this when there is an extension in the current ply and the previous ply,this avoids tactical problems. I think FH is too unsound (for that matter MC pruning also) to use it as a substitute of null move.
some engines like fruit do null move only when the evaluation predicts a fail high. What i am currrently doing is still try the null move but with a reducted depth.