Jocul Tic-Tac-Toe în rețea neuronală - învățarea rețelei neuronale

Partea finală a proiectului ne cere ca sa si invatam reteaua sa faca “ceva”…

In cazul de fata sa joace jocul Tic Tac Toe pe o tabla de 3x3. La prima vedere pare simplu, dar calcularea solutiei corecte, invatarea fiecarui pas urmator pentru a putea sugera utilizatorului (–jucatorului-) pasul urmator, cu sansele cele mai mari de cistig nu este o sarcina usoara.

Pentru simplitate s-a despartit in trei parti jocul:

-generarea tuturor combinatiilor posibile de cistig

-filtrarea intr-un fel a variantelor de cistig si limitarea cantitatii de date folosite pentru a intra in reteaua neuronala

-jocul propriu zis

Gengame

Este un programel pentru generarea tuturor combinatiilor posibile ale jocului Tic-Tac-Toe, pe o tabla de 3x3.

Jucatorii marcheaza succesiv cate un camp al tablei de joc. Traditional, un jucator marcheaza campurile pe care le ocupa cu “x”, iar partenerul sau cu “o”. Castiga cel care reuseste sa ocupe trei campuri alaturate, aflate pe o linie, pe o coloana sau pe o diagonala a tablei de joc.

Se foloseste algoritmul Backtracking.

Se declara o stiva in care se memoreaza campurile tablei de joc, in ordinea in care s-au ocupat.

Initial, pe prima pozitie a stivei se memoreaza “1”, adica primul jucator a ocupat primul camp al tablei de joc. Urmatorul jucator ocupa primul camp ramas liber, care este campul 2. Jocul continua astfel pana cand toate campurile tablei de joc sunt ocupate, sau pana cand unul dintre jucatori castiga. Daca la un moment dat nu se poate avansa in stiva, se revine pe pozitia precedenta si se incearca modificarea valorii aflate acolo. In caz de succes, se avanseaza in stiva si se incearca continuarea jocului. Daca nici in pozitia precedenta nu se gaseste o continuare a jocului, se revine la nivelul imediat inferior si se incearca modificarea acestuia.

Dupa fiecare mutare, se verifica daca s-a ajuns sau nu la o victorie. Deoarece algoritmul genereaza toate combinatiile posibile, rezulta ca fiecarei partide castigate de “x” ii corespunde o victorie a lui “o” –cazul trivial in care pur si simplu schimbam marcajele “x” si “o” intre ele. De aceea numai partidele in care jucatorul “x” a castigat sunt salvate intrun fisier text.

Pentru simplitate, in fisier se salveaza numai continutul stivei in momentul victoriei jucatorului “x”. Pe fiecare linie a fisierului se afla cel mult 9 cifre intre 1 si 9, reprezentand in ordine campurile ocupate de cei 2 jucatori. De exemplu daca daca pe o linie a fisierului avem 1 3 5 6 9, atunci primul jucator a ocupat campul 1, al doilea a ocupat campul 3, apoi jucatorul unu a ocupat campul 5, al doilea a ocupat 6 dupa care primul jucator a ocupat campul 9 castigand partida, deoarece 1,5 si 9 sunt pe o diagonala a tablei de joc.

Programul se incheie atunci cand stiva este goala. In acest moment fisierul text este inchis si redeschis pentru citire.

Partea a doua a programului serveste doar pentru vizualizare/verificare, datele salvate nu mai sunt modificate.

Pentru vizualizarea rezultatelor, s-au creat 9 etichete (label) asezate intro matrice 3x3. Continutul acestora este initial “.”(punct). La fiecare click pe butonul b2 este citita o solutie din fisier iar matricea de 3x3 este actualizata cu “x” sau “o”, dupa caz. De asemenea, pentru a evidentia victoria, linia de 3 caractere care a condus la victorie este scrisa cu majuscule.

Convert

Deoarece programul urmator asteapta datele in alt format decat cel generat de Gengame, a fost scris acest mic programel de conversie a datelor. De asemenea, fiind un program didactic, s-a impus limitarea cantitatii de date.

Experimental am observat ca folosind doar 300 combinatii (din cele aproximativ 65000 posibile) calculatorul a avut nevoie de circa 5 minute pentru calcul (calculator cu 2G RAM, procesor de 1600MHZ Intel Celeron). Am incercat si 3000 de variante si durata calculului a ajuns undeva la 120 minute…. Antrenarea retelei neuronale nu este perfecta, dar timpul necesar rularii programului a scazut la valori rezonabile.

Din folderul gengame se copiaza fisierul “TicTicToe.txt” in folderul convert

Programul deschide pentru citire fisierul “tictictoe.txt” si creeaza fisierul “testdata.txt” in folderul convert. Citeste o linie din primul fisier si scrie in fisierul de iesire o linie continand 9 cifre, astfel: pentru fiecare camp al tabelei neocupat, se scrie zero, pentru fiecare camp ocupat de “o” scrie -1, si pentru fiecare camp ocupat de “x”, mai putin ultimul, scrie cifra 1. Ultimul camp din linia de la intrare este cel care a dus la victorie. Pe un rand separat scriem zero pe toate pozitiile, mai putin pe pozitia care a dus la victorie, unde punem cifra unu. Semnificatia acestor doua randuri este urmatoarea: “daca la intrare apare combinatia din primul rand, atunci pe stratul de iesire este de dorit sa apara toate iesirile pe zero, mai putin cea care duce la victorie, care sa fie pe unu”.