Cobra Draughts

Posted
Email, RSS Follow

Chi mi segue su Google+ o Twitter sa già tutta la storia. Per chi invece non lo fa eccola qui.

Un paio di settimane fa stavo pensando a quale progetto portare per l’esame di Machine Learning. Dopo aver scartato un po’ di idee perché troppo banali e altre perché troppo complesse mi si è accesa la lampadina. Ho pensato di progettare un intelligenza artificiale per il gioco della dama in grado di apprendere con l’esperienza.

Per l’apprendimento ho avuto subito le idee chiare: usare gli algoritmi genetici. Il fatto che la dama sia un gioco suggerisce subito un ambiente competitivo. Si fanno sfidare AI con parametri diversi fra loro e si selezionano i migliori, che si fanno riprodurre e di nuovo combattere fra loro. Dopo un certo numero di generazioni si ottiene un AI con i parametri migliori.

A questo punto mancava una grossa parte secondaria del progetto, un motore di gioco. Senza una AI che giochi a dama tutto il resto non è fattibile.

Dopo una ricerca infruttuosa di motori di dama adatti allo scopo ho deciso di farmelo da me. Il motore doveva avere le seguenti caratteristiche:

  • Essere discretamente veloce.
  • Essere di facile realizzazione per non diventare il collo di bottiglia nello sviluppo dell’intero progetto.
  • Offrire la possibilità di variare i parametri di analisi della damiera.
  • Offrire la possibilità di auto-sfidarsi con due coppie di parametri differenti.

Così, dopo qualche giorno di programmazione ho tirato fuori Cobra Draughts, un software damistico che soddisfa tutti i requisiti che ho elencato precedentemente. Certo, se l’avessi scritto in C (bene) sarebbe stato più veloce ma avrei aggiunto una marea di lavoro in più.

Il programma è discretamente performante, in un secondo riesce ad analizzare l’albero di ricerca fino al 6° livello, tuttavia credo che non lo spingerò oltre al 4° dato che una buona euristica (appresa automaticamente) può compensare i livelli mancanti (o almeno vorrei dimostrare questo).

Potete trovare maggiori informazioni sul progetto nell’apposita pagina google code dove presto metterò anche materiale più tecnico per chi vuole usare il programma a scopo didattico o semplicemente aiutarmi a migliorarlo.

8 comments on “Cobra Draughts”

    • Intendi l’algoritmo di apprendimento? 🙂 Non appena ho qualcosa che mi soddisfa. 🙂

        • Se ti interessa solo l’intelligenza artificiale nel progetto su Google Code c’è il codice. È nel file DraughtsBrain.py.

          http://code.google.com/p/cobra-draughts/

          Un AI per la scopa è paradossalmente più complessa di quella del gioco della Dama. Il motivo principale è che mentre Dama è un gioco a informazione completa la Scopa non lo è (non posso infatti vedere le carte in mano all’avversario).

          Questo complica abbastanza la situazione e, a mio avviso, la strada migliore è usare un approccio probabilistico (ovvero “quanto è probabile una mossa sconveniente del mio avversario se gioco la carta X?”). Se trovi un modo per rispondere questa domanda hai risolto il 90% del problema. 🙂

          • Scusa avevo visto solo Downloads e non Source (eppure lo uso pure io google code).

            Però per l’approccio probabilistico l’AI dovrebbe ricordare le carte uscite, ovviamente non può ricordarle tutte, magari quelle più importanti.

          • Di nulla. Capita 😀 Non ho messo nulla in Download perché ufficialmente è ancora in sviluppo. Ma presto ci metterò qualcosa.

            Il numero di carte che deve ricordare dipende da quanto vuoi che sia forte l’AI. Se le ricorda tutte allora hai un AI che gioca nel modo migliore possibile, altrimenti hai vari “livelli di difficoltà”. 🙂

            Il punto chiave è che per ogni mossa che può fare la tua AI devi valutare quanto sia buona la situazione di arrivo in modo da selezionare la mossa migliore e in caso di informazione incompleta puoi fare solo valutazioni statistiche. 🙂