Fastest best move

[Volker Böhm]

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

Hi Ron,

I think you don?t need spare bits. It is only neccessary to XOR another value to your hash keys, taken from a additional array with 100 elements.

Greetings volker

[Ron Murawski]

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

Hi Ron,

I think you don?t need spare bits. It is only neccessary to XOR another value to your hash keys, taken from a additional array with 100 elements.

Greetings volker

Hi Volker,

I'm thinking more about this and I believe that for the side that is ahead
you want the shortest path (smallest 50-move count), but for the side
behind in the scoring you want the longest path (largest 50-move count).
For games that are close to a draw, I don't know...

I don't think I expressed my idea well. In the endgame only, when a new
score is the same as a score stored in the hash table, my thought is not to
store the move from the deepest search, but the one with the smallest or
largest 50-move count. Perhaps this would force the engine to make
progress (if winning) or prevent progress by the opposing engine (if
losing).

Or am I missing something fundamental here???

Ron

[Volker Böhm]

Hi Ron,

I do not think you miss something fundamental. I think it is fair to score the 50move count for evaluation. The higher the 50move count is the more the score should get to draw. This may not only solve the problem where engines play waiting moves until the see the 50move bound but perhaps also the following problems:

* Engines that are behind should not open a position. Perhaps it is wise to just move around if the opponent cannot really do anything (pawn - moves, captures). - Could be dangerous-
* Engines that have an advantage should prevent situations where the opponent could force many moves without captures or pawn pushes (perhabs by giving endless checks".

The problem I cannot realy solve for now is the way the hash is handled correctly.

In your proposal (using the maximum amount of moves in a row that doesn?t move pawns or does capture pieces) you depend on two values when storing to hash:
1. The current maximum.
2. The current 50move counter.

If you store both with the hash entry (either by own bits or just by xoring them to the hash key) there will perhaps be far less hash hits.

Greetings Volker

[Ron Murawski]

Hi Volker,

Another result of getting the longest/shortest path correct would encourage
the losing side to blockade opposing pawns, preventing their advance.

I'm not sure if my idea will actually work. I'm also wrestling with proper
handling of the hash -- I think it is difficult to get correct. I've tried many
non-productive ideas and this might be another one of them.

Perhaps the best place to influence longest/shortest path is in the move
ordering where the 50-move count will either be one larger than before or
reset to zero. A move-ordering bonus/penalty for proper/improper path
(longest or shortest) might do better than trying to store the information in
the hash.

Some other questions without easy answers:
* What if the score is close to draw... Do you want a long or short path?
* How far ahead does the engine have to be in order to decide to take the
shortest path?
* How far behind to decide to take the longest path?

My engine is still a long way from accurately estimating who is ahead in the
endgame so I would need to have fairly large values to trigger the
longest/shortest path code. Until my endgame evaluation code improves I
have no way to test these ideas.

Best regards,
Ron

[H.G.Muller]

The original queston in this thread was: "how to make the engine go for the fastest path". It is indeed an independent matter if (or when) you acually would want that. This is no so much technical problem, but more a philosophical one, and therefore much more difficult to answer. It depends on opponent modelling/contempt. Does it pay to postpone a gain because he will suffer from horizon effect and will start making pointless sacrifices as long as the gain is unavoidable? Does it pay to check his king first, in the hope that he will forget to step out of it?

In my experience the side that has the gain pending is more vulnerable to unpleasant surprises. Partly because it is usually tactically bad to do this: e.g. if I don't immediately recapture his Knight after an intended exchange of Knights, but postpone it by presentng the opponent wth another forcing move, like attacking his Rook with a Bishop, you open up lines of defense to him where he ignores the new threats, but starts to wreck havoc with the Knight that was lost anyway. (e.g. taking a defended pawn, on a square from where he can give a King-Queen fork). How sure can you be that your engine will see all that (in QS, where other delaying moves by him might push it)? The fact that he is forcibly going to lose material, lowers his standards and maks lots of tricks good that would otherwise be unacceptable. If your search is tactically perfect, all that does not matter. But statistically speaking, in a biased tree where many more paths are good for him than good for you, a mistake is much more likely to favor him than you...

The hashing is another problem. Formally the value of the 50-move counter and the set of previously visited position along the path are part of the state of the game. So it is OK if the stored evaluation depends on that. Unfortunately, making the key dependent on that information will make the hash table practically useless du to the low hit-rate. Especially in the end-game, where the tree contains many occurrences of the same position reached through different approaches of the King.

'For this reason I think it is better not to rely on the 50-move rule or indeed, not even implement it. If your engine is so stupid that he can not win a won situaton with (say) a 20-ply search in 40 moves, it is very questionable if he can solve it in the remaining 10 moves, when the 50-move draw first gets within the horizon. More likely he has already 'painted himself in a corner'. Consider the KbnK end-game, withoud the aid of positional information (and the knowledge that it is good to get the bare King closer to a certain corner). You wil see 40 random moves, and then the score will drop from +6 to 0 because an unavoidable draw is recognized. No big help. The 50-move rule is not the solution to the problem of indecision, in the cases where it does help, it was a lucky side-effect...

[smcracraft]

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

Have you tried putting in an eval bonus of two connected passed
pawns on the 6th rank being equal to a rook in value?

This evaluation term may help you solve that problem.

Stuart

[Volker Böhm]

Hi Stuart,

a situation specific eval will allways solve every single task, but I am thinking about a search-trick to handle such positions. Thus the answer is "no".

Greetings Volker