Page 103 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 103
ka 1: Nastavitve spletne aplikacije
strategijam, ki v prvem krogu sodelujejo. V nadaljnih pote- igralcu pridobi najniˇzjo ˇstevilo let v zaporu [12].
zah spremljamo zadnjo nasprotnikovo odloˇcitev. V primeru,
da v zadnji potezi nasprotnik sodeluje, v naslednji potezi so- V to vrsto turnirja smo dodali ˇse dodatno pravilo izloˇca-
delujemo tudi mi. To storimo z upanjem, da bo tudi v nasle- nja, ki na koncu vsakega turnirja izloˇci najslabˇsega igralca
dnji potezi nasprotnik sodeloval, ker je to za oba najboljˇsa (tistega, ki bi moral v zaporu preˇziveti najveˇcje ˇstevilo let)
poteza. Cˇ e nas nasprotnik kadarkoli izda, ga mi v nasle- in ponovili celotni turnir s preostalimi igralci. Kadar izlo-
dnjih dveh potezah izdamo in tako upamo, da pridobimo ˇcimo strategije, ki jih je preprosto izkoriˇsˇcati, lahko pri tem
nazaj izgubljene toˇcke. Strategija je najbolj uspeˇsna proti ugotovimo, katere strategije so v povpreˇcju najboljˇse.
tistim strategijam, ki izmeniˇcno sodelujejo in izdajajo, ima
pa tudi dobre rezultate proti bolj sofisticiranim strategijam. 4. POSKUSI IN REZULTATI
Algoritem 1 Strategija PRAKAC Strategije smo med sabo primerjali z uporabo implemen-
1: N ⇐ current turn tirane spletne aplikacije, na kateri lahko nastavimo ˇstevilo
2: X ⇐ cooperate iteracij, ˇstevilo tekmovalcev, ki predstavljajo doloˇceno stra-
3: if N = 1 or (N − 1 or N − 2) = betrayed then tegijo ter naˇcin izvajanja turnirja (z izloˇcanjem ali brez).
4: X ⇐ betray Za primerjavo strategij smo v obeh vrstah turnirja izpiso-
5: end if vali rezultate za 10, 100, 500 in 1000 iteracij. Tako lahko
6: return X ugotovimo, katere strategije so boljˇse na krajˇsi in katere na
daljˇsi igralni rok. Sˇtevilo igralcev, ki predstavljajo doloˇceno
V Algoritmu 1 vidimo postopek izbire odloˇcitve pri strate- strategijo smo nastavili najprej na 1, nato na 5 in na koncu
giji “PRAKAC”. Najprej inicializiramo spremenljiko N , v ˇse na 10. Cˇ e pri turnirju z izloˇcanjem vsako strategijo pred-
katero shranjujemo nasprotnikove odloˇcitve. Vrednost spre- stavlja samo 1 igralec, se lahko zgodi, da bo strategija, ki
menljivke X hrani naˇso trenutno odloˇcitev. Privzeto jo na- v povpreˇcju dosega zelo dobre rezultate, ˇze v zaˇcetku tur-
stavimo na sodelovanje. Potem s pogojnim stavkom pogle- nirja igrala z moˇcnejˇso strategijo in bo izpadla zelo hitro.
damo, ˇce je bila nasprotnikova zadnja ali predzadnja odlo- Z veˇcjim ˇstevilom igralcev na vsako strategijo ta problem
ˇcitev izdajanje. Cˇ e pogojni stavek drˇzi, nastavimo vrednost omilimo. Za verodostojne rezultate smo vsem strategijam
spremenljivke X na izdajanje. Kot rezultat algoritma vr- vedno nastavili enako ˇstevilo igralcev.
nemo vrednost spremenljivke X.
Za demonstracijo smo naˇso strategijo primerjali z ostalimi
3.3 Turnir s krožnim dodeljevanjem implementiranimi strategijami v igri s stotimi iteracijami.
V Tabeli 2 vidimo rezultate lastne strategije v igri ena proti
Pri turnirju s kroˇznim dodeljevanjem vsak posameznik tek- ena, z ˇze obstojeˇcimi igralnimi strategijami. Za dvoboj smo
muje z vsemi ostalimi [11]. V naˇsem primeru smo to vr- dodelili 100 iteracij, z namenom da imajo strategije ki teme-
sto turnirja uporabili za testiranje uˇcinkovitosti posameznih ljijo na odzivanju moˇznost blesteti. Opazimo, da strategija
strategij. V turnir smo vkljuˇcili poljubno ˇstevilo igralcev, “PRAKAC” premaga vse strategije in pridobi najmanjˇso ˇste-
ki igrajo eno od opisanih strategij. Igralec je nato tekmo- vilo let v zaporu, z izjemo “ALL-D”, s katero odigra izenaˇcen
val z ostalimi in glede na uspeˇsnost pridobival leta, ki jih rezultat.
mora preˇziveti v zaporu. Na koncu smo pridobili rezultat v
obliki ˇstevila let, ki jih dobi igralec, ˇce uporablja doloˇceno Na Sliki 2 vidimo grafiˇcno predstavitev rezultatov lastne
strategijo. Kot najbolj uspeˇsna strategija se smatra tista, ki strategije v igri ena na ena proti ostalim strategijam. Opa-
zimo, da je rezultat v primerjavi s strategijami “ALL-D”,
“TIT-FOR-TAT” in “TESTER” precej izenaˇcen, medtem ko
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 103
Koper, Slovenia, 10 October
strategijam, ki v prvem krogu sodelujejo. V nadaljnih pote- igralcu pridobi najniˇzjo ˇstevilo let v zaporu [12].
zah spremljamo zadnjo nasprotnikovo odloˇcitev. V primeru,
da v zadnji potezi nasprotnik sodeluje, v naslednji potezi so- V to vrsto turnirja smo dodali ˇse dodatno pravilo izloˇca-
delujemo tudi mi. To storimo z upanjem, da bo tudi v nasle- nja, ki na koncu vsakega turnirja izloˇci najslabˇsega igralca
dnji potezi nasprotnik sodeloval, ker je to za oba najboljˇsa (tistega, ki bi moral v zaporu preˇziveti najveˇcje ˇstevilo let)
poteza. Cˇ e nas nasprotnik kadarkoli izda, ga mi v nasle- in ponovili celotni turnir s preostalimi igralci. Kadar izlo-
dnjih dveh potezah izdamo in tako upamo, da pridobimo ˇcimo strategije, ki jih je preprosto izkoriˇsˇcati, lahko pri tem
nazaj izgubljene toˇcke. Strategija je najbolj uspeˇsna proti ugotovimo, katere strategije so v povpreˇcju najboljˇse.
tistim strategijam, ki izmeniˇcno sodelujejo in izdajajo, ima
pa tudi dobre rezultate proti bolj sofisticiranim strategijam. 4. POSKUSI IN REZULTATI
Algoritem 1 Strategija PRAKAC Strategije smo med sabo primerjali z uporabo implemen-
1: N ⇐ current turn tirane spletne aplikacije, na kateri lahko nastavimo ˇstevilo
2: X ⇐ cooperate iteracij, ˇstevilo tekmovalcev, ki predstavljajo doloˇceno stra-
3: if N = 1 or (N − 1 or N − 2) = betrayed then tegijo ter naˇcin izvajanja turnirja (z izloˇcanjem ali brez).
4: X ⇐ betray Za primerjavo strategij smo v obeh vrstah turnirja izpiso-
5: end if vali rezultate za 10, 100, 500 in 1000 iteracij. Tako lahko
6: return X ugotovimo, katere strategije so boljˇse na krajˇsi in katere na
daljˇsi igralni rok. Sˇtevilo igralcev, ki predstavljajo doloˇceno
V Algoritmu 1 vidimo postopek izbire odloˇcitve pri strate- strategijo smo nastavili najprej na 1, nato na 5 in na koncu
giji “PRAKAC”. Najprej inicializiramo spremenljiko N , v ˇse na 10. Cˇ e pri turnirju z izloˇcanjem vsako strategijo pred-
katero shranjujemo nasprotnikove odloˇcitve. Vrednost spre- stavlja samo 1 igralec, se lahko zgodi, da bo strategija, ki
menljivke X hrani naˇso trenutno odloˇcitev. Privzeto jo na- v povpreˇcju dosega zelo dobre rezultate, ˇze v zaˇcetku tur-
stavimo na sodelovanje. Potem s pogojnim stavkom pogle- nirja igrala z moˇcnejˇso strategijo in bo izpadla zelo hitro.
damo, ˇce je bila nasprotnikova zadnja ali predzadnja odlo- Z veˇcjim ˇstevilom igralcev na vsako strategijo ta problem
ˇcitev izdajanje. Cˇ e pogojni stavek drˇzi, nastavimo vrednost omilimo. Za verodostojne rezultate smo vsem strategijam
spremenljivke X na izdajanje. Kot rezultat algoritma vr- vedno nastavili enako ˇstevilo igralcev.
nemo vrednost spremenljivke X.
Za demonstracijo smo naˇso strategijo primerjali z ostalimi
3.3 Turnir s krožnim dodeljevanjem implementiranimi strategijami v igri s stotimi iteracijami.
V Tabeli 2 vidimo rezultate lastne strategije v igri ena proti
Pri turnirju s kroˇznim dodeljevanjem vsak posameznik tek- ena, z ˇze obstojeˇcimi igralnimi strategijami. Za dvoboj smo
muje z vsemi ostalimi [11]. V naˇsem primeru smo to vr- dodelili 100 iteracij, z namenom da imajo strategije ki teme-
sto turnirja uporabili za testiranje uˇcinkovitosti posameznih ljijo na odzivanju moˇznost blesteti. Opazimo, da strategija
strategij. V turnir smo vkljuˇcili poljubno ˇstevilo igralcev, “PRAKAC” premaga vse strategije in pridobi najmanjˇso ˇste-
ki igrajo eno od opisanih strategij. Igralec je nato tekmo- vilo let v zaporu, z izjemo “ALL-D”, s katero odigra izenaˇcen
val z ostalimi in glede na uspeˇsnost pridobival leta, ki jih rezultat.
mora preˇziveti v zaporu. Na koncu smo pridobili rezultat v
obliki ˇstevila let, ki jih dobi igralec, ˇce uporablja doloˇceno Na Sliki 2 vidimo grafiˇcno predstavitev rezultatov lastne
strategijo. Kot najbolj uspeˇsna strategija se smatra tista, ki strategije v igri ena na ena proti ostalim strategijam. Opa-
zimo, da je rezultat v primerjavi s strategijami “ALL-D”,
“TIT-FOR-TAT” in “TESTER” precej izenaˇcen, medtem ko
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 103
Koper, Slovenia, 10 October
