Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Interesting mate test for hashing

Author: Robert Hyatt

Date: 10:09:10 09/10/99

Go up one level in this thread


On September 10, 1999 at 11:31:03, Ed Schröder wrote:

>On September 10, 1999 at 09:35:02, Robert Hyatt 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
>>
>>
>>I played with this yesterday.  This means you will _never_ store a fail-low
>>position, where you tried all the moves and each one was refuted by the move
>>below it in the tree.  Not storing those will definitely slow you down.
>
>I see. I assume you only have the A/B bounds for getting the best move?
>I use an extra bound so I always have a best move.
>

I use fail-soft...  if that is what you mean, but that doesn't guarantee a
best move.. as _all_ moves can return the exact same score, which could be
alpha, or some value below alpha.  In that case, how do you tell which is
best?

This is at a node where every move searched gets a score <= alpha...  In most
cases I tested, the moves either all got alpha, or they all got the same value
< alpha, because I am using PVS and lazy eval...




>Ed
>
>>The trick I used above solves this cleanly without losing the fail-low (UPPER
>>bound) cases that still continue to work.
>>
>>Assuming I read what you meant correctly?



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.