TalkChess.com

Posted: **Thu Oct 04, 2007 12:07 am**

Karlo Bala wrote:
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.

Alpha-beta search() uses a range of integers (-infi, +inf) to represent something call "scores". Scores have a non-mate 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 non-mate 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 alpha-beta.

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 mate-in-fifty 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 = x-1

Best Regards,
Rasjid
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?

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.

Posted: **Thu Oct 04, 2007 12:12 am**

Karlo Bala wrote:

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.

Yes, that was one of my points.
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&#58; 8/8/8/8/3k4/8/8/4K2R w - - 0 1 

Crafty_1919&#58;
   8	00&#58;00	     125.029	1.136.627	+6.21	1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2
   9	00&#58;00	     133.183	887.886	+6.21	1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Rg8
   9	00&#58;00	     252.341	1.009.364	+6.21	1. Rh8 Kc3 2. Rg8 Kb2 3. Rf8 Ka1 4. Rh8 Ka2 5. Rg8
  10	00&#58;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&#58;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&#58;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&#58;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&#58;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&#58;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&#58;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&#58;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&#58;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&#58;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&#58;05	   5.383.331	980.570	+6.21	1. Rh8 Kc4 2. Rg8 Kd4 3. Rf8 Kc4 4. Kd2 <HT>
  15	00&#58;07	   7.822.778	1.009.390	+6.61	1. Rh5!!
  15	00&#58;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&#58;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&#58;08	   8.874.108	1.015.344	+6.61	1. Rh5!!
  16	00&#58;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&#58;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&#58;17	  17.960.830	1.041.207	+6.61	1. Rh5!!
  17	00&#58;17	  18.023.258	1.044.826	+7.61	1. Rh5!!
  17	00&#58;18	  19.313.514	1.043.973	+9.61	1. Rh5!!
  17	00&#58;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&#58;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&#58;40	 245.249.179	1.114.768	+6.61	1. Rh5!!
  18	03&#58;40	 245.288.661	1.114.948	+7.61	1. Rh5!!
  18	03&#58;40	 245.356.639	1.115.257	+9.61	1. Rh5!!
  18	03&#58;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&#58;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&#58;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&#58;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&#58;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>

That's an easy one. First, it is an EGTB mate. The reason for the problem is that sometimes shorter mates have fewer forcing-type 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.

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..

Posted: **Thu Oct 04, 2007 12:31 am**

bob wrote:
Karlo Bala wrote:
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.

Alpha-beta search() uses a range of integers (-infi, +inf) to represent something call "scores". Scores have a non-mate 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 non-mate 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 alpha-beta.

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 mate-in-fifty 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 = x-1

Best Regards,
Rasjid
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?
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.

OK that is standard approach. But how to retrieve in Muller version if you change alpha & beta before retrieving?
Is it enough to add or subtract ply from result?

Posted: **Thu Oct 04, 2007 1:35 am**

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 null-window.

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 path-dependent information in the scores, without having path-dependent 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.

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 path-dependent 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 path-dependent information is not one of them. In fact, half the point was to make it easier not to store path-dependent information in the hash.

Posted: **Thu Oct 04, 2007 1:46 am**

Karlo Bala wrote:
bob wrote:
Karlo Bala wrote:
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.

Alpha-beta search() uses a range of integers (-infi, +inf) to represent something call "scores". Scores have a non-mate 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 non-mate 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 alpha-beta.

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 mate-in-fifty 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 = x-1

Best Regards,
Rasjid
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?
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.
OK that is standard approach. But how to retrieve in Muller version if you change alpha & beta before retrieving?
Is it enough to add or subtract ply from result?

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...

Posted: **Thu Oct 04, 2007 6:38 am**

K Bala wrote:-

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?

Standard method is score-consistent 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/probe-hash here.

Muller's approach is score-inconsistent 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

Posted: **Sat Oct 13, 2007 2:20 pm**

hgm wrote:
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....
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):
Code: Select all
C&#58;if&#40;m>I-M|m<-I+M&#41;d=98;                        /* mate is indep. of depth  */
which is uMax speak for:
Code: Select all
cutoff&#58;
    if&#40;BestScore > MATESCORES | BestScore < -MATESCORES&#41; IterDepth = 98;
...

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 21-character line, after all, and mainly a relic from very old versions.

So I decided to fully implement the bounds-mucking 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 mate-distance pruning for quickly performing mate-in-a-few.

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 K-capture 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 null-move 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&#40;k,q,l,e,E,z,n&#41;        /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,E,z,n;      /* &#40;q,l&#41;=window, e=current eval. score, E=e.p. sqr.*/
&#123;                       /* 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+&#40;J+k*E&U-1&#41;;                     /* lookup pos. in hash table*/

 q-=q<e;l-=l<=e;                                          /* adj. window&#58; delay bonus */
  ...
  P=d>2&&l+I?D&#40;24-k,-l,1-l,-e,S,S,d-3&#41;&#58;I;           /* search null move         */
      ...
      if&#40;i<0&#41;m=I,d=98;                         /* K capture                */
      if&#40;m>=l&d>1&#41;goto C;                      /* abort on fail high       */
 ...
 return m+=m<e;                                /* delayed-loss bonus       */
&#125;

which stands for

Code: Select all

Search&#40;Color, Alpha, Beta, Eval, epSqr, z, Depth&#41;
&#123;                       
 ...
 Alpha -= &#40;Alpha<Eval&#41;;
 Beta -= &#40;Beta<=Eval&#41;;                        /* adj. window&#58; delay bonus */
  ...
  OpponentScore = IIDDepth > QS && Beta != -INF /* suppress N-M search if Beta=-INF */
                   ? Search&#40;OpponentColor, -Beta, 1-Beta, -Eval, S, S, IIDDepth-3&#41; 
                   &#58; INF; 
      ...
      // Generate next move
      if&#40;Victim==KING&#41; BestScore=INF, IIDDepth=98;  /* K capture  */
      if&#40;BestScore>=Beta & IIDDepth >= QS&#41;goto Cutoff;  /* abort on fail high  */
      // Search next move
 ...
 return BestScore + &#40;BestScore < Eval&#41;; /* delayed-loss bonus       */
&#125;

With this code it now finds the shortest checkmate in KRK perfectly (once it is within the horizon, of course, which might not follow trivially from the reported search depth due to the LMR pruning). There is no mate-dependent limit imposed on the deepening, though. So even if a mate-in-6 is seen, and no branch can go beyond that level, the root simply keeps deepening past 11 ply. Initially this still causes an increase in the time per iteration, as all the reduced branches are now also pushed towards this 11-ply limit. (Which in uMax actually lies at 13 ply, as it searches to King capture, not mate). But eventually the tree fills up completely, and from than on all iterations walk the same fixed-depth tree.

From mate-in-5 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 mate-in-5 move is played in 4.1 sec, the mate-in-4 in 0.26 sec, mate-in-3 in 0.08 sec, and then unmeasurably fast.

The mate distance kept decreasing regularly from mate-in-10 on.

I posted the cleaned-up version (micro-Max 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 game-stage 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 non-setup position.

Posted: **Mon Oct 15, 2007 11:49 pm**

As a note, the line count for crafty is:

search.c : 663
quiesce.c: 170

significant difference.

TalkChess.com

Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores

Re: Hashing and mate scores