COME FARE L'ALGORITMO DI SCANSIONE DELL’ALBERO?


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

Home Forum Vecchi ma interessanti post su Yahoo gruppi COME FARE L'ALGORITMO DI SCANSIONE DELL’ALBERO?

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

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

    Administrator
    Moderatore

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