inteligenta artificiala - "life game"

UNIVERSITATEA TEHNICA GH. ASACHI-IASI

FACULTATEA DE AUTOMATICA SI CALCULATOARE

INTELIGENTA ARTIFICIALA

LIFE GAME

"Life Game" presupune realizarea unor constructii bazate pe existenta unor simple reguli de "viata" si "moarte", constructii, pe care calculatorul le trece printr-o serie de rapide transformari. Acest model, propus de Dr. John Horton Conway ( Universitatea Cambridge -Anglia) , a captat interesul cercetatorilor din intreaga lume.

Life Game este bazat pe "Celular automata theory" si este un automat celular bidimensional (matrice), aflat intr-un plan infinit, din care putem observa o singura parte.

Life game simuleaza evolutia unor colonii de organisme vii pe care, aici, le reprezentam prin matrici, ale caror elemente au urmatoarea reprezentare:

fiecare " * " reprezinta o celula vie;

fiecare " . " reprezinta o celula moarta;

fiecare celula ,cu exceptia celor situate pe margini, are cate opt vecini, care ii pot influenta starea .

Soarta unei celule este schimbata in concordanta cu o serie de reguli care se aplica simultan fiecarei celule din spatiu. Aceste reguli se bazeaza atat pe cele doua stari ale unei celule, cat si pe starile colective ale vecinilor; iar o celula poate fie sa se nasca, fie sa moara.

Regulile lui Conway sunt cheia acestui joc. El a selectat aceste reguli in mai multi ani, astfel incat sa evite cele doua extreme: modelele care se inmultesc foarte repede fara limite si modelele care mor repede. Pastrind echilibrul, el a construit modele imprevizibile si modele cu o activitate variata incredibila. Cu toate ca aceste reguli nu sunt complicate, modele "life" complexe pot aparea plecand de la modele foarte simple. A fost aratat ca in "life" exista posibilitatea unui fenomen de miscare a intregii generatii, cu posibilitatea de a aparea altele identice.

Aceste reguli sunt:

daca una din celule este moarta, ea devine vie atunci cand are trei celule vii ca vecine;

daca o celula este vie, ea ramane in aceasta stare daca are doua sau trei celule vii ca vecine; in caz contrar ea devine o celula moarta, disparind in generatia urmatoare.

Matricea aleasa trece intr-o stare intermediara, in care este specificat care celula moare (m) si care invie(v), si in starea finala, prin actualizarea celulelor vii si a celor moarte( "m" devine "." , iar "v" devine "*").

Modalitate de rezolvare

Mai intai se alege matricea cu care vom lucra. Aceasta poate fi generata aleator, sau poate fi aleasa dintre generatiile standard. In program matricea este reprezentata sub forma de sir.

Pentru fiecare element al sirului sir, este creat un alt sir vecini in care vor fi inserati vecinii lui.Trebuie tinut cont de faptul ca nu toate celulele au opt vecini, si de faptul ca matricea este un sir.

;in sirul vecini pun pe rand vecinii fiecarui element

(bind ?element (nth$ (+ ?j (* ?n ( - ?i 1))) $?sir))

(bind $?vecini (create$))

(if (!= ?i 1) then

(bind $?vecini (insert$ $?vecini 1 (nth$ (+ ?j (* ?n (- ?i 2))) $?sir)))

)

(if(!= ?i ?m) then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ ?j (* ?n ?i )) $?sir)))

)

(if(!= ?j 1) then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ (- ?j 1) (* ?n (- ?i 1 ))) $?sir)))

)

(if (!= ?j ?n) then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ (+ ?j 1) (* ?n (- ?i 1))) $?sir)))

)

(if (and (!= ?j 1)(!= ?i 1)) then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ (- ?j 1) (* ?n (- ?i 2))) $?sir)))

)

(if (and (!= ?j ?n)(!= ?i 1))then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ (+ ?j 1) (* ?n (- ?i 2))) $?sir)))

)

(if (and (!= ?j 1)(!= ?i ?m))then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ (- ?j 1) (* ?n ?i )) $?sir)))

)

(if (and (!= ?j ?n)(!= ?i ?m))then

(bind $?vecini(insert$ $?vecini 1 (nth$ (+ (+ ?j 1) (* ?n ?i )) $?sir)))

)

Cu ajutorul acestui vector se vor calcula numarul de celule vii, numar care va fi introdus in sirul sirvec.

;calculez nr de vecini vii ai celulei

(loop-for-count (?k ?dim)

(bind ?valoare (nth$ ?k $?vecini))

(if(eq ?valoare *) then

(bind ?nr (+ ?nr 1))

)

)

;in sirvec retin nr de vecini vii pt fiecare celula

(bind $?sirvec (insert$ $?sirvec (+ ?j (* ?n ( - ?i 1))) ?nr))

(delete$ $?vecini 1 ?dim)

)

Fiecarui element din sirul sir, i se va aplica regulile "Conway" descrise mai sus, dupa numarul de vecini dati de sirvec.

;aplicarea regulilor

(bind ?element (nth$ (+ ?j (* ?n (- ?i 1))) $?sir))

(bind ?nr (nth$ (+ ?j (* ?n (- ?i 1))) $?sirvec))

(if(and(eq ?element *)(and(!= ?nr 2)(!= ?nr 3))) then

(bind ?new m)

(bind $?sir (replace$ $?sir (+ ?j (* ?n ( - ?i 1))) (+ ?j (* ?n ( - ?i 1))) ?new ))

)

(if(and(eq ?element .)( nr 3)) then

(bind ?new v)

(bind $?sir (replace$ $?sir (+ ?j (* ?n ( - ?i 1))) (+ ?j (* ?n ( - ?i 1))) ?new))

)

Urmatorul pas este afisarea matricii intermediare (contine pe langa "*","." si simbolurile "m" si "v" ), si apoi are lor reactualizarea matricii (renasterea generatiei ).

Exista mai multe modele cu comportari particulare:

-glider (planor-ul)- este cel mai important model al jocului, putem observa cum se misca in plan, schimbandu-si forma la fiecare pas, dupa patru pasi revenind la forma initiala:

- navele

-pentadecathlon

 

- oscilatorul

-cele doua modele utilizate in acest proiect , cu transformarile lor: