Imaginary Journey to the Frontier of AI: A Glimpse into the Year 2912

In this imaginative journey to the frontier of AI, we’ll project ourselves into the year 2912, where we will challenge the Data Analysis module of ChatGPT v4 to solve a space-time anomaly.

interstellar titanic ship

To break the ice, I asked ChatGPT to briefly describe, based on its knowledge, how it imagines humanity in the year 2912, especially in relation to intergalactic travel.

“By the year 2912, I envision humanity as a highly advanced civilization, spread across multiple planets and star systems. Thanks to discoveries in physics and bioengineering, humans are able to adapt to different space environments and have developed intergalactic travel technology that allows crossing vast cosmic distances in a short time. Spacecrafts are elegant and sophisticated, equipped with AI systems to assist and protect travelers. Human cultures are diverse, influenced by various space colonies, yet united by a common quest for exploration and knowledge.”

I share ChatGPT’s optimism, which doesn’t describe a dystopian future or conflicts, but collaboration among civilizations; probably a reflection of its algorithms’ optimism bias.

Now, let’s describe our intergalactic problem presented on Kaggle:

Addison Howard, Ashley Chow, Ryan Holbrook. (2022). Spaceship Titanic. Kaggle

The interstellar spaceship Titanic, on its maiden voyage, is transporting about 13,000 emigrants from our solar system to three newly habitable exoplanets. Passengers come from Earth, Mars, and Europa, some in cryogenic sleep. The ship offers various services, including VIP treatments, a SPA, a shopping center, and a high-tech Virtual Reality deck. All onboard activities are tracked by a next-generation computer system.

Near Alpha Centauri, en route to the torrid 55 Cancri E, the ship encounters a space-time anomaly hidden by a dust cloud. After 1,000 years, it seems the tragedy of the previous Titanic is repeating in space.

After the impact, although the ship remains miraculously intact, nearly half the passengers are teleported to an alternate dimension!

view of spaceship

To aid rescue teams and recover the missing passengers, we must predict which passengers have been teleported using data from the damaged computer system.

Here’s where we come in with the assistance of ChatGPT v4 and its Data Analytics module.

We face a synthetic problem, created in the lab, which I consider extremely valid and complete to delve into various themes related to data analysis and machine learning algorithms.

To effectively solve these types of problems typically requires complex theoretical and programming knowledge. ChatGPT assists the operator by guiding through all stages of the process.

Here are the details of the Spaceship Titanic problem:

We start with a training file containing data on two-thirds of the passengers and information on whether they have been teleported, and a test file with the same data but no information on the remaining passengers’ teleportation status.

The challenge is to predict, as accurately as possible, whether the passengers in the test file will be teleported.

Here are the known passenger data.

CAMPODESCRIZIONE
PassengerIdA unique ID for each passenger, in the format gggg_pp where gggg indicates a group the passenger belongs to and pp is the passenger number within the group.
HomePlanetThe planet the passenger departed from, usually their permanent residence planet.
CryoSleepIndicates whether the passenger chose to be put in suspended animation for the journey. Cryosleep passengers are confined to their cabins.
CabinThe cabin number where the passenger is located. Presented in the format deck/number/side, where the side can be P for Port (left) or S for Starboard (right).
DestinationThe planet where the passenger disembarks.
AgeThe passenger’s age.
VIPIndicates whether the passenger paid for a special VIP service during the trip.
RoomServiceAmount the passenger charged to room service. NameThe names and surnames of the passenger.TransportedIndicates whether the passenger has been transported to another dimension. This is the target variable, the column we are trying to predict.

FoodCourtAmount the passenger charged to the food court.
ShoppingMallAmount the passenger charged to the shopping center.
SpaAmount the passenger charged to the spa.
VRDeckVRDeckAmount the passenger charged to the virtual reality deck.
NameThe name and surname of the passenger.
TransportedIndicates whether the passenger has been transported to another dimension. This is the target variable, the column we are trying to predict.
known passenger data

I attempted to solve the problem using ChatGPT v. 4.0 utilizing its Data Analysis module.

After presenting the training file, ChatGPT reprocessed it in the best way and also proposed the best strategies for managing missing data.

Spoiler Alert if you want to tackle this problem without any information.

I asked ChatGPT to explain how these variables might influence the Target Transported variable, and here’s the response:

CHATGPT RESPONSE — SPOILER ALERT —

Predicting whether a passenger has been teleported or not is based on analyzing various factors (or variables) in the dataset. Here’s a brief summary of how some of these variables might influence the probability of being teleported:

HomePlanet (Planet of Origin): The probability of being teleported may vary depending on the passenger’s planet of origin. There could be specific trends or policies associated with each planet influencing this probability.

CryoSleep (Cryogenic Sleep): Passengers in cryogenic sleep may have a higher probability of being teleported, perhaps due to specific procedures or protocols related to their state.

Cabin (Cabin): The type or location of the cabin might correlate with the probability of being teleported, perhaps due to proximity to specific teleportation devices or areas of the spacecraft.

Destination (Destination): The final destination might influence the probability of being teleported, perhaps due to different procedures for different places or travel distances.

Age (Age) and VIP: Though with a weaker correlation, age and VIP status may play a role, potentially due to policies or preferential treatments for certain age groups or VIPs.

Expenses (RoomService, FoodCourt, etc.): Expenditures in various categories (like RoomService, FoodCourt, etc.) show a correlation, suggesting that a passenger’s spending behavior might be linked to their probability of being teleported.

It’s important to note that these are correlations observed in the data and do not necessarily imply a direct cause-effect relationship. Teleportation decisions might be influenced by a complex interplay of these factors and others not captured in the dataset.

END OF CHATGPT RESPONSE — END OF SPOILER ALERT —

The analysis phase was truly impressive, considering it was completely automated.

chatgpt-data-analysis

During the model construction phase, ChatGPT guided us through various stages. Errors occurred several times, which were analyzed and recovered more or less effectively. A major limitation is that more complex computations are also interrupted due to timeout.

ChatGPT suggested using the Random Forest algorithm for the model.

I asked for the rationale behind this choice.

CHATGPT RESPONSE

I chose the Random Forest model to predict the teleportation status for various reasons, making it particularly suitable for this type of problem:

Handling Categorical and Continuous Variables: Random Forest effectively manages both categorical and continuous variables. In the provided dataset, we have both types of variables, making Random Forest an appropriate choice.

Robustness to Noisy Data and Outliers: Random Forest is known for its robustness to noisy data and outliers, which can be present in real datasets like this.

Lower Risk of Overfitting: Thanks to its ensemble algorithm nature, combining the results of many decision trees, Random Forest tends to have a lower risk of overfitting compared to single decision trees.

Variable Importance: Random Forest provides useful insights into variable importance, which can help understand which factors most significantly influence the prediction. This is useful for interpreting the model’s results in relation to the business problem.

Good Overall Performance: Generally, Random Forest is known for its good performance across a wide range of classification problems, making it a reliable starting point for many machine learning applications.

Flexibility and Scalability: It’s a flexible model that can be easily adapted to improve performance (e.g., adjusting the number of trees) and scales well with large datasets.

In summary, I chose Random Forest for its robustness, reliability, and ability to provide high-quality results on a complex dataset like the one provided.

END OF CHATGPT RESPONSE

The result achieved was an accuracy of 0.79822, which I find astonishing given that it was conducted in a fully guided mode; we also placed reasonably well on the leaderboard for this problem.

These are the parameters obtained on the validation set.

PARAMETERValue
Accuracy0.7901
Precision (False)0.8000
Precision (True)0.7800
Recall (False)0.7700
Recall (True)0.8100
F1-Score (False)0.7800
F1-Score (True)0.8000
validation set parameters

All the Python code created can be viewed, which is extremely useful for beginners.

ChatGPT V4 Data Analysis proved to be an incredible assistant, albeit a bit unstable as there were errors that forced me to start over.

All images were created by DALL·E 2 through ChatGPT v4.

Share

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

Infection Spread Simulator Construction Kit

Al fine di comprendere meglio l’articolo: Modeling How Infectious Diseases like Coronavirus Spread ed i riferimenti citati, continuando ad approfondire, mi sono ritrovato a costruire il framework: “Infection Spread Simulator Construction Kit”.

Si tratta di un notebook Python su Colab per la modellazione della diffusione di un’infezione attraverso un modello SEIR descritto da un sistema di equazioni differenziali (o un algoritmo); lo stesso modello proposto per l’analisi della diffusione del covid-19 nell’articolo che ha ispirato questo lavoro.

Chiunque, anche senza nessuna base matematica, con una conoscenza basilare di programmazione, può modificare il notebook all’interno della propria sandbox Colab, descrivere un virus o il comportamento di un’infezione ed analizzare la sua diffusione nel tempo per comprendere come la variazione di certi parametri può incidere nella diffusione.

Si tratta di un prototipo, nato per uso strettamente personale, con molti limiti ma voglio comunque condividerlo con la comunità rilasciandolo come software libero sotto la licenza GNU/GPL v.3.

Sarei felice di ricevere i vostri feedback, i vostri modelli, le vostre evoluzioni anche direttamente su github. Nei prossimi giorni, utilizzando questo framework o una sua evoluzione, vorrei provare a realizzare il complesso modello di diffusione del covid-19 descritto nell’articolo.

Segue il link diretto al notebook su github:

NOTEBOOK INFECTION SPREAD SIMULATOR CONSTRUCTION KIT (GITHUB)

MALARIA
Il primo modello reale (non SEIR) che rilascio è quello della malaria. In questo caso ho dovuto apportare delle modifiche più complesse al modello base.

MALARIA NOTEBOOK (GITHUB)

Share

Computer vision: OpenCV realtime face detection in Python

Per festeggiare degnamente l’arrivo del mio nuovo portatile in famiglia ho pensato di renderlo in grado di riconoscere volti umani da una sorgente video in tempo reale.

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 demo 009

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

Share

AI: sviluppo di un giocatore artificiale di Reversi

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

Il Turco

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

John Conway’s Game of Life in Python

Come primo progetto in Python, ho deciso di realizzare una semplice versione del famosissimo automa cellulare di Conway: “Game of Life”.

jaGOF - just another Game of Life screenshoot

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

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

gameoflifeWikipedia(it): “Gioco della vita”
LifeWiki
Life Lexicon Home Page

Share