COME FUNZIONA L'ALGORITMO PER LA GENERAZIONE DI MOSSE DI RAFFAELA?


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

Home Forum Vecchi ma interessanti post su Yahoo gruppi COME FUNZIONA L'ALGORITMO PER LA GENERAZIONE DI MOSSE DI RAFFAELA?

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
  • #5418

    Administrator
    Moderatore

    Stefano Gemma wrote:
    >
    > > Non ho capito… nell’algoritmo che sfrutta le BB non c’e’ nulla
    > > di simile! Puoi spiegarti meglio?
    >
    > Consideriamo solo donne,alfieri e torri. L’idea è di tenere per ogni
    > casa un elenco delle “mosse” che passano per quella casa.

    > Questa era l’idea di base. Cosa c’entrano le bb? Uno sviluppo successivo
    > mi ha portato a constatare che le mosse “annullate” dipendono dalla
    > posizione dei pezzi e che, da buon programmatore assembly, stanno in 8 bit.
    > Da qui a codificare ogni riga e ogni colonna come vettore di bit delle case
    > occupate e usarlo come indice per il vettore delle mosse di ogni pezzo, il
    > passo è stato non breve ma forzato. Per gli alfieri, è altrettanto ovvio
    > codificare ogni diagonale allo stesso modo. Tuttavia l’anologia alle bb si
    > ferma qui, perchè questo “algoritmo” richiede di lavorare con puntatori, non
    > con bit.

    Una certa analogia esiste, effettivamente, ma e’ piuttosto sfumata…
    Cmq per la precisione con le bb si lavora sempre su 64 bit, non su 8 se
    non per gli indici delle tabelle

    > Il tutto è molto inefficiente, perchè ogni mossa di un pezzo
    > comporta l’aggiornamento di almeno una lista di valori (quella delle mosse
    > che attraversano una casa). Considerato che comunque avrei dovuto scorrere
    > le liste di mosse di ogni pezzo, per trovare le eventuali prese, mi sono
    > chiesto “ma chi me lo fa fare?” )). Costa meno generare le mosse ogni
    > volta.

    Tutto cio’ con le rotated bb non e’ necessario: l’aggiornamento
    consiste in poche semplici operazioni booleane.

    >
    > > Numero di istruzioni in che senso? Se intendi “lunghezza del codice”,
    > > puo’ anche essere vero; se ti riferisci ai cicli di clock,
    > > assolutamente no: con le rotated bb e’ possibile generare tutte le
    > > mosse pseudolegali di ciascun pezzo su ciascuna casa semplicemente
    > > con due lookup in una tabella statica e un’operazione di OR booleano…
    > > Dubito sinceramente si possa fare di meglio!
    >
    > Se ho capito bene il concetto di bb, quello che mi chiedo è: “ok, con
    > una manciata di istruzioni genero tutte le mosse del mio pezzo, ora le devo
    > eseguire, partendo dalla migliore… come faccio?”. Le bb mi forniscono
    > l’indice ad una tabella contenente le mosse del pezzo? Allora devo scorrere
    > la tabella che ho indicizzato con così poca fastica.

    Guarda che la tabella contiene gia’ una bb: non devi scorrere
    assolutamente niente!

    > Se è così… non mi
    > costerebbe di meno scorrere direttamente la scacchiera? Sempre di tabelle si
    > tratta… col vantaggio che la scacchiera è più piccola e sta tutta nella
    > cache (come hai fatto notare). Ma forse non ho capito le bb.

    La seconda che hai detto!

    > Comunque un algoritmo dinamico ben studiato è
    > complesso come implementazione ma ridotto come numero di cicli. Certo che
    > anche solo 10 cicli per mossa vanno moltiplicati per una quarantina di
    > mosse. In questa ipotesi, per essere più efficienti, le bb devono eseguire
    > la prima mossa in circa 400 cicli di clock (la butto lì: circa 100
    > istruzioni C?). Il numero è abbastanza elevato per supporre che sia così, ma
    > non ho modo di verificarlo. C’è qualche volontario?

    Cento istruzioni?! In cento istruzioni C a momenti ci sta tutto il
    programma! ))

    > > Su architetture a 64 bit, che mai potrebbe esserci di piu’
    > > comodo?!

    > Ad esempio: memorizzare la posizione del pezzo con un bit nella casa
    > giusta, spostarlo con uno shift, vedere se la casa è libera con un and e un
    > sacco di altre cosette simpatiche

    Non ho capito se stai scherzando… Questo e’ appunto tutto e solo
    quello che si fa con le bb!

    > > Dimenticavo: c’e’ un punto in cui le rotated bb sono assolutamente
    > > imbattibili: la generazione delle catture, che e’ poi di solito
    > > la funzione piu’ chiamata in un programma di scacchi… Bastano
    > > sempre due table lookups e un paio di OR booleani; sfido chiunque
    > > a fare meglio!
    >
    > Su questo sono d’accordo. Peccato che la maggior parte delle catture non
    > siano la migliore mossa, il che costringe comunque ad analizzare anche le
    > mosse “tranquille”. Di certo le catture sono però la migliore risposta alle
    > peggiori mosse, in questo caso sì che sono veramente importanti.

    Il punto e’ proprio questo: i nodi, durante la ricerca, si dividono
    fra fail-low e fail-high con grande maggioranza di fail-high. Direi
    che in media almeno l’80% di nodi sono di fail-high, e cio’ significa
    che, in circa l’80% dei casi, basta generare le sole catture per
    completare la ricerca del nodo: l’efficienza della funzione di
    generazione delle catture e’ quindi di gran lunga il parametro piu’
    significativo per valutare il generatore di mosse.

    > Complimenti ad Alessandro. La ricerca scientifica si basa
    > sull’esplorazione di strade non percorse da altri, ma nulla vieta di partire
    > da dove altri sono giunti. Io esploro diramazioni forse già abbandonate,
    > perchè mi muovo senza guardare la mappa. Chissà dov’è il tesoro?

    Il primo che lo trova faccia un fischio!

    > > Grande! Credo che, scoglio dell’assembler a parte, essendo un prog.
    > > completamente originale potra’ risultare interessantissimo per tutti.
    >
    > Quasi quasi… se interessa veramente a qualcuno…

    Scherzi?! Per l’occasione sarei disposto finanche a dare una
    rispolverata ai miei manuali di assembler!

    > > > Se considerassimo le sole mosse legali, avremmo circa
    > > > 47.000.000 mosse generate al secondo… ma ovviamente il numero crollerà
    > > Il numero diminuira’ abbastanza, suppongo, per un’altra ragione:
    >
    > …ad esempio: un bacherozzolo che faceva uscire dalla routine di
    > generazione quasi immediatamente Corretto il baco, ho riprovato la
    > posizione iniziale, ottenendo un più credibile 4.000.000 di mosse in 3
    > secondi.

    Accidenti, che peccato! Avevo creduto veramente che grazie all’
    assembler fossi riuscito ad ottenere quel fantastico risultato…
    ((

    Cmq mi sa che o ho capito male io, o hai sbagliato i conti tu: il mio
    primitivo abbozzo di algoritmo con le BB genera, nella posizione
    iniziale, oltre 4 milioni di mosse al secondo e quindi risulta tre
    volte piu’ veloce del tuo!
    Uso un PII 333MHz, e il benchmark si limita a generare la lista
    delle mosse (non le gioca sulla scacchiera, ma riempie un array
    con casa di partenza, casa di arrivo e vari flag).

    > In questa posizione “sadica”:
    >
    > “-R——”
    > “–t—–”
    > “——–”
    > “—-d—”
    > “——aa”
    > “—c-r–”
    > “t–c—-”
    > “——–”
    >
    > le mosse generate sono 79.000.000 in 33 secondi (contate a mano, per non
    > turbare i tempi), quindi circa 2.400.000 mosse al secondo e circa 300.000
    > n/s.

    Nella stessa configurazione di prima, il mio generatore risulta di
    nuovo tre volte piu’ veloce del tuo: le mosse sono 80, per la
    precisione; e la generazione ripetuta un milione di volte delle mosse
    non di cattura sul mio PC impiega meno di 10 secondi (9.87 ms in
    media, ho fatto la prova piu’ volte) e quindi oltre 8 milioni di
    mosse al secondo.
    Chiamare invece sempre un milione di volte la funzione di generazione
    delle catture (per accorgersi semplicemente che non ci sono catture
    possibili) costa invece 1.57 secondi.
    Per completare il quadro, ti do’ anche i tempi per generare la
    lista delle mosse del nero (ancora, ripetuta 1 milione di volte):

    – generazione mosse semplici (5 mosse di re): 1.41 secondi
    – generazione catture (una sola, la presa della torre): 0.54 secondi

    Tieni presente che il mio algoritmo e’ standard per quanto riguarda
    le bb, non usa nessuna particolare ottimizzazione: e stiamo parlando
    di tempi per generare la lista delle mosse, non le semplici bitboards
    delle case attaccate (che costerebbe 10 volte meno).

    Qui i casi sono due: o tu oltre a generare tutte le mosse fai anche
    qualcos’altro (tipo aggiornare la scacchiera), oppure hai sbagliato
    i conti un’altra volta! )

    > > non sara’ una diminuzione sensibile quando generi tutte le mosse
    > > pseudolegali, ma si sentira’ tantissimo quando devi invece generare
    > > le sole catture: il numero di catture generate al secondo crolla
    > > decisamente man mano che la posizione si apre (questo invece con
    > > le rotated bb non succede, eheheh!)
    >
    > Ricordati che non seguo algoritmi standard… per cui le catture
    > vengono generate assieme alle altre mosse, non vengono trattate
    > diversamente.

    Forse, dato che scorri dinamicamente tutta la scacchiera per generare
    le mosse, generare le catture da sole non porterebbe a grossi
    miglioramenti nelle prestazioni; cmq qualcosa dovresti guadagnare, il
    che per quanto detto in precedenza potrebbe risultare in un guadagno
    importante sulle prestazioni complessive. Se ti e’ possibile, ti
    consiglio di provare!

    > > Suppongo che implementare una buona funzione di valutazione interamente
    > > in assembly sia un’impresa titanica: hai considerato la possibilita’ di
    > > farla in C, e sfruttare l’assembly la’ dove e’ piu’ utile
    >
    > Ho pensato anche a questo. Credo che sarà una cosa mista. Se la
    > valutazione avverrà nei nodi finali, è indispensabile che sia in assembly,
    > sennò va bene anche in C.

    Ma la valutazione nei nodi finali ci _deve_ essere… Senno’ dove la
    vorresti mettere!? ))

    > Alla radice potrebbe essere anche in Cobol, che
    > cambierebbe poco )))))))

    Ciao,
    Carmelo

    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