Projekt 2018

Zadatak Teorija Implementacija Članovi tima




Zadatak

Zadatak projekta bio je uz pomoć neuronskih mreža i genetskog programiranja napraviti autonomne igrače (botove) za dvije logičke igre. Odabrali smo sljedeće:

Warlight
Halite
Lights
Lights
Warlight je strateška igra osvajanja svijeta. U igri postoji nekoliko različitih poteza koji definiraju strategiju. Svaki igrač ima određen broj vojski koje u potezu postavlja na svoje zemlje. Kada su sve vojske postavljene, igrač definira smjer (zemlju) koju želi napasti, tj. u koju želi premjestiti vojsku. Na jednoj zemlji može biti neograničeno mnogo vojski. Svaki napad rezultira gubitkom dijela vojske za igrače. Pobjednik je onaj igrač koji uspije prije 100 krugova poraziti sve suigračeve vojske.
Halite je strateška igra koja se igra na kvadratnom mreži. Svaki igrač osvaja jedan dio mreže. Neki dijelovi mreže nisu osvojeni i "pripadaju" mapi dok ih igrači ne osvoje. Svaki komad mreže ima određenu snagu. Na početku svakog poteza botovi odlučuju kako će se micati. Validni potezi su : MIRAN, SJEVER, JUG, ZAPAD, ISTOK. Kada komad mreže ostane MIRAN njegova snaga je povećana za proizvodnu vrijednost od mjesta na kojem je. Kada 2 ili više komada mreže od istog igrača pokušaju okupirati isto mjesto, tada rezultantni komad mreže dobiva sumu njihovih snaga(maksimalna snaga je 255). Kada komadi mreže sa različitim vlasnicima se pomaknu na isto mjesto ili susjedno mjesto, komadi se moraju "boriti" i svaki komad gubi snagu jednaku protivničkoj snazi. Isto vrijedi kada i osvojeni komad mreže dođe na komad koji pripada mapi. Ako komad mreže izgubi svu svoju snagu, tada on umire i miče se sa cijelokupne ploče.



Teorija

    Genetsko programiranje

    Genetsko programiranje evolucijski je algoritam. Osnovna struktura rješenja je stablo odluke. Čvorovi stabla mogu biti aritmetičke operacije, ugrađene funkcije, varijable ili konstante. Svaka generacija rješenja se evaluira, križa i mutira da bi se dobila nova generacija sa boljim svojstvima. Evaluacija se radi na temelju funkcije dobrote. Ona govori koliko su kvalitetne odluke stabla. Uobičajeno se križanje radi zamjenom podstabla jednog roditelja podstablom drugog. Mutacija se može napraviti na više načina. Na primjer zamjenom djece, brisanjem podstabla i dodavanje random-generiranog novog podstabla...

    Neuronske mreže

    Umjetna neuronska mreža struktura je podataka korištena za učenje, evaluaciju, predikciju i sl. Mreža se sastoji od neurona. Tri su dijela neuronske mreže: ulazni sloj neurona, skriveni slojevi te izlazni sloj neurona. Neuroni su međusobno spojeni vezama kroz koje prolaze signali. Svaki sloj definira aktivacijska funkcija koja te signale propušta. Ulazima u svaki neuron pridjeljene su različite težine. Cilj treniranja mreže za neki zadatak svodi se na podešavanje tih težina. Kada su one podešene, mreža se može koristiti.




Implementacija


Projekt smo podijelili u nekoliko osnovnih dijelova:
  1. Pokretanje i modifikacija pokretača igre (engl. game engine)
  2. Izrada početnih igrača
  3. Implementacija algoritma učenja igrača
  4. Izrada omotača (engl. wrapper)




Sudionici

    Članovi tima

  1. Josip Jukić - Implementacija GP, Evolucija
  2. Alen Štruklec - Halite, Neuronska mreža
  3. Josip Matak - Pripremanje podataka
  4. Josip Mrđen - Određivanje varijabli
  5. Pavao Jerebić - Scoring system
  6. Dorotea Protrka - Križanje ( GP )
  7. Matej Pipalović - Proof of concept za GP i stabla odluke
  8. Fran Huzjan - Parser stabla




Mentor : Domagoj Jakobović