Alcuni risultati con LazySMP


Questa pagina ha una gerarchia - Pagina madre:Programmazione

Home Forum Programmazione Alcuni risultati con LazySMP

Questo argomento contiene 33 risposte, ha 8 partecipanti, ed è stato aggiornato da  sasachess 1 anno, 2 mesi fa.

Stai vedendo 15 articoli - dal 16 a 30 (di 34 totali)
  • Autore
    Articoli
  • #9795

    marco belli
    Membro

    questo è il codice lazy smp di vajolet, ( scritto così nemmeno compila, ma è per intenderci :P)

    
    //----------------------------
    // multithread : lazy smp threads
    //----------------------------
    
    // Lancio n-1 thread di aiuto
    for(unsigned int i = 0; i < (threads - 1); i++)
    {
    	alphaBeta(depth+((i+1)%2), alpha, beta);
    				}
    
    //thread principale
    res = alphaBeta<search::nodeType::ROOT_NODE>(depth, alpha, beta);
    // alla fine della ricerca stoppa i thread di aiuto 
    for(unsigned int i = 0; i< (threads - 1); i++)
    {
    	helperSearch.stop = true;
    }
    // fai il join dei thread
    for(auto &t : helperThread)
    {
    	t.join();
    }
    

    quindi in pratica io prendo i risultati solo dal thread principale. gli aiutanti aiutano, e se finiscon prima… aspettano.
    questi sono i risultati di questo algoritmo dal sito ccrl: versione 4T vs 1T +109 ELO
    questi i risultati di cheng: +110 ELO

    credo che alla fine cambi molto poco.

    #9815
    Luigi
    Luigi
    Membro

    Così, giusto ad intuito, il fatto di prendere il risultato solo dal thread principale, piuttosto che di considerare buono quello del primo thread che finisce, nella pratica non penso che possa portare a grandi differenze.
    Il vantaggio del 2° approccio è solo quello di iniziare l’iterazione successiva prima – non appena un thread termina – mentre il 1° attende in ogni caso l’esito del primo thread (che potrebbe essere il primo a terminare – e non ci sarebbero differenze – oppure l’ultimo) …
    Tenendo in considerazione inoltre che generalmente i thread vengono lanciati a profondità X e X+1, i tempi di terminazione tra uno e l’altro (considerando inoltre tutto il guadagno che si ha con il riempimento della Hash), credo che siano – sempre nella pratica – trascurabili.

    Credo che affinché il 1° approccio sia sempre necessariamente peggiore del 2° sia imputabile solamente …. alla sfiga 🙂

    Chiaramente, il tutto detto da uno che non ha mai implementato (né ci ha mai provato) un algoritmo PVS multithread!! 🙂 … ma sono abbastanza fiducioso del mio intuito, a meno che la sfiga sopra menzionata non ci voglia mettere lo zampino!!!!

    Ciao

    Luigi

    #9816
    stegemma
    stegemma
    Moderatore

    C’è qualcosa di “intimamente sbagliato” in LSMP: analizzare rami a differenti profondità per forzare un “de-sincronismo” così da riempire la TT ad uso e consumo di tutti. Sembra una cooperazione alla cieca ed è un miracolo che funzioni! Forse il concetto andrebbe analizzato più a fondo, per estrarne solo il “perché funziona” e realizzare da esso un algoritmo più coerente. Facile a dirsi, difficile a farsi.

    #9817

    La difficoltà nella ricerca parallela è quella di impiegare i vari thread/processi a disposizione nella maniera più efficiente possibile. I limiti grossi in una ricerca YBWC sono l’operazione di split (che copia la posizione corrente più altri dati in una struttura condivisa dagli altri thread) e i mutex mantenuti per estrarre le mosse nei nodi ricercati in parallelo da più thread. Il vantaggio del lazy smp è che non ci sono né mutex e né copie di dati tra i vari thread durante la ricerca.
    A mio parere è un algoritmo talmente semplice che è difficile da migliorare.
    Sulla ricerca YBWC si possono fare notevoli miglioramenti, avvicinandola magari ad un ricerca DTS complicando però la mantenibilità dell’engine.

    #9845

    sasachess
    Partecipante

    Buondì,
    ho una domandina semplice semplice sul lazySMP.
    Come gestite le posizioni di matto?
    Mi spiego meglio. Nella ricerca single thread, al fine di conservare la corretta distanza (in ply) del matto dalla radice, uso un paio di funzioni per trasformare lo score di matto aggiungendo e sottraendo ply in modo opportuno e lo stratagemma funziona.

    Nel caso del lazySMP, può accadere che un thread trovi una posizione di matto a profondità n e la scrivi nella hash. Un altro faccia il probe a profondità m (diversa da n) e trovi quella posizione di matto. Risultato: la distanza corretta del matto dalla radice va a farsi friggere.

    C’è modo di risolvere?

    Regards,
    Salvatore

    #9847

    Non ci dovrebbe essere nessun problema con gli score di matto, perchè andrebbero sempre salvati nella hash come matto in n ply dall’attuale posizione. Solo quando lo recuperi dalla hash lo trasformi in matto in n ply rispetto alla radice.

    Nel probe lo score lo correggi così:

    
    if (hashval>MATTOMIN) hashval -= ply;
    if (hashval<-MATTOMIN) hashval += ply;
    

    Nello store, invece, così:

    
    if (alpha>MATTOMIN) hashval = alpha+ply;
    if (alpha<-MATTOMIN) hashval = alpha-ply;
    

    Una volta che in ricerca tieni traccia del ply a partire dalla radice non hai nessun problema.
    Un matto in 5 è un matto in 5 sia se lo ricerchi a profondità 20 che 21 ecc…

    #9849

    marco belli
    Membro

    concordo pienamente con quanto detto da Fabio, quello è il metodo giusto di salvare i matti nella hash.
    Se in gogobello non fai così allora devi corregere un BUG 🙂

    #9861

    sasachess
    Partecipante

    Ehm, ho preso un abbaglio.. grazie per l’aiuto! 🙂

    #9870

    Ho rilasciato la versione di Cinnamon 2.0 con l’implementazione dell’algoritmo lazySMP classico (depth sui thread pari e depth+1 su quelli dispari) i risultati su 40/4:0+0 sono i seguenti:

    ratings
    Rank Name                       Elo    +    - games score oppo. draws 
       1 Cinnamon 2.0-quad-core    2109    6    5  4662   66%  2000   33% 
       2 Cinnamon 2.0-single-core  2000    5    6  4662   34%  2109   33% 
    

    il guadagno su 4 thread è di circa 109 punti elo

    #9874

    marco belli
    Membro

    sembra in linea con i risultati riportti dal sito CCRL, 4 core vs 1 con il lazy smp valgono circa 100 punti elo

    #9941

    sasachess
    Partecipante

    Continuo ad avere grattacapi, credo che la causa sia nella shared hash, ma non so più dove guardare.
    Se eseguo un test su 1T, tutto fila liscio. Con 2T o più, cominciano i guai con mosse random ogni tanto e perdita di elo.

    Pubblico il mio codice (lockless) per lo store e il probe della hash table.
    Mi sembra ok, dite che devo cercare altrove?

    void HashStore(ty_s_ChessBoard *b,uint8_t depth,uint8_t ply,uint8_t hashflag,short score,ty_s_Move bestmove){
    
        uint64_t key          = b->hashKey;
        ty_s_Hash *pHashTable = &gt_Hash[key%gs_Info.maxHash];
        ty_s_Hash *pHashTemp  = NULL;
    
        int min = C_MaxPly;
    
        /* Exit if stopping */
        if(gs_Info.timeStop || gs_Info.threadStop) return;
    
        for (int i=0; i<4; i++, pHashTable++){
    
            /* Always replace the match*/
            if ( (pHashTable->Key^pHashTable->Data.Data64)==key){
                min = 0;
                pHashTemp = pHashTable;
                break;
            }
    
            /* Age replacing scheme */
            if (pHashTable->Data.Age < min)
            {
                min       = pHashTable->Data.Age;
                pHashTemp = pHashTable;
            }
        }
    
        if (min != C_MaxPly){
            pHashTemp->Data.Best           = bestmove;
            pHashTemp->Data.Depth          = depth;
            pHashTemp->Data.Score          = ScoreToTT(score,ply);
            pHashTemp->Data.Flags          = hashflag;
            pHashTemp->Data.Age            = gs_Info.aging;
            pHashTemp->Key                 = key^pHashTemp->Data.Data64;
        }
    }
    short ProbeHashTable(ty_s_ChessBoard *b,ty_s_Move *pHashMove,uint8_t depth,uint8_t ply,short alpha,short beta){
        uint64_t  key         = b->hashKey;
        ty_s_Hash *pHashTable = &gt_Hash[key%gs_Info.maxHash];
    
        for (int i=0; i<4; i++, pHashTable++){
            if ( (pHashTable->Key^pHashTable->Data.Data64)==key){
    
                *pHashMove = pHashTable->Data.Best;
    
                if(pHashTable->Data.Depth>=depth){
                    pHashTable->Data.Age=gs_Info.aging;
                    short score = ScoreFromTT(pHashTable->Data.Score,ply);
    
                    switch (pHashTable->Data.Flags) {
                        case C_HashFlagEXACT:
                                return score;
                        case C_HashFlagBETA:
                            if (score>=beta){
                                return score;
    
                            }
                        case C_HashFlagALPHA:
                            if (score<=alpha){
                                return score;
                            }
                    }
                }
                return C_KeyOk;
            }
        }
    
        return C_NullScore;
    }
    #9949

    Come dici tu il tuo codice è lockless per cui è normale che trovi mosse random.
    Quando accedi con più thread all’hash condiviso devi garantire che l’accesso sia esclusivo

    #9952

    sasachess
    Partecipante

    Grazie per la risposta Giuseppe, ma non credo che il problema sia quello. Quando citavo l’approccio lockless, mi riferivo a questo: A lockless transposition table implementation for parallel search

    Comunque, sto pian piano isolando il problema. Ho commentato il codice in “eccesso” e sto testando ogni piccola aggiunta progressivamente.

    #9955

    Se accedi ogni volta direttamente alla hash senza salvarti l’ingresso in locale rischi sempre che qualche altro thread possa modificare quell’ingresso nel frattempo.
    La soluzione, a mio avviso, è quella di copiarsi l’ingresso della hash in locale, fai xor e poi ci fai tutte le operazioni che vuoi, a quel punto nessun altro thread può intervenire.

    #9956

    sasachess
    Partecipante

    Grazie Fabio, seguirò certamente il tuo consiglio.
    Non mi spiego ancora, però, perché il problema è più evidente abilitando il Null Move Pruning.

Stai vedendo 15 articoli - dal 16 a 30 (di 34 totali)

Devi essere loggato per rispondere a questa discussione.

© 2017 G 6 Tutti i diritti riservati - Buon divertimento!

By continuing to use the site, you agree to the use of cookies. more information

Questo sito utilizza i cookie per fonire la migliore esperienza di navigazione possibile. Continuando a utilizzare questo sito senza modificare le impostazioni dei cookie o clicchi su "Accetta" permetti al loro utilizzo.

Chiudi