Un filtro bayesiano può giocare a scacchi?

Pubblicato: 3 novembre 2007 in Giochi, Vaccate ipertecnologiche
Tag:, ,

Premessa: tecnicismi.
Sottotitolo: non è una domanda sciocca, non è come chiedersi: Un tostapane a pile può giocare alla morra?

Ingredienti: un classificatore bayesiano, nella fattispecie dbacl e un po’ di competenza nel gioco degli scacchi, io non ne ho ma sicuramente qualcuno di voi ne ha moltissima.

Un classificatore bayesiano è un programma che usualmente viene usato per riconoscere i messaggi email buoni nella marea di messaggi cattivi (spam) ma evidentemente il cui spettro di utilizzo non è stato ancora pienamente esplorato. Il suo lavoro è diviso fondamentalmente in due fasi, una fase di apprendimento o training nella quale bisogna insegnargli a riconoscere un po’ di pattern comuni alle mail cattive e un po’ di pattern comuni a quelle buone. Sulla base di questo training poi il classificatore è in grado di decidere se una mail ricade in una o nell’altra delle due categorie. Più in generale i classificatori bayesiani possono essere usati, generalmente con efficacia minore a dire il vero, per decidere se un dato testo appartiene a una delle “categorie” per le quali è stato effettuato un training precedente. Un esempio vincente di questo utilizzo è nei riconoscitori di lingua. Creando con il training una diversa categoria per ogni lingua (italiano, inglese, francese, spagnolo, ecc.) il classificatore bayesiano riesce molto bene a riconoscere la lingua in cui è scritto un testo solo a partire dal training e dal testo stesso.

Laird A. Breyer che incidentalmente è colui che ha scritto dbacl, si domanda in questo articolo se la sua creatura sarebbe in grado di giocare a scacchi, cioè più precisamente di effettuare una partita non completamente casuale. Sembra davvero una domanda priva di senso, cos’hanno in comune gli scacchi e lo spam?

E invece in questo lungo tutorial Laird ci dimostra passo passo come in effetti il suo classificatore bayesiano sia in grado di arrivare ad un livello minimo di capacità (sono certo che mi batterebbe, per dire), senza grandi sforzi.
L’articolo è lungo e tecnico, è in inglese ma è abbastanza semplice e molto divertente.
Ma com’è possibile tutto questo? la questione risiede tutta nel fatto che le partite di scacchi si possono descrivere con una notazione testuale, ad esempio

e4 e5 Nf3 Nc6 Bc4 Nf6 Ng5 Nxe4 Bxf7+ Ke7 d3 Nf6
Bb3 d5 Nc3 Bg4 f3 Bf5 f4 Bg4 Qd2 h6 fxe5 Nxe5 Qe3
Kd6 d4 Nd3+ Qxd3 Qe7+ Be3 Re8 Nf7+ Qxf7 O-O c6
Bf4+ Kd7 Be5 Be7 Rae1 Rhf8 Nxd5 cxd5 Ba4+ Kd8 Qc3
Bb4 Qxb4 Re6 c4 Rb6 Qa5 Bc8 c5 1-0

e agli occhi di un classificatore bayesiano questo è un testo come un altro. La “semantica” di questo tipo di testi è in effetti molto semplice, si può riassumere nei due valori “vittoria” o “sconfitta” (in realtà non è così e alcuni di questi aspetti vengono sfiorati nell’articolo, ci sono anche altre interpretazioni delle varie posizioni che potrebbero venire usate, “vantaggio” e “svantaggio” tanto per cominciare). Quindi il responso del classificatore grosso modo risponde a questa domanda: “a partire da questa posizione, qual’è la posizione successiva che più probabilmente porta alla categoria ‘vittoria’?”. La posizione non è altro che una “frase” composta da “parole” che sono le mosse ed il training non è altro che il fagli fagocitare un gran numero di partite vinte dauna parte e perse dall’altra.
Questo approccio naif porta a risultati scadenti e per arrivare ad un giocatore non proprio disastroso bisogna ricorrere a qualche trucchetto che però non altera la sostanza del discorso; la risposta alla domanda: un filtro bayesiano può giocare a scacchi? è senza dubbio sì.
Due osservazioni finali. La prima è che un grosso limite alla capacità di gioco di dbacl risiede nel fatto che il programma stesso è per sua natura limitato, cosa non vera per altri categorizzatori non bayesiani presenti in natura. La seconda è che anche il training proposto può essere notevolmente migliorato conoscendo a fondo gli scacchi, con elementi che coinvolgono le posizioni, le fasi e forse anche con l’utilizzo di altre notazioni magari più ridondanti ma più complete.

(Via)

commenti
  1. Flavio scrive:

    Un’idea interessante, leggero’ l’articolo, grazie per la segnalazione!

    Non sono totalmente d’accordo sul fatto che i classificatori bayesiani non siano bravi nella categorizzazione dei testi. Io direi che sono bravi laddove le categorie possono essere definite in termini puramente sintattici. Sta a noi creare le categorie giuste, trasportando quanto più possibile in sintassi ciò che intuitivamente consideriamo semantica. Ma la differenza fra sintassi e semantica è un terreno scivoloso e non mi ci addentro oltre. Dirò solo che qualche anno fa scrissi un semplice classificatore bayesiano con un mix di bash, awk, e altri pezzi d’antiquariato. Lo utilizzai per riconoscere articoli scientifici (solo da categorie abbastanza ristrette) e anche alcuni stili letterari (dopo averlo istruito con l’opera completa di Shakespeare, Dickens, Joyce, Kafka, e altri autori disponibili su Project Gutenberg). E’ un po’ lento, ma funziona egregiamente (anche come filtro anti-spam).

  2. miki scrive:

    Chissà come gioca a scacchi?

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...