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.

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.

Video dell’applicazione realizzata

Segue il video dimostrativo dell’applicazione realizzata:

OpenCV (Open Source Computer Vision Library)

Era da tempo che desideravo utilizzare la libreria Open CV per tornare a fare qualche esperimento di Computer Vision e per esplorare le sue tanto decantate potenzialità.

OpenCV è una libreria rilasciata sotto licenza BSD dalla Intel per l’elaborazione realtime delle immagini e la Computer Vision.

Scritta in C e C++ è utilizzabile, tramite wrapper (sia ufficiali che non) in diversi linguaggi: Python, Ruby, Java, C# ed è stata portata sui principali sistemi operativi: GNU/Linux, FreeBSD, Mac OS X, Windows ma anche Android e iOS per lo sviluppo di applicazioni su dispositivi mobili.

Alcuni wrapper esportano solo un limitato sottoinsieme di funzionalità.

Mi sono reso conto che le potenzialità di tale libreria sono superiori alle mie più rosee aspettative: c’è tutto quello che può servire (e si può sognare) per realizzare applicazioni avanzate di Computer Vision ed elaborazione delle immagini.

Video di alcune interessanti applicazioni che è possibile realizzare

Sviluppare un’applicazione di ottima qualità per la face detection in realtime, problema normalmente complesso, diventa banale a tal punto che mi sono limitato a fare qualche ricerca su internet ed assemblare poche righe di codice Python trovate in alcuni blog.

Face Detection ed Haar-like features

L’algoritmo molto efficiente che viene utilizzato per la rilevazione dei volti, basato sulle Haar wavelet, è stato elaborato da Viola-Jones nell’ambito dell’object detection ed è stato pensato proprio per il problema della face detection in tempo reale.

Con OpenCV è possibile addestrare nuovi identificatori di oggetti tuttavia sono già presenti i seguenti classificatori (in formato xml):

haarcascade_eye_tree_eyeglasses.xml
haarcascade_eye.xml
haarcascade_frontalface_alt2.xml
haarcascade_frontalface_alt_tree.xml
haarcascade_frontalface_alt.xml
haarcascade_frontalface_default.xml
haarcascade_fullbody.xml
haarcascade_lefteye_2splits.xml
haarcascade_lowerbody.xml
haarcascade_mcs_eyepair_big.xml
haarcascade_mcs_eyepair_small.xml
haarcascade_mcs_lefteye.xml
haarcascade_mcs_mouth.xml
haarcascade_mcs_nose.xml
haarcascade_mcs_righteye.xml
haarcascade_mcs_upperbody.xml
haarcascade_profileface.xml
haarcascade_righteye_2splits.xml
haarcascade_upperbody.xml

Nelle mie prove, dopo aver individuato il volto, ho provato a rilevare anche gli occhi e la bocca ma in questo caso i risultati non mi hanno soddisfatto.

Sorgente Python

I miei esperimenti sono stati effettuati su una macchina GNU/Linux Ubuntu 11.04 con OpenCV 2.1.

E’ richiesto il pacchetto python-opencv, presente nei repository ufficiali e si assume che nel path dello script sia presente una directory haarcascades contenente i vari xml necessari per la detection.

Su Ubuntu 11.04 è possibile trovarli nella directory:

/usr/share/doc/opencv-doc/examples/haarcascades/haarcascades/

segue il codice sorgente utilizzato per la realizzazione del video:

#!/usr/bin/python

#----------------------------------------------------------------------------
# Face Detection Test (OpenCV)
#
# thanks to:
# http://japskua.wordpress.com/2010/08/04/detecting-eyes-with-python-opencv
#----------------------------------------------------------------------------

import cv
import time
import Image

def DetectFace(image, faceCascade):

    min_size = (20,20)
    image_scale = 2
    haar_scale = 1.1
    min_neighbors = 3
    haar_flags = 0

    # Allocate the temporary images
    grayscale = cv.CreateImage((image.width, image.height), 8, 1)
    smallImage = cv.CreateImage(
            (
                cv.Round(image.width / image_scale),
                cv.Round(image.height / image_scale)
            ), 8 ,1)

    # Convert color input image to grayscale
    cv.CvtColor(image, grayscale, cv.CV_BGR2GRAY)

    # Scale input image for faster processing
    cv.Resize(grayscale, smallImage, cv.CV_INTER_LINEAR)

    # Equalize the histogram
    cv.EqualizeHist(smallImage, smallImage)

    # Detect the faces
    faces = cv.HaarDetectObjects(
            smallImage, faceCascade, cv.CreateMemStorage(0),
            haar_scale, min_neighbors, haar_flags, min_size
        )

    # If faces are found
    if faces:
        for ((x, y, w, h), n) in faces:
            # the input to cv.HaarDetectObjects was resized, so scale the
            # bounding box of each face and convert it to two CvPoints
            pt1 = (int(x * image_scale), int(y * image_scale))
            pt2 = (int((x + w) * image_scale), int((y + h) * image_scale))
            cv.Rectangle(image, pt1, pt2, cv.RGB(255, 0, 0), 5, 8, 0)

    return image

#----------
# M A I N
#----------

capture = cv.CaptureFromCAM(0)
#capture = cv.CaptureFromFile("test.avi")

#faceCascade = cv.Load("haarcascades/haarcascade_frontalface_default.xml")
#faceCascade = cv.Load("haarcascades/haarcascade_frontalface_alt2.xml")
faceCascade = cv.Load("haarcascades/haarcascade_frontalface_alt.xml")
#faceCascade = cv.Load("haarcascades/haarcascade_frontalface_alt_tree.xml")

while (cv.WaitKey(15)==-1):
    img = cv.QueryFrame(capture)
    image = DetectFace(img, faceCascade)
    cv.ShowImage("face detection test", image)

cv.ReleaseCapture(capture)

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:

• Maze Generation
• Think Labyrinth: Maze algorithms
• Maze Solving Algorithm
• Maze
• Mazework – How to build a Maze citato nell’articolo
• Labirinto
• labirinti e matematica

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();

Mandelbrot, I: 40 Z: -2.5, 1.0 x -1.0, 1.0

E’ davvero meraviglioso quando la natura ci sorprende facendo coesistere l’infinitamente semplice con lo smisuratamente complesso come in questo caso. Solo Lei può permettersi di farlo in modo così raffinato ed esuberante: una banale successione quadratica nel dominio dei numeri complessi, apparentemente insignificante ed innocua, è in grado di generare ricorsivamente “uno dei più complessi oggetti della matematica”; così è stato definito l’insieme di Mandelbrot da Benoît Mandelbrot, Heinz-Otto Peitgen e John H. Hubbard suoi iniziali divulgatori.

Il comportamento dei sistemi caotici ha ancora misteriose proprietà che l’uomo non è stato ancora in grado di decifrare; mattoncini matematici che la natura ha combinato per la costruzione dell’universo e di cui – forse – potremmo parlare nei prossimi articoli.

Erlang e frattali

In questo articolo, ho deciso di realizzare un’applicazione distribuita per la rappresentazione in Erlang degli insiemi frattali di Mandelbrot e Julia in Erlang introducendo anche i colori.

Mandelbrot, I: 500 Z: -0.981,-0.6457 x 0.0169, 0.3527

Un bel frullato di: caos, frattali, colori, concorrenza, programmazione funzionale, emozioni, infinito. Una frizzante e fatale alchimia di argomenti dalla quale non è possibile esser risucchiati!

Erlang

L’Erlang è un linguaggio funzionale progettato da Joe Armstrong, per conto di Ericsson, con lo scopo di favorire lo sviluppo di applicazioni: distribuite, soft-realtime, con un elevato grado di concorrenza ed affidabilità nel campo delle telecomunicazioni. La prima versione proprietaria del linguaggio è stata rilasciata internamente nel 1986 mentre, dopo varie vicessitudini, nel 1998 Erlang è stato distribuito opensource.

Concorrenza e gestione dei processi

The world is concurrent
Things in the world don’t share data
Things communicate with messages
Things fail - Joe Armstrong

Erlang è progettato per la concorrenza massiva. Per spingere tale caratteristica a livelli estremi, si è ben pensato di progettare un gestore di processi ed uno scheduler interni alla virtual-machine. Tali componenti non delegano i loro compiti al kernel del sistema operativo (come fa la quasi totalità degli altri linguaggi) e sono in grado di gestire processi con un’efficientissima gestione della memoria e dello scheduling.

Julia, I: 150 K: -0.835+0.2321i Z: -1.8,1.8 x -1.0, 1.0

Scrivere applicazioni distribuite, scalabili e robuste in Erlang è normalmente più semplice che in altri linguaggi. I processi possono esser distribuiti trasparentemente su più core oppure su più macchine e comunicano tramite message-passing asincrono.

Apprendere l’Erlang

Se siete semplicemente curiosi di conoscere la sintassi del linguaggio, potreste provare questo breve tutorial online che simula via web la shell di Erlang: Tryerlang.

Per un corso online è possibile visitare: Learn You Some Erlang oppure Erlang for Skeptics

I libri che non possono mancare nella biblioteca di chi ama tale linguaggio (sui quali ho studiato l’Erlang):

• Erlang Programming: A Concurrent Approach to Software Development, Francesco Cesarini and Simon Thompson, O’Reilly Media
• Programming Erlang: Software for a Concurrent World, Joe Armstrong, The Pragmatic Bookshelf

Applicazione Erlang: frk

Segue il codice sorgente in Erlang, del modulo principale, che ho scritto per la mia applicazione: frk.

-module(frk).
-author('LucaAmore').
-export([save/11, save/9, julia/9, mandelbrot/7]).

%------------------------------------------------------------------------
%    Copyright (C) 2011 Luca Amore <luca.amore at gmail.com>
%------------------------------------------------------------------------

% extract all screen coords
screen(W, H)->
    [ {X,Y} || Y <- lists:seq(0, H - 1), X <- lists:seq(0, W - 1) ].

% convert bitmap point to complex point
complex(X, Y, MinX, MinY, FactX, FactY)->
    { MinX + X * FactX, MinY + Y * FactY }.

iterate(_, _, _, _, MaxIterations, Iterations)
    when Iterations >= MaxIterations -> Iterations;

iterate(Zre, Zim, _, _,  _, Iterations)
    when Zre * Zre + Zim * Zim  > 4 -> Iterations;

iterate(Zre, Zim, Cre, Cim, MaxIterations, Iterations)->
    iterate(
        Zre * Zre - Zim * Zim + Cre,
        2 * Zre * Zim + Cim,
        Cre, Cim,
        MaxIterations, Iterations+1
    ).

%------------------------------------------------------------------------
% Julia's set
%
% Z1 = C0, Zn+1 = Zn^2 + K
%------------------------------------------------------------------------
julia(X, Y, MinX, MinY, FactX, FactY, Kre, Kim, MaxIterations)->
    {Cre, Cim} = complex(X, Y, MinX, MinY, FactX, FactY),
    iterate(Cre, Cim, Kre, Kim, MaxIterations, 0).

%------------------------------------------------------------------------
% Mandelbrot's set
%
% Z1 = 0, Zn+1 = Zn^2 + C0
%------------------------------------------------------------------------
mandelbrot(X, Y, MinX, MinY, FactX, FactY, MaxIterations)->
    {Cre, Cim} = complex(X, Y, MinX, MinY, FactX, FactY),
    iterate(0, 0, Cre, Cim, MaxIterations, 0).

% Julia's set exploration
generate(julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations)
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    FactX = (MaxX - MinX) / W,
    FactY = (MaxY - MinY) / H,
    [ julia(X, Y, MinX, MinY, FactX, FactY, Kre, Kim, MaxIterations) ||
        {X, Y} <- screen(W, H) ].

% Mandelbrot's set exploration
generate(mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations)
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    FactX = (MaxX - MinX) / W,
    FactY = (MaxY - MinY) / H,
    [ mandelbrot(X, Y, MinX, MinY, FactX, FactY, MaxIterations) ||
        {X, Y} <- screen(W, H) ].

% save Julia's set in ppm format
save(julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations, FileName)
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    M = [
            paletteblu:color(Iterations, MaxIterations) ||
                Iterations <- generate(
                    julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations
                )
    ],
    ppm:save(image, W, H, 255, FileName, M).

% save Mandelbrot's set in ppm format
save(mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations, FileName)
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    M = [
            palettered:color(Iterations, MaxIterations) ||
                Iterations <- generate(
                    mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations
                )
    ],
    ppm:save(image, W, H, 255, FileName, M).

Mandelbrot, I: 40 Z: -1.825,-1.705 x -0.06, 0.06

Per non appesantire troppo il codice ho deciso di utilizzare come formato delle immagini di output PPM (tra i più semplici disponibili) e poi convertirlo in PNG, tramite script bash, utilizzando l’utility convert di ImageMagick.

Tutte le immagini dei frattali di questo articolo sono stati generati da frk.

L’applicazione frk. rilasciata come software libero sotto licenza GNU/GPL, è disponibile presso:

Repository GIT su GITHUB di FRK

Mandelbrot

La rappresentazione dell’insieme di Mandelbrot, considerato uno dei frattali più popolari, è tra i miei algoritmi di prova preferiti quando studio un nuovo linguaggio di programmazione.

L’algoritmo di base è estremamente semplice e si presta facilmente ad esser parallelizzato.

Recentemente, all’interno dei Google Labs, è stata rilasciata un’applicazione Web che, sfruttando le API di Google Maps e canvas di HTML5, permette la navigazione all’interno dell’insieme di Mandelbrot o di altri frattali (es. Julia); vi consiglio di utilizzarla per un tour veloce.

Definizione formale

L’insieme di Mandelbrot è definito come il sottoinsime del piano complesso per cui la successione ricorsiva:

al tendere di n all’infinito, rimane limitata nel suo modulo, ovvero:

Sorgente perl

Ecco un sorgente perl che rappresenta l’insieme in modalità rigorosamente monocromatica:

#!/usr/bin/perl

##########################
# M A N D E L B R O T
# Luca Amore
##########################

use strict;
use warnings;

use GD;

my $FILENAME = 'mandelbrot.png';
my $ITERATIONS = 30;
my ($SIZEX, $SIZEY) = (700, 400);
my ($RE_MIN, $RE_MAX) = (-2.5, 1.0);
my ($IM_MIN, $IM_MAX) = (-1.0, 1.0);

my $re_factor = ($RE_MAX - $RE_MIN) / $SIZEX;
my $im_factor = ($IM_MAX - $IM_MIN) / $SIZEY;

my $img = new GD::Image->newTrueColor($SIZEX,$SIZEY)
    or die "Can't create GD::Image";

# palette
my $cl_black = $img->colorAllocate(  0,  0,  0);
my $cl_white = $img->colorAllocate(255,255,255);

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

binmode $fh;

my $C_im = $IM_MIN;

YY: for (my $yy=0; $yy < $SIZEY; $yy++){

    my $C_re = $RE_MIN;

    XX: for (my $xx=0; $xx < $SIZEX; $xx++){

        my ($Z_re, $Z_im, $i) = (0,0);

        # Z0=0, Zn+1 = Zn^2 + C
        ESCAPE_ITERATIONS: for ($i = 1; $i<$ITERATIONS; $i++){

            my ($Z_re2, $Z_im2) = ($Z_re * $Z_re, $Z_im * $Z_im);

            last ESCAPE_ITERATIONS unless ($Z_re2 + $Z_im2 < 4);

            # (a+bi)^2 = a^2 + 2abi - b^2
            $Z_im = 2 * $Z_re * $Z_im + $C_im;
            $Z_re = $Z_re2 - $Z_im2 + $C_re;

        } # end: ESCAPE_ITERATIONS

        # draw pixel
        $img->setPixel(
            $xx, $yy, $i == $ITERATIONS ? $cl_black : $cl_white
        );

        $C_re += $re_factor;

    } # end: XX

    $C_im += $im_factor;

} # end: YY

# save image
print $fh $img->png(0);
close $fh;

Il codice è stato mantenuto semplice per facilitare le modifiche e la comprensione.

E’ richiesto il package GD per la produzione dell’immagine di output in formato PNG: “mandelbrot.png“.

mandelbrot.png generato dal sorgente perl

Colori

Normalmente, per rendere tale frattale più gradevole, nella sua rappresentazione più semplice, si colorano i punti esterni all’insieme in funzione della velocità con la quale divergono a più infinito. Per la colorazione dei punti interni ed esterni esistono una miriade di algoritmi di complessità crescente; alcuni spunti interessanti.

Insieme di Julia

Una variante dell’insieme di Mandelbrot è l’insieme di Julia definito in questo modo:

Rispetto all’insieme di Mandelbrot cambia la successione ricorsiva ed è stata introdotta una costante complessa K.

Analogamente a Mandelbrot i punti appartenenti all’insieme di Julia sono quelli per cui il modulo della successione ricorsiva non diverge.

Alcuni valori di K che si consiglia di esplorare:

• K = 0.353+0.288i
• K = -0.70176-0.3842i
• K = -0.835-0.2321i
• K= -0.45+0.1428i

Dopo aver adeguato lo script perl, ho rappresentato questi insiemi di Julia:

Insieme di Julia (K=0.353+0.288i)

Insieme di Julia (K=-0.835-0.2321i)

Riferimenti

Mandelbrot Set – Wikipedia
Mu-Ency – The Encyclopedia of the Mandelbrot Set
The Mandelbrot Set (algoritmo tracciamento)
Julia Set – Wikipedia

Esplorazione

Visual Guide To Patterns In The Mandelbrot Set
Mandelbrot: World Map and Popular Tourist Areas

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

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

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”.

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.

Valori tipici del Branch Factor medio (B):

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 (), 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 ; 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).

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).

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

screenshot di jaGOF

Quick start

Per maggiori informazioni su Life vi rimando alla pagina di Wikipedia in italiano oppure in inglese ed ai vari riferimenti ed approfondimenti che citerò al termine di questo articolo.

Se utilizzate un browser che supporta l’HTML5 potete provare velocemente Life in HTML5.

The Game of Life

The Game of Life, concepito al termine degli anni 60 dal matematico britannico John Horton Conway, è un automa cellulare che simula l’evoluzione di una popolazione tramite regole che stabiliscono vita, nascita, morte di ogni singolo individuo.

La magia di questo gioco sta nella sua semplicità contrapposta alla profondità e complessità dell’esplorazione dei risultati; piccole variazioni di un solo individuo nella distribuzione della popolazione iniziale possono condurre ad evoluzioni totalmente diverse.

Ogni cella di una popolazione, transitando dallo stato di vita o morte, condiziona l’evoluzione delle celle confinanti; queste interazioni provocano evoluzioni estremamente complesse ed interessanti anche a partire da configurazioni apparentemente banali.

In molti si sono cimentati nella ricerca di configurazioni iniziali con determinate proprietà o nella classificazione sistematica dei possibili schemi o pattern ricorrenti.

Descrizione formale dell’algoritmo di evoluzione

Il mondo è costituito da una griglia rettangolare di N x M celle le quali possono essere in due possibili stati: vive o morte.

Due celle si definiscono confinanti se sono connesse in una delle 8 direzioni possibili (anche in diagonale); i confini del mondo sono tra loro connessi come in un pianeta perfettamente sferico.

Definita una configurazione iniziale di celle, l’automa simula l’evoluzione della vita. In intervalli di tempo discreti tutte le cellule del mondo vengono aggiornate simultaneamente (ogni aggiornamento è definito generazione o epoca) seguendo queste regole:

• una cella viva rimane in vita se esistono 2 o 3 celle vive confinanti (sopravvivenza)
• una cella viva muore se confina con meno di due celle vive (isolamento)
• una cella viva muore se esistono piu’ di 3 celle confinanti (sovraffollamento)
• una cella morta con esattamente 3 celle vive confinanti nasce e diventa viva (riproduzione)

Evoluzione e classificazione di alcuni schemi

L’evoluzione della popolazione può giungere verso l’estinzione totale della specie oppure verso varie tipologie di configurazioni ricorrenti che possono essere di:

• tipo statico (blocco, barca)
• oscillante (lampeggiatore, rospo)
• in movimento o navicelle spaziali (aliante, astronave leggera LWSS)

Altri schemi estremamente interessanti sono:

• fucili: stazionari che sparano alianti o navicelle spaziali
• fumatori: si muovono lasciando in coda frammenti di vita
• rastrelli: si muovono ed emettono navicelle
• reattore: lascia una coda di fucili (tasso di crescita quadratico)

Su Wikipedia sono disponibili le configurazioni di questi schemi base oppure su ConwayLife Wiki o su  Life Lexicon è possibile trovare una classificazione ancora più accurata ed estesa.

jaGof: just another Game of Life (la mia realizzazione)

Per realizzare Life in Python ho utilizzato la libreria Pygame (python-pygame) che si basa su SDL. Potete scaricare i sorgenti di jaGof, rilasciati sotto licenza GNU/GPL v.3, e siete incoraggiati a farne quello che desiderate.

Nella directory seeds sono stati inclusi più di 400 pattern iniziali in formato .cell scaricati da Life Lexicon.

Ricordo che si tratta del mio primo progetto in Python.

Visualizza o scarica i sorgenti dal repository su github

Futuri sviluppi

Mi piacerebbe sviluppare un algoritmo automatico per la ricerca di qualche configurazione con determinate proprietà.

Riferimenti

The Game of Life (HTML5)
Wikipedia (eng): “Conway’s Game of Life”
Wikipedia(it): “Gioco della vita”
LifeWiki
Life Lexicon Home Page

Anche se non si tratta di una pubblicazione recentissima, consiglio questo libro a tutti coloro che intendono consolidare la propria comprensione sulle basi del funzionamento interno dei principali DB.

Solo dopo aver esposto questi meccanismi, il libro guida il lettore verso l’analisi dei vari piani di esecuzione e del loro condizionamento al fine di migliorarne efficienza e robustezza.

Gli esempi fanno riferimento a vecchie versioni di Oracle, DB2, SQL Server; tuttavia i concetti base illustrati, poichè quasi sempre non legati alle varie implementazioni, possono essere estesi facilmente a tutti i possibili DB relazionali.

Era da tanto che desideravo farlo.

Mia figlia e mia moglie dormono profondamente mentre io mi diverto a capire come funziona WordPress e m’interrogo sulle tipologie di contenuti che intendo pubblicare.

Ancora non ho trovato un tema definitivo ma ho già avuto modo di costatare quanto sia potente e configurabile WordPress; certamente non sarà il massimo in termini di sicurezza ma è veramente molto usabile.

Il blog è ospitato da una macchina GNU/Linux con Debian e risorse estremamente limitate ma spremute fino all’ultimo MB; sarà più divertente mantenere tutto funzionante.

La mia espressione è simile a quella di mia figlia quando scopre un nuovo gioco; del resto, per quanto riguarda curiosità e la voglia di esplorare, sono rimasto ancora neonato.

Vado solo a vedere alla finestra se sta nevicando e poi mi addormenterò.