LA DIMENSIONE DELLE TABELLE DEI FINALI E' SEMPRE LA STESSA?


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

Home Forum Vecchi ma interessanti post su Yahoo gruppi LA DIMENSIONE DELLE TABELLE DEI FINALI E' SEMPRE LA STESSA?

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

    Administrator
    Moderatore

    Ciao Claudio
    Claudio wrote:—– Original Message —–
    From: rigel_g@iol.it
    To: g_6@egroups.com
    Sent: Saturday, December 30, 2000 4:51 PM
    Subject: Re: R: [g_6] benvenuto a rigel_g
    Caro Claudio,
    Mi spiace deluderti ma purtroppo la dimensione dei miei file di finali è maggiore di quella di Nalimov. In compenso le mie statistiche sono più corrette perché Nalimov considera alle volte casi uguali per simmetria, ma questo non c’entra con la dimensione fisica dei file.
    Sto in questo momento riscrivendo il programma ed anche l’indicizzazione dei file che saranno più piccoli di quelli attualmente presenti sul mio sito, ma non riesco proprio a capire come faccia Nalimov ad ottenere dimensioni minori delle mie ultime. Proverò, quando ho tempo, a guardare nel suo codice. Sto inoltre tentando con la mossa retrograda che funziona perfettamente su finali banali tipo RDR o RTR ed aumenta molto la velocità, ma mi va in crisi quando vi sono finali in cui può avvenire cattura o promozione perché in tali situazioni bisogna eseguire una mossa normale. Mi ci vuole un’idea …Beh, le tabelle di Nalimov non sono le ultime arrivate… :) Io ancora non ho provato a fare qualcosa del genere, ma, vista la velocità con cui le tablebases Nalimov sono diventate ormai uno standard, penso che alla fine mi piegherò passivamente senza cercare di sviluppare qualcosa di originale.
    Hai disponibile uno schema o un documento che spieghi procedimenti e algoritmi da te usati? Penso potrebbero essere molto utili e rientrare di diritto negli argomenti tecnici del sito.ciaoSull’algoritmo per generare i database dei finali ho scritto pochi e sparuti appunti allo scopo di ordinare le idee e fare mente locale sui punti che non riuscivo a risolvere sul momento.
    Per scrivere qualcosa di ordinato ci vorrebbe molto tempo, tuttavia incomincio a buttar giù qualche idea sull’algoritmo in forma sintetica per te e per coloro che fossero interessati e che volessero accingersi a fare qualcosa in questo campo:

     

    I problemi sono principalmente due:
    1. Algoritmo di indicizzazione

    Per un dato finale (prendo RDR in notazioni nostrane come esempio) io devo crearmi all’interno della memoria (su disco i tempi di calcolo crescerebbero di un migliaio di volte o più) due vettori che contengono 1 byte per ogni disposizione possibile dei 3 pezzi sulla scacchiera. I vettori sono due perché il primo considera la mossa al B, il secondo la mossa al N. In questi byte andrà messo un codice che indicherà il risultato trovato. Disponendo di 256 combinazioni ne attribuirò circa metà alle vittorie e lo stesso alle sconfitte in quanto devo anche ricordare il numero di mosse con cui conseguo il risultato. Inoltre dovrò avere un codice per la patta, un codice per la disposizione illegale e un codice per l’inizializzazione, che serve a indicarmi, nel corso del calcolo, quali posizioni non ho ancora calcolato. Io ho aggiunto un codice per lo stallo, distinto dalla patta. Inoltre se vai a vedere sulle mie statistiche trovi un’informazione paradossale: patta in n mosse! Questa informazione ha significato solo per le statistiche e indica il ciclo a cui ho potuto decidere che il risultato migliore di quella posizione era la patta. Nel caso RDR, mossa al N, vi sono posizioni in cui il RN nero può mangiare la DB e pattare, ma il programma (stupidissimo come tutti i programmi!!!) immagina che vi siano possibilità di vittoria per il N, e si decide alla patta solo quando vede che tutte le altre mosse portano alla sconfitta!

    Ora tornando a bomba io devo creare una corrispondenza biunivoca tra l’indice del vettore e la disposizione dei pezzi. In questo caso il sistema più semplice (orrore!) sarebbe quello di pensare che esistono 64*64*64 disposizioni per RDR (l’ordine dei pezzi deve restare fisso) per un totale di 256k posizioni per ciascun vettore, di cui in realtà solo 18081 con mossa al B e 28056 con mossa al N (Nalimov ottiene un valore diverso perché considera alcune posizioni duplicate) sono legittime e strettamente necessarie.
    In questo caso il meccanismo di indicizzazione sarebbe rapidissimo ma l’occupazione di memoria sarebbe folle per un caso così semplice.

    Posso diminuire questo numero:

    64*63*62 = 249984 – Se l’ordine dei pezzi è fisso il primo ha 64 caselle a disposizione, il secondo 63 e il terzo 62. Anche qui pochi problemi per passare da disposizione ad indice e viceversa.
    10*63*62 = 39060 (incominciamo a ragionare: le mie vecchie tabelle) – Poiché non vi sono pedoni quasi tutte le disposizioni dei pezzi hanno altre 7 disposizioni simmetriche ed il RB può collocarsi solo in 10 posizioni distinte (a1,b1,c1,d1,b2,c2,d2,c3,d3,d4) tutte le altre essendo riconducibili per simmetria a queste. Qui il problema si complica perché ogni volta che nel corso del calcolo eseguo una mossa devo trasformare la nuova posizione in modo che il RB sia in una delle citate caselle.
    462*62 = 28644 (le mie nuove tabelle) – I due Re sono considerati sempre insieme, tanto esistono sempre e possono occupare legalmente solo 462 posizioni (non è difficile contarle, ma neanche facilissimo). In questo caso l’ordine dei pezzi è (RB+RN)-DB. I due Re devono essere trattati in blocco e per calcolare l’indice dalla posizione e viceversa sono necessarie due tabelle per trattare i Re. Si deve tenere presente che il vincolo di tempo è fondamentale per questi calcoli e l’uso delle tabelle è sempre migliore dell’impiego di un algoritmo. Questo vale anche per i programmi di gioco.

    Vi sono poi il problema dei pezzi duplicati che generano N*(N-1)/2 posizioni (se fossero n sarebbe N*(N-1)*…(N-n+1)/n!) e il problema dei pedoni che possono occupare solo 48 caselle e i pedoni duplicati, ecc.
    Nalimov riesce a stare più contenuto di me nel dimensionare i vettori, riuscendo ad eliminare dal conto posizioni illegali in cui chi muove potrebbe mangiare il Re avversario, ma come ti dicevo, devo guardare come fa: usa certamente delle tabelle e probabilmente al crescere del numero dei pezzi deve disporre di ulteriori tabelle, mentre il mio programma, in teoria solamente!, potrebbe calcolare tabelle con qualsiasi numero di pezzi.

    Inoltre tbgen è molto veloce, circa 2 volte più del mio nei casi fino a 4 pezzi e di più ancora per i finali a 5 pezzi, credo principalmente a causa dell’algoritmo di indicizzazione, e (forse?) anche nella generazione delle mosse.

    2. Algoritmo di calcolo

    Immagina di aver costruito le tabelle in memoria e di averle inizializzate, dopo aver marcato le posizioni illegali (e su queste ultime un altro discorso che una volta iniziai su IHS…).
    Adesso eseguo il ciclo 0 scandendo prima tutte le posizioni con mossa al B cercando quelle posizioni in cui il B non ha mosse possibili. Marco queste posizioni come sconfitte in 0 mosse o stallo se il Re non è sotto scacco. Nel caso particolare RDR non ne esistono, ma se ora scandisco le stesse posizioni con mossa al N, ne troverò un certo numero.

    Ora eseguo il ciclo 1, poi il ciclo 2, poi il ciclo 3, ecc. fino ad esaurimento, scandendo ogni volta la tabella prima con mossa al B e poi con mossa al N, naturalmente saltando le posizioni già calcolate ai cicli precedenti.

    Ad es. nel ciclo 1 scandisco il vettore delle posizioni con mossa al B per ogni posizione irrisolta e ne calcolo tutte le possibili mosse legali verificando se almeno una mossa mi porta ad una posizione che controllata nel vettore delle posizioni con mossa al N è una posizione di sconfitta del N. Se succede così, allora la posizione che sto analizzando è una posizione di vittoria del B in 1 mossa e quindi la marco come tale. In alternativa potrebbe accadere che tutte le mosse del B mi portano a mosse in cui il N vince: in questo caso la posizione che sto analizzando sarebbe una sconfitta in 1 mossa. Poi sempre per il ciclo 1 ripeto analogamente la cosa per il N scambiando i ruoli. Quindi passo al ciclo 2 e ripeto tutta la procedura e così via, fino a quando il numero di vittorie o di sconfitte non cresce. A questo punto marco come patte tutte le posizioni rimanenti.

    Il metodo della mossa retrograda che sto provando ragiona invece su questo concetto: nel corso del ciclo 0 con mossa al B, se io trovo una sconfitta del B allora io procedo all’indietro con tutte le possibili mosse retrograde del N e trovo tutte le vittorie del N in una mossa. Non proseguo su questo argomento perché la lettera diventerebbe lunga. Questo metodo, anche secondo Nalimov, dovrebbe essere molto più veloce ma vi è un punto che non so risolvere in modo soddisfacente

    I punti esposti sono solo i principali, ve ne sono moltissimi altri di dettaglio che però devono, come tu sai, essere tutti risolti. Poi si scoprono un sacco di eccezioni, di buchi, ecc.

    Ti aggiungo infine due considerazioni generali:

    il tempo, oltre alla memoria, è un fattore criticissimo e l’ottimizzazione deve essere spinta al massimo soprattutto in quelle funzioni ripetute anche miliardi di volte.
    le tabelle vanno calcolate con vincoli di sequenza. In altre parole se io calcolo un finale RDRD devo aver prima calcolato il finale RDR per tener conto dei casi in cui vi è una cattura e poter conoscere il risultato da tabelle già calcolate. Lo stesso dicasi per RPR, per il quale devo possedere già le tabelle RDR ed RTR (RAR ed RCR non le calcolo perché sono patte matematiche) che mi servono in caso di promozione.
    Spero, sia pure in via approssimata, di essermi spiegato e di averti messo una pulce da qualche parte …al fine di spingerti a scrivere un programma. Quando si riesce a realizzare un qualcosa che funzioni in questo campo si ha una grandissima soddisfazione … spirituale s’intende!
    Se per caso provi i miei programmi (anche in versione non ultima dovrebbero funzionare correttamente!) cerca con “glfs” l’unico caso del finale RTRC vinto dal B in 40 mosse e poi analizza la posizione con “gifs”. Le prime 32 semimosse sono obbligate!
    Ti aggiungo che a mio avviso vi sarebbe moltissimo lavoro da sviluppare in questo campo, ma ci vorrebbe un gruppo di persone che lavorano insieme a pieno tempo su macchine al top per CPU e memoria, compreso un matematico (io non lo sono, e poi sarebbe meglio una matematica …) per gli algoritmi di compressione.

    Ciao
    Guido

    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