Author: Ed Schröder
Date: 22:43:12 09/10/99
Go up one level in this thread
On September 11, 1999 at 00:44:19, Robert Hyatt wrote:
>On September 10, 1999 at 22:50:17, Dave Gomboc wrote:
>
>>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
>
>
>No. And here's why (this is the same reason that Chris's original idea
>is very ineffecient.)
>
>We are searching moves one by one. And each returns a score <=alpha,so we
>can't use that to reasonably pick the one that is best. So we either use
>the static eval (Chris) or else call Quiesce() (your idea) for each move to
>get some sort of score.
>
>OK, we have invested a _lot_ of cpu time to do either of those. And the
>probability that we will search this position again and use this suggested
>best move is only 1 in 10 during the middlegame (about 10% hash hits is what
>I normally see, roughly, in the middlegame).
>
>So we invest all that computer time to store a hash move that isn't used 90%
>of the time, anyway.
>
>Why not wait until we reach a position where the hash table has no suggested
>best move, and _then_ generate all the moves, and for each one either call
>Evaluate() (Chris) or Quiesce() (you) and _now_ order the moves based on this.
>Same amount of work. But only done 1/10th of the time.
>
>In chess, the credo is "never do today what you can put off until tomorrow,
>because tomorrow may _never_ come..."
>
>That was why I said the original "rough_best" idea from Chris was NFG,
>because there is another way to do the same thing and I'd hope that everyone
>agrees that using either eval or quiesce to order moves as I suggested would
>_really_ slow the program down... Far more than just forgetting the hash move
>and dropping into the best-capture-first move ordering.
>
>Was that understandable or too rambling? It is almost 12am here so it could
>be incomprehensible for all I know. :)
Do not underestimate the idea that in case there is no bestmove from the
hash table you do a full static evaluation of all nodes first and based
on that you pick the bestmove as being the first move you are going to
search for this (new) depth. The very early Rebel's (1981) worked that
way and I remember (although the system is very time consuming) it was
superior to all other systems I tried.
I later removed the system because hash tables + bestmove was more powerful
at least for Rebel. But I wouldn't exclude the possibility such a system
can have a positive effect on the speed of the search.
Actually I didn't remove the system but I replaced it with a faster one
that is:
- generate all legal moves;
- for all moves do a (very) quick evaluation;
- sort all moves based on the quick evaluation.
This (move ordering) system (for Rebel) is still superior.
Ed
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.