about hashtable

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Daniel Anulliero
Posts: 688
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

about hashtable

Post by Daniel Anulliero » Fri Mar 04, 2016 3:00 pm

Hi
Yesterday I tried to run Isa , my engine , with more Hashtable
I compiled 3 versions , 64mb, 128mb and 256mb

I tested with this position :

[d]4k3/8/4pPp1/3pP1P1/2pP4/2P2K2/8/8 b - - 1 1

here is my values of probing :

64mb :
positions tested : 5187633
positions founded : 1397685 (26.94%)
positions saved : 1077415 (20.77%)

128mb :
positions tested : 4713120
positions founded : 1240323 (26.32%)
positions saved : 988693 (20.98%)

256mb :
positions tested : 4894309
positions founded : 1355172 (27.69%)
positions saved : 1018324 (20.81%)

I think I got some strange values , 26% hits isn't too few?
And I must doing something wrong , because the values are very close even with hashsize is bigger ... any lights?

here is my codes for probing and saving (implémented with the help of bruce Moreland pages) :

Code: Select all

int probe_hash(int depth, int alpha, int beta)
{
    HASHE *phashe = &tt[hash_code_position % HASH_TABLE_SIZE];

    positions_testees++;

    if(phashe->key == hash_code_position)
    {
        positions_trouvees++;
        if(phashe->depth >= depth)
        {
            if(phashe->flag == hashfEXACT)
                return phashe->value;
            if&#40;&#40;phashe->flag == hashfALPHA&#41; && &#40;phashe->value <= alpha&#41;)
                return alpha;
            if&#40;&#40;phashe->flag == hashfBETA&#41; && &#40;phashe->value >= beta&#41;)
                return beta;
        &#125;
    &#125;
    return valINCONNUE;
&#125;


void save_hash&#40;int depth, int val, int hashf, MOVE *pbest&#41;
&#123;
    HASHE *phashe = &tt&#91;hash_code_position % HASH_TABLE_SIZE&#93;;

    positions_sauvees++;

    phashe->key     = hash_code_position;
    phashe->depth   = depth;
    phashe->flag    = hashf;
    phashe->value   = val;
    phashe->best    = pbest;
&#125;

[/code]

Stan Arts
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: about hashtable

Post by Stan Arts » Fri Mar 04, 2016 5:43 pm

Hi Daniel,

Most likely the values are so close because it seems you are searching only very few positions? So the hashtable gets no where near full even with 64MB.

Try searching much much longer to see a clearer difference in efficiency.

Positions found vs tested seems normal at first glance. Ie. You would get say 4x as many leafnodes each time that you haven't encountered before and are not in hash even with massive transpositions. (It's not a closed position, white is winning so it's looking at new variations with a queen on etc. where the transpositions get way lower.)

But I don't know why you are saving only 20-ish percent instead of atleast as many as tested positions. You don't store everything? Do you test in Qsearch but not store? Or does saved mean positions where you get a cutoff. I might misunderstand your numbers.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: about hashtable

Post by stegemma » Fri Mar 04, 2016 6:43 pm

Maybe it is better to use a switch instead of the three if() statement:

Code: Select all

int probe_hash&#40;int depth, int alpha, int beta&#41;
&#123;
    HASHE *phashe = &tt&#91;hash_code_position % HASH_TABLE_SIZE&#93;;

    positions_testees++;

    if&#40;phashe->key == hash_code_position&#41;
    &#123;
        positions_trouvees++;
        if&#40;phashe->depth >= depth&#41;
        &#123;
            switch&#40;phashe->flag&#41;
            &#123;
                case hashfEXACT&#58;  return phashe->value;
                case hashfALPHA&#58; if&#40;phashe->value <= alpha&#41; return alpha;
                                           break;
                case hashfBETA&#58; if&#40;phashe->value >= beta&#41; return beta;
                                         break;
            &#125;
        &#125;
    &#125;
    return valINCONNUE;
&#125;
PS: I count as a hit only the return statement, not the hash hit itself
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Daniel Anulliero
Posts: 688
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: about hashtable

Post by Daniel Anulliero » Sat Mar 05, 2016 5:05 pm

Stan Arts wrote:Hi Daniel,

Most likely the values are so close because it seems you are searching only very few positions? So the hashtable gets no where near full even with 64MB.

Try searching much much longer to see a clearer difference in efficiency.

Positions found vs tested seems normal at first glance. Ie. You would get say 4x as many leafnodes each time that you haven't encountered before and are not in hash even with massive transpositions. (It's not a closed position, white is winning so it's looking at new variations with a queen on etc. where the transpositions get way lower.)

But I don't know why you are saving only 20-ish percent instead of atleast as many as tested positions. You don't store everything? Do you test in Qsearch but not store? Or does saved mean positions where you get a cutoff. I might misunderstand your numbers.
Well thank you stan for some hints but I had a display bug , fixed now, here is the real search infos for the position :

Code: Select all

TIME 5 seconds / moves

Hashsize = 64mb
depth = 29 , eval = +13.32 , nodes = 258496 , qnodes = 863 
pv = f3e3 e8f7 e3d2 f7f8 d2c2 f8f7 c2b2 f7f8 b2a3 f8f7 a3b4 f7f8 b4c5 
f8e8 c5d6 e8f7 d6d7 f7f8 d7e6 f8e8 f6f7 e8f8 e6d7 f8f7 e5e6 f7f8 e6e7 
f8g7 e7e8Q g7h7 d7e6 h7g7 e6d5 g7h7 d5c4
hash &#58;
tested = 159599, found = 79244, saved = 67266

Hashsize = 128mb
depth = 29 , eval = +13.32 , nodes = 257867 , qnodes = 861
pv = f3e3 e8f7 e3d2 f7f8 d2c2 f8f7 c2b2 f7f8 b2a3 f8f7 a3b4 f7f8 b4c5 
f8e8 c5d6 e8f7 d6d7 f7f8 d7e6 f8e8 f6f7 e8f8 e6d7 f8f7 e5e6 f7f8 e6e7 
f8g7 e7e8Q g7h7 d7e6 h7g7 e6d5 g7h7 d5c4
hash &#58;
tested = 159440, found = 79187, saved = 67170

Hashsize = 256
depth = 29 , eval = +13.32 , nodes = 258099 , qnodes = 863
pv = f3e3 e8f7 e3d2 f7f8 d2c2 f8f7 c2b2 f7f8 b2a3 f8f7 a3b4 f7f8 b4c5 
f8e8 c5d6 e8f7 d6d7 f7f8 d7e6 f8e8 f6f7 e8f8 e6d7 f8f7 e5e6 f7f8 e6e7 
f8g7 e7e8Q g7h7 d7e6 h7g7 e6d5 g7h7 d5c4
hash &#58;
tested 159488, found = 79274, saved = 67165

And yes I'm so disapointed when I look at my résults , no improvment for more Hashsize ...
And yes , I don't know why it save not much positions in the ttable ...
I'm so lost in the TT labyrinth now lol

her is my alpha beta / pvs code , If you look at it you can see I save hash positions when cut off , mate found , stale mate too and at the end of the function

Code: Select all

//----------------------------------------------------------------------------------------------------------------
//                                         alpha beta + PVS
//----------------------------------------------------------------------------------------------------------------
int pvs&#40;int alpha, int beta, int depth, MOVE * pBestMove, bool nulmove, int extension&#41;
&#123;
    int i,j;
    int value;
    int havemove;
    int movecnt;
    int hashf = hashfALPHA;
    int rep;
    bool echec = FAUX;
    bool echec2 = FAUX;
    bool ext = FAUX;
    int ply = 0;
    MOVE moveBuf&#91;200&#93;;
    MOVE tmpMove;
    int margin&#91;4&#93; = &#123;0, 125, 325, 525&#125;;
    int score;
    bool prune = FAUX;

    //-----------------------------------------------------------------
    //          controle temps depasse ou non &#40;jeu au temps&#41;
    //-----------------------------------------------------------------
    fin_recherche = controle_si_temps_depasse&#40;);
    if&#40;fin_recherche&#41;
        return 0;
    //-----------------------------------------------------------------
    //                          longueur pv
    //-----------------------------------------------------------------
    long_pv&#91;prof&#93; = prof;
    //-----------------------------------------------------------------
    //               profondeur limite ateinte &#58; retourne eval&#40;)
    //-----------------------------------------------------------------
    if&#40;prof >= MAXPLY-1&#41;
        return eval&#40;);
    //-----------------------------------------------------------------
    //                  nulle règle des 50 coups? ?
    //-----------------------------------------------------------------
    if&#40;cinquante == 100&#41;
    &#123;
        return 0;
    &#125;
    //-----------------------------------------------------------------
    //             nulle règle des triples répétitions ?
    //-----------------------------------------------------------------
    rep = triple_repetition&#40;);
    if&#40;prof && rep&#41;
    &#123;
        return 0;
    &#125;
    //-----------------------------------------------------------------
    // extension d'une profondeur si la couleur en cours est en échec
    //-----------------------------------------------------------------
    echec = roi_attaque&#40;pos_roi&#91;side&#93;, side&#41;;
    if&#40;echec&#41;
    &#123;
        depth++;
    &#125;
    //-----------------------------------------------------------------
    // extension d'une profondeur si le coup précédent a été une promotion
    // ou une avance de pion à la 7eme rangée
    //-----------------------------------------------------------------
    if&#40;extension&#41;
        depth++;
    //-----------------------------------------------------------------
    // on ateint la profondeur en cours quiescence
    //-----------------------------------------------------------------
    if&#40;depth <= 0&#41;
    &#123;
        value =  quiesce&#40;alpha, beta, &tmpMove&#41;;
        return value;
    &#125;
    //-----------------------------------------------------------------
    //               position dans la table de hashage ?
    //-----------------------------------------------------------------
    if&#40;hash_ok&#41;
    &#123;
        if&#40;prof&#41;
        &#123;
        	value = probe_hash&#40;depth, alpha, beta&#41;;
        	if&#40;value != valINCONNUE&#41;
        	&#123;
            	return value;
        	&#125;
		&#125;
    &#125;
    //-----------------------------------------------------------------
    //                          FUTILITY PRUNING
    // conditions &#58; depth >0 et < 4 , !echec , !pv
    //-----------------------------------------------------------------
    if&#40;(!echec&#41; && (!follow_pv&#41; && &#40;depth > 0 && depth < 4&#41; && (!extension&#41;)
    &#123;
        score = eval&#40;);
        if&#40;score <= alpha-margin&#91;depth&#93;)
            return &#40;quiesce&#40;alpha, beta, &tmpMove&#41;);
        if&#40;score >= beta+margin&#91;depth&#93;)
            return beta;
    &#125;
    //-----------------------------------------------------------------
    //                              NULLMOVE
    //              conditions &#58;    pas de finale de pion
    //                              pas en échec
    //                              profondeur >=2
    //-----------------------------------------------------------------
    if&#40;nm_ok&#41;
    &#123;
        if&#40;(!echec&#41; && &#40;ok_pour_nul_move&#40;)) && &#40;depth >= 2&#41; && &#40;nulmove&#41; && (!follow_pv&#41; && (!extension&#41;)
        &#123;
            ++ctr_nm;
            //printf&#40;"ok pour null move &#40;echec &#58; %d phase &#58; %d  &#40;ok_pour_nul_move&#40;) &#58; %d&#41;  prof &#58; %d   nulmove &#58; %d&#41;\n",
            //echec,PHASE,ok_pour_nul_move&#40;),prof,nulmove&#41;;
            jouer_coup_nul&#40;);
            value = -pvs&#40;-beta, -&#40;beta-1&#41;, depth - NULL_DEPTH - 1, &tmpMove, NO_NULL, FAUX&#41;;
            dejouer_coup_nul&#40;);
            if &#40;value >= beta&#41;
            &#123;
                return beta;
            &#125;
        &#125;
    &#125;
    //-----------------------------------------------------------------
    //     init du pointeur et flag "au moins un coup jouable"
    //-----------------------------------------------------------------
    havemove = 0;
    pBestMove->type = COUP_VIDE;
    //-----------------------------------------------------------------
    //              génération des coups pseudo-légaux
    //-----------------------------------------------------------------
    movecnt = gen_coups&#40;side, moveBuf&#41;;
    if&#40;follow_pv&#41;
        tri_pv&#40;moveBuf, movecnt&#41;;
    //-----------------------------------------------------------------
    //                      boucle coups normaux
    //-----------------------------------------------------------------
    for &#40;i = 0; i < movecnt; ++i&#41;
    &#123;
        ext = FAUX;
        meilleur_coup_suivant&#40;moveBuf, movecnt, i&#41;;

        if &#40;jouer_coup&#40;moveBuf&#91;i&#93;))
        &#123;
            continue;
        &#125;

        echec2 = roi_attaque&#40;pos_roi&#91;side&#93;, side&#41;;

        havemove++;
        nodes++;
        //extension si pion avance a la 7eme rangée &#40;et coup non réduit lmr&#41;
        if&#40;moveBuf&#91;i&#93;.piece_from == PION && &#40;ROW&#40;moveBuf&#91;i&#93;.dest&#41; == 1 || ROW&#40;moveBuf&#91;i&#93;.dest&#41; == 6&#41;)
            ext = VRAI;
        //extension si promotion
        if&#40;PROMO&#40;moveBuf&#91;i&#93;.type&#41;)
            ext = VRAI;

        if&#40;havemove == 1&#41;
        &#123;
            value = -pvs&#40;-beta, -alpha, depth - 1, &tmpMove, OK_NULL, ext&#41;;
        &#125;
        else
        &#123;
            //------------------------------------------------------
            //                      lmr possible?
            //------------------------------------------------------
            if&#40;lmr_ok&#41;
            &#123;
                if&#40;&#40;prof >= START_PROF&#41; && (!echec&#41; && (!echec2&#41; && (!ext&#41; &&
                   (!follow_pv&#41; && &#40;moveBuf&#91;i&#93;.type == NORMAL&#41;)
                &#123;
                    if&#40;havemove > 5&#41;
                    &#123;
                        if&#40;moveBuf&#91;i&#93;.evaluation < 50000&#41;
                            value = -pvs&#40;-&#40;alpha+1&#41;, -alpha, &#40;depth - 3&#41; , &tmpMove, OK_NULL, ext&#41;;
                        else
                            value = -pvs&#40;-&#40;alpha+1&#41;, -alpha, &#40;depth - 2&#41; , &tmpMove, OK_NULL, ext&#41;;
                    &#125;
                    else
                        value = -pvs&#40;-&#40;alpha+1&#41;, -alpha, &#40;depth - 1&#41; , &tmpMove, OK_NULL, ext&#41;;
                &#125;
                else
                &#123;
                    value = alpha + 1;
                &#125;
                if&#40;value > alpha&#41;
                &#123;
                    ++ctr_pvs;
                    value = -pvs&#40;-&#40;alpha+1&#41;, -alpha, depth - 1, &tmpMove, NO_NULL, ext&#41;;
                    if&#40;value > alpha && value < beta&#41;
                    &#123;
                        value = -pvs&#40;-beta, -alpha, depth - 1, &tmpMove, OK_NULL, ext&#41;;
                    &#125;
                &#125;
            &#125;
            else
            &#123;
                ++ctr_pvs;
                value = -pvs&#40;-&#40;alpha+1&#41;, -alpha, depth - 1, &tmpMove, NO_NULL, ext&#41;;
                if&#40;value > alpha && value < beta&#41;
                &#123;
                    value = -pvs&#40;-beta, -alpha, depth - 1, &tmpMove, OK_NULL, ext&#41;;
                &#125;
            &#125;
        &#125;

        dejouer_coup&#40;);

        if &#40;value > alpha&#41;
        &#123;
            history&#91;moveBuf&#91;i&#93;.from&#93;&#91;moveBuf&#91;i&#93;.dest&#93; += &#40;prof * prof&#41;;
            if&#40;history&#91;moveBuf&#91;i&#93;.from&#93;&#91;moveBuf&#91;i&#93;.dest&#93; >= 999999&#41;
                history&#91;moveBuf&#91;i&#93;.from&#93;&#91;moveBuf&#91;i&#93;.dest&#93; = 999999;
            if&#40;max_hh < history&#91;moveBuf&#91;i&#93;.from&#93;&#91;moveBuf&#91;i&#93;.dest&#93;)
            &#123;
                max_hh = history&#91;moveBuf&#91;i&#93;.from&#93;&#91;moveBuf&#91;i&#93;.dest&#93;;
            &#125;
            *pBestMove = moveBuf&#91;i&#93;;
            if &#40;value >= beta&#41;     //" cutoff "
            &#123;
                save_hash&#40;depth, beta, hashfBETA, pBestMove&#41;;

                if&#40;moveBuf&#91;i&#93;.type < PROMO_CAVALIER&#41;
                &#123;
                    killer2&#91;prof&#93; = killer1&#91;prof&#93;;
                    killer1&#91;prof&#93; = moveBuf&#91;i&#93;;
                &#125;
                return beta;
            &#125;
            hashf = hashfEXACT;
            alpha = value;

            //-----------------------------------------------------------------
            //                       mise a jour pv
            //-----------------------------------------------------------------
            pv&#91;prof&#93;&#91;prof&#93; = *pBestMove;
            for &#40;j = prof + 1; j < long_pv&#91;prof + 1&#93;; ++j&#41;
            &#123;
                pv&#91;prof&#93;&#91;j&#93; = pv&#91;prof + 1&#93;&#91;j&#93;;
            &#125;
            long_pv&#91;prof&#93; = long_pv&#91;prof + 1&#93;;
        &#125;
    &#125;
    //-----------------------------------------------------------------
    //              si aucun coups , situation de MAT ou de PAT
    //-----------------------------------------------------------------
    if (!havemove&#41;
    &#123;
        if &#40;roi_attaque&#40;pos_roi&#91;side&#93;, side&#41;)
        &#123;
            save_hash&#40;depth, -MATE + prof, hashf, pBestMove&#41;;
            return -MATE + prof;
        &#125;

        else
        &#123;
            save_hash&#40;depth, 0, hashf, pBestMove&#41;;
            return 0;
        &#125;
    &#125;
    save_hash&#40;depth, alpha, hashf, pBestMove&#41;;
    return alpha;
&#125;
[/b]

zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: about hashtable

Post by zd3nik » Sun Mar 06, 2016 12:09 am

I also see very little difference in TT hits on this position. Regardless of TT size. I suspect, in this case it's mostly due to the simplicity of the test position. With all the pawns locked the number of unique positions is relatively small. So even a 1MB TT is just as effective as a 512MB TT.

I ran the position through one of my engines with these results (10 seconds per test):

Code: Select all

512MB TT, 34604919 nodes, 13923253 TT gets &#40;40%), 7387973 TT hits &#40;53%)
256MB TT, 34964278 nodes, 13944053 TT gets &#40;40%), 7088723 TT hits &#40;50%)
128MB TT, 37854772 nodes, 13892314 TT gets &#40;37%), 7605096 TT hits &#40;54%)
 64MB TT, 33780566 nodes, 13573303 TT gets &#40;40%), 5545490 TT hits &#40;40%)
  4MB TT, 48785122 nodes, 14109908 TT gets &#40;29%), 9369903 TT hits &#40;66%)
  1MB TT, 52790429 nodes, 14114051 TT gets &#40;27%), 8605917 TT hits &#40;61%)
My engine's TT implementation is very similar to yours Daniel, except I also store a best move to try in case the depth/score isn't good enough to return immediately. This gives the search a good first move to try which usually improves cutoffs. It should also direct the search into lines/positions that have already been searched, which should increasing the chances of getting a TT hit.

All that being said I would like to see TT figures from a top tier engine on this position. Just to verify that only a very small TT size is capable of getting similar numbers on this position as larger TT sizes.

Going forward, a more complex position than this one is needed to truly test TT performance.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: about hashtable

Post by stegemma » Sun Mar 06, 2016 8:00 am

I find usefull this very simple position, to discover bugs in TT:

[d]1k6/7R/1K6/8/8/8/8/8 b[/d]
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

flok

Re: about hashtable

Post by flok » Mon Mar 07, 2016 4:44 pm

stegemma wrote:I find usefull this very simple position, to discover bugs in TT:

[d]1k6/7R/1K6/8/8/8/8/8 b[/d]
May I ask, what steps do you then take to verify the tt?
(And) what is so specific about this position?

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: about hashtable

Post by stegemma » Mon Mar 07, 2016 4:55 pm

My engine still doesn't works well with TT so the simplest position is the simpler to debug. Here black has always a couple of choices: one often lead to a short mate and the other to a little longer one. With this position I can debug:

1) that black choose the longer mate
2) that white choose the shortest one
3) that white doesn't fall in a loop, choosing its move (triple repetition or longer mates)
4) that the engine reports the correct "moves to mate" both with white or black

Because the position is simple, I can know the shortest mate even by mind, without the need of another engine to compare with.

My first goal is to "solve" this simple position, then I could pass to a more complex one.

PS: at present I debug move by move but I plan to add a double check to compare any single node with and without TT
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Daniel Anulliero
Posts: 688
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: about hashtable

Post by Daniel Anulliero » Fri Mar 11, 2016 6:13 pm

stegemma wrote:Maybe it is better to use a switch instead of the three if() statement:

Code: Select all

int probe_hash&#40;int depth, int alpha, int beta&#41;
&#123;
    HASHE *phashe = &tt&#91;hash_code_position % HASH_TABLE_SIZE&#93;;

    positions_testees++;

    if&#40;phashe->key == hash_code_position&#41;
    &#123;
        positions_trouvees++;
        if&#40;phashe->depth >= depth&#41;
        &#123;
            switch&#40;phashe->flag&#41;
            &#123;
                case hashfEXACT&#58;  return phashe->value;
                case hashfALPHA&#58; if&#40;phashe->value <= alpha&#41; return alpha;
                                           break;
                case hashfBETA&#58; if&#40;phashe->value >= beta&#41; return beta;
                                         break;
            &#125;
        &#125;
    &#125;
    return valINCONNUE;
&#125;
PS: I count as a hit only the return statement, not the hash hit itself
Do you think it will change something with a switch Instead of if block ( in term of speed) ?

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: about hashtable

Post by stegemma » Fri Mar 11, 2016 7:16 pm

Daniel Anulliero wrote:[...]
Do you think it will change something with a switch Instead of if block ( in term of speed) ?
If you use "if" and "else if" correctly then it doesn't but here it depends on how the compiler is smart. For sample, this is the same code but simplified:

Code: Select all

if&#40;a==1&#41; return x;
if&#40;a==2 && b&#41; return y;
if&#40;a==3 && c&#41; return z;
Here if a==2 but b is false, then you test for a==3 because "return y" would not be executed.

here this doesn't happens:

Code: Select all

if&#40;a==1&#41; return x;
if&#40;a==2&#41; &#123; if&#40;b&#41; return y; &#125;
       else if&#40;a==3 && c&#41; return z;
But IMHO it is still clearest with a switch:

Code: Select all

swicth&#40;a&#41;
&#123;
   case 1&#58; return x;
   case 2&#58; if&#40;b&#41; return y;  break;
   case 3&#58; if&#40;c&#41; return z;  break;
&#125;
The difference is obviously so little that it is hardly measurable.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Post Reply