ESPERIENZE SU HASH TABLE E DINTORNI


Questa pagina ha una gerarchia - Pagina madre:Vecchi ma interessanti post su Yahoo gruppi

Home Forum Vecchi ma interessanti post su Yahoo gruppi ESPERIENZE SU HASH TABLE E DINTORNI

Questo argomento contiene 0 risposte, ha 1 partecipante, ed è stato aggiornato da  Administrator 4 anni, 2 mesi fa.

Stai vedendo 1 articolo (di 1 totali)
  • Autore
    Articoli
  • #5426

    Administrator
    Moderatore
    Vedrò di riuscire a rispondere ad un po’ tutte le domande in un’email sola… 🙂
    ALGORITMO DI SCANSIONE DELL’ALBERO
    L’algoritmo di scansione dell’albero è un usuale negamax ovviamente CON alpha-beta pruning, che in un secondo tempo trasformerò in MTD(f), dal momento che dalla teoria, ove faccia uso di hash tables, si comporta come un algoritmo negamax alpha-beta perfettamente ordinato (d’ora in poi darò per scontata l’esistenza di alpha e beta, come del resto avevo fatto nel messaggio precedente).
    In realtà, Alessandro, avevo proprio pensato di passare per il PV search nella “traduzione” da negamax a MTD(f), dal momento che il PV search è strutturalmente quasi identico al negamax ma fa uso già enorme di finestre di larghezza 1, restituendo così un’informazione “binaria”. A proposito del fatto che MTD(f) non restituisce la PV, ma solo la mossa da giocare… sai come fa allora AnMon a visualizzare la PV? Mantiene le mosse da giocare nella tabella di trasposizione?
     Su MTD(f) ho anch’io molta documentazione, Marco, anche se un po’ disordinata… magari quando mi ci metterò confronterò anche quello che hai tu e ne metteremo una cartella nei download.
    FUNZIONE DI GENERAZIONE DELLE MOSSE
    La funzione che ho realizzato restituisce tutte mosse rigorosamente REGOLARI. Non c’è poi più bisogno di verificarne la correttezza in seguito. Capisco l’obiezione “meglio non verificare la regolarità di mosse che non verranno considerate grazie al pruning”, e l’ho considerata anch’io all’inizio, però poi mi è sembrata più soddisfacente questa scelta (è anche molto probabile che mi sbagli).
    Spiego in breve:
    La rappresentazione della scacchiera è su un array di 144 celle (rappresenta una scacchierona 12×12), di cui solo 64 (la scacchiera 8×8 interna alla scacchierona) sono valide. Ogni mossa generata che includa come casella di arrivo una cella fittizia è scartata grazie ad una semplice operazione di “&” (and binario).
    L’unica cosa che rimane da controllare è quella di non generare mosse per cui il re si trovi poi sotto scacco… piuttosto che andare ogni volta a chiamare la funzione SottoScacco(), preferisco evitare al nascere il problema, per cui:
    1- se si è già sotto scacco e lo scacco è doppio, occorre muovere il re:
    2- se si è sotto scacco e lo scacco è semplice, di può muovere il re, frapporre un pezzo (se chi attacca è Q,R o B) o mangiare il pezzo stesso;
    3- se non si è sotto scacco bisogna evitare di muovere i pezzi inchiodati, a meno delle direzioni di inchiodatura. Si può inoltre considerare se è lecito l’arrocco.
    In definitiva chiamo la funzione SottoScacco(), che è la più lenta, una sola volta… se la andassi ad applicare poi nella ricerca, dovrei chiamarla 30-35 volte ai livelli alpha e 1-4 volte ai livelli beta grazie al pruning. Quindi in media 15-20 volte. Dal momento che sul mio P200 i tempi di esecuzione sono:
    SottoScacco() 8/9 microsecondi;
    MossePossibili() 35/80 microsecondi a seconda della difficoltà della posizione;
    penso comunque di guadagnare qualcosa a generare mosse solo legali.
    Per quanto riguarda il codice, Marco, non ho ancora deciso se rilasciarlo pubblicamente prima o poi (prima deve funzionare!!!) e comunque in tale caso dovrei almeno unifomare la lingua usata per le variabili. 🙂 Per il g_6 comunque sarà pubblica ovviamente. Se ti accontenti di una versione così com’è, non troppo commentata, te la posso comunque mandare via email, così come a chiunque del g_6 voglia.
    QUIESCENZA
    Quando parlavo di profondità media pari a 2 sulle partite lightning mi riferivo a Golem, che infatti va a vedere le prese fino a profondità 4, ecco perché mi sembrava più “furbo” del mio scacchi che invece ancora non ha totalmente quiescenza… 🙂 questo da un lato mi porta a 40knps (SOS per esempio sul mio computer 35knps di media, ma picchi più elevati), dall’altro fa comparire un horizon-effect da paura! E infatti alla fine proprio questo causa enormi blunder che gli fanno perdere molte delle partite. Qualcuno di voi ha qualche bel documento su come fare una funzione di quiescenza, anche grossolana, ma veloce? E Alessandro, hai qualcosa di scritto di quello che ha detto Ed Schröder nel CCC?
    ALBERI BINARI BILANCIATI
    Io sapevo che gli alberi rossi e neri fossero una variante di quelli bilanciati. Se sai, ho hai un documento a riguardo, come bilanciare alberi rossi e neri dopo eliminazione di un elemento fammi sapere. Io ho realizzato la mia bilanciatura per alberi bilanciati, ma non ho la sicurezza che funzioni sempre… anzi, come tutte le cose in cui mi muovo euristicamente, ho quasi la sicurezza che non funzioni. 🙂
    HASH TABLE
    Alla fine ho realizzato un’hash table grossolana per il mio programma di dimensione regolabile da file .ini
    Risultato:
    Scacchi 0.08 senza ht (700kb di memoria allocata)
    Scacchi 0.09 con ht=19 (8200kb di memoria allocata)
    risultato (partita in 15 minuti):
    Scacchi 0.08 – Scacchi 0.09 1-0 (ovviamente!!!)
    mi sa che ci dovrò lavorare ancora molto 🙂
    Mi pare che ho toccato un po’ tutti gli argomenti…
    alla prossima, ciao a tutti
    ——————————————————————————————————————–
    R: [g_6] Re: Hash Tables
    hey claudio … come mi piace discutere di queste cose con te perche
    in pratica stiamo penetrando nel cuore di ogni “golem” scacchistico.— In g_6@egroups.com, “Claudio” <clade@f…> wrote:
    > Vedrò di riuscire a rispondere ad un po’ tutte le domande in
    un’email sola… 🙂
    >

    > ALGORITMO DI SCANSIONE DELL’ALBERO

    questo capitolo lo salto perche non sono ferrato sull’argomento

    qui ci vuole Alessandro o Ciccio o Marco …

    > L’algoritmo di scansione dell’albero è un usuale negamax
    ovviamente
    CON alpha-beta pruning, che in un secondo tempo trasformerò in MTD
    (f), dal momento che dalla teoria, ove faccia uso di hash tables, si
    comporta come un algoritmo negamax alpha-beta perfettamente ordinato
    (d’ora in poi darò per scontata l’esistenza di alpha e beta, come
    del
    resto avevo fatto nel messaggio precedente).
    > In realtà, Alessandro, avevo proprio pensato di passare per il
    PV
    search nella “traduzione” da negamax a MTD(f), dal momento che il PV
    search è strutturalmente quasi identico al negamax ma fa uso
    già
    enorme di finestre di larghezza 1, restituendo così
    un’informazione “binaria”. A proposito del fatto che MTD(f) non
    restituisce la PV, ma solo la mossa da giocare… sai come fa allora
    AnMon a visualizzare la PV? Mantiene le mosse da giocare nella
    tabella di trasposizione?
    > Su MTD(f) ho anch’io molta documentazione, Marco, anche se un po’
    disordinata… magari quando mi ci metterò confronterò anche
    quello
    che hai tu e ne metteremo una cartella nei download.
    >
    > FUNZIONE DI GENERAZIONE DELLE MOSSE

    ecco di questo volgio parlare

    > La funzione che ho realizzato restituisce tutte mosse rigorosamente
    REGOLARI. Non c’è poi più bisogno di verificarne la correttezza
    in
    seguito. Capisco l’obiezione “meglio non verificare la regolarità
    di
    mosse che non verranno considerate grazie al pruning”, e l’ho

    confermo e’ proprio cosi’ … provare per credere.

    ovviamente parlo di mosse legali e pseudo-mosse intendendo
    come pseudomosse tutte le mosse regolari generate senza dover
    tener conto se il re e’ sotto scacco o no.
    In pratica quelle che generi tu normalmente prima di fare la
    scrematura con la funzione ReSottoSscacco()

    >considerata anch’io all’inizio, però poi mi è sembrata più
    >soddisfacente questa scelta (è anche molto probabile che mi
    sbagli).

    a parte le considerazioni teoriche prova … vedrai come si velocizza
    la cosa ….
    Prova anche semplicemente a fare una versione che fa’ il controllo
    SottoScacco solo generando le mosse a liv.0 e falle giocare l’una
    contro l’altra … quella senza sotto scacco dovrebbe vincere a mani
    basse … mi meraviglierei del contrario.
    Chiamiamo La futura implementazione di ESC … ESC2
    Non ti preoccupare che Esc2 non lascera’ lo stesso il re in presa ..
    perche’ vale troppo e quindi prima di farselo mangiare lo spostera.
    attualmente e’questo che sta facendo golem!!!
    purtroppo non avevo considerato (grazie ciccio della spiegazione) che
    talvolta in particolari situazioni questo tipo di struttura prende in
    considerazione lo scambio dei re(sic) ma anche a questo c’e’ una
    soluzione … basta che il search al momento che si accorge che il
    suo re e’ in presa non ritorni un valore tipo -100 pedoni (che si
    gnifica ho perso un mare di materiale) ma una vera e propria
    segnalazione di errore.
    Si tratta di tecniche supercollaudate … prova a dare un’occhiata
    al programma TSCP ( c’e’ anche nella dir del gelo ) oppure a faile
    oppure a qualsiasi altro programma.

    > Spiego in breve:
    > La rappresentazione della scacchiera è su un array di 144 celle
    (rappresenta una scacchierona 12×12), di cui solo 64 (la scacchiera
    8×8 interna alla scacchierona) sono valide. Ogni mossa generata che
    includa come casella di arrivo una cella fittizia è scartata
    grazie
    ad una semplice operazione di “&” (and binario).
    > L’unica cosa che rimane da controllare è quella di non generare
    mosse per cui il re si trovi poi sotto scacco… piuttosto che andare
    ogni volta a chiamare la funzione SottoScacco(), preferisco evitare
    al nascere il problema, per cui:
    > 1- se si è già sotto scacco e lo scacco è doppio, occorre
    muovere
    il re:
    > 2- se si è sotto scacco e lo scacco è semplice, di può
    muovere il
    re, frapporre un pezzo (se chi attacca è Q,R o B) o mangiare il
    pezzo
    stesso;
    > 3- se non si è sotto scacco bisogna evitare di muovere i pezzi
    inchiodati, a meno delle direzioni di inchiodatura. Si può inoltre
    considerare se è lecito l’arrocco.
    >
    > In definitiva chiamo la funzione SottoScacco(), che è la più
    lenta,
    una sola volta… se la andassi ad applicare poi nella ricerca,
    dovrei chiamarla 30-35 volte ai livelli alpha e 1-4 volte ai livelli
    beta grazie al pruning. Quindi in media 15-20 volte. Dal momento che
    sul mio P200 i tempi di esecuzione sono:
    > SottoScacco() 8/9 microsecondi;
    > MossePossibili() 35/80 microsecondi a seconda della difficoltà
    della posizione;
    > penso comunque di guadagnare qualcosa a generare mosse solo legali.

    I calcoli non valgono perche la funzione sotto scacco (a parte il
    trascurabile livello 0) non la devi chiamare mai!!
    e’ il search che al momento che trova una mossa che mangia il re
    ritorna una segnalazione di mossa irregolare e il ramo viene tagliato
    a posteriori in quanto irregolare!

    >
    > Per quanto riguarda il codice, Marco, non ho ancora deciso se
    rilasciarlo pubblicamente prima o poi (prima deve funzionare!!!) e
    comunque in tale caso dovrei almeno unifomare la lingua usata per le
    variabili. 🙂

    anch’io 🙂 e ho intenzione di farle tutte in inglese. cosi puo’
    essere diffusa a tutti.

    >Per il g_6 comunque sarà pubblica ovviamente. Se ti

    bene!

    >accontenti di una versione così com’è, non troppo commentata,
    te la
    >posso comunque mandare via email, così come a chiunque del g_6
    >voglia.

    io mi prenoto … ma non adesso … perche’ voglio prima rendere
    disponibile al g6 golem

    >
    > QUIESCENZA
    > Quando parlavo di profondità media pari a 2 sulle partite
    lightning
    mi riferivo a Golem, che infatti va a vedere le prese fino a
    profondità 4, ecco perché mi sembrava più “furbo” del mio
    scacchi che
    invece ancora non ha totalmente quiescenza… 🙂 questo da un lato mi

    purtroppo la quiescenza ci vuole 😉

    >porta a 40knps (SOS per esempio sul mio computer 35knps di media, ma
    picchi più elevati), dall’altro fa comparire un horizon-effect da
    paura! E infatti alla fine proprio questo causa enormi blunder che

    me lo immagino

    >li fanno perdere molte delle partite. Qualcuno di voi ha qualche bel
    documento su come fare una funzione di quiescenza, anche grossolana,
    ma veloce?

    a me piace quella del TSCP … cioe’ prolungare tutte le linee che
    conivolgono “mangiamenti” cercando di mangiare il piu’ grande col
    piu’ piccolo.
    tra l’altro quella di tscp non ha profondita limitata ma va’ fino in
    fondo … questo vuol dire che e’ sufficentemente efficente

    >E Alessandro, hai qualcosa di scritto di quello che ha detto Ed
    Schröder nel CCC?

    qui cedo la parola a alessando ma voglio dire 2 cose

    — la quiescienza di golem e’ regolabile con l’istruzione

    set qd N
    dove N e’ il livello desiderato

    — purtroppo la mia implementazione e’ troppo lenta e il livello 4
    e’ semplicemente quello che mi sembrava promettesse migliori
    risultati con il gelo (ho provato a fare tornei tra golems a
    profondita di quiescienza diversa)
    la soluzione definitiva comunque sara una quiescienza piu’ efficiente
    e una bella SEE.

    >
    > ALBERI BINARI BILANCIATI
    > Io sapevo che gli alberi rossi e neri fossero una variante di
    quelli bilanciati. Se sai, ho hai un documento a riguardo, come
    bilanciare alberi rossi e neri dopo eliminazione di un elemento fammi
    sapere. Io ho realizzato la mia bilanciatura per alberi bilanciati,
    ma non ho la sicurezza che funzioni sempre… anzi, come tutte le
    cose in cui mi muovo euristicamente, ho quasi la sicurezza che non
    funzioni. 🙂
    >

    > HASH TABLE
    > Alla fine ho realizzato un’hash table grossolana per il mio
    programma di dimensione regolabile da file .ini
    > Risultato:
    > Scacchi 0.08 senza ht (700kb di memoria allocata)
    > Scacchi 0.09 con ht=19 (8200kb di memoria allocata)
    > risultato (partita in 15 minuti):
    > Scacchi 0.08 – Scacchi 0.09 1-0 (ovviamente!!!)
    >
    > mi sa che ci dovrò lavorare ancora molto 🙂
    >
    > Mi pare che ho toccato un po’ tutti gli argomenti…
    > alla prossima, ciao a tutti

    questi ultimi 2 punti per ora non li ho mai toccati nei miei
    programmi di scacchi.

    ciao
    e facci sapere come va’ ESC2 😉

    gianluigi

    —————————————————————————————
    Re: R: [g_6] Re: Hash Tables

    ALGORITMO DI SCANSIONE DELL’ALBERO
    L’algoritmo di scansione dell’albero è un usuale negamax ovviamente CON alpha-beta pruning, che in un secondo tempo trasformerò in MTD(f), dal momento che dalla teoria, ove faccia uso di hash tables, si comporta come un algoritmo negamax alpha-beta perfettamente ordinato (d’ora in poi darò per scontata l’esistenza di alpha e beta, come del resto avevo fatto nel messaggio precedente).
    In realtà, Alessandro, avevo proprio pensato di passare per il PV search nella “traduzione” da negamax a MTD(f), dal momento che il PV search è strutturalmente quasi identico al negamax ma fa uso già enorme di finestre di larghezza 1, restituendo così un’informazione “binaria”. A proposito del fatto che MTD(f) non restituisce la PV, ma solo la mossa da giocare… sai come fa allora AnMon a visualizzare la PV? Mantiene le mosse da giocare nella tabella di trasposizione?

    Dato che in ogni nodo non esistono valori esatti, ma solo dei bound, l’MTD non ritorna nessuna informazione sulla migliore mossa. Perciò non esiste la PV (come si sa, la PV contiene le migliori mosse dei giocatori). L’uso della hashtable per costruiere una PV mi sembra il migliore metodo per MTD. Non so se anche AnMon la fa, ma non rimangono tante possibilità (dato che non esiste la PV :).

    Chi usa l’MTD deve accettare delle PV non da usare per capire le mosse sulla scacchiera. Anch’io avevo esperimentato con MTD, ma per me la PV è centrale nei scacchi! La PV mi dice proprio per quale ragione sceglie la mossa alla radice dell’albero di ricerca (mi scuso con i puristi per “albero”).

    QUIESCENZA
    Quando parlavo di profondità media pari a 2 sulle partite lightning mi riferivo a Golem, che infatti va a vedere le prese fino a profondità 4, ecco perché mi sembrava più “furbo” del mio scacchi che invece ancora non ha totalmente quiescenza… 🙂 questo da un lato mi porta a 40knps (SOS per esempio sul mio computer 35knps di media, ma picchi più elevati), dall’altro fa comparire un horizon-effect da paura! E infatti alla fine proprio questo causa enormi blunder che gli fanno perdere molte delle partite. Qualcuno di voi ha qualche bel documento su come fare una funzione di quiescenza, anche grossolana, ma veloce? E Alessandro, hai qualcosa di scritto di quello che ha detto Ed Schröder nel CCC?

    Mmmh, “[…] una quiescenza, anche grossolana, ma veloce […]”. La più semplice è quella standard (senza intelligenza):int Quiescence (int alpha, int beta)
    {
    int best, value;

    best= StaticEval(position);
    if (best>=beta) return best;

    if (best>alpha) alpha= best;

    n= GenerateCaptures(); i= 0;
    while (i<n && best<beta) {
    make(move);
    value= -Quiescence(-beta, -alpha);
    unmake(move);

    if (value>best) {
    best= value;
    if (best>alpha) alpha= best;
    };

    i++;
    };
    // it applies: i==n || best>=beta

    return best;
    }

    per MTD:
    alpha = beta-1
    =>
    (best>alpha <=> best>=beta)  &  -alpha = -beta+1

    int MTDquiescence (int beta)
    {
    int best, value;

    best= StaticEval(position);
    if (best>=beta) return best;

    n= GenerateCaptures(); i= 0;
    while (i<n && best<beta) {
    make(move);
    value= -Quiescence(-beta+1);
    unmake(move);

    if (value>best) best= value;

    i++;
    };
    // it applies: i==n || best>=beta

    return best;
    }

    Per farla veloce va bene un SEE, che all’inizio può essere grossolano. Sconsiglio di usare il SEE alla radice dell albero della quiescenza!

    Per quello che ha detto Ed Schröder nel CCC:
    Dovresti cercare nell archivio del CCC tramite il tool apposito per il CCC. Non mi ricordo quando l’aveva detto.

    Ciao

    Alessandro

    Le faq sono nel menu principale, sotto Documentazione! 😉

Stai vedendo 1 articolo (di 1 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