Face Detection e Face Recognition in Python – Test su Matrix Reloaded e Game of Thrones

Uno dei post che ha generato il maggior interesse in questo blog è certamente quello dedicato alla face detection tramite OpenCV. Riprendiamo questo tema dopo molto tempo parlando degli algoritmi alla frontiera per il Face Detection e Face Recognition. Lo scopo del post è fare il punto sullo stato dell’arte ed indirizzare verso mouduli open source liberamente e facilmente utilizzabili nelle applicazioni reali.

Matrix Reloaded – The Architect

La Face Detection è l’elaborazione che ha lo scopo di rilevare la presenza di volti umani all’interno di un’immagine digitale; nel precedente articolo è stata affrontata solo questa tematica attraverso algoritmi tradizionali ma consolidati.

Gli algoritmi di Face Detection si sono evoluti nel tempo migliorando l’accuratezza della rilevazione anche attraverso l’uso di reti neurali convoluzionarie (CNN) o reti Deep Learning opportunamente strutturate ed addestrate; tale processamento sfrutta massivamente l’eventuale presenza di moderne GPU o NPU per aumentarne l’efficienza ed il parallelismo. Nel nostro caso specifico ci siamo limitati al riconoscimento di volti umani in posizione frontale.

Matrix Reloaded Architect – Face Detection Benchmark MTCNN

Il benchmark estremo che ho utilizzato per mettere alla prova i moduli python individuati, è un breve video tratto dal dialogo tra Neo e l’Architetto in Matrix Reloaded; nel video, in un’atmosfera surreale, sono presenti innumerevoli volti che variano rapidamente per dimensione, inclinazione, espressione, presenza o meno di occhiali. Un video estremo di prova che farà friggere neuroni e sinapsi anche alle più evolute e performanti reti neurali convoluzionarie.

Questo è il video che è stato prodotto attraverso la nostra elaborazione:

Il Benchmark che ho utilizzato per la Face Detection in Python – L’architetto in Matrix Reloaded – questo è il risultato ottenuto tramite l’uso del modulo MTCNN insieme ad OpenCV che ho usato per l’elaborazione del video

Il modulo Python che, almeno nei miei esperimenti, ha dimostrato i migliori risultati in termini di qualità e prestazioni è MTCNN; in esecuzione su una sessione Colab con GPU attiva elabora efficientemente il flusso di frame con un livello di accuratezza molto alto se si escludono i volti in posizione non frontale. Nel video prodotto si trova l’esito dell’elaborazione dove, oltre ai volti, sono stati marcati anche alcuni punti caratteristici del viso (occhi, naso, estremi della bocca). Questo modulo è quello che riesce a rilevare meglio volti di dimensioni più piccole e non perfettamente allineati garantendo anche un’efficienza molto più alta degli altri moduli provati; MTCNN fornisce, per ogni volto rilevato, anche un livello di confidenza nella rilevazione (in tutto il video ho trovato solo un falso positivo pertanto non ho ritenuto necessario introdurre una soglia).

Il Trono di Spade – foto usata come base per l’apprendimento dei principali personaggi

In alternativa, si propone l’uso del modulo: face_recognition che ha comunque garantito un’ottima precisione su volti di dimensioni significative ed un’efficienza adeguata; su tale modulo è possibile variare l’algoritmo di rilevamento (CNN o HOG) ed effettuare del tuning per cercare di rilevare volti di dimensioni minori. Sul benchmark utilizzato la rilevazione CNN non riusciva ad intercettare gli stessi volti di MTCNN mentre la rilevazione HOG, oltre a non velocizzare molto il processamento, riduceva drasticamente il numero di volti rilevati. In condizioni normali anche questo modulo è da considerare un’ottima scelta e noi lo useremo per effettuare anche il Face Recognition. Questo modulo può richiedere un quantitativo di memoria sulla GPU più elevato soprattutto se si vogliono rilevare i volti con dimensioni più piccole.

Tutti i personaggi sono stati correttamente rilevati

Dopo aver rilevato ed isolato i volti, l’elaborazione della Face Recognition ci permette l’associazione di un volto ad una persona. In assenza di informazioni o di preappendimento sulle persone da ricercare, è possibile aggregare i volti su possibili individui basandosi sulla similitudine delle caratteristiche fisiologiche e biometriche. Gli algoritmi per effettuare tale riconoscimento, per codificare un volto in un insieme di parametri comparabili sono davvero molteplici e tutti estremamente interessanti. Anche in questo caso le reti neurali convoluzionarie (CNN) offrono un contributo importante a questi algoritmi.

Tutti i personaggi sono stati correttamente rilevati ad eccezione di Missandei che non era presente nella foto iniziale

Per implementare un Face Recognition in pochissime righe di codice Python ed in modo efficiente è possibile usare il modulo face_recognition; se si vuole approfondire come questo modulo funziona internamente vi consiglio di leggere questo aricolo.

Tutti gli attori presenti nel file di training sono stati correttamente rilevati anche senza abiti ed acconciature di scena. Come atteso Drogo non viene rilevato perché non presente nel file di training.

In questo caso ho creato un notepad colab di test che da una foto iniziale acquisisce le caratteristiche fisiologiche e biometriche dei vari personaggi della serie Il Trono di Spade; il modulo utilizzato, alla versione attuale, dovrebbe rappresentare ciascun volto tramite 128 parametri caratteristici.

tutti gli attori presenti nella foto di training sono stati rilevati anche Daenarys che appare molto differente rispetto al personaggio interpretato

Per testare il rilevamento ho provato a far riconoscere i personaggi su altre foto contenenti anche personaggi non presenti all’interno della foto di apprendimento; i risultati sono impeccabili. Il modulo utilizzato ha un’accuratezza eccellente sia per quanto riguarda i personaggi appresi che per quelli non analizzati che non ha mai classificato come falsi positivi.

anche in questo caso tutti gli attori presenti nella foto di training sono stati individuati correttamente

Per spingere oltre il test abbiamo avviato la detection su foto in cui gli attori non appaiono con i costumi di scena ed hanno acconciature o il colore dei capelli totalmente differente dai personaggi che hanno interpretato; anche in questo caso l’algoritmo non sbaglia e non rileva mai falsi positivi.

Anche se non ho effettuato delle prove dirette, sono convinto che l’algoritmo scali bene all’aumentare del numero delle persone da rilevare; non ho provato a sottoporre qualche foto degli attori quando erano più giovani.

NOTEBOOK COLAB – UTILIZZATO PER LA FACE DETECTION E FACE RECOGNITION

Concludiamo dicendo che oltre alla Face Detection ed alla Face Recognition ai volti possono essere applicati altri algoritmi per l’estrazione di caratteristiche molto importanti come la rilevazione del sesso, dell’età, del sentimento (es. rabbia, gioia, paura, sorpresa, …).

Fatemi sapere i vostri pareri e le vostre esperienze su Face Detection, Face Recognition nei commenti.

Share

Kaggle Competition – Titanic – Machine Learning from Disaster – Predict survival on the Titanic

L’RMS Titanic è stato un transatlantico britannico della classe Olympic naufragato nelle prime ore del tragico 15 aprile 1912, durante il suo viaggio inaugurale, a causa della collisione con un iceberg avvenuta nella notte.

La sfida proposta da Kaggle: Titanic – Machine Learning from Disaster alla quale ho aderito, richiede l’analisi di un dataset contenente informazioni relative ad un sottoinsieme di passeggeri imbarcati sul Titanic con lo scopo di realizzare un modello predittivo che sia in grado di classificare al meglio se un determinato passeggero si salverà dal naufragio.

tassi di sopravvivenza per classe

Alcune delle informazioni disponibili per l’analisi, di cui occorre individuare il livello di correlazione con la probabilità di salvezza, sono: sesso, età, cabina, classe, ponte, numero di parenti a bordo, porto di imbarco, tariffa pagata; moltissime altre informazioni possono essere derivate da elaborazioni più o meno complesse ed implicite tra i dati disponibili come ad esempio dai nomi completi è possibile risalire ai titoli, ad alcune professioni o anche spingersi al raggruppamento delle famiglie.

La grande sfida è quella di spingere al massimo l’accuratezza del modello predittivo al fine di classificare al meglio un insieme di passeggeri di test di cui non è nota la sorte; solo dopo la sottomissione a Kaggle si scoprirà il livello di accuratezza raggiunto.

Il modello predittivo di base che occorre superare e contro il quale ci si deve confrontare, che ho definito come modello baseline, assume semplicemente che tutte le donne si salveranno; applicando questa condizione elementare, si raggiunge un’accuratezza dell’insieme di passeggeri da classificare di poco superiore al 76%.

modello baseline: tutte le donne si salvano raggiunge un’accuratezza dello 0.76555

Questa competizione è un’ottima introduzione alla piattaforma Kaggle e richiede lo sviluppo di tutte le fasi di costruzione di un modello predittivo: analisi dei dati, preparazione e raffinamento dei dati, visualizzazione dei dati, costruzione del modello, validazione del modello e della sua accuratezza, comprensione della piattaforma Kaggle.

Nel mio notebook ho deciso di affrontare la sfida in Python costruendo un modello tramite la libreria XGBoost nota sia per essere alla base delle migliori implementazioni all’avanguardia del settore ma anche perché alla base dei modelli vincenti delle competizioni Kaggle. Tale libreria implementa il framework Gradient Boost in modalità estremamente scalabile, efficiente e portabile.

La mia implementazione, già completamente funzionante, è ancora in evoluzione è raggiungibile a questo indirizzo:

Kaggle Competition – Titanic – Machine Learning from Disaster – Predict survival on the Titanic – Luca Amore

Share

AI: Pac-Man and Ms Pac-Man

E’ da molto che non scrivo in questo blog; semplicemente sono stato impegnato in alcuni progetti che non reputo ancora pubblicabili.

Voglio segnalarvi due interessanti riferimenti nel campo dell’AI, computational intelligence, machine learning; argomenti di cui mi sto occupando in questo periodo.

The Pac-Man Projects

Come base degli esercizi per un corso di intelligenza artificiale, presso l’università di Berkeley, viene proposto agli studenti di sviluppare in python alcuni algoritmi all’interno del famoso gioco del Pac-Man; il corso termina con un multi-player contest.

The Pac-Man Projects

Trovo questa idea geniale e molto efficace dal punto di vista didattico.

Il materiale può essere liberamente utilizzato come base per corsi di intelligenza artificiale ma si richiede di non pubblicare online le soluzioni dei problemi posti.

Pac-Man

Ms Pac-Man vs Ghost Team Competition

Per chi volesse cimentarsi nello sviluppo in java di algoritmi che pilotano Ms Pac-Man o la squadra dei quattro fantasmi è stata organizzata un’avvincente competizione:

Ms Pac-Man vs Ghost Team Competition

Un risultato interessante (che mi sorprende) è che i punteggi ottenuti dai migliori giocatori artificiali sono molto più bassi di quelli umani.

Tra i vari algoritmi utilizzati: Ant Colony Optimization, Genetic Programming, Neural Networks, Influence Maps, Minimax, Rule Based.


Share

Cammelli labirinti e depth-first search: realizzazione di un generatore e risolutore di labirinti in Perl

labirinto 20 x 20 generato da maze.pl

Se Téseo (Θησεύς), eroe spregiudicato nonchè figlio del re ateniese Ègeo (Αἰγεύς), avesse conosciuto qualche rudimento di Perl, avrebbe potuto risolvere brillantemente il problema del Labirinto di Cnosso adottando l’algoritmo deep-first search, sconfiggere il Minotauro (Μινώταυρος) Asterione ma – soprattutto – non avrebbe spezzato il cuore della povera Arianna (Αριάδνη), figlia di Minosse e Pasifae (ed anche madre del Minotauro), seducendola per ottenere il risolutivo gomitolo di filo rosso (un surrogato di stack analogico ideato da Dedalo ) per poi abbandonarla ancora dormiente nell’isola deserta di Nasso (pare pure dopo una lunga notte di “festeggiamenti” nella sua nave).

A chi mi obietta – ingiustamente – che ai tempi non era disponibile un interprete Perl così come un notebook agevolmente trasportabile in un Labirinto, ma anche a tutti gli altri che gridano vendetta contro il comportamento di Téseo nei confronti della povera Arianna, consiglio vivamente la lettura dell’avvincente leggenda del Minotauro; scoprirete che la storia di Téseo, per opera di Poseidone, si conclude in modo tragico a causa dell’inversione di un’informazione booleana (1 bit) ma vitale: il colore delle vele della sua imbarcazione.

Dopo questa mitologica premessa, certo di esser perdonato per eventuali errori sulla mitologia greca, sperando di non deludere il forse unico temerario lettore che avrà avuto l’ardore di proseguire nella lettura di questo articolo, vi presento un semplicissimo generatore e risolutore di labirinti scritto interamente in Perl.

Labirinto 60 x 40 generato da maze.pl

Questo progetto è ispirato da un articolo che ho letto nel blog di Eriol in cui il problema viene affrontato in Python.

In rete esistono anche molti riferimenti sui labirinti (storia, classificazione, generazione, risoluzione, miti e leggende) dove è piacevole perdersi:

Nella mia implementazione, esaltando alcune caratteristiche tipiche del Perl, ho progettato delle strutture dati leggere ed efficienti (memorizzo solo le aperture del labirinto) ed ho adottato la versione dell’algoritmo depth-first search ricorsiva sia per la costruzione del labirinto (metodo Maze::asterione) che per la ricerca del percorso che conduce dall’ingresso all’uscita (metodo Maze::teseo).

Sono disponibili:

l’output del labirinto generato e risolto in modalità ASCII (Maze::toText):


lookee@grog:~/devel/maze$ ./maze.pl

+..+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|..|.. ..|              |  |           |           |        |
+..+..+..+  +--+--+--+  +  +  +  +--+  +  +  +--+  +  +--+  +
|.. ..|..|  |              |  |  |     |  |     |     |     |
+--+--+..+  +--+--+--+--+  +  +  +  +--+--+--+  +--+--+  +--+
|.. .. ..|              |  |  |  |              |     |  |  |
+..+--+--+--+  +--+--+  +--+  +  +--+--+  +--+--+--+  +  +  +
|..|.. .. ..|  |     |        |     |     |        |     |  |
+..+..+--+..+  +  +  +--+--+--+--+  +--+--+  +--+  +  +--+  +
|.. ..|  |..|     |  |           |  |        |     |        |
+--+--+  +..+--+--+  +--+  +--+  +  +  +--+--+  +--+--+--+--+
|        |.. ..|  |     |     |  |     |.. ..|     |        |
+  +--+--+--+..+  +--+  +--+  +--+--+  +..+..+--+  +  +--+  +
|           |..|              |.. ..|  |..|.. ..|        |  |
+--+--+--+  +..+  +--+--+--+--+..+..+--+..+--+..+--+--+--+  +
|           |..|  |     |.. ..|..|.. .. ..|  |.. .. ..|     |
+  +--+--+  +..+  +  +--+..+..+..+--+--+--+  +--+--+..+..+  +
|  |     |  |..|     |.. ..|..|.. ..|     |        |.. ..|  |
+  +  +  +--+..+--+--+..+--+..+--+..+  +  +  +  +--+--+..+--+
|     |      .. .. .. ..|   .. .. ..|  |     |         .. ..|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+..+

l’output in formato PNG(Maze::toImage):

labirinto 200 x 100 generato da maze.pl

Per la generazione dell’immagine si richiedono le librerie GD.

Il tutto sarebbe ottimizzabile e migliorabile ma al momento sono già abbastanza soddisfatto dei risultati ottenuti!

Potete scaricare i sorgenti di maze.pl nel repository del progetto su github (software libero rilasciato sotto licenza GNU/GPL v. 3)


#!/usr/bin/perl

#------------------------------------------------------------------------
# M A Z E
#------------------------------------------------------------------------
use strict;
use warnings;

package Maze;

use Carp qw(croak verbose);
use GD;

sub new {
    my ($class, $x, $y) = @_; 

    my $self = { 
        x => $x, 
        y => $y,
        doors => [], 
        solution => [],
    };

    bless $self;
    $self->openWall(0, 0, 'N');
    $self->openWall($x - 1, $y - 1, 'S');

    return $self;
}

sub _getWallIndex($$$){
    my ($self, $x, $y, $dir) = @_;

    my @idx =
        $dir eq 'N' ? ($x,      $y,     'N') :
        $dir eq 'S' ? ($x,      $y + 1, 'N') :
        $dir eq 'W' ? ($x,      $y,     'E') :
        $dir eq 'E' ? ($x + 1,  $y,     'E') :
            croak "wrong direction";

    return @idx;
}

sub isWallOpen($$$){
    my ($self, $x, $y, $dir) = @_;

    my ($wx, $wy, $wdir) = $self->_getWallIndex($x, $y, $dir);    

    return $self->{door}[$wx][$wy]{$wdir} || 0;
}

sub openWall($$$) {
    my ($self, $x, $y, $dir) = @_;

    my ($wx, $wy, $wdir) = $self->_getWallIndex($x, $y, $dir);    

    $self->{door}[$wx][$wy]{$wdir} = 1;
}

sub getCellNeighbors($$$){
    my ($self, $x, $y) = @_;
    grep {
        $_->[0] >= 0 and $_->[0] < $self->{x} and
        $_->[1] >= 0 and $_->[1] < $self->{y}
    } (
        [$x - 1, $y    , 'W'],
        [$x + 1, $y    , 'E'],
        [$x    , $y - 1, 'N'],
        [$x    , $y + 1, 'S']
    );
}

sub getCellOpenedNeighbors($$$){
    my ($self, $x, $y) = @_;
    grep { 
        my (undef, undef, $dir) = @$_;
        $self->isWallOpen($x, $y, $dir)
    } $self->getCellNeighbors($x, $y);
}

sub isCellExit($$$){
    my ($self, $x, $y) = @_;
    return 
        ($x == $self->{x} -1 ) && ($y == $self->{y} -1 );
} 

sub markSolution($$$){
    my ($self, $x, $y) = @_;
    $self->{solution}[$x][$y] = 1;
}

sub isSolution($$$){
    my ($self, $x, $y) = @_;
    $self->{solution}[$x][$y];
}

# generate maze
sub asterione($$$$){
    no warnings 'recursion';
    my ($self, $x, $y, $visited) = @_;
    $visited->[$x][$y] = 1;
    return if $self->isCellExit($x,$y);
    my @neighbors = $self->getCellNeighbors($x, $y);
    while (scalar @neighbors){
        my ($tox, $toy, $dir) = 
            @{ splice(@neighbors, rand(@neighbors), 1) };
        next if $visited->[$tox][$toy];
        $self->openWall($x, $y, $dir);
        $self->asterione($tox, $toy, $visited);
    }
}

# solve maze
sub teseo($$$$){
    no warnings 'recursion';
    my ($self, $x, $y, $visited) = @_;
    $visited->[$x][$y] = 1;
    if ($self->isCellExit($x, $y)){
        $self->markSolution($x, $y);
        return 1;
    }
    my @neighbors = $self->getCellOpenedNeighbors($x, $y);
    while (scalar @neighbors){
        my ($tox, $toy, $dir) = 
            @{ splice(@neighbors, rand(@neighbors), 1) };
        next if $visited->[$tox][$toy];
        my $isSolution = $self->teseo($tox, $toy, $visited);
        if ($isSolution){
            $self->markSolution($x, $y);
            return 1;
        }
    }
    return 0;
}

sub toText(){

    my $self = shift;

    my ($x, $y, @l1, @l2);
    my $out = '';
    for ($y = 0; $y < $self->{y}; $y++){
        @l1 = @l2 = ();
        for ($x = 0; $x < $self->{x}; $x++){
            my $solution = $self->isSolution($x, $y) ? '.' : ' ';
            push(@l1, $self->isWallOpen($x, $y, 'N') ? $solution x 2 : '-' x 2);
            push(@l2, $self->isWallOpen($x, $y, 'W') ? ' ' : '|');
            push(@l2, $solution x 2);
        }
        push(@l2, $self->isWallOpen($x, $y, 'E') ? ' ' : '|');
        $out .= 
            '+' . join('+',@l1) . '+' . "\n" . 
            join('',@l2) . "\n";
    }

    @l1 = ();
    for ($x = 0; $x < $self->{x}; $x++){
        my $solution = $self->{solution}[$x][$self->{y} -1] ? '.' : ' ';
        push(@l1, 
            $self->isWallOpen($x, $self->{y} -1, 'S') ? 
                $solution x 2 : '-' x 2
        );
    }

    $out .= '+' . join('+', @l1) . '+' . "\n";

    print $out;
}

sub toImage($$){

    my ($self, $FILENAME) = @_;

    my ($WX, $WY) = (10, 10);

    my ($SIZEX, $SIZEY) = ($self->{x} * $WX, $self->{y} * $WY);

    my $img = new GD::Image->newTrueColor($SIZEX,$SIZEY)
        or croak "Can't create GD::Image";
 
    my $cl_white = $img->colorAllocate(255,255,255);
    my $cl_black = $img->colorAllocate(  0,  0,  0);
    my $cl_red   = $img->colorAllocate(255,  0,  0);
    
    $img->fill( 0, 0, $cl_white);

    open(my $fh, '>', $FILENAME)
        or croak "Can't open $FILENAME: $!";

    binmode $fh;

    my ($xx, $yy);

    YY: for ($yy = 0; $yy < $self->{y}; $yy++){

        XX: for ($xx = 0; $xx < $self->{x}; $xx++){

            $img->filledRectangle(
                $xx * $WX, $yy * $WY, ($xx + 1) * $WX, ($yy + 1) * $WY, 
                $cl_red
            )
                if $self->isSolution($xx, $yy);
            
            $img->line(
                    $xx * $WX, $yy * $WY, ($xx + 1) * $WX, $yy * $WY, 
                    $cl_black
            )
                unless $self->isWallOpen($xx, $yy, 'N');

            $img->line(
                    $xx * $WX, $yy * $WY, $xx * $WX, ($yy + 1) * $WY, 
                    $cl_black
            )
                unless $self->isWallOpen($xx, $yy, 'W');
        }

        $img->line(
            $xx * $WX - 1, $yy * $WY, $xx * $WX -1, ($yy + 1) * $WY, 
            $cl_black
        )
            unless $self->isWallOpen($xx - 1, $yy, 'E');
    }

    for ($xx = 0; $xx < $self->{x}; $xx++){
        $img->line(
            $xx * $WX, $yy * $WY - 1, ($xx + 1) * $WX, $yy * $WY - 1, 
            $cl_black
    )
                unless $self->isWallOpen($xx, $yy - 1, 'S');
    }

    print $fh $img->png(0);
    close $fh;
}

package main;

# init
my $m = Maze->new(60,40);

# generate paths
$m->asterione(0,0,[]);

# solve maze
$m->teseo(0,0,[]);

# generate PNG
$m->toImage('out.png');

# print ASCII
#$m->toText();

Share

AI: sviluppo di un giocatore artificiale di Reversi

Il TurcoNei giochi di strategia a turni, ho sempre ammirato le grandi sfide tra uomo e calcolatore; epiche battaglie tra pensiero strategico umano e forza tattica del calcolatore; equilibrio precario tra sinapsi e silicio, agilità contro forza, tensione tra grande visione d’insieme ed imponente valutazione di ogni dettaglio. L’epilogo può essere violento: il pensiero strategico umano si prende gioco della miopia del calcolatore e lo annichilisce; la forza bruta del calcolatore devasta il giocatore umano conducendolo verso una combinazione di cui ha previsto ogni minima variante.

Sfide dove a vincere è sempre l’uomo: il grande maestro oppure la squadra di progettisti che ha concepito un giocatore artificiale in grado di competere contro la finezza del pensiero umano.

In questo articolo, ho trovato una citazione degli autori del programma scacchistico Deep Throught (precursore di Deep Blue) sullo stile di gioco del calcolatore:

“… il computer non imita il pensiero umano – raggiunge gli stessi obiettivi per vie diverse. Vede lontano, ma osserva poco; ricorda tutto, ma non impara niente. Non fa sbagli clamorosi, ma non si innalza mai al disopra della sua normale abilità. Eppure talvolta produce intuizioni che sfuggono anche a grandi maestri.”

(Hsu, F., Anantharaman, T., Campbell, M., Nowatzyk, A. – “A Grandmaster Chess Machine“, Scientific American, Ottobre 1990)

realizzazione di Reversi42 in Python

Reversi42 screenshot

Reversi42 screenshot

In questi giorni ho provato a realizzare un prototipo di giocatore automatico di Reversi in Python (sto approfondendo ancora la conoscenza di questo linguaggio) che ho battezzato Reversi42 (in onore di Douglas Adams e della famosa domanda: “The Ultimate Question of Life, the Universe and Everything“).

Non finirò mai di ringraziare Donato Barnaba, maestro della FNGO (Federazione Nazionale Gioco Othello), per il suo prezioso aiuto, la sua disponibilità e grande competenza (anche dal punto di vista dei giocatori automatici); senza di lui lo sviluppo di Reversi42 non sarebbe stato così stimolante e divertente! Reversi42, allo stato attuale, è solo un prototipo; eventuali imprecisioni sono da attribuire solo a me!

Reversi42, come altre mie realizzazioni, è un software libero rilasciato sotto la licenza GNU/GPL; siete incoraggiati a studiarne il sorgente, migliorarlo e farci tutto ciò che desiderate; ogni commento o contributo sarà gradito.

Di Reversi esiste un libro di Brian Rose che lo presenta così: “un minuto per imparare… una vita per diventare maestri”; le regole del gioco sono facili da apprendere (e quindi da codificare) ma il gioco può essere estremamente complesso dal punto di vista strategico e tattico (ottima sfida per la realizzazione di un giocatore automatico).

Reversi42 screenshot

Reversi42 screenshot

Nella progettazione del motore AI di gioco, ho deciso di adottare l’approccio classico che viene adottato in tutti i giochi di strategia ad informazione perfetta per due giocatori: si esplora in profondità l’albero delle possibili mosse valutando la bontà di ogni posizione ottenuta; si assume, inoltre, che l’avversario risponda sempre con la migliore mossa disponibile.

Trattandosi di un prototipo, sviluppato principalmente nei ritagli di tempo, ho voluto concentrare la mia attenzione solo sugli algoritmi e non sull’ottimizzazione delle singole procedure.

Citando Donald E. Knuth:

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified”.

GRhino vs Reversi42

screenshot sfida tra GRhino e Reversi42 (test)

Ho comunque introdotto alcune metriche (certamente migliorabili) per valutare efficienza e sensitività (rispetto a modifiche) dei punti critici dell’algoritmo.

La guida di riferimento che ho adottato è: “Stategy Game Programming” di Martin Fierz che propone un graduale ed avvincente percorso tra le principali tecniche adottate per la costruzione di un buon giocatore automatico per giochi strategici (es. scacchi, dama, Reversi, forza quattro).

Le problematiche affrontate nella realizzazione del prototipo sono:

  • ricerca nell’albero delle posizioni della mossa più efficace
  • realizzazione di una buona valutazione della posizione
  • sintesi delle regole del gioco Reversi

Ricerca nell’albero delle posizioni della mossa più efficace

Lo scopo di questo problema (indipendente dal tipo di gioco) è quello di costruire l’albero di tutte le mosse possibili e percorrerlo in profondità ricercando la mossa migliore; si assume che l’avversario giochi sempre le mosse migliori.

All’aumentare della profondità di analisi (D), che condiziona la forza del giocatore, il numero di mosse da valutare (M) cresce esponenzialmente in funzione del fattore Branch Factor medio (B) tipico di ogni gioco.

M=B^{D}

Valori tipici del Branch Factor medio (B):

GiocoBranch Factor (B)
Reversi7
Forza quattro7
Dama10
Scacchi40
Go300 (!!!)

M=BF^DF

andamento del numero di mosse da analizzare al variare del gioco e profondità (in scala semilogaritmica)

Il mio obiettivo era quello di raggiungere una profondità di gioco (D) di 5-8 al fine di realizzare un giocatore automatico discreto; sul mio netbook riesco a giocare, a profondità (D) pari a 6, con tempi di attesa sempre ragionevoli (inferiori al minuto).

L’algoritmo di ricerca adottato è quello della potatura alfa-beta (in forma negamax), estremamente più efficace del minimax poichè è in grado di escludere dalla ricerca (pruning) interi rami dell’albero che condurrebbero a mosse non convenienti rispetto ad altre già individuate.

Per massimizzare il numero di rami da potare è opportuno introdurre un criterio euristico per ordinare in sequenza le mosse da valutare; le migliori mosse dovrebbero esser analizzate per prime. Rispetto all’algoritmo minimax, che richiede l’analisi di tutto l’albero delle possibili mosse (M=B^{D}), nel caso migliore della potatura alfa beta, ovvero nel caso ideale di ordinamento perfetto (le mosse più forti vengono valutate per prime), le posizioni da analizzare si abbattono a M=\sqrt{B^D}=B^{\frac{D}{2}}; siamo in grado di raddoppiare la profondità di analisi a parità di risorse di calcolo impiegate!

Il criterio euristico, con il quale vengono ordinate le mosse prima dell’alfa-beta su Reversi42, è quello di assegnare una priorità statica a tutte le mosse della scacchiera; le celle che hanno un valore più basso hanno maggiore priorità e vengono esplorate per prime (es. gli angoli).

18766781
89744798
75322357
642246
642246
75322357
89744798
18766781

Da quando è stato adottato questo ordinamento, le prestazioni della ricerca sono aumentate notevolmente; molto spesso la mossa migliore ricade tra le prime analizzate.

Valutazione della posizione

La valutazione della posizione è un elemento cruciale di un giocatore artificiale in quanto  ne condiziona: strategia, tattica ed efficienza. Occorre ponderare due parametri contrastanti: l’accuratezza dell’analisi e l’efficienza computazionale. Riuscire a trovare un compromesso ottimale tra queste due caratteristiche è un arte che si affina con l’esperienza! Un algoritmo di valutazione troppo accurato potrebbe rallentare la ricerca e quindi penalizzare eccessivamente la profondità di analisi; un algoritmo rapido ma poco accurato potrebbe perdere grandi opportunità.

In questo prototipo ho impostato la partita su due momenti distinti:

  • apertura e mediogioco: meno del 70% delle pedine non sono state giocate
  • finale: almeno il 70% delle pedine sono state giocate

In apertura e mediogioco ho cercato di massimizzare la mobilità, ovvero il numero di mosse disponibili che potranno essere utilizzate per dominare il finale; ho anche assegnato dei pesi ad alcune case strategiche che concorrono alla conquista degli angoli (caselle stabili).

10-30000-310
-3-70000-7-3
00000000
00000000
00000000
00000000
-3-70000-7-3
10-30000-310

Vengono assegnati punti di bonus se si occupano angoli mentre, se si conquistano delle case adiacenti agli angoli, vengono assegnate delle penalità poiché sarà più difficile difendere l’angolo dalla conquista avversaria. Le case adiacenti all’angolo perdono la loro penalità quando l’angolo è conquistato.

Nel finale si ricerca la vincita della partita oppure, grazie alla mobilità ottenuta in apertura e nel mediogioco, si inizia a massimizzare il numero di pedine possedute rispetto a quelle dell’avversario. L’errore fatale, tipico di giocatori mediocri di Reversi, è proprio quello di perseguire intuitivamente tale obiettivo sin dalla prima mossa.

Sorgenti

Visualizza o scarica i sorgenti dal repository su github

richiede:
python-pygame – SLD bindings for games development in Python

Share