futility pruning


Questa pagina ha una gerarchia - Pagina madre:Programmazione

Home Forum Programmazione futility pruning

Questo argomento contiene 25 risposte, ha 5 partecipanti, ed è stato aggiornato da Lissandrello Luca Lissandrello Luca 5 anni, 4 mesi fa.

Stai vedendo 15 articoli - dal 1 a 15 (di 26 totali)
  • Autore
    Articoli
  • #2710

    Sto corteggiando questo algoritmo da più di un anno e ancora non riesco ad ottenere risultati soddisfacenti.

    Innanzitutto ho un problema teorico. Il futility pruning si fa nei nodi di frontiera (depth 1): se la valutazione statica del nodo + il guadagno materiale della mossa + un margine di sicurezza è inferiore ad alfa, allora non analizzo la mossa. Bene. Però la mia ricerca quiescente si interrompe se la valutazione statica è maggiore di beta (implementazione standard). Per cui il risparmio che ottengo con questa potatura è nullo. Difatti l’analisi delle mosse che poto verrebbe interrotta subito a depth 0 dalla ricerca quiescente.

    Da quanto mi pare di capire, l’unico vantaggio del futility pruning è quello di non dover calcolare la valutazione statica dei nodi foglia potati. Molto bello se la funzione di valutazione è particolarmente pesante, totalmente inutile in ProChess poiché la mia funzione di valutazione è incrementale e velocissima.

    Dopo essermi messo l’anima in pace ho incominciato a sperimentare l’extended futility pruning (depth 2). Ho trovato delle buone condizioni per evitare che le potature riducessero la qualità dell’albero, un margine di sicurezza interessante e sono passato ai test.

    Confrontando la pv con e senza futility su posizioni di test andava tutto bene: pochissime differenze nella variante mostrata, stessa valutazione, stessa bestmove, minor numero di posizioni analizzate. Tutto felice ho provato a far giocare qualche centinaio di partite contro i miei soliti sparring partner. Risultato: uno schifo! Nessun miglioramento, forse un leggero peggioramento (ma nei margini di errore).

    Qualcuno ha avuto la mia stessa esperienza frustrante?

    &d0

    #2712

    Beh, per quanto riguarda il primo problema, e’ chiaro che se hai una funzione di valutazione molto leggera puo’ essere minimo il risparmio, ma quando un giorno vorrai mettere dei termini di valutazione in piu’, il risparmio aumenta (l’innovazione ti costa meno).

    Forse puoi ottenere risultati migliori estendendo il pruning a profondita’ superiori (anche tipo 4 – con opportuni margini).

    Tieni anche conto che se hai altre forme di potatura/riduzione queste si possono anche sovrapporre e sminuire l’effetto l’una dell’altra. Hai provato a fare una statistica di quante volte una mossa e’ stata potata? Puo’ darti un’idea dell’ordine di grandezza del fenomeno.

    Riguardo all’ultimo problema: hai deciso i parametri in base ai test? Perche’ in genere i test tattici vanno a esplorare posizioni con “sorprese tattiche”, quindi casi in cui la maggiorparte delle tecniche di forward pruning in genere fa un po’ schifo, per cui potresti essere portato, dai test, a usare dei margini troppo conservativi, col risultato di non potare abbastanza. Per questo sarebbe utile vedere nelle varie posizioni (suites tattiche vs partite) quanto pota in proporzione.

    Del resto tu stesso hai detto che ad occhio nei test i risultati con e senza pruning era compatibile, il risultato in partite sara’ simile 😉

    bye^2,     mr

    #2713
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    se la valutazione statica del nodo + il guadagno materiale della mossa + un margine di sicurezza è inferiore ad alfa, allora non analizzo la mossa

    Ecco perchè alla scacchistica mi hai fatto la domanda su se la mia valutazione statica dipendeva anche da mosse effettuate in nodi precedenti! 🙂
    In merito Luca Naddei penso che ci abbia smanettato tanto; Uragano è molto basato su questo tipo di pruning, però non so quanto possa aiutarti dato che è presissimo al lavoro in questo periodo.
    Personalmente sono sempre molto tentato dall’implementazione di tale funzionalità, ma ogni volta che ci ho provato ho sempre trovato incredibili guadagni di tempo ma spesso anche tagli a rami potenzialmente corretti. Più aumentavo il margine di sicurezza e ovviamente meno guadagno di tempo avevo e meno rischi correvo.
    Attualmente ho implementato la logica di questa tecnica direttamente in quella che chiamo occhio di falco, ma scendo nei particolari solo se lo volete, dato che esula un po’ dall’argomento.

    Imho il futility (depth 1) non dovrebbe cozzare sempre con la tua quescenza, sono due cose che non si escludono a vicenda. E’ vero che la quiescenza taglia tutto quello che trova oltre beta ma analizza solo quelle dove sono presenti dei cambi di materiale (standard), non tutte.

    Da quanto mi pare di capire, l’unico vantaggio del futility pruning è quello di non dover calcolare la valutazione statica dei nodi foglia potati.

    Nel caso tuo sì, dovrebbe esser così.

    Sull’extended futility pruning non so dirti molto, certo i tuoi risultati sono strani… hai provato ProChess EFP vs ProChess (magari basato su posizioni particolari e invertendo sempre i colori)? Dove ‘sbaglia’?

    Bye!
    LL

    LL

    #2714
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Uh! non ho visto la risposta di Mauro 🙂
    La sua risposta è più interessante, ma io ci ho messo le quote 😉

    Bye!
    LL

    LL

    #2715

    lucaNaddei
    Membro

    Quello di cui stai parlando tu Edo è un futility pruning a depth zero! Certo che non ti dà nessun vantaggio.

    Il concetto del futilit pruning (tralasciando alfa beta e cavolacci vari)  è:

    – Devo generare ancora le mosse dell’ultimo depth (mettiamo per esempio il bianco)

    – Il bianco ha già un vantaggio enorme (il famoso margine di sicurezza)  , il suo re è al sicuro.

    Restituisco il valore della valutazione statica.

    Su di questo ci puoi naturalmente ricamare sopra, ad esempio se si sono già cambiate le donne il margine di sicurezza si può abbassare.

    Luca

     

     

    #2716
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Attenzione, prima di dare questa risposta Luca Naddei si è addirittura resettato la password, quindi occhio a contraddirlo! 😉

    Ciao Luca!
    LL

    LL

    #2717

    lucaNaddei
    Membro

    Scusa avevo dimenticato una cosa importante  (è un po’ che non smanetto 🙂 )

    fare Il futility a dept 1 può darti MATEMATICAMENTE lo stesso risultato che non farlo (con il risparmio di un depth)

    Considera questa situazione.

    – Devo generare ancora le mosse dell’ultimo depth (mettiamo per esempio il bianco)

    – Il bianco ha già un vantaggio di una torre  (rispetto a beta), il suo re è al sicuro.

    – Il bianco non ha Torri nè regine sotto attacco da nessun pezzo nero.

    Facendo la ricerca normale andresti a quiescenza con il nero.  Sicuramente in questa combinazione si arriverebbe comunque al taglio del ramo.

     

    Luca

    #2718

    Calma, calma, rispondo a tutti!

    @ Mauro: ogni nuova versione di ProChess la costruisco ripartendo da zero. Dal perft, all’alfa-beta, poi il preordinamento, poi l’hashtable e così via. Mi prende un po’ più di tempo ma elimino quasi tutti i bachi dal codice. Soprattutto con gli algoritmi “nuovi”, cioè che non ho mai usato come il futility, procedo con i piedi di piombo. In questo caso ho fatto i test del futility senza nessun’altra forma di potatura, riduzione o mossa nulla. Solo alfa-beta, estensioni degli scacchi, hashtable e quiescenza. Date alcune posizioni test (sia quiz tattici sia posizioni tranquille), su 30 secondi di analisi, ho contato il numero di volte in cui il futility (extended cioè depth 2) avrebbe potato e il numero di volte in cui la potatura sarebbe stato un errore. Paradossalmente il maggiore numero di errori l’ho ottenuto nei finali (quelli di pedoni sono terribili!) e non nelle posizioni tatticamente caotiche. La mia scelta dei parametri portava a leggeri miglioramenti nelle posizioni di mediogioco tranquille, circa il 30% di velocità in più nelle posizioni incasinate e nessun miglioramento nei finali. Il tutto con sporadiche variazioni della pv (ma non della best-move) rispetto alla versione senza futility. Perché non produca miglioramenti della forza di gioco è un mistero…

    @ Luca L: ProChess EFP perde di misura (entro il margine di errore) contro ProChess. Ho provato anche contro altri motori e i risultati sono altalenanti. Devo ammettere di avere perso le speranze e quindi non ho fatto test molto metodici; è il mio tipico difetto, non posso farci nulla 🙂

    @ Luca N: sono d’accordo con te, ma quello di cui stai parlando si chiama extended futility pruning (o almeno così lo chiama la “teoria”). C’è una grande confusione di notazioni negli articoli che si trovano in rete 🙁

    #2720

    dimenticavo… sto in chat fino alle 16 per parlarne più liberamente.

    #2721

    lucaNaddei
    Membro

    Per quanto mi ricordo io il futility pruning ti fa risparmiare una generazione di mosse e l’extended 2 quindi….

    Non vorrei che la confusione nasca a seconda  di dove lo si mette rispetto alla search, se lo metti in alto sulla search (prima della genmove) sei già ad un depth in più, se lo metti dopo la makemove del livello precedente sei ancora a depth-1.

    luca

    #2746

    C’e’ un thread su talkchess che e’ correlato con cio’ che ci dicevamo ieri in chat, subject: “Some thoughts on QS”.

    bye^2,     mr

    #2747

    Sì, gli ultimi post sono interessanti: lì si parla addirittura di sopprimere la ricerca quiescente e di sostituirla con un SEE (occhio di falco!). Non c’è niente da fare, è la dimostrazione che Neurone è un programma tremendamente innovativo 🙂

    Comunque ho ripensato a ciò che abbiamo discusso in chat e sono giunto alla conclusione di lasciare perdere il futility pruning per l’ennesima volta e provare il delta pruning senza tabella dei pezzi attaccati come mi ha suggerito Luca N. Ormai ho due o tre modifiche da testare e mi manca tempo-macchina, avrò i risultati a fine settimana 😉

    A risentirci!

    &d0

    #2748
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Grazie per i complimenti fratello 😉 io invece ho appena implementato l’extended futility pruning (in realtà l’avevo già implementato in una vecchia versione, ma siccome era piena di bachi, ho preso tutto e l’ho buttato).

    In questo momento Neurone sta giocando su fics (megamatch con un certo greyhorse, se le stanno dando di brutto) e io analizzo le posizioni più interessanti tirando fuori il log e verificando un po’.

    Mi sembra di capire che l’incremento a livello di nodi tagliati è del 10% in media, ma può variare clamorosamente da posizione a posizione. In qualunque caso ci voglio lavorare ancora, magari aumentando il margine di tranquillità con l’aumentare dl tempo a disposizione. Non voglio rischiare nulla contro Yao; già parto sconfitto, se poi Neuro mi va pure a tagliare qualcosa di buono è finita.

    Bye!
    LL

    LL

    #2749

    @Edoardo

    In effetti piu’ che altro il SEE un tempo veniva usato come qsearch semplificata: nel thread e’ menzionato Chess Genius, ma io mi ricordavo prima ancora Sargon (pero’ visto che lo dice una pietra miliare come Ed Schroeder, io credo piu’ a lui che a me stesso 🙂 ).

    Riguardo alla faccenda della tabella dei pezzi attaccati, io personalmente non ce l’ho. Cmq devo dire che ci ho pensato, e il FP di cui parlavate non e’ proprio la stessa cosa di cui parlavo io. E infatti il delta pruning e’ semplicemente il futility pruning (come lo intendo io) in qsearch (frase non mia, ma di Hyatt), che nella chat-tata di ieri era data come una cosa ancora diversa, quindi dovremmo riallineare il vocabolario 🙂

    @Luca (ma pure per Edo)

    Mi sembra che ci siano un po’ troppe remore a tagliare: tagliare e’ bello, come dice Monti 🙂 Pensate che qui non ci sono precari o esodati che se lo prendono … in tasca 😉

    Ogni forma di forward pruning e’ rischiosa, e fa perdere qualita’ alla parte terminale dell’albero: pero’ ti permette di esplorare alberi piu’ profondi, per cui aumenta la qualita’ della prima parte della PV (e pure delle PV concorrenti). Per la mia esperienza (ok, non e’ poi un granche’ 🙂 ), e’ piu’ frequente sbagliare perche’ si pota troppo poco. Alla fine l’unica cosa che conta e’ la bestmove, come si arriva alla “mossa migliore” (o mossa approssimativamente migliore) e’ solo una questione di estetica.

    Il tutto rigorosamente IMHO, anzi mi dispiace di avere spifferato tutti i miei segreti 😛

    bye^2,     mr

    #2750
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Mi sono sempre ripromesso di condividere un po’ di informazioni legate a logiche neuroniche particolari e approfitto di quest’occasione 🙂
    In generale non sono contro i tagli nell’albero, anzi! Ci sono però pro e contro generici e specifici del mio engine da considerare.

    Il mio engine valorizza, attraverso una serie di analisi (che a volte giustamente si escludono), lo score di una posizione solo se ci si trova nei nodi foglie (i terminali dell’albero).
    Le posizioni intermedie (a parte depth 1 e, ultimodepth -1 per via della futility) non vengono analizzate, a parte i casi di stalli, matti ecc…
    Purtroppo nella generazione del mio albero (credo di aver capito il perchè, e in merito ci sto lavorando), pur essendo una roba iterativa, ad ogni nodo generato mi aumenta la memoria utilizzata dal sistema.
    In realtà la definizione di memoria utilizzata non è la parola corretta, è più corretto parlare di risorse utilizzate, rilasciate, ma operazione di garbage stranamente non effettuata, comunque dato che in pratica si nota in termini di mb (da Arena), alla fine se mi esprimo diversamente, siamo lì, ci capiamo.

    La conseguenza è che più pezzi ci sono sulla scacchiera, più nodi dovrebbe generare e più aumenta la memoria usata. Ovviamente oltre un certo limite il programma va in crash, per cui, al di là dell’operazione di fissare il baco di fondo, nel frattempo occorre usare dei ‘paletti’.

    Tali paletti li definisco all’inizio della generazione delle mosse; in pratica …
    – faccio una stima dei nodi che verrebbero generati basandomi a tutta una serie di parametri (e diciamo incredibilmente che ci vado sempre molto vicino).
    – in base a questa stima e al tempo che mi rimane per finire la partita stabilisco a priori la profondità da raggiungere.
    E’ facile vedere come spesso il mio engine, nel mediogioco non va oltre depth 3, questo succede appunto perchè ha valutato a priori che andare a depth 4 non gli conviene o per l’investimento in termini di tempo oppure perchè utilizzerebbe troppa memoria 🙁 quindi si ferma a 3.
    Quando a poco a poco i pezzi sulla scacchiera diminuiscono è chiaro che la stima dei nodi generati è inferiore e di conseguenza il ‘paletto’ di neurone si sposta da 3 a 4, 5, fino ad arrivare a 8-9 nel caso di finali con un solo pedone.

    In considerazione di questo l’utilizzo di tagli aiuta molto Neurone perchè alloca meno memoria e di conseguenza potrebbe spingersi più in là con i depth.
    Il taglio attraverso la transposition table, è stato una grande implementazione. Un po’ meno quello attraverso la futility dato che taglia molto meno e ha un pizzico di rischio da gestire.
    Quello molto indicato è il classico alfabeta: grossi tagli, grande risparmio di tempo e memoria e nessuna valutazione finale ‘sporcata’.
    Appunto sulla valutazione ‘sporcata’ volevo scrivere due righe… uno degli obiettivi del progetto Neurone è quello di usarlo anche a scopo didattico, analizzando la sua valutazione (e non solo in termini di score) della mossa scelta, ma anche di tutte le alternative.
    Un giorno (ho sempre poco tempo, ma che fretta c’è?) svilupperò una modalità di analisi che mostrerà tutti i ragionamenti che hanno portato alla scelta di una mossa piuttosto che di un’altra. Ovvio quindi che più ‘pulite’ sono le valutazioni e meglio è. In qualunque caso, in fase di analisi, penso che disattiverò i prunig potenzialmente scorretti.

    Il fatto di non riuscire ad avere grandi profondità non è una cosa che mi turba più di tanto; Neurone deve cercare di ragionare come un essere umano. Noi pensiamo per esempio che un vantaggio strutturale dei pedoni su di un lato potrà portare alla vittoria e di conseguenza non analizziamo tutti i dettagli tattici che ne potrebbero scaturire, ma cerchiamo soltanto di arrivare ad avere quel vantaggio posizionale (almeno per me è così). Allo stesso modo, è vero che Neuro ha l’occhio di falco (che comunque non è perfetto come la quescenza), ma ha anche una comprensione posizionale non da poco (valutazione statica); questo secondo me lo avvicina all’essere umano.
    Il problema dei tatticismi rimane, soprattutto in posizioni aperte, ma lo sto ridimensionando sempre più. Proprio stasera ad esempio implementerò una roba che mi aiuterà in tal senso. Si tratta di una penalizzazione basata sui pezzi indifesi che si trovano in una particolare zona della scacchiera (tale zona dovrà essere variabile in base allo status della partita; apertura(solo fascia centrale), mediogioco(quasi tutta la scacchiera a parte la prima e ultima riga) e finale(tutta la scacchiera)). Ovviamente sono tutti artifici da implementare nel contesto della valutazione statica della posizione.
    Il finale invece rappresenta un problema per tutti i chess engines, chi più chi meno… opposizione, regola del quadrato e robetta simile Neuro ce l’ha già, ma dovrei ritestar tutto perchè secondo me qualche bachetto lo trovo. Chiaramente tutto ha un senso se ci si riesce ad arrivare 😉

    Bye!
    LL

    LL

Stai vedendo 15 articoli - dal 1 a 15 (di 26 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