Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch
|
Trenčianska Univerzita Alexandra Dubčeka v Trenčíne
Fakulta Mechatroniky |
|
| Autor: | Ľubomír Milko
|
| Pedagogický vedúci: | Ing. Juraj Ďuďák |
| Študijný odbor: | Mechatronika
|
| Akademický rok | 2009/2010
|
| Abstrakt
Táto práca obsahuje charakteristiku teórie hier a teórie grafov a následne popisuje použitie princípov z tejto oblasti v základných druhoch rozhodovacích problémov. Vo štvrtej kapitole sa podrobnejšie opisujú princípy analýzy a riešenia hier, ktoré môžu byť reprezentované hernými stromami. Posledná časť práce je venovaná implementácii rozobraných princípov voľby vhodného ťahu v doskovej hre dáma. |
| Abstract
tu bude anstrakt v AJ |
Úvod
Problémy vyžadujúce správne rozhodovanie s ohľadom na následky zvoleného rozhodnutia nás sprevádzajú v takmer všetkých oblastiach ľudskej činnosti od hrania rôznych spoločenských hier až po pokročilé riadenie cestnej siete, správne ekonomické rozhodnutia alebo stratégiu vojenských konfliktov. Postupné snahy o matematickú interpretáciu a riešenie týchto problémy voľby správneho rozhodnutia vyústili v samostatné odvetvie aplikovanej matematiky s názvom teória hier. V tejto teórii sa rozhodovacie problémy znázorňujú ako množina stratégií, ktoré možno prijať a množina následkov, ktoré vzniknú v dôsledku zvolenej stratégie. Následky sú často číselnou interpretáciou daného stavu. Na praktickú interpretáciu tohto súboru množín sa využíva teória grafov. Tieto dve teórie možno použiť na vyriešenie mnohých praktických rozhodovacích problémov. Zaujímavým praktickým a názorným príkladom aplikácie môže byť aj hľadanie optimálneho ťahu v doskových hrách akou je napríklad dáma. Súčasťou tejto práce je teda aj podrobnejšia ukážka využitia teórie hier a teórie grafov v tomto type hier. Cieľom tejto práce potom je:
- charakteristika teórie hier a teórie grafov,
- popis interpretácie základných rozhodovacích problémov pomocou týchto teórií,
- praktické použitie popísaných teoretických princípov pri voľbe vhodného ťahu v doskovej hre dáma.
Zoznam použitých skratiek a symbolov
- hra
- strategická interakcia medzi jednotlivcami
- hráč
- účastník hry
- minimax
- algoritmus, ktorý prechádzaním herného stromu vyberá optimálny ťah v hre
- pozícia
- aktuálny stav hry
- strom
- typ grafu, využívaný na znázornenie hier v rozšírenej forme
- ťah
- zvolená a uskutočnená stratégia hráča v danom bode hry
Teória hier
Základné pojmy a charakteristika teórie hier
Teória hier je odvetvím aplikovanej matematiky, ktorá sa snaží matematicky zachytiť správanie v strategických situáciách, kde úspech jednotlivca pri vykonaní určitej voľby závisí od volieb ostatných [1].
Súbor situácií, v ktorých sa každý účastník môže nachádzať je v teórii hier nazývaný hra. Hra je akousi strategickou interakciou medzi jednotlivcami. Každý účastník (prvok, ktorý sa aktívne zúčastňuje hry) je označený ako hráč. Každý hráč má v daných momentoch možnosť voľby akcie, ktorá ďalej ovplyvní priebeh hry. Každá z možných akcií, ktoré hráč môže vykonať sa označuje ako ťah. Súbor ťahov, ktoré hráč použije v hre je označovaný ako stratégia.
Teória hier skúma predpokladané a skutočné správanie sa hráčov v hrách, rovnako ako aj optimálne stratégie. Zdanlivo odlišné typy interakcií medzi hráčmi a hrou sa môžu prejavovať podobnými štruktúrami pohnútok, takže všetky môžu byť reprezentované ako príklady jednej konkrétnej hry. V počiatkoch bola teória hier rozvíjaná na analyzovanie súťaží (situácií), kde každému hráčovi sa darilo lepšie na úkor ostatných [1]. Jedná sa o tzv. hry s nulovým súčtom (viď. kapitola 2.5). Išlo napr. o analýzu rôznych vojenských konfliktov, prípadne spoločenských hier. Neskôr sa teória hier rozšírila na analyzovanie širokého spektra interakcií, ktoré sú klasifikované podľa niekoľkých kritérií. Dnes pojem teória hier zahŕňa množstvo teórií, ktoré možno aplikovať v rôznych rozhodovacích problémoch, kde hráčmi môžu byť ľudia, počítače, zvieratá, rastliny, atď.
Tradičné aplikácie teórie hier sa snažia v hrách nájsť stav rovnováhy. To znamená nájsť súbor stratégií, kde je nepravdepodobné, že jednotlivé prvky budú meniť svoje správanie. Na riešenie týchto problémov bolo vyvinutých veľa konceptov, z ktorých najznámejšia je Nashova rovnováha [1].
Nashova rovnováha je koncept riešenia hier zahŕňajúcich dvoch alebo viac hráčov, kde každý hráč pozná stratégie rovnováhy (teda najlepšie stratégie, aké môžu zvoliť ostatní, aby získali čo najviac) ostatných hráčov a žiadny hráč nemá čo získať zmenou iba svojej vlastnej stratégie. Ak každý hráč zvolil stratégiu a žiadny hráč nemôže profitovať zmenou svojej stratégie, pokiaľ ostatní hráči ponechajú svoje stratégie nezmenené, potom daný súbor strategických rozhodnutí a odpovedajúcich odmien stanovuje Nashov stav rovnováhy. Inými slovami, byť v Nashovom stave rovnováhy znamená, že každý hráč odpovie negatívne na otázku : “Ak s určitosťou poznám stratégie ostatných hráčov, môžem profitovať zmenou mojej stratégie ?“ [1]. Jedným z najznámejších typov takejto hry je napr. väzňova dilema spopularizovaná matematikom Albertom W. Tuckerom. Opis problému je nasledovný:
Dvaja väzni vykradli banku a boli neskôr chytení políciou. Vo väzení ich zavrú do samostatných ciel. Väzni nemajú možnosť spolu komunikovať. Polícia nemá dosť dôkazov aby uväznila oboch. Obaja dostanú od polície ponuku spolupracovať (zradiť komplica), výmenou za nízky trest pre seba. Možné výsledky sú takéto:
- Ak budú obaja navzájom spolupracovať, budú ich držať najviac rok vo vyšetrovacej väzbe.
- Ak jeden z väzňov zradí komplica, pustia ho ihneď na slobodu, ale komplic dostane 10 rokov väzenia.
- Ak sa priznajú/zradia obaja, rozdelia si 10 ročný trest, čiže každý dostane 5 rokov.
Z hľadiska skupinového správania sa je najvýhodnejšie riešenie ak obaja spolupracujú, pretože vtedy je celkový čas ktorý obaja strávia vo väzení najmenší. Z hľadiska sebeckého správania sa každého z nich je najjednoduchšie priznať sa, pretože tak môže dostať v horšom prípade 5 rokov, oproti možnostiam 1 alebo 10 rokov ak sa neprizná [11].
Stručný vývoj teórie hier
Prvá známa zmienka o teórii hier sa vyskytla v liste z roku 1713 napísanom Jamesom Waldegraveom. V tomto liste Waldegrave navrhol tzv. zmiešanú minimax stratégiu ako riešenie kartovej hry pre dvoch hráčov nazývanej “le Her”. Neskôr roku 1838 využil hernú teoretickú analýzu Antoine Augustin Cournot vo svojej knihe Výskumy matematických princípov teórie bohatstva. V tejto svojej práci Cournot pojednáva o duopoloch a prezentuje riešenie, ktoré je obmedzenou verziou Nashovej rovnováhy.
