Author: Robert Hyatt
Date: 09:11:57 06/18/02
Go up one level in this thread
On June 18, 2002 at 06:00:59, Sune Fischer wrote:
>On June 17, 2002 at 19:13:22, Robert Hyatt wrote:
>
>>On June 17, 2002 at 18:04:38, Uri Blass wrote:
>>
>>>On June 17, 2002 at 11:30:28, Robert Hyatt wrote:
>>>
>>>>>
>>>>>It is also obvious that if I do not clear the hash tables after every move
>>>>>replace only when you have bigger depth is a mistake because you are going to be
>>>>>left with old nodes that are not important and my first implementation of hash
>>>>>tables was without clearing the hash tables.
>>>>
>>>>
>>>>This can be fixed with an "age" field. first, use depth-preferred only if
>>>>the position is from the current search, otherwise keep it but overwrite it
>>>>whenever you want to store, regardless of the age. I do this in Crafty and
>>>>it works well.
>>>>
>>>>I also use two tables in crafty, one is "depth-preferred" as you explain,
>>>>the other is "always store". I _always_ store a hash entry in one or the
>>>>other, most often the latter.
>>>>
>>>>
>>>>
>>>>
>>>>>
>>>>>I remember that I did not find clear advantage for replace only when the depth
>>>>>is bigger but it may be also a result of other problems.
>>>>>
>>>>>I decided to record moves in the hash tables only when the score is bigger than
>>>>>beta because my tests showed that it is better than other options that I tried
>>>>>inspite of knowing that in theory it should not be the case.
>>>>
>>>>You should store a best move when score > alpha. If score == alpha, you
>>>>won't have a best move, but in all other cases you will.
>>>>
>>>>
>>>>>
>>>>>Inspite of all the problems and the fact that hash tables are used only for
>>>>>better order of moves test suites proved that hash tables made movei clearly
>>>>>faster(about 1.5 times faster relative to movei without hash tables).
>>>>
>>>>That is normal for middlegame positions. You don't get many "EXACT" type
>>>>hash hits. But try fine # 70 and this will change.
>>>
>>>Movei does not use hash tables to prune the tree but only for better order of
>>>moves so I am not surprised if it's search is not good in endgame positions.
>>>
>>>Note that Junior4.6 had also serious problems in simple endgames and I suspect
>>>that it did not use hash tables to prune the tree at that time but I do not know
>>>because I did not ask Amir.
>>>
>>>Note that it is not trivial for me to decide to use the hash tables to prune the
>>>tree.
>>>
>>>One reason is that my search rules are not trivial and I use the values of alpha
>>>and beta for it's extensions and pruning rules in some cases so it does not seem
>>>safe for me to prune a line only because I have a score at the same depth for
>>>that line.
>>>
>>>Another reason is that I have not one variable to define the real remaining
>>>depth.
>>>I have one integer that gives me the remaining depth in plies and another
>>>integer that gives partial extensions.
>>>
>>>I may consider using the hash tables to prune the tree only when the depth is
>>>clearly bigger and not equal to the depth in the hash tables but before doing it
>>>I think that it is better to improve the use of hash tables for order of moves.
>>>
>>>I have some well defined problems to solve that may give me hints about it.
>>>There was a game when Movei lost against gnuchess when the last move of movei
>>>showed that movei let the opponent to do a mate in 1 when the score was only
>>>longer mate.
>>>
>>>Movei saw the mate in 1 at depth 2 and changed it's mind but later it changed
>>>it's mind again after it saw that other moves are also losing and forgot about
>>>the mate (it has -20 or -30 score at depth 4 and later discovered a longer mate
>>>at depth 5).
>>>
>>>It means that there is some problems in the way that
>>>it is using the hash tables because it should not forget mate in 1.
>>>
>>>I guess that not seeing the mate in 1 may be because of some pruning that is
>>>dependent on alpha and beta and I will try to find the problems tomorrrow.
>>>
>>>Uri
>>
>>
>>If you store a mate score in the hash table (I do) then you must adjust it
>>to be "mate in N from the current ply" not "mate in N from the root". If you
>>fix that right, mates work just fine...
>
>Glad you brought it up, I have a bug with these hashed matescores.
>
>If I setup a testposition for eg. mate in 5 it solves it correctly and I play
>out the moves and it says mate in 4, mate in 3 etc. as it should.
>
>But if I play a game it will suddenly announce mate in 1, then mate in 4, then
>mate in 2, then in 5 etc. completely messed up.
>
>So exactly what do you mean by "ply" and "root" here?
>By "root" do you refer to the original start position of the game, or the root
>position of the tree search?
>The "ply" counter in my program is the number of halfmoves from the original
>position, but I suspect it is not the same in Crafty.
>
>I've noticed you subtract 1:
>
> switch (type) {
> case EXACT:
> if (abs(val) > MATE-300) {
> if (val > 0) val-=(ply-1);
> else val+=(ply-1);
> }
> *alpha=val;
> return(EXACT);
>
>why is that?
>I've tried with and without the subtraction, still buggy.
I subtract 1 because of the way I score mates. The mate score MATE gets
set one ply beyond the move that actually delivers the mate. In Crafty, to
make interpretation simple, positive odd scores mean the computer is mating
the opponent. Negative even scores means the computer is getting mated by
the opponent.
No good reason for that other than that is how I did it in Cray Blitz and I
kept the idea. It would be just as easy to have some other way of counting
the mates, such as in 2-ply increments, so that mate in 1 is MATE-1, and mated
in 1 is -(MATE-1). It makes the adjustment in the hash code above a bit more
complicated since "ply" is no longer used as the adjustment, it would need to
be (ply+1)>>1, for example...
>
>-S.
OK... define "MATE" as 32768, for now.
If you find a move at the root that leads to a mate in 4, the score
will typically be 32768 - 8 since you find you are mated at ply=8 and
you return MATE-ply (I do, anyway). Therefore, the root score that
gets backed up will be 32760, and so far, all is well. That means that
the "mate score" that gets returned from ply = 8 has to be - ( MATE - PLY )
so that - is bad for the side on move at ply=8.
Note that you have 4 moves for the program in the path, the move at
ply=1, 3, 5 and 7. When you store a hash table entry at ply=7, you
should store MATE-1, since the move at ply 7 will result in a MATE at
ply=8. At ply 5, you should store MATE-3, at ply 3 you should store MATE-5
and if you want to store the entry at the root, it would be MATE-7.
All this means is that at any point in the path that terminates in a mate
score of any kind, you have to adjust the score so that it is a mate-in-N
from the current ply, not from the root. Because the root score is wrong
at the current ply, since we are _closer_ to the final mate than we were at
the root of the search.
If that isn't clear enough, ask again. You can find how I return a mate score
by looking at the bottom of search.c in Crafty (look for string MATE). You can
find how I adjust the mate score before I store it in the hash table by looking
at hash.c, module Store()...
Bob
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.