Author: Ed Schröder
Date: 12:51:44 09/10/99
Go up one level in this thread
On September 10, 1999 at 13:12:35, Robert Hyatt wrote:
>On September 10, 1999 at 11:40:40, Ed Schröder wrote:
>
>>On September 10, 1999 at 08:01:35, Alessandro Damiani wrote:
>>
>>>On September 10, 1999 at 07:48:44, Ed Schröder wrote:
>>>
>>>>On September 10, 1999 at 00:19:37, Robert Hyatt wrote:
>>>>
>>>>>Here is an interesting position given to me by Steffen Jakob:
>>>>>
>>>>> /p/P5p/7p/7P/4kpK/// w
>>>>>
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 8 | | | | | | | | |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 7 | *P| | | | | | | |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 6 | P | | | | | | *P| |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 5 | | | | | | | | *P|
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 4 | | | | | | | | P |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 3 | | | | | *K| *P| K | |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 2 | | | | | | | | |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> 1 | | | | | | | | |
>>>>> +---+---+---+---+---+---+---+---+
>>>>> a b c d e f g h
>>>>>
>>>>>
>>>>>Obviously black is getting crushed. He has one move, Kh3, which leads to a
>>>>>mate in 6. Steffen asked me to try this and Crafty found a mate in 4, which
>>>>>doesn't exist. I spent the entire day debugging this thing and here is what
>>>>>I found:
>>>>>
>>>>>If you recall the discussion here a couple of weeks ago, I reported that I store
>>>>>absolute mate scores (EXACT scores) in the hash table, and that I adjust them
>>>>>so that they are always stored as "mate in N from the current position". This
>>>>>has always worked flawlessly for me, and still does.
>>>>>
>>>>>For bounds, I once tried adjusting the bounds as well, but found quirks, and
>>>>>left them alone. Wrong answer. To fix this mate in 4 problem, I decided to
>>>>>adjust the bounds as well, but I now set any bound value that is larger than
>>>>>MATE-300, by reducing it to exactly MATE-300, but still using the "LOWER"
>>>>>flag to say that this is the lowest value this position could have. For bound
>>>>>values < -MATE+300, I set them to exactly -MATE+300 and leave the flag as is.
>>>>>
>>>>>This position is cute. Because not only is it a mate in 6, but there are
>>>>>transpositions that lead to mate in 7, mate in 8, and there are shorter (but
>>>>>non-forced) mates in 4 and 5. And there are stalemates, and positions with
>>>>>1 legal move, and so forth.
>>>>>
>>>>>You ought to find the following variation as one mate in 6:
>>>>>
>>>>>Kh3, f2, Kg2, Ke2, Kg3, f1=Q, Kh2, g5, hg, Kf3, g6, Qg2#
>>>>>
>>>>>If you find a shorter mate, it is wrong. If you find a longer mate, you
>>>>>are probably just extending like mad on checks (crafty finds a mate in 8 at
>>>>>shallow depths (9 plies, 2 secs on my PII/300 notebook), and doesn't find the
>>>>>mate in 6 until depth 10, 3 seconds.
>>>>>
>>>>>It is a good test as the transpositions are real cute with white's king caught
>>>>>in a tiny box, but with several different moves that triangulate and transpose
>>>>>into other variations...
>>>>>
>>>>>If you get it right, you have either handled the bounds right, or else you are
>>>>>very lucky. IE Crafty 16.17 gets this dead right. But if I disable the eval,
>>>>>it goes bananas, yet the eval is not important when mate is possible.
>>>>>
>>>>>Have fun...
>>>>>
>>>>>I did... :)
>>>>
>>>>A simple solution: do not store a position in the hash table if there is
>>>>no best-move. It solves the mate-cases and also repetition cases. Also
>>>>there is no speed loss of the search.
>>>>
>>>>Ed
>>>
>>>Do you mean by "no best-move"
>>> bestmove == 0
>>>or
>>> best<=alpha, after having searched all moves (best: minimax score)?
>>>
>>>What I do:
>>> if bestmove == 0 then don't store anything, just return the score (mate or
>>> stalemate).
>>>
>>>Alessandro
>>
>>- For each new ply in the search: bound=-INF; bestmove=0;
>>- For each move on that ply: if (score > bound) { bound=score; bestmove=move; }
>>- For hashing: if (bestmove==0) do_not_update_hash_table
>>
>>Ed
>
>
>I still don't follow your idea. Because at 'fail low' (also called "ALL" nodes
>in Knuth/Moore) nodes the test above will _always_ be true. But what do you do
>if _every_ move returns a score > -infinity, but < alpha, and this score is the
>same for all moves? If you store a random move in the hash table, you totally
>wreck your move ordering, because you will try a random move _before_ you try
>the winning captures, and that can kill efficiency.
I do the bestmove calculation BEFORE I do the A/B check.
Thus...
1) For each new ply in the search: bound=-INF; bestmove=0;
2) For each move on that ply: if (score > bound) { bound=score; bestmove=move; }
3) try A/B
>What do I not understand about your idea?
I don't know, hope it is clear now.
>IE you aren't using PVS/negascout/aspiration search???
Aspiration search.
Ed
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.