hashing question

[adams161]

if i capture the king on ply 9 ( i dont store the score on ply 9 i just return alpha or beta but i make the value 7500-9) then on ply 7 if i really have mate on ply 7, i.e. no move on ply 8 can evade a king capture on ply 9 ( so ply 7 is the checkmate node ) then i need to store the score. If it was just a bad move on ply 8 that led to the king capture on ply 9 then of course when another move is tried on ply 8 they will realize they have a better move and that score will never be stored.

on ply 7 i see my score is 7491, what i'm hearing is i need to score 7491 and distance from king capture which is 2. That way if the checkmate postion occurs again but its no longer a king capture 9 ply into search but earlier, i will be able to evaluate an absolute score of king capture in 2 moves for this ply, or if it gets stored on ply 5 i would know king capture in 4 moves.

I"m not storing any scores other than alpha and beta fail high low, so when i score a checkmate it should be a legitamate score, but the kludge as its been put of checkmate value minus ply searched introduces relative ( yet real ) scores were as evaluate scores are not depth dependent.

Mike

[hgm]

I am not sure what exactly you are asking.

What I do, is return 7500, (using your values), and increase every returned score < -7400 by 1 ('delayed-loss bonus'). So the node that can capture the King gets score 7500, the parent, if he has no better move, returns -7499 (=checkmated), the grandparent score +7499 (mate-in-1) etc. In pseudocode:

Code: Select all

int Search(Alpha, Beta)
{
    if(Alpha < -7400) Alpha--;
    if(Beta <= -7400) Beta--;

    ProbeHash();
    if(HASH_HIT) BestScore = HASH_SCORE;
    else {
        for(ALL_MOVES)
        {   Score = -Search(-Beta, -Alpha);
            if(Score > BestScore)
            {   BestScore = Score;
                 .... 
            }
        }
    }

    StoreHash(BestScore);
    if(BestScore < -7400) BestScore++;
    return BestScore
}

[adams161]

just for clairty when i say i dont hash the score on king capture but set value = 7500 - ply, i mean i set value to 7500-ply then check value against alpha and beta. I could actually have a fail low as i'm seeing a king capture here 9 moves into search but one may have been established 5 moves into search which means my 7491 wouldnt even change alpha. Or i could have a fail high as in beta is 900 and my 7491 is >beta so i return beta. Were it seems it might get introduced as a score is when 7491 or the king capture value on ply 9 is > alpha but less than beta. If i return to ply 8 of courser and its a bogus move and the very next move on ply 8 shows such a checkmate is easily avoided ply 8 of course would return the value for this move etc.

so its not illegal moves i'm worried about so much, the normal alpha beta routines will weed them out, but real checkmates and how to score them when my kludge of checkmate = checkmate score minus depth searched returns a relative score. A neccesary kludge that works outside of hashing since you want the program to value getting checkmate sooner than later so it finds the fastest checkmate.

Mike

[adams161]

i'll have to look at this more closely but it seems like it would work since your meeting two goals: valuing the score that checkmates the quickest ahead of later checkmates at any node in search, and two storing the score in such a way that the score always represents distance to checkmate not distance from root node. The weakening of the score once gotten from hash will be introduced as the score returns and gets a point knocked off it as it gets each ply closer to root.

Mike

[hgm]

Yes, exactly. The tricky thing is that if you mess with the score that a search will return, you have to do the inverse operation on the search window limits, to make sure that the result after messing is positioned the same way w.r.t. the original window as the original score was compared to the pre-adjusted window. So the +1 bonus at the end must never be able to change a score that was obtained as an upper bound (because it was below the alpha that was in force during the search obtaining it) is raised to above beta (after which it would be interpreted as a lower bound in stead, which would be completely wrong).

The code above does the required pre-adjustment, and is what I use in uMax.

I hesitate to answer your questions about the other method, as I never used it. There must be a parallel between the two methods, which would be even more obvious if I would not only add 1 for scores < -7400, but siubtract 1 for scores > 7400 as well. Then you see that in my method the score is adapted while propagating towards the root, while in 'your' syste,mm it is propagated unchanged, but you the required change you need in the root is added in one step, when you subtract (or add) the depth from the root. But what you store in the hash would then be the same as what I would store in the hash, so on every hash probe and store you would have to correct for the current depth of the node.

[bob]

if i capture the king on ply 9 ( i dont store the score on ply 9 i just return alpha or beta but i make the value 7500-9) then on ply 7 if i really have mate on ply 7, i.e. no move on ply 8 can evade a king capture on ply 9 ( so ply 7 is the checkmate node ) then i need to store the score. If it was just a bad move on ply 8 that led to the king capture on ply 9 then of course when another move is tried on ply 8 they will realize they have a better move and that score will never be stored.

on ply 7 i see my score is 7491, what i'm hearing is i need to score 7491 and distance from king capture which is 2. That way if the checkmate postion occurs again but its no longer a king capture 9 ply into search but earlier, i will be able to evaluate an absolute score of king capture in 2 moves for this ply, or if it gets stored on ply 5 i would know king capture in 4 moves.

I"m not storing any scores other than alpha and beta fail high low, so when i score a checkmate it should be a legitamate score, but the kludge as its been put of checkmate value minus ply searched introduces relative ( yet real ) scores were as evaluate scores are not depth dependent.

Mike

That sounds like a recipe for mistakes.

If you capture a king on ply 9, the move you made at ply 8 was illegal. If all moves at ply 8 end up being illegal, then either you are mated or stalemated. You should not store any sort of mate score because you capture a king, because that does not imply you are checkmated at all...

[hgm]

Capturing a King is logically equivalent to mate-in-minus-1. The only thing that you need to add to get the proper scoring is that you correct the score to draw in a 'mate-in-0' position if you are not in check. Then the checkmates get properly scored without the engine knowing what checkmate is.

Hashing the King-capture positions in such an engine can still be beneficial, as other checkmate positions (or even non-mates) from which moves lead that give hits on the K-capture position might be searched. E.g. with w:Kc3,Qb2 b:Ka1, once you have figured out that Ka1xb2 will be followed by Kc3xb2, you can also benefit from that knowledge in positions with the black King on a2 or b2, or even c2.

Of course, when you hit again on the original mate position, you would already take a hash cut there. Mates scores that you are sure of are the fastest mates from this position (so in particular all checkmate positions themselves) should be treated as if they have infinite draft during probing (but not during replacement!). But it is quite possible that other branches encounter the King capture too. So you might as well put it in the hash.

[adams161]

I just wanted to clarify two points.

One why do you modify beta? seems you could just modify alpha and it would work. as you go up in depth the score improves to mate in fewer moves and as you go back down the score gets worse with just modifying alpha when alpha is a negative mate score.

also i assume this is the first thing you do before you try hashing or null move.

the second is if best alpha at bottom when you return it is negative mate you return alpha + 1. Just for clarity , you do this to alpha even if alpha never changed> i.e. no score better than alpha. seems you would have to and i think that is what you meant.

thanks
Mike

[adams161]

i did an account update on my email and was locked out for a few days, all fixed now. but i wanted to respond to this post and wrote something up actually middle of last week:

Hi,

Pulsar currently does not recognize stalemates and i've accepted that as part of the engines strenght/weakness. I find stalemates in practice come up very infrequently despite pulsar's blindness. Players resign or get mated in postions before they lose all material. The incidence of stalemate is probably less than 1/100 games. What I am concerned about ( allowing that pulsar will miss a stalemate) is that it properly see mates in general when that is not a factor. And also that it avoid mates. If it stalemates at least it didnt lose i figure.

What brought up my present concern with properly scoring checkmates in hash is programming for crazyhouse actually. In regular chess a direct frontal assault on teh king is only one factor in the game. More games seem to be won by the atrition of material. Getting a pawn or more ahead can often win the game. An attack on the king of course and forcing someone to defend can lead to material gain. It will be interesting to see if more accurate mate detection will increase pulsar's regular chess ablity. But from watching its games pulsar seems to be able to find most mates ok despite some hashing bugs.

In crazyhouse stalemates are not a real possiblity. In this variant you get to hold the pieces you capture and if you want you can use a turn to drop one. So all the pieces are eathier on the board or can be dropped on the board a turn at a time. there is no endgame in crazyhouse. What happens is players orchestrate attacks on the opponents king. This means pulsar faces attacks that can lead to mate as opposed to a material loss, on over 50% of its moves in crazyhouse. Players will actually decline taking material or take less advantageous exchanges if it gives them tempo to attack the king or a move they make can move the king from the square its on or weaken the king on that square. Players sacrafice quite a bit as well. If your holding 8 pieces gaining a 9th or worrying about losing a piece or two is often not as important as forcing the king out. Even if during your run on the king the opponent gains substantial material, that may be worth it if you get the king to move out in the open or strip its defenses so whatever remaining pieces you have on the board can with the pieces you hold force a mate.

So because of this, while still allowing the stalemate bug to persist, i am trying to more accurately score checkmates and hash the depth correctly. Fixing the stalemate bug is going to be an improvement, though it wont help in crazyhouse, but fixing the checkmate detection bug ( doesnt always report correct depth ) will be a much bigger improvement. Particularly in some variants were i run check extensions, like crazyhouse, these lines can get searched very deep ( lines that lead to mate threats i.e. have checks ) and an accurate score is important. The basic idea that you store distance from mate not distance from origin i think will work for me. I appreciate your candor Bob, and i find your answers generally usefull. Even in this case i could tell there was a lack of clarity on my part, i.e. i asked about storing king captures ( an illegal move not always something needing to be stored ) as opposed to checkmates originally ( which is what i'm really after )

So i want to say thanks, and i look forward to trying out some code changes to see if i can get more accurate checkmate scoring.

Mike

[hgm]

One why do you modify beta? seems you could just modify alpha and it would work. as you go up in depth the score improves to mate in fewer moves and as you go back down the score gets worse with just modifying alpha when alpha is a negative mate score.

True, you could do without modifying beta. This is a general consequence of the fact that having a larger-than-necessary search window never leads to errors, but it does lead to lower efficiency ofalpha-beta pruning. For checkmates this might have no impact, though. I just write it there out of habit, ad in my engines I replace the 7400 by currentEval, as I not only want them to go for fastest mate, but I also want to encourage them not needlessly putting off gain of other material.

With mate scores, the main advantage of decreasing beta is that at some point beta gets below your inital score for best move (the one that you set to Eval in QS, and to CHECKMATED in normal search), so that you get a stand-pat-like beta cutoff without having searched any moves. This is automatic mate-distance pruning, you won't search any branches to a depth larger than a proven checkmate in a parallel branch. So your engine will give an immediate move when it can mate in one,unlike many others, which still need a 2 min think for that.

also i assume this is the first thing you do before you try hashing or null move.

Yes.

the second is if best alpha at bottom when you return it is negative mate you return alpha + 1. Just for clarity , you do this to alpha even if alpha never changed> i.e. no score better than alpha. seems you would have to and i think that is what you meant.

Indeed. This is what the pseudo-code says. Always increment best score (which is alpha if you do fail-hard and no moves were found) when it is in the negative mating range. Doesn't matter how it got its value.

thanks
Mike[/quote]