Old version page

Crobots IoProgrammo Article

CROBOTS, una battaglia a colpi di 'C'


`` Alle soglie del 2000, in un mondo governato da colossi, che combattono battaglie con armi potenti e sofisticate, ideate da geni dell'OOP, create a colpi di 'C++', 'Delphi' e 'Java', esiste un gruppo di prodi programmatori che, emulando le gesta di Re Artù e dei suoi cavalieri della Tavola Rotonda, si sfidano ancora oggi con la spada e lo scudo dell'"antico" ANSI 'C'.
Nessun effetto grafico accattivante, nessun suono strabiliante, deciderà la loro sorte. Soltanto semplici soldati, gettati nella polverosa mischia di un'arena medioevale... soltanto dei Robot...''

Di che cosa stiamo parlando? È forse fantascienza? O magari storia dell'informatica? Nulla di tutto ciò. Stiamo parlando di CROBOTS!.

Che cos'è CROBOTS:

CROBOTS si pronuncia innanzi tutto "see-robots", e la "C" iniziale denuncia subito un legame con l'omonimo linguaggio di programmazione. CROBOTS è infatti, per prima cosa, un compilatore ANSI 'C'. Creato da Tom Poindexter nei lontani anni ottanta, esso è più precisamente un gioco basato sulla programmazione di computer, dove non è richiesta alcuna abilità nel pilotare joystick, mouse, ed avere dimestichezza con alieni, cyborg o macchine da corsa, come accade negli arcade: CROBOTS non è un videogioco interattivo!
È richiesta, da parte del giocatore, l'abilità di programmazione, la voglia e la pazienza di sedersi davanti alla tastiera per ingaggiare una sfida mentale a distanza con gli avversari, prima che la battaglia vera e propria abbia inizio!.
La strategia di gioco di CROBOTS risiede nella capacità di scrivere programmi nel linguaggio 'C', sì da controllare un robot dotato della capacità di muoversi, di trovare e distruggere i nemici, altri robots, pilotati da differenti programmi, scritti dai nostri avversari.
Tutti i robots sono equipaggiati allo stesso modo ed iniziano il combattimento con la medesima dotazione "bellica". Ciascun robot resta perfettamente efficiente pur subendo danni, finché non è completamente distrutto. Ciò che fa la differenza risiede nel programma che pilota il robot!

CROBOTS consiste essenzialmente in un compilatore 'C', in un computer virtuale ed in un display (la cui grafica è resa in modalità carattere) che mostra il campo di battaglia (ciò che possiamo chiamare "arena virtuale"). Il compilatore accetta un ristretto (ma estremamente potente!) subset del linguaggio ANSI 'C'. Le estensioni specifiche mettono a disposizione funzioni per la gestione di un motore, che permette al robot un movimento a velocità e direzione variabili, un radar in grado di eseguire uno scanning entro un range di 20 gradi in una data direzione e di un cannone che può sparare colpi a ripetizione, di gittata e direzione variabili. Ogni programma pilota un singolo robot e la battaglia (fra due, tre ed al massimo quattro robots contemporaneamente) può essere osservata sullo schermo. Il movimento dei combattenti, i loro colpi ed alcune informazioni che concernono il loro stato, sono visualizzate sullo schermo in real-time. Nel caso in cui si scelga di disputare una serie di scontri in sequenza fra diversi avversari, il solo output del programma CROBOTS è il risultato della battaglia: vittoria di un robot o il pareggio fra due o più robot (ma avremo modo di parlarne diffusamente più avanti). Ogni robot è consapevole del destino che lo attende:

`` THERE CAN BE ONLY ONE ''

Già come primo impatto, appare indubbio che CROBOTS attiri gli amanti della competizione, basata sull'abilità di programmazione e sulle capacità tecniche e strategiche con le quali si sceglie di pilotare la propria creatura. Nondimeno, la semplicità d'uso di CROBOTS e della programmazione dei robots, avvicina le persone che desiderano imparare il linguaggio 'C' ai concetti basilari legati alla programmazione di computer, fornendo inoltre un continuo stimolo al miglioramento tramite l' incentivo del confronto diretto con avversari reali. I risultati raggiunti finora sono stupefacenti: grazie alla competizione e alla libera circolazione dei sorgenti dei robots si è passati in pochi anni da robot con comportamenti assolutamente "stupidi" a vere e proprie macchine da guerra che "sembrano" dotate di intelligenza artificiale.

Nonostante i quattordici anni di età, CROBOTS è più attuale ai giorni nostri di quanto non lo sia mai stato in passato, dal momento che solo adesso disponiamo di computer economici abbastanza potenti da permettere di simulare tornei che abbiano significatività statistica. Benché infatti sia possibile giocare un singolo match anche su un computer dotato di un 8086, la cosa non avrebbe alcuna rilevanza pratica.
Il risultato di una partita può essere influenzato da alcuni fattori casuali, e solo la ripetizione degli incontri per un sufficiente numero di volte può garantire che sia il crobot più forte, e non il più fortunato, ad emergere. Per questo motivo possiamo introdure

il funzionamento di CROBOTS:

Come già brevemente anticipato, CROBOTS può funzionare in due differenti modalità. La prima, chiamata single play, consiste nel far disputare un solo match ai robots. La battaglia è visualizzata a pieno schermo, con la rappresentazione grafica dell'arena virtuale, dei contendenti e dei dati statistici; un simpatico screenshot rende meglio l'idea di tante altre parole:

Sono visibili i quattro robot, contrassegnati da un numero, le tracce del proiettile sparato dai loro cannoni, un paio di esplosioni ed a fianco, sulla destra, alcuni dati sullo stato dei contendenti: oltre al nome del combattente è visibile l'ammontare dei danni percentuali (al 100% il robot è distrutto ed escluso dalla mischia), la direzione (in gradi) in cui punta il cannone, la direzione in cui si muove (sempre in gradi) e la velocità espressa in percentuale; in basso a destra il numero di cicli della CPU virtuale trascorsi.
Per match play si intende la modalità in cui gli stessi robot disputano un numero prefissato di scontri, in genere molto alto. L'ouput del programma mostra a video l'esito di ciascun incontro in forma sintetica, come riportato di seguito:
Match     10:  cycles = 26985:
  Survivors:
   (1)       /jedi.r: damage=% 66  
  Cumulative score:
   (1)       /jedi.r: wins=5 ties=0        (2)    /hal9000.r: wins=3 ties=0  
   (3)       /borg.r: wins=1 ties=0        (4)      /t1000.r: wins=0 ties=0

Tale output può (in genere deve) essere rediretto su file per l'elaborazine successiva dei dati (conteggio delle vittorie, dei pareggi, delle sconfitte, calcolo della classifica e di tutte le statistiche necessarie).
La linea di comando da impartire, valida sia per CROBOTS versione Ms-DOS che Linux è, dal prompt comandi:
crobots [options] robot-program-1 [robot-program-n] [outfile]

Le opzioni ed i parametri validi sono:
  • -c (opzionale) : Compila solamente; genera il codice macchina (assembler) virtuale e la tavola dei simboli. Restituisce anche la percentuale di codice utilizzato, in quanto CROBOTS pone il limite di 1000 istruzioni virtuali per robot.
  • -d (opzionale) : Compila un solo robot ed invoca la macchina virtuale in modalità single step tracing, per il debug.
  • -mxxx (opzionale) : Lancia un serie di match, dove xxx indica il numero di volte che tale match deve essere ripetuto (modalità match play). Non ci devono essere spazi fra il numero e l'opzione. Di default, se l'opzione non è indicata, CROBOTS funziona in modalità single play.
  • -lxxx (opzionale) : Limita il numero di cicli CPU della macchina virtuale per singolo match. Valida solo quando indicata anche l'opzione "-m", non devono esserci spazi fra il numero e "-l". Nel caso in cui al termine di tali cicli CPU, due o più robot siano sopravvissuti, tali robot terminano il match in parità; in caso contrario il match termina prima del limite imposto, con la vittoria del solo robot sopravvissuto o, nel raro caso di "mutual destruction", con nessun robot sopravvissuto!
  • robot-programs (obbligatorio) : Indica i nome di file dei sorgenti dei robot. Tranne nel caso della compilazione o debug, il numero minimo dei robot è due, il numero massimo è quattro. Nel caso in cui, in modalità single o match play, è indicato un solo robot, questo viene "clonato" (viene creata una copia esatta) per permettere lo svolgimento del match con almeno due robot. Il nome del file può essere qualunque (limitato alle restrizioni del sistema operativo) con il forte consiglio di usare l'estensione ".r".
  • <infile (opzionale) : CROBOTS richiede al termine della compilazione di ciascun robot e subito prima di calcolare i match, la pressione del tasto RETURN. Nel caso in cui vi sia la necessità (es. in torneo) di eseguire in batch mode CROBOTS non è pensabile di mettersi a premere RETURN ad ogni richiesta dello stesso, e tale ridirezione dell'input da file (effettuata anche con un file vuoto!) annulla l'inconveniente.
  • >outfile (opzionale) : Questa è la ridirezione dell'output utile per salvare la compilazione (opzione "-c") o il log in modalità match play (opzione "-m"). Per effettuare un "append" di output successivi si deve usare il simbolo ">>". La ridirezione dell'output non va usata, ovviamente, in modalità single play.
Ecco alcuni semplici esempi:
  1. Per osservare tre robots gareggiare a tutto schermo:
    crobots robot1.r robot2.r robot3.r
  2. Compilare un robot, e salvare il listato:
    crobots -c robot1.r >robot1.lst
  3. Eseguire il debug ad un robot (dopo aver ottenuto il listato di codice macchina virtuale):
    crobots -d robot1.r
  4. Lanciare 50 matches, con il limite totale di 200000 cicli/CPU, salvando i risultati su file:
    crobots <cr -m50 -l200000 robot1.r robot2.r >save.log
    N.B.: "cr" è il file di ridirezione dell'input, per evitare la pressione del tasto RETURN.
Possiamo, senza indugio, passare ai più interessanti
Parametri di gioco e principi di programmazione
L'arena virtuale è un quadrato di 1000x1000 unità. Come in un piano cartesiano si fa distinzione fra l'asse x, il bordo a sud, e l'asse y, il bordo ad ovest. L'origine delle coordinate di gioco (0,0) è situata in basso a sinistra (sud-ovest) ed il punto (1000,1000) è a nord-est. Un muro circonda il perimetro di gioco ed andarci a sbattere contro procura dei danni al robot.
La "bussola", grazie alla quale possiamo esprimere la direzione, in gradi, è fatta in questo modo:
             135    90   45
                  \  |  /
                   \ | /
             180 --- x --- 0
                   / | \
                  /  |  \
              225   270   315
Programmare un robot è veramente semplice!
Nonostante siano state omesse alcune caratteristiche dello stadard ANSI C di K&R quali:
  • variabili floating point, carattere, puntatori
  • strutture, unioni, vettori
  • costrutti for, do..while, switch..case, instruzini break, continue, gotos e label
  • parametri o costanti esadecimali od ottali
  • nessuna funzione di input, output ed argomenti alla funzione principale mail()
ciò che il linguaggio mette a disposizione è assolutamente sufficiente per costruire un programma che controlli un robot!
Le caratteristiche salienti dell'ANSI 'C' presenti nel linguaggio di programmazione sono qui di seguito riportate:
  • variabili e costanti intere a 32 bit signed
  • costrutto if..then..else, while e chiamate di funzione
  • commenti (non innestati)
  • la stragrande maggioranza degli operatori di assegnamento
  • operatori bit a bit
  • operatori logici
  • operatori di incremento e decremento prefissi e postfissi (trattati però come i prefissi)
  • operatori aritmetici
  • operatori-funzioni matematico-trigonometrici con alcune limitazioni
L' unico tipo di variabile manipolabile è intero (word a 32 bit, range da -2147483648 a 2147483647), per questo motivo le funzioni matematico-trigonometrici sin(),cos(), restituiscono un valore intero tra -90 e 90 gradi e la funzione atan() ritorna un valore scalato (moltiplicato) per 100000.
Le istruzioni hanno tutte la stessa "dimensione" ed il compilatore pone il limite massimo di 2000 istruzioni per robot.
Il programma deve essere costituito da una funzione principale chiamata main() (obbligatoria). Opzionalmente possono essere inserite funzioni aggiuntive, variabili esterne o interne. Un piccolissimo robot può fare da esempio:
int angle;
int range; /* variabili esterne */

main() /* Un piccolo robot che segue il bersaglio cannoneggiandolo */
{
angle = 0;
   
  while(1) {
    drive(angle,49);    /* velocita` massima per cambiare direzione */
	shot();				/* funzione esterna	*/
    angle = (angle + 85) % 360;     /* scannig nei quattro quadranti */
  }
}  /* end of main */

shot() /* funzione esterna */
{
   while((range = scan(angle,10))) /* esegui una scansione finche' il */
	{/* bersaglio non e` individuato... */
       cannon(angle,range);        /* e poi spara */
    } 
}
Possiamo a questo punto prendere confidenza con le estensioni al linguaggio 'C' La dotazione bellica di ciascun combattente è composta da un radar e da un cannone. Il primo dispositivo è pilotato dalla funzione
scan(dir,ang)
dove dir indica la direzione espressa in gradi e ang il range angolare variabile da 0 ad un massimo di 10 gradi a destra e a sinistra della direzione indicata. L'angolo e il range devono essere non negativi, come da esempio:
range = scan(45,0); /* scansione a 45 gradi, senza variazione*/
range = scan(365,10); /* scansione nel range da 355 a 15 gradi*/
Il secondo dispositivo è pilotato dalla funzione
cannon(ang,range)
dove ang indica la direzione (in gradi) dove sparare e range la gittata, limitata a 700. Valori di range superiori a tale limite vengono troncati a 700. Il cannone non può sparare a ripetizione senza alcun intervallo fra un colpo ed il successivo, ma necessita di ricarica che occupa circa 150 cicli CPU (durante i quali resta inattivo).
Altre funzioni in dotazione al combattente virtuale gestiscono il motore, e la velocità, la rivelazione della posizione corrente e dei danni; andando in ordine abbiamo
drive(dir,speed)
Che permette lo spostamento in direzione dir (espressa in gradi) alla velocità (espressa in percentuale) speed. Per mandare il robot alla massima velocità è sufficiente impartire il comando
drive(dir,100); /* vai alla massima velocita` */
e 
drive(dir,0); /* fermati! */
per arrestare il motore. L'accelerazione e la decelerazione non sono istantanei ma impiegano alcuni cicli CPU. Per poter cambiare direzione di cammino la velocità non deve superare il 50%. La funzione
speed()
restituisce un valore compreso fra 0 e 100, che indica appunto la velocità espressa in percentuale. Un piccolo pezzo di codice per mostrare il corretto funzionamento del motore può essere questo:
drive(dir,0);
/* ferma il motore */

while(speed() > 49) ;
/* finche' la velocita` e` superiore al 50% non fai nulla */

drive(dir+=180,100);
/* inverti la direzione del cammino e parti alla massima velocita` */
Per tenere sott'occhio la propria posizione, espressa nelle coordinate (x,y), si utilizzano le funzioni
loc_x(), loc_y()
che restituiscono valori compresi fra 0 e 999 della posizione corrente, espressa rispettivamente dalla coordinata x e y. Questa che segue
damage()
restituisce, sotto forma di percentuale, la quantità di danni subiti da robot durante il combattimento. Il valore è compreso fra 0 e 99. È utile conoscere, a questo punto, il modo in cui il robot può subire danni:
  • 2% per la collisione con il muro o con un altro robot. In entrambi i casi il motere viene fermato istantaneamente e la velocità ridotta a 0%.
  • 3% a causa dell'esplosione di un missile nel raggio di 40 unità
  • 5% a causa dell'esplosione di un missile nel raggio di 20 unità
  • 10% a causa dell'esplosione di un missile nel raggio di 5 unità
I danni sono cumulativi e non possono essere riparati. Il robot non perde alcuna mobilità o potenza di fuoco al variare dei danni subiti; la sua efficienza rimane uguale da 0% al 99% di danni. Raggiunto il 100% è distrutto ed escluso dal combattimento (e cancellato dall'arena virtuale).
Un pizzico di teoria sul computer virtuale CROBOTS:
CROBOTS oltre che funzionare da compilatore, integra le caratteristiche di un computer virtuale, dotato di CPU stack-oriented.
Il set di istruzioni della CPU è formato da 10 istruzioni: FETCH, STORE, CONST, FCALL, RETSUB, BINOP, BRANCH, CHOP, FRAME, NOP, alcune delle quali prevedono un argomento. Tramite debugger è possibile seguire il single step tracing del programma mentre viene eseguito (opzione "-d") con la possibilità di simulare l'aumento di danni e seguire passo passo il comportamento del robot. In modalità debug viene simulata la presenza, al centro dell'arena virtuale, di un bersaglio immobile. Questo modo di operare è molto utile nella fase di "tuning" del programma.
CROBOTS dal lato della pratica
Quello che è importante sapere, e che condiziona il modo di progettare e testare un robot, non è tanto l'abile utilizzo del debugger (buono per il lavoro di "raffinamento"), ma la conoscenza del funzionamento del computer virtuale:
CROBOTS inizializza ed esegue in parallelo tutti i programmi caricati; la posizione iniziale di ciascun robot è determinata in modo casuale. Non c'è alcuna gestione degli errori a run-time ma, nel caso in cui se ne verifichi qualcuno (es. una divisione per 0) il programma che l'ha provocato viene resettato e riprende dalla prima istruzione della funzione mail(). Lo stesso accade nel caso in cui avvenga una collisione nello stack (es. ricorsione troppo spinta).
La velocità di calcolo della CPU è, con due robot, in un processore 8088 a 4.77MHz, di 270 instruzioni macchina virtuali al secondo... 0.00027 mips!
La comunità di "crobottisti" per distinguere i mips di un computer reale da quelli calcolati dalla CPU di CROBOTS, ha coniato, per questi ultimi, il simpatico termine SGNips. Facendo un po' di conti e qualche test si scopre che un Pentium 90MHz sotto Ms-DOS raggiunge la potenza di calcolo di circa 55k SGNips e, sotto S.O. Linux, tocca i 125k SGNips.
Poichè le variabili che influenzano l'esito di uno scontro sono alcune volte manipolate dal caso è strettamente necessario ripetere il match molte, molte, moltissime volte.
Solitamente si usano batterie di test, utilizzando quattro robot contemporaneamente, scegliendo il numero di ripetizione dei match (opzione "-mxxx") tale da permettere l'incontro di una coppia di robot un numero di volte piuttosto elevato, non inferiore a 1000. Statisticamente, usando questi valori, i risultati in termini di efficienza del robot, hanno una varianza che oscilla tra l'1% ed il 3%.

''Ecco che i moderni mostri di silicio (e rame!) portano in trionfo CROBOTS, progettato quando gli 80286 non esistevano ancora, grazie al loro esuberante numero di SGNips calcolati, in interminabili tornei, fino all'ultimo ciclo di CPU virtuale!''

Il parco software di sorgenti dei programmi-robot è oggi molto vasto; il programmatore può sbizzarrirsi nello scegliere il campione da imitare, nella filosofia tattico-strategica da seguire, nel gruppo di robot da usare come test... la fantasia e l'abilità completeranno il lavoro, c'è il divertimento assicurato per tutti!

CROBOTS visto un po' più da vicino

Il programma CROBOTS nasce sotto UNIX, scritto interamente in 'C', per mano dell'autore Tom Poindexter. La sezione del compilatore è stata sviluppata con i noti programmi UNIX 'yacc' (yet another compiler-compiler) e 'lex' (lexical analyzer). Purtroppo i sorgenti di CROBOTS non sono tutt'oggi liberamente disponibili; l'autore ne ha fatto un prezioso dono a pochi fortunati, tra cui anche un programmatore italiano che ha permesso il porting su piattaforma Linux. Il programma CROBOTS (compilato) è invece liberamente distribuibile per piattaforma Ms-DOS, Linux e perfino Amiga (anche se in veste grafica del tutto differente). I sorgenti UNIX sono stati infatti portati sotto Ms-DOS e ricompilati nel lontano 1985 con il compilatore "Lattice v.2.15E" (che gli amighisti riconosceranno senza dubbio), con alcune modifiche per le routine di scrittura su video... Un vero pezzo di antiquariato! Il porting per Linux (dai sorgenti originali UNIX!) è stato recentemente realizzato per piattaforme Intel, e sono disponibili la versione oggetto e le versioni precompilate in formato ELF i386 32 bit LSB, linkate dinamicamente sia per le libc5 che per le più recenti GNU libc (glibc2 o libc6). Il programma CROBOTS per Amiga è in gran parte differente (e non del tutto compatibile) con il "cugino" Ms-DOS/UNIX, dotato di una veste grafica molto accattivante.
L'eseguibile per Ms-DOS ha richieste hardware e software veramente esigue (ai giorni nostri s'intende!); direttamente dal manuale (forse questi dettagli oggi fanno sorridere...) :
  • Un computer IBM-PC compatibile che utilizza la chiamata INT 10H per il video.
  • 192k memoria RAM (!)
  • Ms-DOS 2.0 o sup (!)
  • Un disk drive (!)
  • Un monitor grafico monocromatico o a colori (!!)
  • Il vostro Text editor preferito (!!!)
La versione Amiga non è da meno:
  • Amiga 500, 1000, 2000, 2500 o sup.
  • 512k memoria RAM
  • AmigaOS 1.3 o sup.
  • Libreria ARP 1.3 o sup.
e la stessa dotazione equivalente a quella per Ms-DOS.
Per Linux le cose sono più semplici:
  • Sistema operativo Linux per piattaforma Intel (processore i386 o sup.)
  • Kernel 1.2.13 o sup.
  • Supporto per il formato degli eseguibili ELF
  • Librerie libc 4 o sup. (ormai esistono solo le 5 e le glibc), e librerie ncurses.
Essendo disponibile il file oggetto ('crobots.o') in caso di difficoltà è possibile linkarlo con la propria configurazione di kernel/librerie.

Conclusioni
Nella speranza di aver suscitato in ciascuno di voi l'istinto primordiale del programmatore d'assalto, l'anima dello stratega, la pazienza del beta-tester che lascia il proprio PC accesso a calcolare ore ed ore (e che l'ENEL, in combutta con le leggi di Murphy, non faccia scherzi!), CROBOTS è ancora oggi, alle soglie del 2000, una sfida affascinante, un duello d'intelligenza intrigante che aspetta soltanto voi!