Volker B?hm wrote: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).
Posted: 07 Jan 2006, 22:49
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...
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.
