COSA SONO LE NULL MOVES?


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

Home Forum Vecchi ma interessanti post su Yahoo gruppi COSA SONO LE NULL MOVES?

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

    Administrator
    Moderatore

    In risposta ad un post di Ivo su IHS, ho buttato giu’ rapidamente una
    descrizione qualitativa sulle nullmoves; la riporto qui per chi fosse
    interessato.

    Credo anche che sarebbe utile, se qualcuno avesse il tempo e la voglia
    di mettersi a spulciare gli archivi su egroups, selezionare i post piu’ significativi sui vari argomenti della computer chess; potrebbero
    costituire una buona base di partenza su cui sviluppare il materiale
    da mettere sul sito. Magari ciascuno potrebbe selezionare i propri
    contributi che ritiene piu’ significativi; poi in seguito si potrebbe
    vedere di sviluppare il tutto in maniera piu’ organica.

    Io per esempio a memoria ricordo di aver scritto qualcosa sulle pipes
    (a proposito della comunicazione con Winboard), sulle hash e ora sulle
    null moves; poi c’era tutta la discussione con Stefano a proposito
    della mobilita’, e qualcosa sulle bitboards.

    Che ne dite? Vi pare un’idea ottima/buona/fattibile/idiota?!

    —-8

    Ok, vediamo se mi riesce di sintetizzare in maniera chiara il concetto
    di null move; prima pero’ credo sia utile una breve introduzione
    riguardo all’algoritmo alpha-beta.

    Chi frequenta il newsgroup dovrebbe avere un’idea di come funzionano
    i programmi di scacchi; cmq, in sintesi tutto si basa sull’analisi
    esaustiva delle varianti possibili fino ad una certa profondita’, e
    sulla valutazione delle posizioni che ne scaturiscono.

    Data la crescita esponenziale dell’albero delle varianti, e’ pero’
    fondamentale “potare” il piu’ possibile i rami di tale albero, una
    volta stabilito che non sono “promettenti”. Ad esempio, se vedo che
    una data mossa lascia la Donna in presa, non e’ necessario che
    analizzi tutte le possibili risposte dell’avversario: basta
    analizzare la presa della Donna per scartare l’intera variante.

    Questa e’ l’idea di base su cui si basa l’algoritmo alpha-beta, che
    effettua una “potatura” (pruning) dell’albero in maniera
    matematicamente “sicura”, cioe’ elimina soltanto rami che e’
    _certamente_ inutile analizzare per stabilire qual e’ migliore mossa
    da giocare nella posizione di partenza.

    In pratica, visitare tutto l’albero o visitare solo i rami non potati
    da alpha-beta porta sicuramente allo stesso risultato; quindi usare
    alpha-beta porta ad un guadagno nelle prestazioni, senza perdita di
    precisione rispetto alla ricerca esaustiva (minimax).

    Purtuttavia nonostante alpha-beta la crescita dell’albero resta
    esponenziale; e’ per questo che tutti i principali programmi, sia
    commerciali che amatoriali, adottano anche altre tecniche di pruning
    le quali, pero’, non sono matematicamente “sicure”: migliorano le
    prestazioni _globali_, ma possono cadere in fallo (e quindi peggiorare
    il gioco del programma) in qualche caso particolare.

    Le null moves fanno parte di questo gruppo: se il pruning basato su
    null moves e’ ben tarato (cioe’, ne’ troppo blando ne’ troppo
    aggressivo), le prestazioni medie migliorano sensibilmente (a parita’
    di tempo il programma e’ in grado di analizzare almeno una semimossa
    in piu’); pero’ si perde qualcosa in termini di precisione tattica, e
    in posizioni particolari il programma puo’ sbagliare completamente
    strada.

    L’idea di base e’ la seguente. In alpha-beta, come accennato in
    precedenza, e’ importante non tanto dare una valutazione _precisa_ ad
    una determinata variante, quanto stabilire se tale variante e’ da
    analizzare o puo’ essere scartata senza timori, perche’ troppo
    favorevole ad uno dei due colori (e quindi verrebbe sicuramente evitata dall’altro). In pratica in ogni posizione ci sono due limiti (bounds),
    alpha e beta (alpha superiore a beta, allora la linea puo’ essere scartata ed e’ inutile analizzare tutte le altre mosse.

    Nella null move heuristic, si da’ per scontato che muovendo si puo’
    solo migliorare la propria posizione. Cioe’, se la valutazione della
    posizione e’ maggiore di beta anche quando io “passo”, cioe’ permetto
    all’avversario di muovere due volte di seguito, allora e’ ragionevole
    supporre che esistera’ una mossa che causa il pruning: se non muovendo
    affatto sto gia’ molto meglio, figuriamoci se muovo!

    Allora supponiamo di dover analizzare una determinata posizione, con
    mossa al Bianco, fino a profondita’ (per es.) pari a 7 e con limiti
    alpha = 7, beta = 220.
    Prima di considerare le varie mosse possibili, provo a vedere che
    succede se non muovo affatto: faccio una mossa “nulla”, e analizzo la
    posizione corrispondente a profondita’ 7-1-R (perche’ 7-1-R lo vedremo
    fra breve). Se ottengo un risultato >= 220, la null move ha avuto
    successo e taglio interamente il ramo; altrimenti ho solo perso tempo
    e procedo all’analisi consueta.

    Qual e’ il vantaggio di una cosa del genere?! Il vantaggio sta nel fatto che la posizione dopo la null move non la analizzo fino a profondita’ 6 (cioe’ il 7 iniziale, meno l’1 della mossa – in questo caso nulla – che ho giocato), bensi’ a profondita’ 6-R, dove R e’ il fattore di riduzione che introduco fidandomi del fatto che, non avendo giocato alcuna mossa, ho sicuramente alternative migliori a disposizione.

    Chiarisco meglio: per analizzare a prof. 7, devo giocare una per una
    tutte le mosse possibili, analizzare fino a profondita’ 6 le posizioni
    risultanti, e scegliere il risultato migliore.

    Se pero’ gioco una null move, analizzo la posizione risultante a
    profondita’ 3 o 4, fidandomi del fatto che lo svantaggio di aver
    permesso all’avversario di muovere due volte di seguito compensi
    l’imprecisione di un’analisi a profondita’ piu’ bassa.

    Ora, perche’ tutto questo funziona? Sostanzialmente perche’ i computer
    non analizzano come gli umani. Di tutte le posizioni considerate, la
    stragrande maggioranza e’ pura spazzatura: linee in cui un colore lascia in presa due o tre pezzi di seguito senza alcun motivo sono comunissime;
    e riconoscere il piu’ presto possibile (e nel modo piu’ economico
    possibile) che tali linee possono essere tagliate senza problemi e’
    fondamentale.

    In media, la null move ha successo (cioe’ permette la potatura) in
    oltre il 70% dei tentativi; e in tal caso la riduzione di profondita’
    effettiva dopo la null move (pari a 2 o 3 ply rispetto alla profondita’ nominale di ricerca) permette di impiegare un decimo o anche un
    centesimo del tempo che sarebbe stato necessario senza null move, per
    accorgersi che il ramo puo’ essere potato.

    Facendo due conti, se per l’analisi di 100 date posizione impieghiamo
    N secondi ciascuna senza null moves, con le null moves nel caso peggiore avremo: in 70 posizioni la null move avra’ successo, e quindi ce la caveremo in un decimo del tempo N; nelle restanti trenta posizioni, avremo sprecato 1/10 del tempo (al massimo! in realta’ di solito ci vuole molto, mooolto meno per accorgersi che la null move fallisce) e quindi impiegheremo 11*N/10 secondi.

    Totale:
    (senza null moves) 100*N
    (con le null moves) 70*N/10 + 30*11*N/10 = 40*N

    Con le null moves ci vuole meno della meta’ del tempo, anche
    considerando il caso peggiore! In realta’ in media guadagni di 5 volte
    o piu’ sono tutt’altro che rari; per cui l’uso delle null moves consente effettivamente di guadagnare un ply o anche due in profondita’ di ricerca.

    Vediamo ad esempio come si comporta Leila, dopo 1. e4 e5
    2. d4 d5. Senza null moves, si ha:

    Depth Score Time Nodes PV
    ————————————–
    1 0.35 0.09 67 g1f3
    2 0.12 0.10 748 d4e5 d5e4 d1d8
    3 0.35 0.16 2750 e4d5 d8d5 g1f3
    4 0.12 0.32 12136 d4e5 d5e4 d1d8 e8d8
    5 0.47 1.04 55109 d4e5 d5e4 d1d8 e8d8 b1c3
    6 0.12 3.29 189170 d4e5 d5e4 d1d8 e8d8 b1c3 b8c6
    7 0.42 16.24 1004498 d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2
    8 0.12 54.48 3359763 d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2 g8e7

    Dopo 55 secondi circa, il programma e’ arrivato a prof. 8 valutando
    3.359.793 posizioni. Vediamo ora che succede con le null moves
    abilitate:

    Depth Score Time Nodes PV
    ————————————–

    1 0.35 0.09 67 g1f3
    2 0.12 0.10 748 d4e5 d5e4 d1d8
    3 0.35 0.14 2401 e4d5 d8d5 g1f3
    4 0.05 0.31 11800 f1b5 c7c6 e4d5
    5 0.47 0.70 33870 d4e5 d5e4 d1d8 e8d8 b1c3
    6 0.12 1.88 101004 d4e5 d5e4 d1d8 e8d8 b1c3 b8c6
    7 0.42 3.38 182842 d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2
    8 0.12 10.36 591001 d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2 g8e7
    9 0.50 18.14 1039760 d4e5 d5e4 d1d8 e8d8 b1c3 c8f5 c1e3
    10 0.25 58.95 3442480 d4e5 d5e4 d1d8 e8d8 b1c3 c8f5 c1f4 b8c6
    f1c4 d8e8

    Null moves tentate: 172.078; percentuale di successo 70%.

    Quindi, per arrivare a profondita’ 8, stavolta il programma ha impiegato
    poco piu’ di 10 secondi e analizzato meno di 600.000 nodi: quasi sei
    volte meno! Casualmente lo score e la PV sono gli stessi del caso
    precedente; ma questo non sempre succede in quanto le null moves
    influenzano comunque la valutazione – anche se sarebbe meglio se non
    lo facessero!

    Inoltre, dopo circa un minuto il programma ha completato l’analisi fino a profondita’ 10: cioe’ usando piu’ o meno lo stesso tempo e visitando
    all’incirca lo stesso numero di nodi, la versione con le null moves
    abilitate e’ riuscita ad analizzare 2 ply (semimosse) in piu’! Questo
    compensa piu’ che abbondantemente gli svantaggi intrinseci nell’uso di
    null moves.

    Ma quali sono questi svantaggi?! Innanzitutto, la riduzione della
    profondita’ di ricerca dopo la null move e’ quasi sempre giustificata,
    ma talvolta puo’ portare ad errori tattici; ad esempio combinazioni con sacrificio molto profonde possono richiedere vari ply in piu’ per poter essere viste, e quindi il programma puo’ non avere tempo a sufficienza
    per accorgersene.

    E poi, l’ipotesi che “se non muovendo vinco, allora muovendo vinco
    ancora piu’ facilmente” cade evidentemente in fallo almeno in un caso
    fondamentale e ben noto: quando c’e’ di mezzo lo zugzwang! E’ per
    questo che tutti i programmi che usano le null moves le disabilitano
    quando sono rimasti pochi pezzi sulla scacchiera, dato che in tal caso
    la probabilita’ di incappare nello zugzwang e’ molto alta; ma cio’ non
    toglie che in posizioni particolari, come quella da te postata, il
    problema possa presentarsi anche con ancora molti pezzi sulla
    scacchiera.

    Li’ infatti il Nero ha ancora tutti i pezzi, per cui la null move non
    viene disabilitata; ciononostante non ha mosse disponibili! Se potesse
    realmente non muovere, non ci sarebbe alcun matto; mentre se e’
    costretto a muovere il matto c’e’… ma usando le null moves non ce ne
    si puo’ accorgere!

    Fortunatamente pero’ posizioni “null-move killers” capitano assai
    raramente in partita viva, e questo riduce notevolmente l’incidenza
    del problema sulle performance dei programmi.

    —-8

    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