Hashing and mate scores

[hgm]

Is it the same as Muller's?

No, this is not the same. You apply inv-fn and fn after one another on (alpha,beta) before doing anything with it, which would be a no-op.

What I do is this:

Code: Select all

for relevant ranges of the integer domain:-
fn(x) = x +1;
inv-fn(x) = x -1;

int search(alpha, beta){
 alpha = inv-fn(alpha);
 beta = inv-fn(beta);

  for (moves){
   score = -search(-beta, -alpha);
   score = fn(score);
   //etc...
  }

  
  return whatever;
}

The change of axis you are talking about does indeed take place. But the deeper search _is_ informed about this. That is the entire point of applying inv-fn to alpha and beta: you translate them to the new axis.

The new axis is needed, because we are deeper in the tree. So mates-in-N that we find, are longer checkmates than mates-in-N that we found at a lower level.

The scores found in the new reference system are translated back to the previous reference system when passing them to the root. If we would do fail-hard, and the node above us returns alpha (the alpha with which it was called, as it is not aware of any other) to indicate a fail low, it actually returns inv-fn(alpha) as score. And applying fn(score) then transforms that back to the alpha in this node.

And Muller recommends this to a novice new to alpha-beta! Just propose the silly 10000 - D stuff which cannot have problems. Also is it certain those who use the ply-independent mate scoring do it correctly?

What makes you think this can have problems? I have been using this since 1980. I would think that it is a lot simpler for a novice to add 3 measly lines of code (simple conditional increments / decrements). Pseudo-code for the other system seems to involve much more.

[bob]

Pradu wrote:-

I think I understand HG's intent with the bounds updating now. It is not about mate-distance pruning (my mistake) but instead about adjusting the bounds to counter the effect of "mucking" the mate scores backwards: Say you are at the root and search one move and get back a score -(MATE-n). Then say you search the second move, but all replies to that move return (MATE+n+1). A score -(MATE-n) at ply 0 is not the same as -(MATE-n) at ply 2. Infact -(MATE-n) at ply 2 is better because it will get "mucked" back up to -(MATE-n-1). But if you don't do bounds updating the -(MATE-n) will fail low at ply 2 and fail high at ply 1 which you don't want it to do. So, you have to increase the bounds to counteract the effect of "mucking" and that's what that portion of code HG has written does.

Since you mentioned you now understand, then Muller is probably not practicing voodoo alpha-beta.
I cannot yet follow your argument as I am fasting, but I vaguely see something interesting.

Alpha-beta searches from a node and whenever a better score is found, we search subsequent moves by passing a bound (alpha, beta) with an updated alpha. Finally we finish and say "...we have found a best-score = alpha...". But this may be after few changes in the bounds passed backed up the tree. Now we do strange things, we create a function fn(integer) and passed up (fn(alpha), beta) instead of (alpha, beta) and if we don't inform the nodes up the tree about it that "there is a change of axis", we don't know if when they work and pass you back information, they compare numbers from a space that includes all numbers they had used previously without adjusting for a "change of axis"... I think this is what Muller mention about the need to know of an inv-fn() = inverse of fn() and for it to be applied to alpha when necessary. My model from instinct :-

Code: Select all

for relevant ranges of the integer domain:-
fn(x) = x +1;
inv-fn(x) = x -1;

int search(alpha, beta){
 alpha = inv-fn(alpha);
 beta = inv-fn(beta);

  for (moves){
   alpha = fn(alpha);
   beta = fn(beta);
   score = -search(-beta, -alpha);
   //etc...
  }
  
  return whatever;
}

Is it the same as Muller's?

And Muller recommends this to a novice new to alpha-beta! Just propose the silly 10000 - D stuff which cannot have problems. Also is it certain those who use the ply-independent mate scoring do it correctly?

Rasjid

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.

[bob]

Is it the same as Muller's?

No, this is not the same. You apply inv-fn and fn after one another on (alpha,beta) before doing anything with it, which would be a no-op.

What I do is this:

Code: Select all

for relevant ranges of the integer domain:-
fn(x) = x +1;
inv-fn(x) = x -1;

int search(alpha, beta){
 alpha = inv-fn(alpha);
 beta = inv-fn(beta);

  for (moves){
   score = -search(-beta, -alpha);
   score = fn(score);
   //etc...
  }

  
  return whatever;
}

The change of axis you are talking about does indeed take place. But the deeper search _is_ informed about this. That is the entire point of applying inv-fn to alpha and beta: you translate them to the new axis.

The new axis is needed, because we are deeper in the tree. So mates-in-N that we find, are longer checkmates than mates-in-N that we found at a lower level.

The scores found in the new reference system are translated back to the previous reference system when passing them to the root. If we would do fail-hard, and the node above us returns alpha (the alpha with which it was called, as it is not aware of any other) to indicate a fail low, it actually returns inv-fn(alpha) as score. And applying fn(score) then transforms that back to the alpha in this node.

And Muller recommends this to a novice new to alpha-beta! Just propose the silly 10000 - D stuff which cannot have problems. Also is it certain those who use the ply-independent mate scoring do it correctly?

What makes you think this can have problems? I have been using this since 1980. I would think that it is a lot simpler for a novice to add 3 measly lines of code (simple conditional increments / decrements). Pseudo-code for the other system seems to involve much more.

The "normal system" involves exactly this, in exactly one place, in the hash probe code:

if (val > MATE - 300)
val -= ply - 1;
else if (val < -MATE + 300)
val += ply - 1;

Quite simply: If the value from the hash table is a mate in N, I correct for the current depth to make it a deeper mate in N+ply. If the value is a "mated in N", I correct it to a mated in N + ply, a deeper loss.

that's it. Only done in hash probe code, only done on MATE scores or bounds retrieved during the search.

It doesn't make the tree dump hard to follow when the bounds are never the same from one ply to the next, it doesn't add in a "impatient bonus" to do things quicker (whatever those things might be). And most importantly it doesn't include any sort of path-dependent information that violates the integrity of the hash scores themselves since the signatures have no path dependent information in them, except specifically for the mate score problem I have previously explained, which can't be solved without wrecking hash table utility.

So how is that so hard to implement? The cost is certainly lower than mucking around with alpha/beta everywhere. First most positions are not hash hits unless we are in a simple endgame. Second, most positions are not mates so the two conditional jumps are almost perfectly predicted. And finally debugging traces are very easy to read. And I don't give my program any impetus to hurry up and do something (make a capture) and give up some small positional advantage by hurrying the process...

[bob]

My first minor question is:-
for first call to search() from root with Alpha = -infi, the line
if(Alpha <= -MATESCORES) Alpha = Alpha - 1;
would be satisfied and Alpha = -INFINITY - 1 ???
I'll see if it's OK.

Yes, that doesn't hurt. It just makes the search window a bit larger, but there will never be any score that falls in the expanded range.

So we now have yet another definition of "infinity" to work with as well? Now there is actually a number smaller than -infinity, or larger than +infinity?

I chose those values to determine how many bits I need in a hash entry. For example 32727 to -32767 which means the thing fits in a 16 bit value. going to 32768 would have dire consequences for my hash entries. Either it would overflow into an adjacent field, or it would get truncated to zero, neither of which would be good.

[Chan Rasjid]

Hello Dr Hyatt,

I think I started this thread correctly and have learn something fairly interesting - about the co-ordinate transformation and the need to apply an inverse.

Now I have some idea after inputs from Muller and Pradu. Mucking(what does it mean ?) around with alpha, beta is indeed tricky as Pradu too need to think twice. I would not have got to this point with the idea of a change-of-axis (more correctly transformation of co-ordinates and inverse) if not that Pradu confirmed Muller was right; we understand better when not affected by doubts. I did not pay much attention earlier to what Muller wrote about ... bounds at this depth... higher depth... etc.. and how things got back-up.

I was about to mention that the method with x = x + 1, x = x - 1 is actually much better in my implementation. With infi-ply, I have to do ply adjustments at quite many places and bug prone too. Applying fn() and inverse() is only at 2 easily determinable points in search() and very clean.

About other possible hazards like path-dependencies etc, I will consider later.Still, I learn something here.

Best Regards,
Rasjid

[hgm]

So we now have yet another definition of "infinity" to work with as well? Now there is actually a number smaller than -infinity, or larger than +infinity?

I don't know about your computers, but on mine there is no representationof infinity in integers. So tin pseudo-code INFINITY just means a large defined constant. Many people use 10,000, some use 2^16-1. Unless they are doing their arithmetic in the score updating in 16-bit short ints (very slow, btw), they should never experience overflow problems. The -INIFINITY-1 only shows up in the local variable (function argument) Alpha, never in the hash. (Remember, this was fail soft.)

In addition, if you can represent +INFINITY in an int, it is always possible to represent =INFINITY-1 in an int of the same size, as most CPUs use 2-complement encoding nowadays. So nothing to worry about, not even on a 16-bit machine. -32678 is quite OK.

[Karlo Bala]

Pradu wrote:-

I think I understand HG's intent with the bounds updating now. It is not about mate-distance pruning (my mistake) but instead about adjusting the bounds to counter the effect of "mucking" the mate scores backwards: Say you are at the root and search one move and get back a score -(MATE-n). Then say you search the second move, but all replies to that move return (MATE+n+1). A score -(MATE-n) at ply 0 is not the same as -(MATE-n) at ply 2. Infact -(MATE-n) at ply 2 is better because it will get "mucked" back up to -(MATE-n-1). But if you don't do bounds updating the -(MATE-n) will fail low at ply 2 and fail high at ply 1 which you don't want it to do. So, you have to increase the bounds to counteract the effect of "mucking" and that's what that portion of code HG has written does.

Since you mentioned you now understand, then Muller is probably not practicing voodoo alpha-beta.
I cannot yet follow your argument as I am fasting, but I vaguely see something interesting.

Alpha-beta searches from a node and whenever a better score is found, we search subsequent moves by passing a bound (alpha, beta) with an updated alpha. Finally we finish and say "...we have found a best-score = alpha...". But this may be after few changes in the bounds passed backed up the tree. Now we do strange things, we create a function fn(integer) and passed up (fn(alpha), beta) instead of (alpha, beta) and if we don't inform the nodes up the tree about it that "there is a change of axis", we don't know if when they work and pass you back information, they compare numbers from a space that includes all numbers they had used previously without adjusting for a "change of axis"... I think this is what Muller mention about the need to know of an inv-fn() = inverse of fn() and for it to be applied to alpha when necessary. My model from instinct :-

Code: Select all

for relevant ranges of the integer domain:-
fn(x) = x +1;
inv-fn(x) = x -1;

int search(alpha, beta){
 alpha = inv-fn(alpha);
 beta = inv-fn(beta);

  for (moves){
   alpha = fn(alpha);
   beta = fn(beta);
   score = -search(-beta, -alpha);
   //etc...
  }
  
  return whatever;
}

Is it the same as Muller's?

And Muller recommends this to a novice new to alpha-beta! Just propose the silly 10000 - D stuff which cannot have problems. Also is it certain those who use the ply-independent mate scoring do it correctly?

Rasjid

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.

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

Code: Select all

[Event "Computer chess game"]
[Site "KBALA"]
[Date "2007.10.03"]
[Round "?"]
[White "Umax4_8w"]
[Black "Fruit-2-3-1"]
[Result "*"]
[Time "18:45:37"]
[TimeControl "120+6"]
[SetUp "1"]
[FEN "8/8/8/8/8/3k4/8/3K3R w - - 0 1"]
[Termination "unterminated"]
[PlyCount "30"]
[WhiteType "program"]
[BlackType "program"]

1. Rh4 {(h1h4) +M8/96 4} Ke3 {(Kd3e3 Kd1c2 Ke3f3 Kc2d3 Kf3g3 Rh4a4 Kg3f3
Kd3d2 Kf3f2 Ra4a3 Kf2f1 Kd2e3 Kf1g2 Ke3e2 Kg2g1 Ke2f3 Kg1h2 Kf3f2 Kh2h1
Ra3h3+) -M10/26 6} 2. Kc2 {(d1c2) +M8/96 0} Kf3 {(Ke3f3 Rh4d4 Kf3e3 Kc2c3
Ke3e2 Rd4d3 Ke2f1 Rd3e3 Kf1f2 Kc3d3 Kf2f1 Re3e2 Kf1g1) -6.03/13 11} 3. Kd2
{(c2d2) +M6/96 0} Kg3 {(Kf3g3 Rh4b4 Kg3f3 Kd2d3 Kf3f2 Rb4h4 Kf2f3 Rh4e4
Kf3f2 Re4e3 Kf2f1 Re3e2 Kf1g1) -6.03/13 11} 4. Rb4 {(h4b4) +M5/96 0} Kf3
{(Kg3f3 Rb4a4 Kf3f2 Ra4a3 Kf2f1 Kd2e3 Kf1g2 Ke3e2 Kg2g1 Ke2f3 Kg1h2 Kf3f2
Kh2h1 Ra3h3+) -M7/27 5} 5. Ra4 {(b4a4) +M5/96 0} Kg2 {(Kf3g2 Kd2e2 Kg2g3
Ra4b4 Kg3g2 Rb4b3 Kg2h1 Ke2f2 Kh1h2 Rb3e3 Kh2h1 Re3h3+) -M6/53 5} 6. Ke2
{(d2e2) +M3/96 0} Kg3 {(Kg2g3 Ra4b4 Kg3g2 Rb4b3 Kg2h1 Ke2f2 Kh1h2 Rb3e3
Kh2h1 Re3h3+) -M5/53 6} 7. Kd2 {(e2d2) +M5/96 0} Kg2 {(Kg3g2) 0.00/63 0} 8.
Ke3 {(d2e3) +M5/96 0} Kg3 {(Kg2g3 Ke3e2 Kg3g2 Ra4a3 Kg2g1 Ke2f3 Kg1h2 Kf3f2
Kh2h1 Ra3h3+) -M5/53 7} 9. Ke2 {(e3e2) +M4/96 0} Kg2 {(Kg3g2 Ra4a3 Kg2g1
Ke2f3 Kg1h2 Kf3f2 Kh2h1 Ra3h3+) -M4/51 7} 10. Rd4 {(a4d4) +M3/96 0} Kg3
{(Kg2g3 Rd4c4 Kg3g2 Rc4c3 Kg2g1 Ke2f3 Kg1h2 Kf3f2 Kh2h1 Rc3h3+) -M5/53 7}
11. Rc4 {(d4c4) +M3/96 0} Kg2 {(Kg3g2 Rc4c3 Kg2g1 Ke2f3 Kg1h2 Kf3f2 Kh2h1
Rc3h3+) -M4/50 5} 12. Rb4 {(c4b4) +M5/96 0} Kg3 {(Kg2g3 Rb4d4 Kg3g2 Rd4d3
Kg2g1 Ke2f3 Kg1h2 Kf3f2 Kh2h1 Rd3h3+) -M5/52 5} 13. Re4 {(b4e4) +M4/96 0}
Kg2 {(Kg3g2 Re4e3 Kg2g1 Ke2f3 Kg1f1 Kf3g3 Kf1g1 Re3e1+) -M4/50 5} 14. Rf4
{(e4f4) +M3/96 0} Kg3 {(Kg2g3 Rf4d4 Kg3g2 Rd4d3 Kg2g1 Ke2f3 Kg1h2 Kf3f2
Kh2h1 Rd3h3+) -M5/52 5} 15. Ke3 {(e2e3) +M4/96 0} Kg2 {(Kg3g2 Rf4g4+ Kg2h3
Ke3f3 Kh3h2 Rg4h4+ Kh2g1 Rh4h7 Kg1f1 Rh7h1+) -M5/47 3} *

Crafty found way to give mate but had big fluctuation in eval while searching.
(you can not see it from pgn...)

Code: Select all

[Event "Computer chess game"]
[Site "KBALA"]
[Date "2007.10.03"]
[Round "?"]
[White "Crafty_1919"]
[Black "Fruit-2-3-1"]
[Result "1-0"]
[Time "18:45:37"]
[WhiteElo "2200"]
[TimeControl "120+6"]
[SetUp "1"]
[FEN "8/8/8/8/8/3k4/8/3K3R w - - 0 1"]
[Termination "normal"]
[PlyCount "39"]
[WhiteType "program"]
[BlackType "program"]

1. Rh8 {(1. Rh8 Kc4 2. Rg8 Kb4 3. Kc2 Kc4 4. Rg4+ Kb5 5. Kc3 Ka5 6. Rg5+
Ka6 7. Kd3 Kb6 8. Ke3 Ka7 9. Kd2 Kb7) +6.21/16 8} Ke4 {(Kd3e4 Rh8h5 Ke4e3
Rh5b5 Ke3f3 Rb5a5 Kf3f2 Kd1d2 Kf2f3 Ra5a4 Kf3f2 Ra4f4+ Kf2g3) -5.59/11 10}
2. Rg8 {(2. Rg8 Kd4 3. Ke2 Kc5 4. Kd2 Kb6 5. Ke3 Kc6 6. Rg4 Kb6 7. Kd3 Kc6
8. Ke4 Kb5 9. Kd5 Ka5) +6.21/16 8} Kd4 {(Ke4d4 Kd1d2 Kd4e4 Rg8h8 Ke4d4
Rh8c8 Kd4e4 Rc8b8 Ke4f3 Rb8b4 Kf3g3) -5.59/10 16} 3. Rg5 {(3. Rg5 Kd3 4.
Rg4 Ke3 5. Rh4 Kd3 6. Ke1 Ke3 7. Rg4 Kf3 8. Rg8 Ke3 9. Rg6 Kd4 10. Rg5)
+6.21/15 7} Ke4 {(Kd4e4 Rg5a5 Ke4d4 Kd1d2 Kd4c4 Kd2e3 Kc4b4 Ra5d5 Kb4c4
Rd5g5 Kc4c3 Rg5g4 Kc3b3) -5.68/13 10} 4. Kc2 {(4. Kc2!!) +7.61/16 7} Kd4
{(Ke4d4 Kc2d2 Kd4c4 Kd2e3 Kc4c3 Rg5g4 Kc3c2 Rg4c4+ Kc2b3 Ke3d4 Kb3b2 Kd4d3
Kb2b3 Rc4f4 Kb3a3) -5.91/13 7} 5. Kb3 {(5. Kb3 Ke4 6. Kc4 Kf4 7. Rd5 Ke4 8.
Rd4+ Ke3 9. Rd3+ Ke4 10. Rd2 Kf4 11. Rc2 Ke4 12. Rc3 Ke5 13. Rd3) +6.21/15
7} Ke4 {(Kd4e4 Kb3c4 Ke4e3 Rg5c5 Ke3f4 Kc4d3 Kf4f3 Rc5c4 Kf3f2 Rc4f4+ Kf2g2
Kd3e2 Kg2g3 Ke2e3 Kg3g2 Rf4g4+ Kg2h3) -5.91/14 7} 6. Kc4 {(6. Kc4 Kf4 7.
Rh5 Ke3 8. Re5+ Kf2 9. Kd4 Kf3 10. Rf5+ Kg2 11. Ke4 Kg3 12. Rg5+ Kf2 13.
Kd4 Kf3 14. Kd3 Kf4) +6.21/15 10} Kf4 {(Ke4f4 Rg5h5 Kf4e3 Rh5h4 Ke3f3 Kc4d3
Kf3g3 Rh4d4 Kg3f3 Rd4e4 Kf3f2 Re4e3 Kf2g1 Kd3e2 Kg1g2 Re3d3 Kg2g1) -5.94/16
5} 7. Rh5 {(7. Rh5 Kg4 8. Re5 Kh4 9. Kd3 Kg3 10. Ke3 Kg4 11. Ke4 Kg3 12.
Rg5+ Kf2 13. Rg4 Ke1 14. Ke3) +6.21/14 8} Ke4 {(Kf4e4 Kc4c3 Ke4e3 Rh5a5
Ke3e4 Ra5c5 Ke4f4 Rc5b5 Kf4f3 Kc3d4 Kf3e2 Rb5b4 Ke2d2 Rb4b2+ Kd2d1 Rb2g2
Kd1e1) -5.94/15 6} 8. Kc3 {(8. Kc3 Kf4 9. Kd4 Kg4 10. Rc5 Kh4 11. Ra5 Kg3
12. Ke3 Kg4 13. Rd5 Kg3 14. Rh5 <HT>) +M14/13 6} Kf3 {(Ke4f3 Kc3d3 Kf3g4
Rh5c5 Kg4f3 Rc5a5 Kf3f4 Ra5b5 Kf4f3 Rb5c5 Kf3f4 Kd3d4 Kf4f3 Rc5f5+ Kf3e2
Rf5f7 Ke2d2 Rf7f2+ Kd2d1) -5.95/17 10} 9. Kd4 {(9. Kd4 Kg4 10. Rd5 Kf4 11.
Re5 Kf3 12. Rf5+ Ke2 13. Rf4 <HT>) +M13/14 6} Kf4 {(Kf3f4 Rh5d5 Kf4f3
Rd5f5+ Kf3g4 Kd4e4 Kg4g3 Rf5f4 Kg3g2 Ke4e3 Kg2g3 Rf4d4 Kg3g2 Rd4g4+ Kg2h3
Ke3f3 Kh3h2 Rg4h4+ Kh2g1 Rh4h5 Kg1f1 Rh5h1+) -M11/24 5} 10. Re5 {(10. Re5
Kf3 11. Rf5+ Kg4 12. Rd5 Kf4 13. Re5 <HT>) +M14/13 6} Kf3 {(Kf4f3 Re5a5
Kf3f4 Ra5a1 Kf4g4 Kd4e5 Kg4g5 Ra1g1+ Kg5h4 Ke5f5 Kh4h3 Kf5f4 Kh3h2)
-6.04/12 10} 11. Rf5 {(11. Rf5+ Kg4 12. Ke4 Kg3 13. Ke3 Kg4 14. Rc5 <HT>)
+M10/13 6} Kg4 {(Kf3g4 Kd4e4 Kg4g3 Rf5f1 Kg3g4 Rf1g1+ Kg4h4 Ke4f5 Kh4h3
Kf5f4 Kh3h2 Rg1g3 Kh2h1) -6.26/11 6} 12. Ke4 {(12. Ke4 Kg3 13. Ke3 Kg4 14.
Rc5 Kg3 15. Rg5+ Kh4 16. Kf4 Kh3 17. Kf3 <HT>) +M9/14 6} Kg3 {(Kg4g3 Rf5f3+
Kg3g4 Rf3f4+ Kg4g5 Ke4e5 Kg5g6 Rf4g4+ Kg6f7 Rg4g2 Kf7e7 Rg2g7+ Ke7f8 Rg7c7
Kf8e8) -6.25/10 5} 13. Ke3 {(13. Ke3 Kg4 14. Rc5 Kg3 15. Rg5+ Kh4 16. Kf4
Kh3 17. Kf3 Kh2 18. Rh5+ Kg1 19. Rh8 Kf1 20. Rh1#) +M8/14 6} Kg4 {(Kg3g4
Rf5b5 Kg4g3 Rb5b4 Kg3g2 Rb4g4+ Kg2h3 Ke3f3 Kh3h2 Rg4h4+ Kh2g1 Rh4h5 Kg1f1
Rh5h1+) -M7/43 5} 14. Rc5 {(14. Rc5 Kg3 15. Rg5+ Kh4 <HT>) +M7/13 0} Kg3
{(Kg4g3 Rc5c4 Kg3g2 Rc4g4+ Kg2h3 Ke3f3 Kh3h2 Rg4h4+ Kh2g1 Rh4h5 Kg1f1
Rh5h1+) -M6/51 6} 15. Rg5 Kh4 {(Kg3h4 Ke3f4 Kh4h3 Kf4f3 Kh3h2 Rg5h5+ Kh2g1
Rh5h4 Kg1f1 Rh4h1+) -M5/50 5} 16. Kf4 Kh3 {(Kh4h3 Kf4f3 Kh3h2 Rg5h5+ Kh2g1
Rh5h4 Kg1f1 Rh4h1+) -M4/4 0} 17. Kf3 Kh2 {(Kh3h2 Rg5h5+ Kh2g1 Rh5h4 Kg1f1
Rh4h1+) -M3/46 5} 18. Rh5 Kg1 {(Kh2g1 Rh5h4 Kg1f1 Rh4h1+) -M2/4 0} 19. Rh8
Kf1 {(Kg1f1 Rh8h1+) -M1/4 0} 20. Rh1 {Mate} 1-0

[bob]

So we now have yet another definition of "infinity" to work with as well? Now there is actually a number smaller than -infinity, or larger than +infinity?

I don't know about your computers, but on mine there is no representationof infinity in integers. So tin pseudo-code INFINITY just means a large defined constant. Many people use 10,000, some use 2^16-1. Unless they are doing their arithmetic in the score updating in 16-bit short ints (very slow, btw), they should never experience overflow problems. The -INIFINITY-1 only shows up in the local variable (function argument) Alpha, never in the hash. (Remember, this was fail soft.)

In addition, if you can represent +INFINITY in an int, it is always possible to represent =INFINITY-1 in an int of the same size, as most CPUs use 2-complement encoding nowadays. So nothing to worry about, not even on a 16-bit machine. -32678 is quite OK.

First, infinity means infinity, which is simply the largest number possible. In 16 bit ints, +infinity becomes 32767 because no numbers are larger.

But my point here is that the term itself, means a number such that there is no larger number as in infinity+1. If infinity+1 is possible, then "infinity" is being incorrectly used. In the case of a tree search +infinity (by definition in alpha/beta tree searching as defined by Newell, Shaw and Simon) is a value that bounds all possible scores, so that no score can ever be greater than or even equal to +infinity. And note that even equal to is critical else you would get fail highs you could not resolve.

I just want to use a term in its correct sense because if I were looking at something and saw a number represented to be larger than +infinity, I would have to scratch my head and wonder what on earth they are talking about.

BTW, in the alpha/beta framework, going from +32767 to -32768 by adding +1 is not "quite ok". It will totally screw up searches that use that way wrong bound.

[bob]

I don't care if a program can not find the shortest mate, when the actual mate itself is beyond the program's horizon. But once a program sees a mate in N score, it must continually reduce N by at least 1 for each move played. I've never seen Crafty violate this with one exception:

A mate is _very_ deep, and my opponent takes forever to find a move. Meanwhile given an obscene amount of time, Crafty finds a mate in N where almost every move is a non-check. My opponent makes an unexpected move that is even worse than what I was expecting, but crafty still can only find a mate in N+10 because that mate triggers extensions where the "quiet" mate does not. I can live with that. But I see programs announce mate in 2 when it is a mate in 3. Etc.

BTW a few years ago Amir Ban and I had a discussion about endgame tables and the KQ vs KR ending. He thought computers could solve that easily without EGTBs but I didn't. I tried it and lo and behold, Crafty could win it every last time, easily. Against tablebases it didn't always play the best move leading to the shortest mate, but it always played moves that led to a forced mate without violating the 50-move rule. And once it saw a forced mate, it behaved perfectly beyond that point.

I will try a few KR vs K endings with crafty (with EGTB) vs Crafty without, as that is easy to do. I'd expect the non-EGTB version to easily force mate every last time, although probably not optimally when compared to the EGTB moves. Crafty has special "mop-up" evaluation code to handle these pawnless cases.

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.

[Uri Blass]

I don't care if a program can not find the shortest mate, when the actual mate itself is beyond the program's horizon. But once a program sees a mate in N score, it must continually reduce N by at least 1 for each move played. I've never seen Crafty violate this with one exception:

A mate is _very_ deep, and my opponent takes forever to find a move. Meanwhile given an obscene amount of time, Crafty finds a mate in N where almost every move is a non-check. My opponent makes an unexpected move that is even worse than what I was expecting, but crafty still can only find a mate in N+10 because that mate triggers extensions where the "quiet" mate does not. I can live with that. But I see programs announce mate in 2 when it is a mate in 3. Etc.

BTW a few years ago Amir Ban and I had a discussion about endgame tables and the KQ vs KR ending. He thought computers could solve that easily without EGTBs but I didn't. I tried it and lo and behold, Crafty could win it every last time, easily. Against tablebases it didn't always play the best move leading to the shortest mate, but it always played moves that led to a forced mate without violating the 50-move rule. And once it saw a forced mate, it behaved perfectly beyond that point.

I will try a few KR vs K endings with crafty (with EGTB) vs Crafty without, as that is easy to do. I'd expect the non-EGTB version to easily force mate every last time, although probably not optimally when compared to the EGTB moves. Crafty has special "mop-up" evaluation code to handle these pawnless cases.

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.

1)Note that the target of the program that was used umax4_8 is not to have the strongest engine but to have the strongest engine relative to the size.

The main question is if it is possible to fix the problem without significant increase in the size.

2)H.G.Muller has another program with the name Joker that is strongest
than umax so another question is if Joker has the same type of problem.

3)Movei like some other programs including glaurung does not count correctly the number of moves to mate and can have a score of mate in 7 when it is practically mate in 10.

The question here is also practical question and I never saw movei or glaurung fail to mate when it had mate score.

I plan to fix the problem later but I think that it is mainly a cosmetic problem and the hypotetical case of missing a mate because of always delaying it never happens based on my experience.


Uri