Page 101 - 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. 101
liza igralnih strategij v iterativni zaporniški dilemi
Klemen Kac Bor Praznik
Laboratorij za heterogene racˇunalniške sisteme Laboratorij za heterogene racˇunalniške sisteme
Koroška cesta 46 Koroška cesta 46
Maribor, Slovenija Maribor, Slovenija
klemen.kac@um.si bor.praznik@um.si
POVZETEK Pravimo, da je strategija Si dominantna za igralca i, ˇce ne
glede na to, katero strategijo Sj igra igralec j, igralec i dobi
V priˇcujoˇci raziskavi smo analizirali igralne strategije v itera- veˇc, kot bi dobil, ˇce bi igral katerokoli drugo strategijo. Igra-
tivni zaporniˇski dilemi. Strateˇske igre so sestavljene iz mno- nje dominantne strategije zagotavlja agentu najboljˇsi izid.
ˇzice igralcev, mnoˇzice strategij za vsakega igralca in vektorja Najbolj vaˇzen koncept v teoriji iger je stabilnost. Dve stra-
izplaˇcil, ki vsaki strategiji priredi doloˇceno vrednost izpla- tegiji S1 in S2 sta stabilni pod pogojem, da:
ˇcila. Cilj strateˇske igre je maksimizirati vrednost izplaˇcila za
posameznega igralca. Igralne strategije v ˇclanku smo med • ˇce igralec i odigra strategijo S1, igralec j ne more od-
seboj primerjali v dveh vrstah turnirjev, kjer se veˇc posame- igrati boljˇse poteze kot S2 in
znikov pomeri v veˇc tekmah. Pri prvi vrsti turnirja, se vsak
igralec pomeri z vsemi ostalimi, pri drugi pa smo uporabili • ˇce igralec j odigra strategijo S2, igralec i ne more od-
turnirsko selekcijo, kjer po vsakem krogu izpade najslabˇsi igrati boljˇse poteze kot S1.
igralec. Implementirali smo tudi lastno igralno strategijo,
ki dosega rezultate primerljive z obstojeˇcimi strategijami. Maksimalna druˇzbena korist ne gleda na izplaˇcilo posame-
Ugotovili smo, da je uˇcinkovitost posamezne igralne stra- znega agenta, ampak vseh agentov skupaj.
tegije zelo odvisna od vrste turnirja, s katerim strategijo
ocenjujemo. Analiza igralnih strategij v zaporniˇski dilemi je ˇze precej
dobro obdelano podroˇcje v teoriji iger. V ˇclanku [1] avtorji
Kjucˇne besede ugotovljajo, da dominantne strategije v posameznem krogu
niso nujno dominantne v veˇc krogih. Axelrod v ˇclanku [2]
zaporniˇska dilema, turnirska selekcija, igralne strategije opisuje evolucijsko razvijanje igralnih strategij v iterativni
zaporniˇski dilemi. Isti avtor v ˇclanku [3] predlaga tudi, kako
1. UVOD uˇcinkovito igrati iterativno zaporniˇsko dilemo.
Strateˇska igra je urejena trojka G = N, S, u , kjer pomenijo: V naˇsi raziskavi smo analizirali ˇze omenjene igralne strategije
v iterativni zaporniˇski dilemi in poskuˇsali izmeriti uspeˇsnost
• N = {1, ..., n} je konˇcna mnoˇzica igralcev, posameznih strategij v doloˇceni vrsti turnirja. Definirali smo
dve vrsti turnirja. Pri prvi vrsti turnirja vsak posameznik
• S = {Si} je mnoˇzica strategij Si, za vsakega izmed tekmuje z vsemi ostalimi. Zmagovalna strategija je tista,
igralcev i = {1, ..., n}, ki ima skupno najboljˇsi rezultat. Pri drugi vrsti po vsa-
kem krogu izloˇcimo najslabˇso strategijo, ostale strategije pa
• ui : S −→ R je funkcija koristnosti, ki vsaki mnoˇzici igrajo ˇse enkrat v naslednjem krogu. V takˇsnem turnirju
strategij S priredi izplaˇcilo za i-tega igralca ui(S). je zmagovalna strategija tista, ki ne izgubi z nobeno izmed
preostalih strategij v turnirju.
Cilj teorije strateˇskih iger je svetovati, katero strategijo bodo
nasprotniki igrali z veˇcjo verjetnostjo, oz. priporoˇciti igral- Struktura ˇclanka v nadaljevanju je naslednja: v drugem po-
cem, katero strategijo igrati, da je izplaˇcilo najveˇcje. glavju podrobneje predstavimo zaporniˇsko dilemo, v tretjem
povzamemo igralne strategije in opiˇsemo obe vrsti turnirja,
V sploˇsnem poznamo tri koncepte strateˇskih iger: dominan- s katerima smo analizirali uspeˇsnosti strategij ter podrob-
tnost, stabilnost in maksimalna druˇzbena korist. Glede na neje opiˇsemo lastno igralno strategijo “PRAKAC”, ˇcetrto
doloˇceno strategijo i-tega igralca obstaja veˇc moˇznih izidov. poglavje je namenjeno predstavitvi poskusov in rezultatov,
v zadnjem poglavju pa povzamemo opravljeno delo ter pred-
stavimo naˇse ugotovitve.
2. ZAPORNIŠKA DILEMA
Zaporniˇska dilema je igra, v kateri nastopata dva igralca,
ki se pretvarjata, da sta zapornika. Zaprta sta vsak v svoji
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.101-106 101
Koper, Slovenia, 10 October
Klemen Kac Bor Praznik
Laboratorij za heterogene racˇunalniške sisteme Laboratorij za heterogene racˇunalniške sisteme
Koroška cesta 46 Koroška cesta 46
Maribor, Slovenija Maribor, Slovenija
klemen.kac@um.si bor.praznik@um.si
POVZETEK Pravimo, da je strategija Si dominantna za igralca i, ˇce ne
glede na to, katero strategijo Sj igra igralec j, igralec i dobi
V priˇcujoˇci raziskavi smo analizirali igralne strategije v itera- veˇc, kot bi dobil, ˇce bi igral katerokoli drugo strategijo. Igra-
tivni zaporniˇski dilemi. Strateˇske igre so sestavljene iz mno- nje dominantne strategije zagotavlja agentu najboljˇsi izid.
ˇzice igralcev, mnoˇzice strategij za vsakega igralca in vektorja Najbolj vaˇzen koncept v teoriji iger je stabilnost. Dve stra-
izplaˇcil, ki vsaki strategiji priredi doloˇceno vrednost izpla- tegiji S1 in S2 sta stabilni pod pogojem, da:
ˇcila. Cilj strateˇske igre je maksimizirati vrednost izplaˇcila za
posameznega igralca. Igralne strategije v ˇclanku smo med • ˇce igralec i odigra strategijo S1, igralec j ne more od-
seboj primerjali v dveh vrstah turnirjev, kjer se veˇc posame- igrati boljˇse poteze kot S2 in
znikov pomeri v veˇc tekmah. Pri prvi vrsti turnirja, se vsak
igralec pomeri z vsemi ostalimi, pri drugi pa smo uporabili • ˇce igralec j odigra strategijo S2, igralec i ne more od-
turnirsko selekcijo, kjer po vsakem krogu izpade najslabˇsi igrati boljˇse poteze kot S1.
igralec. Implementirali smo tudi lastno igralno strategijo,
ki dosega rezultate primerljive z obstojeˇcimi strategijami. Maksimalna druˇzbena korist ne gleda na izplaˇcilo posame-
Ugotovili smo, da je uˇcinkovitost posamezne igralne stra- znega agenta, ampak vseh agentov skupaj.
tegije zelo odvisna od vrste turnirja, s katerim strategijo
ocenjujemo. Analiza igralnih strategij v zaporniˇski dilemi je ˇze precej
dobro obdelano podroˇcje v teoriji iger. V ˇclanku [1] avtorji
Kjucˇne besede ugotovljajo, da dominantne strategije v posameznem krogu
niso nujno dominantne v veˇc krogih. Axelrod v ˇclanku [2]
zaporniˇska dilema, turnirska selekcija, igralne strategije opisuje evolucijsko razvijanje igralnih strategij v iterativni
zaporniˇski dilemi. Isti avtor v ˇclanku [3] predlaga tudi, kako
1. UVOD uˇcinkovito igrati iterativno zaporniˇsko dilemo.
Strateˇska igra je urejena trojka G = N, S, u , kjer pomenijo: V naˇsi raziskavi smo analizirali ˇze omenjene igralne strategije
v iterativni zaporniˇski dilemi in poskuˇsali izmeriti uspeˇsnost
• N = {1, ..., n} je konˇcna mnoˇzica igralcev, posameznih strategij v doloˇceni vrsti turnirja. Definirali smo
dve vrsti turnirja. Pri prvi vrsti turnirja vsak posameznik
• S = {Si} je mnoˇzica strategij Si, za vsakega izmed tekmuje z vsemi ostalimi. Zmagovalna strategija je tista,
igralcev i = {1, ..., n}, ki ima skupno najboljˇsi rezultat. Pri drugi vrsti po vsa-
kem krogu izloˇcimo najslabˇso strategijo, ostale strategije pa
• ui : S −→ R je funkcija koristnosti, ki vsaki mnoˇzici igrajo ˇse enkrat v naslednjem krogu. V takˇsnem turnirju
strategij S priredi izplaˇcilo za i-tega igralca ui(S). je zmagovalna strategija tista, ki ne izgubi z nobeno izmed
preostalih strategij v turnirju.
Cilj teorije strateˇskih iger je svetovati, katero strategijo bodo
nasprotniki igrali z veˇcjo verjetnostjo, oz. priporoˇciti igral- Struktura ˇclanka v nadaljevanju je naslednja: v drugem po-
cem, katero strategijo igrati, da je izplaˇcilo najveˇcje. glavju podrobneje predstavimo zaporniˇsko dilemo, v tretjem
povzamemo igralne strategije in opiˇsemo obe vrsti turnirja,
V sploˇsnem poznamo tri koncepte strateˇskih iger: dominan- s katerima smo analizirali uspeˇsnosti strategij ter podrob-
tnost, stabilnost in maksimalna druˇzbena korist. Glede na neje opiˇsemo lastno igralno strategijo “PRAKAC”, ˇcetrto
doloˇceno strategijo i-tega igralca obstaja veˇc moˇznih izidov. poglavje je namenjeno predstavitvi poskusov in rezultatov,
v zadnjem poglavju pa povzamemo opravljeno delo ter pred-
stavimo naˇse ugotovitve.
2. ZAPORNIŠKA DILEMA
Zaporniˇska dilema je igra, v kateri nastopata dva igralca,
ki se pretvarjata, da sta zapornika. Zaprta sta vsak v svoji
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.101-106 101
Koper, Slovenia, 10 October
