Zobrazenie zdroja stránky Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch

[[Kategória:Študentské práce]]
[[Kategória:Bakalárske práce]]
[[Kategória:Informatika]]
[[Kategória:Matematika]]
<H1_CSS chapter="1" prefix="Kapitola" />
{{Hlavička_FM|{{PAGENAME}}|Ľubomír Milko
|Ing. Juraj Ďuďák
|2009/2010
|Bakalárska práca
|Mechatronika
}}
<div class="sideBox">
{| class="" border=0 cellpadding=5
|+ Obsah práce
|-
| 1.
| [[Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch| Teória hier]]
|-
| 2.
| [[Teória grafov]]
|-
| 3.
| [[Aplikácia stromov a princípov z teórie hier v niektorých ťahových hrách]]
|-
| 4.
| [[Implementácia algoritmov z teórie hier a teórie grafov do spoločenskej hry dáma]]
|}
</div>
__TOC__
{{Abstrakt
|Táto práca obsahuje charakteristiku a stručnú históriu teórie hier a teórie grafov a popisuje rôzne druhy reprezentácie problémov pomocou týchto teórií. Časť práce sa zaoberá použitím herných stromov a metódy minimax na analýzu a riešenie hier. Cieľom práce je potom programová implementácia metódy minimax s alfa-beta orezávaním pri tvorbe umelej inteligencie pre hru dáma naprogramovanú v jazyku C++.
|This work contains the characteristics and short history of  game theory and graph theory and describes various forms of representation of problems using these theories. Part of this work deals with using game trees and minimax method for analysing and solving games. The aim of this work is a program implementation of minimax method with alpha-beta pruning in artificial intelligence for the game draughts programmed in C++ language.
}}

__TOC__

'''Ú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 praktické využitie poznatkov z 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 v programe – hra dáma


'''Zoznam použitých skratiek a pojmov'''

;GUI: (z angl. Graphical User Interface) grafické užívateľské rozhranie
;AI: (z angl. Artificial Intelligence) umelá inteligencia
;RAND: (z angl. Research ANd Development) americká nezisková výskumná korporácia, ktorá bola založená pre americkú armádu, no neskôr sa jej pole pôsobnosti rozšírilo aj do iných oblastí.
;Hra: V teórii hier je hra strategická interakcia medzi jednotlivcami.
;Hráč: Hráčom sa označuje každý aktívny účastník hry.
;Pozícia: Pozícia je označenie pre aktuálny stav hry. Môže to byť napr. rozloženie figúrok na šachovnici.
;Ťah: Ťah je zvolená a uskutočnená stratégia hráča v danej pozícii hry.
;Riešenie hry: Riešením hry je nájdenie takej postupnosti ťahov (stratégie), ktorá vedie k viťaznej pozícii.
;Graf: V teórii grafov je grafom objekt tvorený množinou bodov poprepájaných čiarami podľa daných pravidiel. Body sú označované ako vrcholy a čiary ako hrany grafu.
;Strom: Herný strom je typ grafu, ktorý sa využíva na znázornenie priebehu hry.	
;Vrchol (uzol): Vrchol herného stromu reprezentuje pozíciu hry.
;Hrana: Hrana herného stromu symbolizuje ťah niektorého z hráčov z určitej pozície.
;Minimax: Metóda minimax sa využíva na prehľadávanie herných stromov s cieľom nájdenia optimálneho ťahu z danej pozície.
;Alfa-beta orezávanie: Technika na zmenšenie počtu prehľadávaných vrcholov v metóde minimax, čím sa proces prehľadávania urýchli.
;TRUE: Označenie true symbolizuje logickú hodnotu pravda. Symbolom logickej pravdivosti je aj číslo 1.	
;FALSE: Označenie false symbolizuje logickú hodnotu nepravda. Symbolom logickej nepravdivosti  aj číslo 0.


=Teória hier=
==Základné pojmy a charakteristika teórie hier==

[http://sk.wikipedia.org/wiki/Te%C3%B3ria_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.<ref name="game_theory">Game theory. Wikipedia. [Online] 2009. [Dátum: 2. 1 2009.] http://en.wikipedia.org/wiki/Game_theory.</ref>

Súbor situácií, v ktorých sa každý účastník môže nachádzať je v teórii hier nazývaný [http://en.wikipedia.org/wiki/Game#Definitions 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 [http://en.wikipedia.org/wiki/Strategy 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.<ref name="game_theory"/> Jedná sa o tzv. [[#Hry s nulovým a nenulovým súčtom | hry s nulovým súčtom]]. 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 [http://en.wikipedia.org/wiki/Nash_equilibrium Nashova rovnováha].	

===Nashova rovnováha===

Je to 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 ?“ .<ref name="nash_equilibrium">Nash equilibrium. Wikipedia. [Online] 2008. [Dátum: 2. 1 2009.] http://en.wikipedia.org/wiki/Nash_equilibrium.</ref> Jedným z najznámejších typov takejto hry je napr. [http://sk.wikipedia.org/wiki/V%C3%A4z%C5%88ova_dilema väzňova dilema] spopularizovaná matematikom [http://en.wikipedia.org/wiki/Albert_W._Tucker Albertom W. Tuckerom]. 

===Väzňova dilema===

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á.<ref name="vaznova_dilema">Kadlic, Michal. Iterovaná väzňova dilema. [Online] 2008. [Dátum: 2. 1 2009.] http://www2.fiit.stuba.sk/~kapustik/ZS/Clanky0405/kadlic/ipd.html.</ref>

==Stručný vývoj teórie hier==

Prvá známa zmienka o [[#Teória hier | teórii hier]] sa vyskytla v liste z roku 1713 napísanom [http://en.wikipedia.org/wiki/James_Waldegrave,_1st_Earl_Waldegrave 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 [http://en.wikipedia.org/wiki/Augustin_Cournot 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 [[#Nashova rovnováha | Nashovej rovnováhy]].

Hoci bola Cournotova analýza viac všeobecná ako Waldegraveova, teória hier stále neexistovala ako samostatná oblasť vedy, až pokiaľ [http://en.wikipedia.org/wiki/John_von_Neumann John von Neumann], ktorý je považovaný za zakladateľa teórie hier, nepublikoval sériu prác na túto tému v roku 1928. Neskôr, v roku 1944, Von Neumann spolu s [http://en.wikipedia.org/wiki/Oskar_Morgenstern Oskarom Morgensternom] vydal knihu ''Teória hier a ekonomické správanie''. Táto kniha obsahuje metódy hľadania riešení hier dvoch hráčov [[#Hry s nulovým a nenulovým súčtom | s nulovým súčtom]]. Počas tohto obdobia bola teória hier primárne zameraná na teóriu [[#Kooperatívne a nekooperatívne hry | kooperatívnych hier]], ktorá analyzovala optimálne stratégie pre skupiny jednotlivcov za predpokladu, že môžu medzi sebou presadiť dohodu o vhodnej spoločnej stratégii.

V roku 1950 sa objavila prvá zmienka o väzňovej dileme a organizácia [http://en.wikipedia.org/wiki/RAND RAND]  (Research ANd Development)  podnikla experiment na základe tejto hry. V tomto čase aj [http://en.wikipedia.org/wiki/John_Forbes_Nash,_Jr. John Nash] vyvinul kritérium pre vzájomnú koexistenciu stratégie hráčov, známe ako [[#Nashova rovnováha | Nashova rovnováha]]. Toto kritérium možno aplikovať na širšie spektrum hier, než kritérium, ktoré navrhli Neumann a Morgenstern. Toto kritérium je dostatočne univerzálne a umožňuje analýzu kooperatívnych aj nekooperatívnych hier. 

Teória hier zaznamenala náhly vzostup v 50-tych rokoch, kedy boli vymyslené nové herné koncepty ako napríklad: jadrá, [[#Rozšírená forma | rozšírená forma]] hier, fiktívne hry, atď. V tomto období sa aj objavili prvé aplikácie teórie hier vo filozofii a politike.

V roku 1956 [http://en.wikipedia.org/wiki/Reinhard_Selten Reinhard Selten] uviedol svoj koncept riešenia tzv. [http://en.wikipedia.org/wiki/Perfect_equilibrium perfektnej rovnováhy] v určitej podmnožine hry, ktorá vylepšila [[#Nashova rovnováha | Nashovu rovnováhu]]. 

V 70-tych rokoch bola teória hier výrazne aplikovaná v biológii, hlavne ako dôsledok práce [http://en.wikipedia.org/wiki/John_Maynard_Smith Johna Maynarda Smitha] a jeho evolučne stabilnej stratégie. Navyše boli uvedené a analyzované ďalšie koncepty rozširujúce teóriu hier.

V roku 2005, herní teoretik [http://en.wikipedia.org/wiki/Thomas_Schelling Thomas Schelling] získal Nobelovu cenu za prácu na dynamických modeloch, ktoré boli prvotnými ukážkami [http://en.wikipedia.org/wiki/Evolutionary_game_theory evolučnej hernej teórie]. 

V roku 2007 boli [http://en.wikipedia.org/wiki/Roger_Myerson Roger Myerson], spolu s [http://en.wikipedia.org/wiki/Leonid_Hurwicz Leonidom Hurwiczom] a [http://en.wikipedia.org/wiki/Eric_Maskin Ericom Maskinom] ocenení Nobelovou cenou za ekonomiku za položenie základov [http://en.wikipedia.org/wiki/Mechanism_design_theory teórie dizajnu mechanizmov hier].

==Oblasti využitia teórie hier==

[[#Teória hier | Teória hier]] bola využívaná hlavne na štúdium správania ľudí a zvierat. Primárne bola rozvíjaná v ekonomike na pochopenie rôznych druhov ekonomického správania, zahŕňajúcich správanie firiem, trhu a zákazníkov. Postupne sa využitie teórie hier v spoločenských vedách zväčšovalo a poznatky z teórie hier sa začali aplikovať aj na politické, sociologické a psychologické javy. 

Hernú teoretickú analýzu spočiatku využíval [http://en.wikipedia.org/wiki/Ronald_Fisher Ronald Fisher] na štúdium správania zvierat v 30-tych rokoch (hoci ešte predtým urobil k tejto téme niekoľko neformálnych vyjadrení [http://sk.wikipedia.org/wiki/Charles_Darwin#Orchidee.2C_Vari.C3.A1cia.2C_P.C3.B4vod_.C4.8Dloveka_a_.C4.8Cervy Charles Darwin]). Neskôr boli analytické metódy, ktoré využíval aj Fisher pomenované teória hier. Výsledky rozvoja tejto oblasti v ekonomike boli neskôr rozsiahlo aplikované v biológii Johnom M. Smithom v jeho knihe [http://en.wikipedia.org/wiki/Evolution_and_the_Theory_of_Games Evolúcia a teória hier]. 

Poznatky z teórie hier sa využívajú aj na predpovedanie a vyloženie etického a normatívneho správania. Vo filozofii sa teória hier aplikovala na pochopenie dobrého alebo správneho správania. Počiatky využitia teórie hier na tomto poli môžu byť datované až do čias Platóna. 

Prvotné aplikácie teórie hier v politických vedách je možno nájsť v práci [http://en.wikipedia.org/wiki/Anthony_Downs Anthonyho Downsa]. Významnou je napr. jeho kniha Ekonomická teória demokracie (1957). 

V ekonomike je teória hier využívaná na analýzu veľkého množstva ekonomických javov ako napr. trh, aukcie, výpredaje, duopoly, oligopoly, sociálna sieť a volebné systémy. Tento výskum sa zvyčajne zameriava na určitý súbor stratégií známych ako equilibrium (rovnováha) v hrách. V [[#Kooperatívne a nekooperatívne hry | nekooperatívnych hrách]] je najznámejším z týchto konceptov spomínaná [[#Nashova rovnováha | Nashova rovnováha]].

V posledných rokoch zohráva teória hier významnú úlohu aj v počítačových vedách a logike. Hry sú napr. využívané na modelovanie interaktívnych výpočtov. 

Využitie teórie hier však možno nájsť aj v telekomunikáciách, doprave, psychológii, vojenských vedách, hazarde a mnohých iných oblastiach.

==Spôsoby reprezentácie rozhodovacích problémov==

Hry skúmané v teórii hier sú dobre definovateľnými matematickými objektmi. [[#Základné pojmy a charakteristika teórie hier | Hra]] pozostáva zo súboru hráčov, súboru ťahov (alebo stratégií), ktoré môžu hráči vykonať a daného ohodnotenia, pre každú kombináciu stratégií. Pre [[#Kooperatívne a nekooperatívne hry | nekooperatívne hry]] , kde hráči navzájom nemôžu spolupracovať sa využíva [http://en.wikipedia.org/wiki/Extensive-form_game rozšírená] alebo [http://en.wikipedia.org/wiki/Normal_form_game normálna] forma reprezentácie hry. [[#Kooperatívne a nekooperatívne hry | Kooperatívne hry]] sú často reprezentované [http://en.wikipedia.org/wiki/Characteristic_function charakteristickou funkciou]. 

===Rozšírená forma===

[[Súbor:Atgathvrp-obr1-rozsirena_forma.png | thumb | 200px | right | '''Obr. 1 – Rozšírená forma hry''']]
[http://en.wikipedia.org/wiki/Extensive-form_game Rozšírená forma] môže byť použitá na opis hier s určitým dôležitým poradím vykonávania jednotlivých ťahov (stratégií). Takéto hry sú často reprezentované ako [[Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch_3#Herné stromy | herné stromy]]. Každý vrchol (uzol) tu predstavuje rozhodovací bod hráča. Hráč je označený číslom pri každom vrchole. Čiary smerujúce z každého vrcholu reprezentujú možnú akciu (ťah) príslušného hráča. Odmeny (hodnotenie) hráčov sú reprezentované na konci posledných spodných čiar. 

V hre znázornenej na obrázku 1 sú dvaja hráči. ''Hráč 1'' začína a má možnosti ''F'' alebo ''U''. ''Hráč 2'' vidí ťah ''Hráča 1'' a vyberá si medzi ťahmi ''A'' a ''R''. Ak uvažujeme, že ''Hráč 1'' vyberie ''U'' a ''Hráč 2'' zvolí možnosť ''A'', potom ''Hráč 1'' získa hodnotenie ''8'' a ''Hráč 2'' získa hodnotenie ''2''.

Rozšírenou formou sa dajú zachytiť aj hry so [[#Simultánne a ťahové (sekvenčné) hry | simultánnym pohybom]] a [[#Hry s úplnými a neúplnými informáciami | hry s neúplnou informáciou]]. V takomto prípade buď bodkovaná čiara spája uzly na znázornenie, že sa jedná o rovnaký súbor informácií (teda, že hráči nevedia, v ktorom bode sa nachádzajú) alebo je okolo takýchto uzlov nakreslená uzavretá čiara.<ref name="game_theory"/>

===Normálna forma===

[[Súbor:Atgathvrp-tab1-normalna_forma.png | thumb | 300px | right | '''Tab. 1 – Normálna forma – väzňova dilema''']]
[http://en.wikipedia.org/wiki/Normal_form_game Normálna (alebo strategická)] forma  hry je reprezentovaná maticou, ktorá zobrazuje hráčov, stratégie a odmeny. Pre každú kombináciu ťahov (stratégií) priraďuje zodpovedajúce ohodnotenie (odmenu) každému z hráčov. V tabuľke 1 je znázornená tzv. [[#Väzňova dilema | väzňova dilema]]. ''Väzeň 1'' vyberá svoju stratégiu jednania z riadkov a ''väzeň 2'' zo stĺpcov. Každý z väzňov má na výber dve stratégie, reprezentované dvomi riadkami a dvomi stĺpcami. Vo vnútri buniek sú zapísané počty rokov (odmena) , ktoré budú musieť stráviť vo väzení pri zvolených stratégiách . Nevýhodné odmeny sú zvyčajne pre upresnenie zapísané zápornou hodnotou. Prvé číslo znázorňuje odmena ''väzňa 1'', druhé číslo je odmena ''väzňa 2''. 

Za predpokladu, že ''väzeň 1'' zvolí možnosť spolupracovať a ''väzeň 2'' bude tiež spolupracovať získajú obaja ohodnotenie ''-1''. Ak je hra reprezentovaná touto formou predpokladá sa, že hráči vykonávajú svoje ťahy (stratégie) súčasne alebo prinajmenšom nepoznajú ťah súpera. V opačnom prípade sa hry znázorňujú [[#Rozšírená forma | rozšírenou formou]].<ref name="game_theory"/>

===Forma charakteristickej funkcie===

Využíva sa pri [[#Kooperatívne a nekooperatívne hry | kooperatívnych hrách]], kde nie sú určené žiadne individuálne odmeny pre hráčov. Namiesto toho [http://en.wikipedia.org/wiki/Characteristic_function charakteristická funkcia] definuje ohodnotenie každého spojenectva. Štandardným predpokladom je že prázdna koalícia získa ohodnotenie 0. 

Pôvod tejto formy pochádza z knihy [http://en.wikipedia.org/wiki/Von_Neumann von Neumanna] a [http://en.wikipedia.org/wiki/Oskar_Morgenstern Morgensterna], ktorí pri štúdiu koaličných hier vyjadrených normálnou formou usúdili, že ak sa vytvorí koalícia ''K'', hrá proti inej koalícii ''N'' ''(N\K)'' rovnako ako keby sa hrala hra dvoch hráčov. Existujú rôzne modely odvodenia koaličných odmien z [[#Normálna forma | normálnej formy hry]], ale nie všetky hry v charakteristickej forme  môžu byť odvodené z hier určených normálnou formou. 

Formálne je hra určená formou charakteristickej funkcie daná dvojicou ''(N,ϑ)'', kde ''N'' označuje súbor hráčov a ''ϑ:2^N→R'' je charakteristická funkcia.<ref name="game_theory"/> 

===Forma rozdeľujúcej funkcie===

Rozšírenie [[#Forma charakteristickej funkcie | formy charakteristickej funkcie]], kde odmena koalície nezávisí iba na jej členoch, ale tiež na spôsobe akým sú rozdelení ostatní hráči.<ref name="game_theory"/>

==Typy hier==
===Kooperatívne a nekooperatívne hry===

Hra je [http://en.wikipedia.org/wiki/Cooperative_game kooperatívna] ak hráči majú možnosť vytvoriť medzi sebou určité zväzky - '''koalície'''. V takomto druhu hier sa od hráčov vyžaduje dodržanie týchto ich záväzkov. V [http://en.wikipedia.org/wiki/Non_cooperative_game nekooperatívnych hrách] sa takéto záväzky nedodržiavajú. Často je tiež v kooperatívnych hrách usudzované, že hráči môžu navzájom ''komunikovať'' (teda, že vedia navzájom o svojich stratégiách vo vytvorenom zväzku). Pri nekooperatívnych hrách je na druhú stranu väčšinou možné modelovať situácie do najmenších detailov a vyvodzovať presné dôsledky. Kooperatívne hry sa sústreďujú na hru ako celok. Určitým spojením medzi kooperatívnymi a nekooperatívnymi hrami sú tzv. '''hybridné hry''', ktoré obsahujú elementy z oboch typov.<ref name="game_theory"/>

===Symetrické a asymetrické hry===

[[Súbor:Atgathvrp-tab2-symetricka_hra.png | thumb | 300px | right | '''Tab. 2 – Symetrická hra''']]
[http://en.wikipedia.org/wiki/Symmetric_games Symetrické hry] sú také, kde odmeny (ohodnotenia) za zvolenie určitej stratégie závisia iba od ostatných stratégií, ktoré zvolia ostatní hráči a nie od toho, kto volí danú stratégiu. Inak povedané, ak môžeme zameniť hráčov a odmeny budú stále rovnaké, potom hra je symetrická. Väčšina bežne študovaných hier 2x2 je symetrická. Príkladom je napr. [[#Väzňova dilema | väzňova dilema]]. Tabuľka 2 je ukážka symetrickej hry v [[#Normálna forma | normálnej forme]].

Väčšina asymetrických hier sú hry, kde hráči nemajú na výber rovnaké stratégie. Je tiež ale možné, že hra, ktorá má pre oboch hráčov stratégie identické, nie je symetrická. Takéto hry sa líšia v ohodnotení stratégií v závislosti od toho, aký hráč danú stratégiu vykonal.<ref name="game_theory"/>

===Hry s nulovým a nenulovým súčtom===

[[Súbor:Atgathvrp-tab3-hra_s_nulovym_suctom.png | thumb | 300px | right | '''Tab. 3 – Hra s nulovým súčtom''']]
[http://en.wikipedia.org/wiki/Zero_sum_game Hry s nulovým súčtom] sú špeciálnym typom hier s konštantným súčtom, v ktorých voľby hráčov nemôžu ani zvýšiť a ani znížiť zdroje, ktoré sú k dispozícii. V hrách s nulovým súčtom je celkové ohodnotenie všetkých hráčov vždy rovné nule (hráč môže profitovať iba na adekvátny  úkor ostatných). Príkladom takýchto hier sú aj doskové spoločenské hry ako šach, dáma alebo napr. poker. Tabuľka 3 znázorňuje hru dvoch hráčov s nulovým súčtom.

Mnoho hier však sú hry s nenulovým súčtom (vrátane [[#Väzňova dilema | väzňovej dilemy]]). Zisk jedného hráča tu nemusí nutne znamenať stratu hráča druhého. 

Hry s konštantným súčtom zodpovedajú javom ako krádeže a hazardné hry, ale nie základným ekonomickým princípom, kde je možné potenciálne nadobudnúť zisk z obchodu.<ref name="game_theory"/>

===Simultánne a ťahové (sekvenčné) hry===

[http://en.wikipedia.org/wiki/Simultaneous_game Simultánne hry] sú také, pri ktorých hráči vykonávajú svoje stratégie (ťahy) súčasne alebo ak neťahajú súčasne, tak hráči, ktorí sú na ťahu neskôr nevedia o predošlých akciách svojich súperov. 

V [http://en.wikipedia.org/wiki/Sequential_game sekvenčných hrách] majú tzv. neskorší hráči určité poznatky o predošlých akciách ostatných. Tieto poznatky však môžu byť len veľmi obmedzené. Môžu byť napr. informovaní len o tom, že nejaký hráč nevykonal určitú stratégiu, no nevedia, ktorú z možných stratégií vykonal. Na reprezentáciu simultánnych hier sa často volí [[#Normálna forma | normálna forma]] a na reprezentáciu sekvenčných [[#Rozšírená forma | rozšírená forma]].<ref name="game_theory"/>

===Hry s úplnými a neúplnými informáciami===

[[Súbor:Atgathvrp-obr2-hra_s_neuplnymi_informaciami.png | thumb | 300px | right | '''Obr. 2 – Hra s neúplnými informáciami''' <br>
bodkovaná čiara predstavuje neznalosť hráča 2 o akcii hráča 1]]
Hry s [http://en.wikipedia.org/wiki/Perfect_information úplnými informáciami] sú dôležitou podmnožinou [[#Simultánne a ťahové (sekvenčné) hry | sekvenčných hier]]. Pri hrách s úplnými informáciami všetci hráči vedia o všetkých predošlých ťahoch ostatných hráčov. To znamená, že takýmto druhom hier nemôžu byť simultánne hry, pri ktorých už z princípu ostatní hráči nevedia o všetkých predošlých akciách svojich spoluhráčov.Väčšina hier analyzovaných v hernej teórii sú však hry s neúplnou informáciou. Hry s úplnou informáciou predstavujú aj rôzne doskové spoločenské hry ako napr. šach, Go, dáma a iné. 

Hry s úplnými informáciami bývajú často zamieňané s hrami s [http://en.wikipedia.org/wiki/Complete_information kompletnými informáciami], čo sú hry, pri ktorých každý hráč pozná stratégie a ohodnotenia ostatných hráčov, nemusí však vedieť o tom aké akcie vykonali, teda, ktoré stratégie zvolili. Obrázok 2 ukazuje znázornenie hry s neúplnými informáciami v [[#Rozšírená forma | rozšírenej forme]].<ref name="game_theory"/>

===Nekonečne dlhé hry===

Hry analyzované ekonómami a reálnymi hráčmi sú obecne ukončené po určitom konečnom počte krokov. V matematike a teórii množín však sú objektom štúdia aj hry, ktoré trvajú nekonečný počet ťahov s víťazom (alebo daným ohodnotením) známym až po ukončení všetkých ťahov.

Záujem sa v takomto prípade hier nesústreďuje ani tak na najoptimálnejší spôsob hry ako zisťovanie, či pre určitého hráča existuje alebo neexistuje tzv. '''výherná stratégia'''. Existencia takýchto stratégií má významné dôsledky v deskriptívnej teórii množín.<ref name="game_theory"/>

===Metahry===

Sú to hry, ktorých hra znamená rozvoj pravidiel, cieľa alebo predmetu inej hry. Metahry sa snažia o maximalizovanie praktickej hodnoty vyvinutého súboru pravidiel. Teória [http://en.wikipedia.org/wiki/Metagame metahier] je spojená s dizajnom [http://en.wikipedia.org/wiki/Mechanism_design mechanizmov hier].<ref name="game_theory"/>

==Odkazy==

<references />