Author: Dave Gomboc
Date: 19:50:17 09/10/99
Go up one level in this thread
On September 10, 1999 at 17:40:45, Robert Hyatt wrote:
>On September 10, 1999 at 17:01:58, jonathon smith wrote:
>
>>On September 10, 1999 at 16:45:59, Robert Hyatt wrote:
>>
>>>On September 10, 1999 at 16:21:48, Alessandro Damiani wrote:
>>>
>>>>On September 10, 1999 at 15:58:45, Ed Schröder wrote:
>>>>
>>>>>On September 10, 1999 at 13:17:57, Robert Hyatt wrote:
>>>>>
>>>>>>On September 10, 1999 at 11:29:04, Alessandro Damiani wrote:
>>>>>>
>>>>>>>On September 10, 1999 at 09:36:51, Robert Hyatt 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
>>>>>>>>
>>>>>>>>
>>>>>>>>that doesn't make sense to me. If _every_ move at one node in the tree returns
>>>>>>>>alpha for the score, which is the best move? And since you don't have one, you
>>>>>>>>don't store anything? That hurts performance, because the next time you
>>>>>>>>encounter this position, you get to search it again, while I discover that the
>>>>>>>>last time I searched it I returned alpha, so I can just do that now and not
>>>>>>>>search anything...
>>>>>>>
>>>>>>>No, no. My answer was misleading. What I mean is explained by the following code
>>>>>>>(the code is simpilied!). I have marked the important things by an "****". It is
>>>>>>>assumed that
>>>>>>> - when the king is removed from board its position is -1 ( < 0)
>>>>>>> - alpha, beta < INF
>>>>>>>
>>>>>>>Alessandro
>>>>>>>
>>>>>>>int AlphaBeta (int alpha, int beta, int depth) {
>>>>>>>
>>>>>>>//**************************************
>>>>>>>// legality check:
>>>>>>>
>>>>>>> if (myKingSquare<0) return -INF;
>>>>>>>
>>>>>>>//**************************************
>>>>>>>
>>>>>>> if (depth==0) return Quiescence(alpha,beta);
>>>>>>>
>>>>>>> // here use info from the transposition table
>>>>>>>
>>>>>>> best= -INF; bestmove= 0; startalpha= alpha;
>>>>>>> i= 0; n= GenMoves();
>>>>>>> while (i!=n && best<beta) {
>>>>>>> // m[i] is the current move
>>>>>>>
>>>>>>> make(m[i]);
>>>>>>> value= -AlphaBeta(-beta,-alpha,depth-1);
>>>>>>> unmake(m[i]);
>>>>>>>
>>>>>>> if (value>best) {
>>>>>>> best= value; bestmove= m[i];
>>>>>>> if (best>alpha) alpha= best;
>>>>>>> };
>>>>>>> i++;
>>>>>>> };
>>>>>>>
>>>>>>>//**********************************************
>>>>>>>// no best move => mate or stalemate
>>>>>>>
>>>>>>> if (bestmove==0) {
>>>>>>> if InCheck(Me) return -MATE+ply;
>>>>>>> return STALEMATE;
>>>>>>> };
>>>>>>>
>>>>>>>//**********************************************
>>>>>>>
>>>>>>> // here update the transposition table
>>>>>>>
>>>>>>> return best;
>>>>>>>}
>>>>>>
>>>>>>
>>>>>>Same question as before. The above simply doesn't work as you think it
>>>>>>does. Here is why.
>>>>>>
>>>>>>at ply=N you set best to -inf, and then step thru each move and do a search
>>>>>>after making it. And you pass that search a value for alpha and beta that is
>>>>>>used to terminate the search when it can prove that the score below that move
>>>>>>is >= beta (which at our ply=N node means the move we tried is <= alpha.)
>>>>>>
>>>>>>So lets assume that after we search the first move, we get a score back that
>>>>>>is obviously > -infinity, but < alpha. You remember that move as "best". But
>>>>>>the problem here is that the 'proof' search stopped as soon as it found a score
>>>>>>> beta. It didn't try _all_ moves to get the largest score > beta, just the
>>>>>>first score > beta... which is why we refer to the search as returning a bound.
>>>>>>At least as low, but maybe even lower.
>>>>>>
>>>>>>So you end up with a bunch of random bounds that are all <= alpha, and you take
>>>>>>the largest one and assume that is the best move and store that move in the hash
>>>>>>table? I will run some tests as this is easy to do, but when I tried this a few
>>>>>>years ago, my tree got _bigger_. And when I looked into why, I found myself
>>>>>>searching nonsense moves from the hash table _before_ I got to the winning
>>>>>>captures (the first of which was a move that would refute the move at the
>>>>>>previous ply.)
>>>>>>
>>>>>>Easy to test. I'll supply some data in a bit, just for fun...
>>>>>
>>>>>For one moment forget about alpha and beta, you are on the wrong track as
>>>>>alpha and beta are not a part at all of the code. You need an extra stack
>>>>>that is set to -INF at each ply. Then before you do A/B you do the bestmove
>>>>>calculation for that ply. Involved variables: SCORE and STACK, no alpha beta.
>>>>>
>>>>>Ed
>>>>
>>>>I think the best way to explain is to write a small piece of code in pseudo C,
>>>>else we talk around the point.
>>>>
>>>>Alessandro
>>>
>>>
>>>OK... here is what I did:
>>
>>Drunken code adjustment inserted ................
>>
>>
>>>
>>>Normal alpha/beta first:
>>
>>Drunken code added:
>>
>>>
>>>int Search(int alpha, int beta, etc...) {
>>> best=-infinity;
>> roughbest = -INFINITY;
>>> bestmove=0;
>> roughbestmove = 0;
>>> foreach (move in movelist) {
>>> MakeMove();
>> roughvalue = StaticEvaluate(-whatever,etc);
>>> value=-Search(-beta,-alpha,etc.)
>>> if (value > best) {
>>> best=value;
>>> bestmove=current.move;
>>> }
>>> if (value > alpha) {
>>> if (value >= beta) {
>>> return(value);
>>> }
>>> alpha=value;
>>> }
>> if (roughvalue > roughbest)
>> {
>> roughvalue = roughbest;
>> roughbestmove = current.move;
>> }
>>> }
>> if (THEREWASNTANEWALPHA)
>> HastStore(roughbestmove, etc...)
>> else
>>> HashStore(bestmove,alpha, etc...)
>>>}
>>>
>>>
>>>
>>>So what I did was to simply take the score for each search made after trying
>>>one of the moves at this ply, and remember the 'best' score and associated move.
>>
>>So what you needed to do was think about having an semi-accurate evaluation
>>function at each internal node, rather than a search based quiesence score.
>>
>>
>>>
>>>All I am saying is "this does not work". It is a characteristic of the alpha/
>>>beta search. It isn't a "it might work if ..." it simply won't work. Because
>>>the searches below this node (again, assuming this is a fail-low node where _no_
>>>move produces a score > alpha, which is the case where I claim there is never a
>>>best move to try here) return a bound on the value for that move. And I have no
>>>idea how to choose between a move with a bound <=200 and another move with a
>>>bound <= 150. Because the first could have a score well below 200. I simply
>>>don't know as I told the search below this node to stop whenever you find a
>>>score > X, where X is my negated alpha bound.
>>>
>>>Now, we have code. Did I misunderstand what you are saying? If not, then I
>>>can certainly explain further why that 'best' and 'bestmove' above are no good
>>>in this context. You can think of "best" as a random number that is <= alpha,
>>>nothing more. Which means "bestmove" is a random move chosen from the moves
>>>searched at this ply. And that is _not_ the move we want to try first when we
>>>get back to this position and it is suddenly not a fail-low position where all
>>>moves have to be tried, but rather it is a fail high position where the best
>>>move will let us cut off quickly...
>
>
>That is worthless. You are saying that you would try the best move suggested
>by your static evaluation there? I say you are wasting a bunch of time. And
>I don't think Ed uses his static eval as you suggest, although I could be wrong.
>
>I would _much_ prefer my simpler captures-first approach when I come back here,
>as that is much less expensive to compute than the static eval. And in most
>cases it would be more accurate, since most moves are refuted directly by a
>simple capture...
Would the substitution of
roughvalue = StaticEvaluate(-whatever,etc);
with
roughvalue = Quiesce(-whatever, etc);
appease?
Dave
This page took 0.01 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.