That's the point. This works automatically. When you pull a score out of the hash table and it is a mate score, you just add or subtract the current ply from it depending on whether it is negative or positive. And you are done. When you store a score in the hash table, and you notice it is mate, you do the opposite and subtract or add ply. That makes all hash scores and bounds relative to the position/depth they represent.Karlo Bala wrote:Yes, that is perfectly OK in plain AB, but I'm curios how it interacts with HT?Chan Rasjid wrote:The following is simple reading and does not need much thinking.
An idea is easy after we have the understanding and difficult when we do not yet grasp it in proper perspective. I wish to add another easy approach to understand Muller's pseudo codes that involve shifting mate scores, alpha, beta by +1 / 1 and also some other things.
Alphabeta search() uses a range of integers (infi, +inf) to represent something call "scores". Scores have a nonmate range where :
100 = 1 pawn advantage,
300 = a bishop disadvantage, ....
and they represent likelihood of winning or losing the game. search() is recursive and passes a score on return and on calling search(), it passes up two score arguments in alpha, beta which are score bounds. Passing nonmate scores around in search() present no inherent problem as they may be interpreted consistently relative to any nodes in the chess tree. But this is true only generally.
Say we made a great discovery about evaluation in chess programming. It involves using a huge 8MB tables that is used to scale the value of pieces. And it need to scale in strange manners. Besides other conditions, a queen = 900 at root and scales to 1800 at ply 127. Rook scales downwards, worth 500 at ply 127 and worth 350 at root. Bishops... Knights...etc.
We call score= eval(ply) and then we got stuck. This number can neither be passed downwards nor upwards in the usual manner. If alpha = 125 is passed up as argument and it travels 20 plies up, then when interpreted, the number 125 has another meaning. Numbers don't get passed around together with consistent meaning. We may need to do score mappings ,and maybe inverse mappings, to get our great idea to work with alphabeta.
Getting back to mate scores. In the consistent score method(10000  D), x =infi + 50 represent a checkmate node at ply 50 relative to root. If x is passed around by search(), it is ok as it can be interpreted consistently at every node of the chess tree. In the inconsistent score method, infi = checkmate, mate in 1/2/3/4... is inf+1,inf+2,inf+3,inf+4, but relative to a node. If search() at ply = 7 somehow got hold of a number x =infi + 50 and passed x upwards, and if it propagates 25 plies up and got interpreted as mateinfifty relative to that node, the meaning is wrong by 25 mates. This explains why in Muller's pseudo codes, there is a need to adjust scores with x = x+1 and x = x1
Best Regards,
Rasjid
Not just how to put score int HT but also how to retrieve?
Hashing and mate scores
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Re: Hashing and mate scores
Re: Hashing and mate scores
That's an easy one. First, it is an EGTB mate. The reason for the problem is that sometimes shorter mates have fewer forcingtype moves. One example is a pure king + pawn vs king. No checks until after the queen promotes. that means that you might find a deeper mate with more checking moves, and as the search goes deeper ply by ply you become able to find shorter mates with fewer checks overall.Karlo Bala wrote:Yes, that was one of my points.BTW the output you posted certainly suggests serious bugs in the hashing he is using. You should never see M5, M3, M4, M5 type results. That is broken and can lead to draws.
But it seems that old crafty have some problems also. First it found +mate 24, than +mate 29, than +mate 26
My program had similar problems when using aspiration windows, but you probably know better why it is.
Code: Select all
FEN: 8/8/8/8/3k4/8/8/4K2R w   0 1 Crafty_1919: 8 00:00 125.029 1.136.627 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 9 00:00 133.183 887.886 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Rg8 9 00:00 252.341 1.009.364 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Rg8 10 00:00 262.385 1.009.173 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Rg8 Ka1 10 00:00 516.534 1.033.068 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Rg8 Ka1 11 00:00 531.918 1.042.976 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Kd2 Kb1 6. Kc3 11 00:01 977.753 1.086.392 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Kd2 Kb1 6. Kc3 12 00:01 1.035.219 1.089.704 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Kd2 Kb1 6. Kc3 Ka2 12 00:01 1.684.849 1.059.653 +6.21 1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Kd2 Kb1 6. Kc3 Ka2 13 00:01 1.769.949 1.047.307 +6.21 1. Rh8 Kc3 2. Rg8 Kb3 3. Rg4 Kc3 4. Ke2 Kc2 5. Kf3 Kc1 6. Ra4 Kc2 7. Ke3 13 00:02 2.568.902 954.982 +6.21 1. Rh8 Kc3 2. Rg8 Kb3 3. Rg4 Kc3 4. Ke2 Kc2 5. Kf3 Kc1 6. Ra4 Kc2 7. Ke3 14 00:03 2.674.075 958.449 +6.21 1. Rh8 Kc3 2. Rg8 Kd3 3. Rf8 Kc4 4. Kd2 Kb4 5. Rf5 Kc4 6. Ke3 Kb3 7. Kd3 Ka2 14 00:04 4.764.055 954.720 +6.21 1. Rh8 Kc3 2. Rg8 Kd3 3. Rf8 Kc4 4. Kd2 Kb4 5. Rf5 Kc4 6. Ke3 Kb3 7. Kd3 Ka2 15 00:05 5.383.331 980.570 +6.21 1. Rh8 Kc4 2. Rg8 Kd4 3. Rf8 Kc4 4. Kd2 <HT> 15 00:07 7.822.778 1.009.390 +6.61 1. Rh5!! 15 00:08 8.360.881 1.014.670 +6.21 1. Rh5 Ke3 2. Rh4 Kf3 3. Kd2 Kg3 4. Rb4 Kh2 5. Ke3 Kg3 6. Rb8 Kh2 7. Kf3 Kg1 8. Rb4 15 00:08 8.841.488 1.011.611 +6.21 1. Rh5 Ke3 2. Rh4 Kf3 3. Kd2 Kg3 4. Rb4 Kh2 5. Ke3 Kg3 6. Rb8 Kh2 7. Kf3 Kg1 8. Rb4 16 00:08 8.874.108 1.015.344 +6.61 1. Rh5!! 16 00:09 9.426.450 1.019.075 +6.21 1. Rh5 Ke3 2. Rh4 Kf3 3. Kd2 Kg3 4. Rb4 Kh2 5. Ke3 Kg3 6. Rb8 Kg2 7. Rf8 Kg1 8. Kd3 Kh1 16 00:17 17.738.093 1.028.295 +6.21 1. Rh5 Ke3 2. Rh4 Kf3 3. Kd2 Kg3 4. Rb4 Kh2 5. Ke3 Kg3 6. Rb8 Kg2 7. Rf8 Kg1 8. Kd3 Kh1 17 00:17 17.960.830 1.041.207 +6.61 1. Rh5!! 17 00:17 18.023.258 1.044.826 +7.61 1. Rh5!! 17 00:18 19.313.514 1.043.973 +9.61 1. Rh5!! 17 00:30 29.609.275 986.975 +6.21 1. Rh5 Ke3 2. Rh4 Kf3 3. Kd2 Kg3 4. Rb4 Kf3 5. Kd3 Kf2 6. Kc3 Kg2 7. Kd4 Kg1 8. Ke3 Kf1 9. Kd3 17 03:39 244.739.193 1.117.530 +6.21 1. Rh5 Ke3 2. Rh4 Kf3 3. Kd2 Kg3 4. Rb4 Kf3 5. Kd3 Kf2 6. Kc3 Kg2 7. Kd4 Kg1 8. Ke3 Kf1 9. Kd3 18 03:40 245.249.179 1.114.768 +6.61 1. Rh5!! 18 03:40 245.288.661 1.114.948 +7.61 1. Rh5!! 18 03:40 245.356.639 1.115.257 +9.61 1. Rh5!! 18 03:59 267.181.341 1.117.913 +M24 1. Rh5 Ke4 2. Kf2 Kf4 3. Rc5 Ke4 4. Kg3 Kd4 5. Rg5 Ke4 6. Rh5 <HT> 18 05:51 379.323.950 1.080.695 +M24 1. Rh5 Ke4 2. Kf2 Kf4 3. Rc5 Ke4 4. Kg3 Kd4 5. Rg5 Ke4 6. Rh5 <HT> 19 08:51 545.326.189 1.026.979 +M29 1. Rh5 Ke4 2. Kf2 Kf4 3. Rc5 Ke4 4. Rg5 Kf4 5. Rh5 Kg4 <HT> 19 18:15 950.415.453 867.959 +M29 1. Rh5 Ke4 2. Kf2 Kf4 3. Rc5 Ke4 4. Rg5 Kf4 5. Rh5 Kg4 <HT> 20 21:10 1.091.913.646 859.774 +M26 1. Rh5 Ke4 2. Kf2 Kf4 3. Ra5 Ke4 4. Kg3 Ke3 5. Re5+ Kd4 6. Kf4 Kd3 7. Kf3 <HT>
So on any single search, each depth might show up with a different best mate score, but each depth should never find a longer mate after that depth finds a shorter mate. And once you "get into playing the sequence" the mates will generally become shorter and shorter..

 Posts: 313
 Joined: Wed Mar 22, 2006 9:17 am
 Location: Novi Sad, Serbia
Re: Hashing and mate scores
OK that is standard approach. But how to retrieve in Muller version if you change alpha & beta before retrieving?bob wrote:That's the point. This works automatically. When you pull a score out of the hash table and it is a mate score, you just add or subtract the current ply from it depending on whether it is negative or positive. And you are done. When you store a score in the hash table, and you notice it is mate, you do the opposite and subtract or add ply. That makes all hash scores and bounds relative to the position/depth they represent.Karlo Bala wrote:Yes, that is perfectly OK in plain AB, but I'm curios how it interacts with HT?Chan Rasjid wrote:The following is simple reading and does not need much thinking.
An idea is easy after we have the understanding and difficult when we do not yet grasp it in proper perspective. I wish to add another easy approach to understand Muller's pseudo codes that involve shifting mate scores, alpha, beta by +1 / 1 and also some other things.
Alphabeta search() uses a range of integers (infi, +inf) to represent something call "scores". Scores have a nonmate range where :
100 = 1 pawn advantage,
300 = a bishop disadvantage, ....
and they represent likelihood of winning or losing the game. search() is recursive and passes a score on return and on calling search(), it passes up two score arguments in alpha, beta which are score bounds. Passing nonmate scores around in search() present no inherent problem as they may be interpreted consistently relative to any nodes in the chess tree. But this is true only generally.
Say we made a great discovery about evaluation in chess programming. It involves using a huge 8MB tables that is used to scale the value of pieces. And it need to scale in strange manners. Besides other conditions, a queen = 900 at root and scales to 1800 at ply 127. Rook scales downwards, worth 500 at ply 127 and worth 350 at root. Bishops... Knights...etc.
We call score= eval(ply) and then we got stuck. This number can neither be passed downwards nor upwards in the usual manner. If alpha = 125 is passed up as argument and it travels 20 plies up, then when interpreted, the number 125 has another meaning. Numbers don't get passed around together with consistent meaning. We may need to do score mappings ,and maybe inverse mappings, to get our great idea to work with alphabeta.
Getting back to mate scores. In the consistent score method(10000  D), x =infi + 50 represent a checkmate node at ply 50 relative to root. If x is passed around by search(), it is ok as it can be interpreted consistently at every node of the chess tree. In the inconsistent score method, infi = checkmate, mate in 1/2/3/4... is inf+1,inf+2,inf+3,inf+4, but relative to a node. If search() at ply = 7 somehow got hold of a number x =infi + 50 and passed x upwards, and if it propagates 25 plies up and got interpreted as mateinfifty relative to that node, the meaning is wrong by 25 mates. This explains why in Muller's pseudo codes, there is a need to adjust scores with x = x+1 and x = x1
Best Regards,
Rasjid
Not just how to put score int HT but also how to retrieve?
Is it enough to add or subtract ply from result?
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.
 xsadar
 Posts: 147
 Joined: Wed Jun 06, 2007 8:01 am
 Location: United States
 Full name: Mike Leany
 Contact:
Re: Hashing and mate scores
The only path information HGM stores in his hash is information about the best path from the current node to the leaf nodes. It has nothing to do with the path from the root to the current node. The current node has no information about it's parents or grandparents, etc except for the alpha and beta values they give it; so there's no way he could store pathdependent information if he wanted to. The standard method has more risk of this as the mate score that is passed back up the tree is relative to the root, but HGM's scores are always relative to the current node. HGM's method may have other difficulties, but storing pathdependent information is not one of them. In fact, half the point was to make it easier not to store pathdependent information in the hash.bob wrote:There are other reasons to do it "normally" One that comes to mind is that you will eventually think about various alternatives such as mtd(f). It would seem to me that mucking with the bounds is not going to work there when the original search from the root always starts with a nullwindow.
And as I mentioned, the basic idea of HGM's bounds mucking is to not deal with the mate depth in the hash table. But what he does violates one major principle of hashing, namely that you now have pathdependent information in the scores, without having pathdependent information in the hash signature. So you can get at hit at B, and extract a bound whose score does not fit into the current path since the position and the entry come from different depths. For mates, correcting the bounds works perfectly with the exception that it will overlook draws just as EGTB hits do. Because we can never be sure that when we take a mate score stored at some ply and use it at another position, that there is no repetition in the area of the path that is hidden... the area between where the entry was stored, and where it was probed. We simply ignore that case or hashing becomes ineffective.
I have not studied what he does very carefully because the approach I am using works and has worked for 30 year now. Dating back to chess 4.0 and beyond, not to mention Greenblatt's program of the 60's... So at least we know the idea is sound, and the methodology works. The only issue we deal with is the issue mentioned above, regarding the path. It seems to me that EVERY hash entry HGM stores has path information in it because of how the bounds get mucked, which would invite additional problems beyond the very minimalistic mate score problem we have today dealing with path. I'm not going to study what he does very much, because there is no return for the effort.
Re: Hashing and mate scores
I believe that in his method, you don't need to change the hash table scores/bounds at all, as he is continually changing the real bounds instead...Karlo Bala wrote:OK that is standard approach. But how to retrieve in Muller version if you change alpha & beta before retrieving?bob wrote:That's the point. This works automatically. When you pull a score out of the hash table and it is a mate score, you just add or subtract the current ply from it depending on whether it is negative or positive. And you are done. When you store a score in the hash table, and you notice it is mate, you do the opposite and subtract or add ply. That makes all hash scores and bounds relative to the position/depth they represent.Karlo Bala wrote:Yes, that is perfectly OK in plain AB, but I'm curios how it interacts with HT?Chan Rasjid wrote:The following is simple reading and does not need much thinking.
An idea is easy after we have the understanding and difficult when we do not yet grasp it in proper perspective. I wish to add another easy approach to understand Muller's pseudo codes that involve shifting mate scores, alpha, beta by +1 / 1 and also some other things.
Alphabeta search() uses a range of integers (infi, +inf) to represent something call "scores". Scores have a nonmate range where :
100 = 1 pawn advantage,
300 = a bishop disadvantage, ....
and they represent likelihood of winning or losing the game. search() is recursive and passes a score on return and on calling search(), it passes up two score arguments in alpha, beta which are score bounds. Passing nonmate scores around in search() present no inherent problem as they may be interpreted consistently relative to any nodes in the chess tree. But this is true only generally.
Say we made a great discovery about evaluation in chess programming. It involves using a huge 8MB tables that is used to scale the value of pieces. And it need to scale in strange manners. Besides other conditions, a queen = 900 at root and scales to 1800 at ply 127. Rook scales downwards, worth 500 at ply 127 and worth 350 at root. Bishops... Knights...etc.
We call score= eval(ply) and then we got stuck. This number can neither be passed downwards nor upwards in the usual manner. If alpha = 125 is passed up as argument and it travels 20 plies up, then when interpreted, the number 125 has another meaning. Numbers don't get passed around together with consistent meaning. We may need to do score mappings ,and maybe inverse mappings, to get our great idea to work with alphabeta.
Getting back to mate scores. In the consistent score method(10000  D), x =infi + 50 represent a checkmate node at ply 50 relative to root. If x is passed around by search(), it is ok as it can be interpreted consistently at every node of the chess tree. In the inconsistent score method, infi = checkmate, mate in 1/2/3/4... is inf+1,inf+2,inf+3,inf+4, but relative to a node. If search() at ply = 7 somehow got hold of a number x =infi + 50 and passed x upwards, and if it propagates 25 plies up and got interpreted as mateinfifty relative to that node, the meaning is wrong by 25 mates. This explains why in Muller's pseudo codes, there is a need to adjust scores with x = x+1 and x = x1
Best Regards,
Rasjid
Not just how to put score int HT but also how to retrieve?
Is it enough to add or subtract ply from result?

 Posts: 567
 Joined: Thu Mar 09, 2006 3:47 pm
 Location: Singapore
Re: Hashing and mate scores
K Bala wrote:
Muller's approach is scoreinconsistent and we have to do "mucking" when scores are passed around. But since such scores are already relative to nodes, they may be stored as_is without mucking and also be just retrieved as a score and simply used to update alpha if in need (alpha = SCORE_FROM_HASH).
Rasjid
Standard method is scoreconsistent and scores may be passed around freely. But hashing a node with a score must always ensure the score is "consistent to a node" which may not be "consistent" for passing around, thus "mucking" get pushed to hashing/probehash here.Yes, that is perfectly OK in plain AB, but I'm curios how it interacts with HT? Not just how to put score int HT but also how to retrieve?
Muller's approach is scoreinconsistent and we have to do "mucking" when scores are passed around. But since such scores are already relative to nodes, they may be stored as_is without mucking and also be just retrieved as a score and simply used to update alpha if in need (alpha = SCORE_FROM_HASH).
Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.
 hgm
 Posts: 24740
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: Hashing and mate scores
This being pointed out by Karlo, I started to doubt the usefulness of that line that forces uMax to stop deepening upon the first mate. It is a 21character line, after all, and mainly a relic from very old versions.hgm wrote:Yes, you are right. But that is not because of the mentioned mechanism (which I included mainly not for finding shortest path to mate, but make it more decisive in cashing gains before it lets them evaporate). Like Chan Rasjid I also stop deepening after the first mate score, by setting the iteration number to 98 (the highest allowed number, after which deepening stops):Karlo Bala wrote:I think that best way for testing hash tables is testing with KRK endgames.
Lot of engines can not find shortest mate in analyze mode.
It seems that uMax have problem to find shortest mate....which is uMax speak for:Code: Select all
C:if(m>IMm<I+M)d=98; /* mate is indep. of depth */
...Code: Select all
cutoff: if(BestScore > MATESCORES  BestScore < MATESCORES) IterDepth = 98;
So I decided to fully implement the boundsmucking scheme, adjusting both alpha and beta conditionally on entry to search (rather than unconditionally expanding the window to allow for worst case, which might be needlessly expensive). I would then rely on the mentioned automatic matedistance pruning for quickly performing mateinafew.
This turned out to be a bit tricky, as uMax calls unlimited sequences of null moves before checking for a beta cutoff by a INFINITY score, which would eventually drive up beta so high that King capture would no longer cause a beta cutoff (uMax does implement the Kcapture by giving it a high sore and relying on the normal cutoff test, rather than directly doing a return(+INF), to save some characters). Due to this both Kings could wander in check, and the resulting check extension on both white and black plies would cause an infinite regression, and finally stack overflow.
So I had to suppress a nullmove search if beta = INFINITY (and a fail high can thus be guaranteed beforehand). Finally all problems could be fixed with only using 1 more character compared to the previous version, in the following way:
Code: Select all
D(k,q,l,e,E,z,n) /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,E,z,n; /* (q,l)=window, e=current eval. score, E=e.p. sqr.*/
{ /* e=score, z=prev.dest; J,Z=hashkeys; return score*/
int j,r,m,v,d,h,i,F,G,P,V,f=J,g=Z,C,s;
char t,p,u,x,y,X,Y,H,B;
struct _*a=A+(J+k*E&U1); /* lookup pos. in hash table*/
q=q<e;l=l<=e; /* adj. window: delay bonus */
...
P=d>2&&l+I?D(24k,l,1l,e,S,S,d3):I; /* search null move */
...
if(i<0)m=I,d=98; /* K capture */
if(m>=l&d>1)goto C; /* abort on fail high */
...
return m+=m<e; /* delayedloss bonus */
}
Code: Select all
Search(Color, Alpha, Beta, Eval, epSqr, z, Depth)
{
...
Alpha = (Alpha<Eval);
Beta = (Beta<=Eval); /* adj. window: delay bonus */
...
OpponentScore = IIDDepth > QS && Beta != INF /* suppress NM search if Beta=INF */
? Search(OpponentColor, Beta, 1Beta, Eval, S, S, IIDDepth3)
: INF;
...
// Generate next move
if(Victim==KING) BestScore=INF, IIDDepth=98; /* K capture */
if(BestScore>=Beta & IIDDepth >= QS)goto Cutoff; /* abort on fail high */
// Search next move
...
return BestScore + (BestScore < Eval); /* delayedloss bonus */
}
From matein5 on this tree is so small that the deepening reaches the preset ID maximum of 28 ply before the nominal thinking time of 10 sec/move is up, and from that moment on the search speeds up. The matein5 move is played in 4.1 sec, the matein4 in 0.26 sec, matein3 in 0.08 sec, and then unmeasurably fast. The mate distance kept decreasing regularly from matein10 on.
I posted the cleanedup version (microMax 4.8m) on my website, in stead of the old one. I also fixed the edit command, which did allow setting up a board position, but forgot to set the differential material evaluation and gamestage indicator based on this. So even in KRK it might have been going for a draw because it thought it was equal, and refuse to move its King because he thought it was middle game... I don't expect the playing strength to be affected in nonsetup position.
Re: Hashing and mate scores
As a note, the line count for crafty is:
search.c : 663
quiesce.c: 170
significant difference.
search.c : 663
quiesce.c: 170
significant difference.