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 11 articoli - dal 16 a 26 (di 26 totali)
  • Autore
    Articoli
  • #2752

    prova l’alfabeta prima possibile. anche se si adatta male alla struttura del tuo programma, provalo lo stesso. anche senza ordinamento delle mosse guadagni almeno 1 ply di profondità. puoi sempre disabilitarlo in modalità analisi, ma per l’uomo-macchina DEVI averlo. sarà decisivo, fidati! 🙂

    #2753

    Se la tua ricerca tiene in memoria (parte dell)l’albero durante la ricerca, dovrai per forza limitare la profondita’, e difficilmente riuscirai ad andare piu’ in la’ di un tot. Una parte dell’albero viene comunque memorizzata nella transposition table (anche se non in forma strutturata). Secondo me dovresti usare questo meccanismo per ottenere i tuoi scopi: la TT per esempio puo’ essere usata per memorizzare il libro delle aperture (almeno io faccio cosi’). Con qualche modifica credo si possa riuscire a soddisfare anche delle “esigenze particolari”.

    Anche io (almeno in origine) avevo una idea simile alla tua circa la destinazione d’uso del mio engine: volevo che fosse un programma che io potessi usare per capire le posizioni scacchistiche, per cui in principio doveva tenere a mente delle informazioni che normalmente non servirebbero per l’analisi di un motore. Poi mi sono reso conto di un effetto fastidioso: quando il numero di nodi diventa molto alto, le informazioni che riesci a tirare fuori sono completamente incomprensibili, e quelle che non lo sono sono difficilmente estrapolabili; insomma, e’ un problema molto difficile. Alcune cose le ho lasciate, altre le ho cambiate, non cambio tutto un po’ perche’ spero che “mi si accenda la lampadina” un giorno, e un po’ perche’ tanto prima o poi dovro’ riscrivere tutto daccapo, tanto vale aspettare…

    Una cosa che inseguo da lontano e’ una valutazione delle “opportunita’ in finale”, usando qualcosa di simile al metodo Monte Carlo (data la mia estrazione… 🙂 ): visto che gli engine si basano sul fatto che il numero di nodi esplorati e’ enorme, si puo’ sfruttare questa caratteristica per fare un po’ di statistica. Una cosa che mi ha fatto pensare e’ stato un suggerimento di Jeremy Silman, quello che lui chiama “il metodo delle posizioni di fantasia”, che si basa sul cercare, nell’analisi, di visualizzare la posizione migliore dei propri pezzi, e solo dopo cercare di capire come portarli in quella configurazione (vabbe’, ho un po’ semplificato…). Non ho ancora messo bene a fuoco, ma c’e’ qualcosa che credo si possa importare in contesto Computer Chess: se poi funziona o meno, e’ un altro paio di maniche, per quello ci sono i test 😉 Infatti dovrei iniziare a farli anche io 😀

    More on this later…

    bye^2,     mr

    #2754
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    @Edo: Yes! Di questa settimana faccio la funzioncina Pezzi_a_c****(Zona_rischio as integer) as integer e poi vedo di implementare l’alfabeta (alla buon’ora) 🙂

    @Mauro:Il libro di aperture lo leggo ogni volta, per cui sapevo già potere essere essere cosa buona e giusta leggerlo una volta sola ma avere i valori ‘dentro’ (magari in due ‘hashine’ separate) ma lo metterei dopo l’ab come implementazione.

    Pour parler in testa mi frulla un’idea un po’ strana e che devo perfezionare 🙂 ma di certo non sbagliata; mi spiego attraverso un esempio:


    mossa 30 Neuro score + 0.20
    mossa 30 Avv.
    mossa 31 Neuro score – 2.20

    ovviamente a Neurone è sfuggito qualcosa. Man mano che Neurone migliora (con l’evoluzione delle versioni) è possibile che nella posizione della mossa 30 Neurone non sbagli più. E’ possibile, forse probabile ma non è detto che non succeda.
    … e se Neurone riconoscesse la posizione ‘critica’ attribuendo direttamente un -2.20 alla mossa presa precedentemente in esame e andando avanti come di consueto nell’analisi?
    Sicuramente quell’errore non lo rifarebbe. Ok, basta memorizzare in un bellissimo file le fen critiche e le valutazioni per mossa da considerare (sconsiderare). Tutto bello-bellissimo? Nooo (ovviamente), ci sono alcune considerazioni da fare (proprio quelle che mi vengono im mente, ma sicuramente ce ne saranno altre.
    – l’incredibile numero di posizioni
    – la profondità di analisi
    – la forza dell’avversario

    Se però adottiamol’uso del chess engine in modo automatico, con avversari ad hoc, a cadenze luuuunghissime (e aggiungendo un minimo di ragionamento legato agli score di 5-6 mosse avanti) potrei anche non scartare l’ipotesi di implementare tale feature.

    Mah, valuterò meglio dopo l’uomo-macchina.

    Bye!
    LL

    LL

    #2755

    Riguardo alla tua idea strana, confesso di non avere capito un granche’. Dici di segnare le posizioni critiche del libro di aperture? Molti motori hanno questa funzione di learning, non so quanto funzioni, ma sicuramente e’ sensata. Se invece dici di estendere anche alle posizioni oltre l’apertura, anche se esistono progetti analoghi (vedi Encyclopaedia of chess – EOC – di Ed Schroeder) non so veramente quanto si riesca a coprire al di la delle aperture, io cmq non mi aspetterei risultati grandissimi per il motore.

    Insomma, se vuoi fare un libro delle aperture “annotato” dal motore, o addirittura un libro esteso, voto per te, se intendi estendere il meccanismo oltre, nel mediogioco, ho molti dubbi (che essenzialmente ricalcano almeno in parte i tuoi).

    bye^2,     mr

    #2756
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Diciamo che sono per il meccanismo esteso. Penso che sarà tempo perso, ma prima o poi lo provo, proprio per passarmi lo sfizio.

    Bye!
    LL

    LL

    #2757
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Ho dato una letturina veloce a http://www.rebel.nl/rebel10e.htm (è quello che intendevi?)
    La logica è simile solo che la mia implementazione parte direttamente dal confronto con gli avversari di conseguenza il file verrebbe ad essere sempre aggiornato e basato su posizioni successe a Neurone e non ad altre persone (gm). In più facendo come ha fatto Ed si corre il rischio di importarsi una quantità di roba inutile; il suo programma potrebbe trovare la soluzione da solo, mentre su Neurone tale implementazione partirebbe dal concetto di posizione critica ossia posizione dove Neurone normalmente sbaglia.

    Bye!
    LL

    LL

    #2824

    Ritornando al futility pruning, ho provato varie alternative e finalmente ne ho trovata una che mi soddisfa. La conversazione in chat con Luca N è stata decisiva! Ora taglio tutti i nodi a depth 1 che hanno valutazionestatica>beta+margine dove il margine dipende dal pezzo in presa di maggior valore. La chiave di volta è non troncare l’analisi se l’avversario ha un pedone in settima, così in finale non prendo cantonate!

    Alla prossima,

    &d0

    #2828

    Administrator
    Moderatore

    Quindi hai implementato (anche tu) la funzione ‘Valore pezzo in presa’ all’interno della valutazione statica?
    Quanto hai guadagnato?

    Bye!
    LL

    Le faq sono nel menu principale, sotto Documentazione! 😉

    #2829

    In realtà ho scritto una routine “FutilityPruning” (che fantasia!) che restituisce vero/falso da invocare all’inizio di ogni nodo a depth 1 se il proprio re non è sotto scacco. La routine controlla che non ci siano pedoni in settima e poi genera tutte le mosse di cattura dei pezzi avversari e calcola qual è il pezzo di maggior valore in base alle tabelle dei pezzi. Se valutazionestatica > beta + massimovalorepezzoinpresa allora restituisco vero e l’analisi della posizione non viene fatta. Non ho fatto calcoli precisi, nelle partite a 1’+1″ vale una trentina di Elo in più. Per cadenza più lunghe dovrei guadagnare ancora di più.

    Il prossimo passo sarà riimplementare la mossa nulla, mi tocca un’altra tornata di test+test+test+test+… magari dopo le vacanze! 😀

    #2830

    Dimenticavo: pedoni in settima dell’avversario, poiché magari non posso impedirne la promozione – cosa di cui la ricerca quiescente si accorgerebbe – e se poto prendo cappelle. Altra cosa importantissima: prima di invocare la routine FutilityPruning controllo le patte per ripetizione, per insufficienza di materiale, per le 50 mosse e l’hashtable.

    #2831
    Lissandrello Luca
    Lissandrello Luca
    Moderatore

    Mi sa che la Barbiso stavolta se le prende 😉

    Io la futility l’ho implementata, ma sono ancora fermo al margine ‘quasi’ fisso perchè sto verificando la bontà della mia tabella dei pezzi indifesi… Ogni volta la devo ritoccare e quando mi sembra tutto a posto ecco che i test mi tornano -20 punti elo!

    Robe simili mi sono successe quando attribuivo bonus troppo ‘crescenti’ al pedone passato. Fissata quell’anomalia (che in rarissimi casi portavano Neurone a buttar via allegramente un bel pezzo per un pedone ‘probabilmente’ passato) ho ottenuto un -40 punti elo!

    Alla fine questa stupidaggine mi sta prendendo un sacco di tempo e forse non ce la faccio ad implementare l’ab per l’uomo-macchina.
    Purtroppo sono abituato a finire una cosa prima di cominciarne un’altra.
    Comunque dài, ormai sono al buono, nel senso che se non funziona riprendo la branche vecchia e riparto da lì (vaffa alla tabella) 🙂

    Bye!
    LL

    LL

Stai vedendo 11 articoli - dal 16 a 26 (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