hrcak mascot   Srce   HID

Stručni rad
https://doi.org/10.31784/zvr.5.1.12

ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA

Katarina Volarić Nižić ; Veleučilište u Rijeci, Rijeka, Hrvatska

Puni tekst: hrvatski, pdf (214 KB) str. 177-186 preuzimanja: 202* citiraj
APA 6th Edition
Volarić Nižić, K. (2017). ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA. Zbornik Veleučilišta u Rijeci, 5 (1), 177-186. https://doi.org/10.31784/zvr.5.1.12
MLA 8th Edition
Volarić Nižić, Katarina. "ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA." Zbornik Veleučilišta u Rijeci, vol. 5, br. 1, 2017, str. 177-186. https://doi.org/10.31784/zvr.5.1.12. Citirano 05.12.2019.
Chicago 17th Edition
Volarić Nižić, Katarina. "ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA." Zbornik Veleučilišta u Rijeci 5, br. 1 (2017): 177-186. https://doi.org/10.31784/zvr.5.1.12
Harvard
Volarić Nižić, K. (2017). 'ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA', Zbornik Veleučilišta u Rijeci, 5(1), str. 177-186. https://doi.org/10.31784/zvr.5.1.12
Vancouver
Volarić Nižić K. ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA. Zbornik Veleučilišta u Rijeci [Internet]. 2017 [pristupljeno 05.12.2019.];5(1):177-186. https://doi.org/10.31784/zvr.5.1.12
IEEE
K. Volarić Nižić, "ODREĐIVANJE OPTIMALNIH STRATEGIJA ZA IGRANJE ŠIJAVICE POMOĆU TEORIJE IGARA", Zbornik Veleučilišta u Rijeci, vol.5, br. 1, str. 177-186, 2017. [Online]. https://doi.org/10.31784/zvr.5.1.12

Rad u XML formatu

Sažetak
Teorija igara je matematička disciplina koja modelirajući situacije iz stvarnog života kao igre te analizirajući konflikte koji se pojavljuju u tim igrama omogućava određivanje optimalnih strategija za postupanje u modeliranim situacijama. Teoriju igara moguće je primijeniti u raznovrsnim znanstvenim područjima, od matematike, preko ekonomije, do politike. U radu su definirani osnovni pojmovi vezani uz teoriju igara i matrične igre, prikazano je modeliranje stare igre šijavica kao matrične igre te određene optimalne strategije za njeno igranje. Od 25 mogućih strategija za svakog igrača, samo je pet strategija koje treba odabirati i to tako da ih se odabire s jednakim vjerojatnostima. Također je provjereno da je igra poštena, tj. da su igrači ravnopravni u igri. Poznavanje optimalnih strategija za igranje neke igre igraču omogućuje da u igri postigne što bolji rezultat, sukladno zadanim pravilima igre, a neovisno o strategijama koje odabire protivnik.

Ključne riječi
teorija igara; matrična igra; matrica isplata; strategija; vrijednost igre

Hrčak ID: 183466

URI
https://hrcak.srce.hr/183466

▼ Article Information



1. Uvod

Teorija igara je matematička disciplina koja se razvila polovinom 20. stoljeća. Njenim početkom smatra se knjiga Theory of Games and Economic Behavior (Teorija igara i ekonomsko ponašanje) koju su 1944. objavili matematičar John von Neumann i ekonomist Oskar Morgenstern. Teorija igara se otad počela naglo razvijati. Osim u matematici, primjenjuje se još i u ekonomiji, antropologiji, filozofiji, psihologiji, biologiji, politici, sportu...

Teorija igara temelji se na logičkoj analizi konfliktnih situacija, kao i situacija u kojima je moguća suradnja između dvaju ili više sudionika – igrača. Igra se definira kao situacija u kojoj:

1. sudjeluju barem dva igrača (s tim da igrač može biti jedna osoba, ali isto tako može biti i tim, tvrtka, narod ili čak i biološka vrsta);

2. svaki igrač ima određeni broj mogućih strategija, tj. akcija koje može odabrati;

3. svakom su mogućem ishodu igre pridružene isplate za svakog igrača koje predstavljaju vrijednost ishoda za različite igrače.

Teorija igara proučava kako bi igrači morali racionalno igrati igre. Svaki igrač želi da igra završi tako da on dobije čim veću moguću isplatu. Igrač može donekle utjecati na iznos isplate, birajući strategiju, no isplata ne ovisi isključivo o njegovoj strategiji, već i o strategijama koje odabiru ostali igrači, pa se tu pojavljuju konflikti i suradnja. Naime, ako više igrača uskladi svoje strategije, oni mogu postići da svi dobiju veće isplate. Racionalno igranje uključuje složene osobne odluke prilikom odabira strategije koja će igraču donijeti povoljan ishod, znajući da i svi ostali igrači biraju strategije tako da ishod bude povoljan za njih.

Cilj ovog istraživanja je odrediti optimalne strategije za igranje igre šijavica tako da se igra prikaže kao matrična igra te provjeriti je li igra poštena.

2. MATRIČNE IGRE

Najjednostavnija situacija je igra za dva igrača u kojoj svaki igrač može birati između dviju strategija, što znači da ukupno postoje četiri ishoda igre koje možemo prikazati tablicom. Primjer takve igre dan je u tablici 1.

Tablica 1. Ishodi igre
Drugi igrač
A B
Prvi igrač A (3, -3) (-4, 4)
B (0, 0) (6, -6)

Izvor: autorica

Prvi igrač bira jedan redak, dok drugi igrač istovremeno bira jedan stupac. Svaki igrač zapiše svoj izbor na papir. Igrači istovremeno otkrivaju svoj izbor i na temelju toga određuju isplate. Kod svakog je ishoda prvi član uređenog para isplata za prvog igrača, a drugi član isplata za drugog igrača.

U ovoj igri je zbroj isplata za svaki ishod jednak nuli. Drugim riječima, onoliko koliko prvi igrač dobije, toliko drugi izgubi, i obratno. Dakle, interesi igrača su izravno suprotni. Takva igra naziva se igra sa zbrojem nula i predstavlja situaciju čistog konflikta između dvoje igrača. Za takvu igru dovoljno je navesti isplate za prvog igrača za svaki ishod jer će isplata za drugog igrača kod svakog ishoda biti suprotan broj od isplate za prvog igrača za spomenuti ishod. Stoga igru možemo prikazati ovako:

Tablica 2. Tablica isplata
Drugi igrač
A B
Prvi igrač A 3 -4
B 0 6

Izvor: autorica

Ovakvu tablicu u kojoj su navedeni iznosi koje drugi igrač isplaćuje prvom igraču jednostavnije prikazujemo matricom, u ovom primjeru [TeX:] \( \begin{bmatrix} 3 & -4\\ 0 & 6 \end{bmatrix} \) , koju nazivamo matrica isplata, a igru određenu matricom isplata nazivamo matrična igra.

Prvi igrač želi odabrati redak tako da ishod bude čim veći, a drugi igrač želi odabrati stupac tako da ishod bude čim manji broj. U nastavku će biti uvedeni neki pojmovi teorije igara potrebni za razmatranje takve situacije.

Definicija 1. Strategija S je dominantna nad strategijom T ako je svaki ishod u S barem jednako dobar kao odgovarajući ishod u T i barem jedan ishod u S je strogo bolji od odgovarajućeg ishoda u T.

Prema principu dominacije, racionalni igrač nikad neće odigrati strategiju koja nije dominantna. Taj princip može eliminirati strategije za koje postoji druga strategija koja je dominantna nad njima, tj. smanjiti mogućnost izbora za pojedinog igrača.

Definicija 2. Ishod matrične igre (s isplatama za igrača koji bira retke) naziva se sedlasta točka ako je isplata za taj ishod istovremeno manja ili jednaka svakoj isplati u tom retku i veća ili jednaka svakoj isplati u tom stupcu.

Definicija 3. Ako za matričnu igru postoji broj v takav da prvi igrač ima strategiju koja mu jamči da će dobiti barem v i drugi igrač ima strategiju koja mu jamči da prvi igrač neće dobiti više od v, onda se v naziva vrijednost igre.

Ako je vrijednost igre jednaka nuli, igra je poštena, ako je vrijednost igre pozitivna, onda prvi igrač ima prednost, a ako je vrijednost igre negativna, onda drugi igrač ima prednost. Ako matrica isplata ima sedlastu točku, matrična igra je strogo određena, u njoj sreća ne igra ulogu, a vrijednost igre jednaka je isplati upisanoj na poziciji sedlaste točke.

Određivanje sedlaste točke provodi se tako da se ispišu minimumi svakog retka i među njima označi maksimum (maximin). Zatim se ispišu maksimumi svakog stupca i među njima označi minimum (minimax). Ako je maximin redaka jednak minimaxu stupaca, onda se on pojavljuje u sedlastoj točki. Jedna matrica isplata može imati više sedlastih točaka, ali su njihove vrijednosti tada jednake.

Ako matrična igra ima sedlastu točku, oba igrača će uvijek odabirati strategiju koja sadrži sedlastu točku. To se naziva čista strategija. U matričnim igrama koje nemaju sedlastu točku niti jedan igrač neće stalno odabirati istu strategiju kako to protivnik ne bi mogao iskoristiti, već će odabirati između nekoliko strategija. Mješovita strategija sastoji se od vjerojatnosti prema kojima prvi igrač bira retke, a drugi igrač bira stupce. Zbroj tih vjerojatnosti za pojedinog igrača iznosi 1. Budući da je svakom igraču u interesu da protivnik ne uoči pravilnost u njegovom odabiru strategija, idealno je da igrač odabire strategiju na slučajan način, poštujući spomenute vjerojatnosti (npr. koristeći neki uređaj koji mu može pomoći u odluci koju strategiju da odabere).

Ako vjerojatnosti za prvog igrača zapišemo u retčanu matricu P, a vjerojatnosti za drugog igrača zapišemo u stupčanu matricu Q te označimo li matricu isplata s A, umnožak [TeX:] \( P \cdot A \cdot Q \) predstavlja očekivani dobitak prvog igrača.

Za navedeni primjer, ako drugi igrač igra mješovitu strategiju s vjerojatnostima x i [TeX:] \( 1 - x \) , izračunajmo očekivane vrijednosti za svaku strategiju prvog igrača:

[TeX:] \( \begin{bmatrix} 3 & -4\\ 0 & 6 \end{bmatrix} \cdot \begin{bmatrix} x\\ 1 - x \end{bmatrix} = \begin{bmatrix} 3x - 4 + 4x\\ 6 - 6x \end{bmatrix} = \begin{bmatrix} 7x - 4\\ 6 - 6x \end{bmatrix} \)

Prvi igrač neće moći zloupotrijebiti mješovitu strategiju drugog igrača ako su ove dvije očekivane vrijednosti jednake:

[TeX:] \( 7x - 4 = 6 - 6x \)
[TeX:] \( 13x = 10 \)
[TeX:] \( x = \frac{10}{13'} \)
[TeX:] \( 1 - x = \frac{3}{13'} \)

To znači da ako drugi igrač igra mješovitu strategiju [TeX:] \( \begin{bmatrix} \frac{10}{13} \\ \frac{3}{13} \end{bmatrix} \) , onda drugi igrač može biti siguran da prvi igrač prosječno neće dobiti više od [TeX:] \( \frac{18}{13} \) jedinica po igri, neovisno o tome kako prvi igrač bude igrao.

Ako prvi igrač igra mješovitu strategiju s vjerojatnostima y i [TeX:] \( 1 - y \) , onda su očekivane vrijednosti za svaku strategiju drugog igrača:

[TeX:] \( [y 1 - y] \cdot \begin{bmatrix} 3 & -4\\ 0 & 6 \end{bmatrix} = [3y - 4y + 6 - 6y] = [3y - 10y + 6] \)

Drugi igrač neće moći zloupotrijebiti mješovitu strategiju prvog igrača ako su ove dvije očekivane vrijednosti jednake:

[TeX:] \( 3y = -10y + 6 \)
[TeX:] \( 13y =6 \)
[TeX:] \( y = \frac{6}{13'} \)
[TeX:] \( 1 - y = \frac{7}{13'} \)

Dakle, ako prvi igrač igra mješovitu strategiju [TeX:] \( \begin{bmatrix} \frac{6}{13} & \frac{7}{13} \end{bmatrix} \) onda on može biti siguran da će prosječno dobiti barem [TeX:] \( \frac{18}{13} \) jedinica po igri, neovisno o tome kako drugi igrač bude igrao.

U ovoj matričnoj igri je vrijednost igre [TeX:] \( \frac{18}{13} \) optimalna strategija prvog igrača je [TeX:] \( \begin{bmatrix} \frac{6}{13} & \frac{7}{13} \end{bmatrix} \) a optimalna strategija drugog igrača [TeX:] \( \begin{bmatrix} \frac{10}{13} \\ \frac{3}{13} \end{bmatrix} \) . Vrijedi: [TeX:] \[ \begin{bmatrix} \frac{6}{13} & \frac{7}{13} \end{bmatrix} \cdot \begin{bmatrix} 3 & -4 \\ 0 & 6 \end{bmatrix} \cdot \begin{bmatrix} \frac{10}{13} \\ \frac{3}{13} \end{bmatrix} = \frac{18}{13} \]

John von Neumann je 1928. dokazao sljedeći teorem:

Minimax teorem. Svaka matrična igra sa zbrojem nula za dva igrača ima rješenje. To znači da postoji jedinstveni broj v koji se naziva vrijednost igre i postoje optimalne (čiste ili mješovite) strategije za prvog i drugog igrača takve da:

1) ako prvi igrač igra svoju optimalnu strategiju, njegova očekivana isplata bit će ≥v neovisno o ponašanju drugog igrača,

2) ako drugi igrač igra svoju optimalnu strategiju, očekivana isplata prvog igrača bit će ≤v, neovisno o ponašanju prvog igrača.

Zahvaljujući ovom teoremu pojmove optimalne strategije i vrijednosti igre možemo razmatrati za svaku matričnu igru, a ne samo za one koje su strogo određene.

3. ŠIJAVICA

Šijavica (šije-šete, šijanje) je stara igra za dva igrača koja je rasprostranjena u Istri, Hrvatskom primorju i Dalmaciji. Igrači istovremeno pokazuju prste jedne ruke i pokušavaju pogoditi zbroj pokazanih prstiju tako da oba igrača istovremeno izvikuju broj koji može biti između 2 i 10. Brojevi se izvikuju na iskrivljenom talijanskom jeziku:

2 - do

3 - tre

4 - kvatro

5 - cinkve

6 - šije

7 - šete

8 - oto

9 - nove

10 - tuti (sve).

Igra je dobila naziv upravo po riječi "šije", "šete" (sei, sette).

Ako niti jedan igrač ne pogodi zbroj pokazanih prstiju, ili ako oba igrača pogode, igrači ne dobivaju bodove. Ako samo jedan igrač pogodi zbroj pokazanih prstiju, taj igrač dobije jedan bod.

4. ODREĐIVANJE RJEŠENJA IGRE ŠIJAVICA

Šijavica je matrična igra za dva igrača sa zbrojem nula.

Na temelju pravila igre sastavimo matricu isplata. Koristimo oznaku "P [TeX:] \( i|j \) " za "pokazuje i, izvikuje j". Uočimo da kad igrač pokaže i prstiju izvikuje jedan od brojeva [TeX:] \( i + 1 \) , [TeX:] \( i + 2 \) , [TeX:] \( i + 3 \) , [TeX:] \( i + 4 \) , [TeX:] \( i + 5 \) jer su to jedini zbrojevi koji se mogu postići zbrajanjem brojeva pokazanih prstiju oba igrača.

Tablica 3. Matrica isplata za igru šijavica
P1I2 P1I3 P1I4 P1I5 P1I6 P2I3 P2I4 P2I5 P2I6 P2I7 P3I4 P3I5 P3I6 P3I7 P3I8 P4I5 P4I6 P4I7 P4I8 P4I9 P5I6 P5I7 P5I8 P5I9 P5I10

P1

I2

0 1 1 1 1 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0

P1

I3

-1 0 0 0 0 0 1 1 1 1 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0

P1

I4

-1 0 0 0 0 -1 0 0 0 0 0 1 1 1 1 -1 0 0 0 0 -1 0 0 0 0

P1

I5

-1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 1 1 1 1 -1 0 0 0 0

P1

I6

-1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 1 1 1 1

P2

I3

1 0 1 1 1 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0

P2

I4

0 -1 0 0 0 1 0 1 1 1 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0

P2

I5

0 -1 0 0 0 0 -1 0 0 0 1 0 1 1 1 0 -1 0 0 0 0 -1 0 0 0

P2

I6

0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 1 0 1 1 1 0 -1 0 0 0

P2

I7

0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 1 0 1 1 1

P3

I4

1 1 0 1 1 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0

P3

I5

0 0 -1 0 0 1 1 0 1 1 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0

P3

I6

0 0 -1 0 0 0 0 -1 0 0 1 1 0 1 1 0 0 -1 0 0 0 0 -1 0 0

P3

I7

0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 1 1 0 1 1 0 0 -1 0 0

P3

I8

0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 1 1 0 1 1

P4

I5

1 1 1 0 1 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0

P4

I6

0 0 0 -1 0 1 1 1 0 1 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0

P4

I7

0 0 0 -1 0 0 0 0 -1 0 1 1 1 0 1 0 0 0 -1 0 0 0 0 -1 0

P4

I8

0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 1 1 1 0 1 0 0 0 -1 0

P4

I9

0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 1 1 1 0 1

P5

I6

1 1 1 1 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1

P5

I7

0 0 0 0 -1 1 1 1 1 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1

P5

I8

0 0 0 0 -1 0 0 0 0 -1 1 1 1 1 0 0 0 0 0 -1 0 0 0 0 -1

P5

I9

0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 1 1 1 1 0 0 0 0 0 -1
P5I10 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 1 1 1 1 0

Potražimo sedlastu točku. Budući da su minimumi svakog retka jednaki -1, a maksimumi svakog stupca jednaki 1, ova matrica isplata očito nema sedlastu točku.

Potražimo dominantne strategije. Ne postoje dominantne strategije jer ne postoji neki redak u kojem bi svaki broj bio manji ili jednak odgovarajućem broju u nekom drugom retku. Analogna tvrdnja vrijedi i za stupce.

Odredimo optimalne strategije. Iako smo kod matrične igre određene matricom isplata [TeX:] \( 2 X 2 \) jednostavnim računanjem odredili optimalne strategije za svakog igrača, u slučaju šijavice, čija je matrica isplata [TeX:] \( 25 X 25 \) to bi bilo vrlo zahtjevno, pa je za dobivanje rješenja korišten računalni program na mrežnoj stranici Calculating the Solution of a Matrix Game (https://www.math.ucla.edu/~tom/gamesolve.html).

Vrijednost igre je 0, odnosno, igra je poštena. Optimalna strategija za prvog igrača je:

(0, 0, 0, 0, 0.2, 0.2, 0, 0, 0, 0, 0, 0, 0.2, 0, 0, 0, 0.2, 0, 0, 0, 0, 0, 0, 0.2, 0).

Optimalna strategija za drugog igrača je:

(0, 0, 0, 0, 0.2, 0, 0, 0, 0.2, 0, 0, 0.2, 0, 0, 0, 0.2, 0, 0, 0, 0, 0, 0, 0.2, 0, 0).

Ostaje nam još samo pronaći slučajni način odabira među pet optimalnih poteza za svakog igrača. Jedan od mogućih načina je da igrač na satu očita sekunde pa ako broj sekundi pri dijeljenju s pet daje ostatak jedan, odigra prvi potez, ako broj sekundi pri dijeljenju s pet daje ostatak dva, odigra drugi potez, ako broj sekundi pri dijeljenju s pet daje ostatak tri, odigra treći potez, ako broj sekundi pri dijeljenju s pet daje ostatak četiri, odigra četvrti potez, a ako je broj djeljiv s pet, odigra peti potez.

5. ZAKLJUČAK

U radu je prikazano određivanje optimalnih strategija za igranje igre šijavica koja je modelirana kao matrična igra za dva igrača sa zbrojem nula. Dobiven je rezultat da je za prvog igrača najbolje da s jednakom vjerojatnošću od [TeX:] \( \frac{1}{5} \) igra strategije (poteze): P1I6, P2I3, P3I6, P4I6 i P5I9, dok je za drugog igrača najbolje da s jednakom vjerojatnošću od [TeX:] \( \frac{1}{5} \) igra strategije (poteze): P1I6, P2I6, P3I5, P4I5 i P5I8. Također je izračunato da je vrijednost igre 0, odnosno da je igra poštena.

References

1 

Calculating the Solution of a Matrix Game https://www.math.ucla.edu/~tom/gamesolve.html ( 8. 1. 2017. )

2 

Krčadinac V. Teorija igara - matematičko modeliranje konfliktnih situacija, Hrvatski matematički elektronski časopis, broj 3, http://e.math.hr/old/teorijaigara/index.html ( 20. 12. 2016. )

3 

Straffin P. (1993) Game theory and strategy, vol. 36 Washington: The Mathematical Association of America

4 

Šijavica, https://hr.wikipedia.org/wiki/Šijavica ( 9. 1. 2017. )


This display is generated from NISO JATS XML with jats-html.xsl. The XSLT engine is libxslt.

[engleski]

Posjeta: 449 *