re-deepening


Questa pagina ha una gerarchia - Pagina madre:Programmazione

Home Forum Programmazione re-deepening

Questo argomento contiene 16 risposte, ha 4 partecipanti, ed è stato aggiornato da stegemma stegemma 1 mese, 1 settimana fa.

Stai vedendo 15 articoli - dal 1 a 15 (di 17 totali)
  • Autore
    Articoli
  • #11364
    stegemma
    stegemma
    Moderatore

    L’idea del “re deepening”, di cui ho parlato all’IGT e in chat è questa: se in una iterazione ottengo che la mossa migliore ha un risultato inferiore alle aspettative (quindi non è di fatto più la mossa migliore) => torno all’iterazione precedente, per ottenere una nuova migliore mossa. Supponiamo, ad esempio, che io assegni -INFINITO ad ogni mossa che causa un fail-low, ad una certa iterazione, diciamo a ply 4:

    
    mossa: valore
    m1: 10
    m2: 50
    m3: 90
    m4: -INFINITO
    m5: -INFINITO
    mN: -INFINITO
    

    Le mosse dopo la 3 hanno tutte un valore inferiore a 90 (m3) ma non ho altre informazioni, sul loro valore. Scendo a livello 6 (io salto di 2 in 2) ed ottengo:

    
    m3: -40 ex 90
    -----------------
    m2: ??? ex 50
    m1: ??? ex 10
    m4: ??? ex -INFINITO
    m5: ??? ex -INFINITO
    mN: ??? ex -INFINITO
    
    

    Siccome m3 ha un valore molto inferiore a quello ottenuto a ply 4, quale mossa dovrò esaminare ora? L’unica cosa certa è che m2 verrà prima di m1 ma m4…mN sono state tagliate da un valore di 90, per cui potrebbero essere migliori di m2 ed m1. Qui “scatta” il re-deepening, rivalutando a ply 4, con l’esclusione delle mosse certe:

    
    m3: -40
    m2: ex 50
    m1: ex 10
    -----------------
    m4: alfa=50
    ...tutte le altre...
    

    Quindi m2/m1 non hanno bisogno di essere analizzate ma devo farlo per quelle seguenti la m3 nell’iterazione originale a ply 4. Dopo aver completato la nuova iterazione a ply 4, posso tornare a ply 6, tenendo per buona solo m3 ma partendo dalla miglior mossa seguente.

    Di solito la prima mossa ha un valore decente ma, non avendo quiescenza, nel mio caso è più probabile che ciò non avvenga.

    Non l’ho ancora provato e non so come e se funzionerà; l’algoritmo va inoltre tarato, definendo una soglia al di sotto della quale farlo “scattare”.

    #11365
    Andrea
    Andrea
    Membro

    Sembra una specie di Internal Iterative Deepening applicato alla radice.

    Come tutto va testato, magari funziona, però secondo me, la cosa più semplice da fare in caso di fail low della miglior mossa è estendere il tempo fino ad un certo limite (io permetto di usare fino a 1/3 del tempo rimanente – lo chiamo “panic time” da quando lo lessi nei log di Deep Blue 🙂 ) per cercare di risolvere il fail low e, magari, trovare una nuova miglior mossa.

    Alcuni programmi non fanno partire l’iterazione successiva se si rendono conto che è stata utilizzata gran parte del tempo allocato e quindi non avranno tempo per completare il ply successivo. Io, tendenzialmente, faccio sempre partire la ricerca alla profondità successiva proprio perché potrebbe verificarsi un fail low per la miglior mossa e quindi potrebbe estendere il tempo.

    #11366
    stegemma
    stegemma
    Moderatore

    L’iterazione alla profondità precedente dovrebbe risultare veloce, grazie alla TT (ma la devo riattivare). Sarà comunque sempre più veloce della prosecuzione con una mossa qualsiasi alla profondità maggiore. Il problema principale è che se la mossa migliore risulta pessima, non ho una mossa da giocare.

    Comunque nel mio caso non ho un fail-low della miglior mossa ma semplicemente un valore “inadeguato”. Trattandosi della prima mossa dell’iterazione, il valore minimo atteso è -INFINITO. Per avere un fail-low, dovrei usare aspiration window o qualcosa di simile, che invece non uso. Ripensandoci, un’idea potrebbe essere quella di usare come minimo il valore della seconda miglior mossa… ma sto uscendo dal tema principale 😉

    #11367

    lucaNaddei
    Membro

    E’ una buona soluzione.
    Quando implementai questa cosa Uragano guadagnò oltre 100 punti.

    Praticamente in Uragano (ed anche piccolino) quando nella nuova iterazione la mia “Best Move” ha un sensibile calo di valutazione, riduco di 1 la profondità (ovvero torno alla profondità precedente) per le restanti mosse.
    Terminata la ricerca a profondità P-1 Avrò due casi: (1) la “best move” è la stessa, pazienza ho perso tempo (molto poco, le hash hanno lavorato) (2) la “best move” è un’altra, bene! il tempo perso è ampiamente ripagato da una mossa forse più affidabile ma soprattutto dalle hash che ora contengono dati che mi serviranno ad ordinare meglio le mosse alla profondità successiva (quella originaria).

    Andrea dice: Sembra una specie di Internal Iterative Deepening applicato alla radice. –> ESATTO!

    Stefano dice: L’iterazione alla profondità precedente dovrebbe risultare veloce, grazie alla TT –> NO, se cambia la Best Move.
    Rifare la mossa alla profondità inferiore serve proprio a riempire le hash (soprattutto per l’ordinamento), in quanto alfa beta avrà potato ampiamente i rami sotto la PV forte della sua valutazione.

    Stefano dice: un’idea potrebbe essere quella di usare come minimo il valore della seconda miglior mossa –> NEMMENO
    Il valore della seconda mossa è assolutamente aleatorio con alfa-beta (o meglio è corretto solo se nella ricerca è stata analizzata prima di quella che poi è risultata la best move).

    Luca

    #11368
    stegemma
    stegemma
    Moderatore

    Infatti per “seconda mossa” intendevo la migliore delle mosse trovate prima della… ex miglior mossa 😉

    Non capisco come possa essere di nuovo la stessa la mossa migliore, quando torni indietro; per questa mossa hai già un valore “certo” (a profondità 6, nell’esempio) e non la consideri, nella ricerca che ripeti a profondità 4 per trovare la prossima miglior mossa candidata. Le precedenti mosse migliori le puoi tenere tutte, se ci sono; non ha senso invece considerare il valore certo della ex miglior mossa, perché tanto l’hai già esaminata e stai cercando la prossima.

    #11377
    stegemma
    stegemma
    Moderatore

    Rivedendo la risposta di Luca, in effetti può essere simile all’Internal Iterative Deepening; io credevo che questo fosse in realtà l’applicazione del ID ad ogni nodo, come se ogni nodo fosse la root ma forse quest’ultimo particolare algoritmo ha un altro nome (o ricade anch’esso nell’IID). Nel mio caso, non uso la PV, nel senso comune dei temrini, perché ho alfagemma invece di alfabeta, per cui il RD è un’esigenza tecnica, più che un algoritmo per velocizzare la ricerca. Sempre che funzioni, ovviamente!

    #11378

    lucaNaddei
    Membro

    IL concetto è sempre lo stesso, sia che tu abbia alfa-beta che il tuo alfa-gemma (che da quello che ho capito è un alfa beta “srotolato” e non ricorsivo); quando il programma si accorge che la mossa che riteneva migliore non è poi così buona, comincia a “pensare”, lasciandoti sospeso con una bestmove che non è poi così “best”.
    Più e scarsa la nuova valutazione di questa mossa più la finestra resta ampia e quindi più tempo impiegherà per terminare la ricerca alla profondità corrente.

    A questo punto la priorità 1 è: trovare un’altra mossa e verificare che porti ad un punteggio migliore.
    Non capisco perchè dici di non considerare il valore certo della mossa “degradata”, se passa da +20 a prof4 a -100 a prof6 io quel -100 me lo tengo, anche perchè se è stata analizzata come prima mossa (gran parte dei casi) anche a liv4, non posso sapere quanto le seconde e terze mosse siano corrette come valori; magari restituiscono +10 ma valgono tutte -infinito e scopro che la mia mossa “degradata” è l’unica che non porta al matto.

    Dimenticavo una cosa importantissima, quando succede che una bestmove degrada, vuol dire che ci sono guai in vista, quindi bisogna comunque ASSOLUTAMENTE finire di analizzare la profondità per tutte le mosse (nell’esempio che stiamo facendo la prof6).
    Nel 99% dei casi la bestmove degrada non perchè è scarsa lei come mossa, ma perchè c’è una minaccia da parare da qualche altra parte che non si può apprezzare alla profondità precedente.

    #11379
    stegemma
    stegemma
    Moderatore

    Non avendo la quiescenza, la mossa migliore può “degradare” semplicemente perché c’è una presa fuori dall’orizzonte (che, per me, è praticamente fisso a ply 6, nell’esempio). Dico di non prendere in considerazione il valore, perché comunque sto ripetendo depth 4 per trovare la miglior mossa da analizzare. Se anche fossero tutte < del tuo -100, dovrei comunque analizzarle poi a depth 6, per cui non mi interessa tanto che siano più o meno buone, mi interessa solo sapere quale è la migliore (o la meno peggiore). Se prendessi -100 come limite inferiore, rischierei di trovarmi tutte le mosse a depth 4 di nuovo a -INFINITO!

    #11380

    lucaNaddei
    Membro

    Stefano, chiedo venia, stiamo parlando di due cose diverse.
    Quando ho sentito parlare di rilanciare la ricerca alla profondità precedente l’ho associata a quello che facevo io (tradito anche da Andrea che lo aveva associato ad una specie di IID), poi non capendo ho riletto bene il tuo post ed ho realizzato.

    Comunque alcune cose restano valide:
    Stefano dice: Se prendessi -100 come limite inferiore, rischierei di trovarmi tutte le mosse a depth 4 di nuovo a -INFINITO!
    Beh questo vorrebbe dire che per ora è ancora la tua bestmove.

    Stefano dice: sto ripetendo depth 4 per trovare la miglior mossa da analizzare.
    Se il problema è una presa fuori dall’orizzonte ripetere depth4 non ti darà mai una nuova bestmove ma solo mosse casuali.
    Se a depth4 c’è una forchetta sulla scacchiera, per cui a depth6 ti ritroverai con un pezzo in meno, potrai pure scartare la bestmove, ma qualunque altra seconda mossa non sarà in grado di “valutare” la forchetta esattamente come la tua ex bestmove.
    Io faccio questo “passo indietro” solo per riempire le hash ed avere un ordinamento migliore, ma l’ordinamento inteso non come ordinamento alla radice, ma dei nodi interni mai precedentemente visitati, nodi che poi andrò a rianalizzare all’iterazione successiva.

    Stefano dice: Non avendo la quiescenza…
    Sono fermamente convinto che un motore che analizza a profondità fissa depth6 + 4depth di quiescenza vinca agevolmente contro un motore che analizza a depth10 senza quiescenza (usando anche una frazione del tempo); se hai poco tempo a disposizione prova questa come modifica.

    #11384
    stegemma
    stegemma
    Moderatore

    Purtroppo avevo fretta, per le solite urgenze di lavoro, e non mi sono spiegato bene. Siamo alla root, analizzo a depth 4 e metti che la prima mossa sia già la migliore, con un valore 90. Tutte le altre avranno -INFINITO. Passo a depth 6, sempre dalla root, e trovo che la prima vale -100. Sono ancora a depth 6, quale analizzo? Tutte le altre hanno un valore di -INFINITO e sono state tagliate dal valore 90, che era “sbagliato”. Quello che so è solo che hanno tutte un valore (a depth 4) inferiore a 90 ma non so quale sia la prima da analizzare, ora che sono a depth 6. Supponiamo anche di avere la quiescenza, il problema non cambia di molto… anzi, il valore a depth 4 è più probabilmente simile a quello a depth 6, per cui il 90 precedente è più attendibile (come limite a depth 4) ed il -100 è invece certo; questo significa che a depth 4 so che ho tutte mosse di valore inferiore a 90/d4 (90 depth 4) per cui hanno un valore probabilmente inferiore anche a 90/d6 (nell’ottica di avere la quiescenza e quindi valori abbastanza attendibili e simili tra d4 e d6). Ora però sono sempre a d6 ed ho una mossa con valore -100/d6 che prima era 90/d4 e tante mosse a -INFINITO/d4 che so essere certamente <90/d4 e probabilmente <90/d6… ma non ho il limite inferiore e neppure i valori reali a d4! Ripeto: quale analizzo per prima, a d6? Posso usare qualche euristica, cercare nella TT, consultare i tarocchi 🙂 ma la mia idea è semplicemente quella di dire: torno a depth 4 e ripeto la ricerca, scartando la prima mossa (che ha valore certo -100/d6 ma sbagliato 90/d4) per trovare la prima mossa da cui procedere a d6. Non è prudente usare a d4 il valore -100/d6 come limite, perché se poi le trovo tutte a -INFINITO sono nei guai, non potendo nuovamente procedere a d6. I valori che troverò saranno ovviamente a d4, per cui a d6 potrò trovare altre sorprese ma mi servono per procedere in modo migliore, con una mossa probabilmente più valida che non se ne prendessi una a caso della varie -INFINITO.

    PS: se trovo tutti -INFINITO a d4 con limite -100/d6 non significa che la -100/d6 sia la migliore, perché potrei trovare “piacevoli sorprese” analizzandole a d6

    #11393
    stegemma
    stegemma
    Moderatore

    Dopo alcuni aggiustamenti, ecco il primo match con re-deepening:

    
       Engine       Score  Sa
    1: Sabrina Work 5,0/6  ·· 
    2: LarsenVB     0,5/2  0= 
    2: Pentagon_12  0,5/2  0= 
    4: Piranha      0,0/2  00 
    
    #11396
    stegemma
    stegemma
    Moderatore

    Secondo match:

    
       Engine            Score    Sa
    1: Sabrina Work      6,0/16 ···· 
    2: LarsenVB          3,5/4  11=1 
    3: Satana.2.4.20.w64 3,0/4  11== 
    4: Pentagon_12       2,5/4  ===1 
    5: Piranha           1,0/4  0010 
    

    Ora manca solo la prova del 9: Sabrina RD contro Sabrina senza RD.

    #11400
    stegemma
    stegemma
    Moderatore

    Sembra che il “re-deepening” dia un leggero vantaggio al motore (ma con poche partite di test all’attivo):

    
       Engine         Score    Sa
    1: Sabrina Work   2,5/4  ···· 
    2: Sabrina 3.0.23 1,5/4  10=0 
    
       Engine         Score          Sa
    1: Sabrina Work   5,5/10 ·········· 
    2: Sabrina 3.0.23 4,5/10 ==0====0=1
    
    #11401
    stegemma
    stegemma
    Moderatore

    Nei match a 30 secondi +200ms non c’è storia (ma molti engine perdono per il tempo):

    
       Engine         Score     Sa
    1: Sabrina Work   29,5/32 ····· 
    2: Sabrina 3.0.23 1,5/4   0=10
    3: Piranha        0,5/4   0=00  
    3: Giraffe        0,5/4   =000  
    5: DarkHorse      0,0/4   0000  
    5: LarsenVB       0,0/4   0000  
    5: Pentagon_12    0,0/4   0000  
    5: Raffaela       0,0/4   0000  
    5: Neurone_XXVI   0,0/4   0000
    
    #11406
    stegemma
    stegemma
    Moderatore

    L’implementazione attuale del re-deepining non tiene conto del valore soglia ma viene sempre applicato, perché era più veloce fare così (ma non necessariamente più efficiente). Il re-deepening funziona meglio a tempi brevi forse perché non prevede un limite di profondità, per cui torna sempre al ply precedente (-2, in realtà). Sospetto inoltre di averlo implementato con una piccola svista, perché non ho messo a -INFINITO il valore attuale del livello (ovvero alfa). Visti i risultati incoraggianti, ci lavorerò ancora, possibilmente riattivando la TT (che è importante, per le prestazioni del TT). Il debugger del Visual Studio è misteriosamente “morto” e non posso debuggare!?!?!

    Questo è il mio codice della prima bozza del RD:

    
    FOR_MOVES
    {
    	[...]
    	// re-deepening
    	if(pLoopMove->alfavalue == -ENGINE_INFINITY_VALUE)
    	{
    		clsMove *pActualFirstMove = pNode->pFirstMove;
    		pNode->pFirstMove = pLoopMove; // esclude le mosse già analizzate al livello corrente
    		AlfaGemma(level - 2);            // ripete l'analisi, per determinare la migliore mossa seguente
    		SortMovesDescAlfa();           // riordina le mosse rimanenti
    		pNode->pFirstMove = pActualFirstMove;
    		--pLoopMove;
    		continue;
    	}
    	++pNode->nValidMoves;
    	ExecuteMove(pLoopMove);
    	{
    		SwapColor();
    		++pNode;
    		if(!bTimeExpired)
    		{
    			val = -AlfaGemma(level);
    		}
    		--pNode;
    	}
    	[...]
    }
    

    In Sabrina ho una funzione separata alla root, che chiama AlfaGemma (come si vede nel codice), per gestire meglio la radice. AlfaGemma è nella versione “con goto”.

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