Zvážte párovú konečnú hru. Nechajte hráča A má T osobné stratégie, ktoré označujeme
Nechajte hráča IN k dispozícii P osobné stratégie, označme ich. Hovorí sa, že hra má rozmery T X P.
V dôsledku toho, že si hráči zvolia ľubovoľnú dvojicu stratégií, je výsledok hry jednoznačne určený, t.j. výhry A;. hráč A(pozitívne alebo negatívne) a straty (-ay) hráč IN. Predpokladajme, že hodnoty A.. známy pre akúkoľvek dvojicu stratégií (A:, B;). Matrix P =(a..), i = = 1, 2, ..., m j = 1, 2, ..., P, ktorých prvkami sú výhry zodpovedajúce stratégiám A. A Bj, volal platobná matica, alebo matice hry. Všeobecná forma takáto matica je uvedená v tabuľke. 12.1. Riadky tejto tabuľky zodpovedajú stratégiám hráča A, a stĺpce – stratégie hráča IN.
Tabuľka 12.1
Vytvorme platobnú maticu pre ďalšiu hru.
12.1. Hľadanie hry.
Hráč A môže sa ukryť v jednom z dvoch úkrytov (I a II); hráč IN hľadá hráča A, a ak ho nájde, dostane pokutu 1 den. Jednotky od A, inak zaplatí hráč A 1 deň Jednotky Je potrebné zostaviť platobnú maticu hry.
RIEŠENIE. Na zostavenie platobnej matice by ste mali analyzovať správanie každého hráča. Hráč A môže sa skrývať v úkryte I - túto stratégiu označujeme A v alebo do úkrytu II – stratégia A. d Prehrávač IN môže hľadať prvého hráča v úkryte I - stratégia IN(alebo do útulku II - stratégia IN.,. Ak hráč A sa nachádza vo Vault I a tam ho objaví hráč IN, tie. implementuje sa niekoľko stratégií (Α ν IN{), potom hráč A zaplatí pokutu, t.j. A n = -1. Podobne dostaneme A. n = -1 (A 2, IN.,). Je zrejmé, že stratégie (A, IN.,) a (L2, /1,) dajte hráčovi A odmena je 1, teda A P = a. n = I. Pre vyhľadávaciu hru s veľkosťou 2x2 teda získame výplatnú maticu:
Zvážte hru T X P s matricou P = a j) , i = 1,2, ..., τη; j= 1, 2, ..., a určiť najlepšiu spomedzi stratégií A pri A v..., A t) Výber stratégie A jy prehrávač A musí očakávať, že hráč IN odpovie pomocou jednej zo stratégií IN., za čo je odmena pre hráča A minimálne (hráč IN snaží sa hráčovi „ublížiť“. A).
Označme a; najmenšie výhry hráča A keď zvolí stratégiu L; pre všetky možné hráčske stratégie IN(najmenšie číslo v i-tý riadok platobná matica), t.j.
Medzi všetkými číslami a (r = 1,2,..., T) Vyberme najväčšie: . Zavolajme a nižšia cena hry, alebo maximálne výhry (maximum). Toto zaručená výhra pre hráča A pre akúkoľvek stratégiu hráča B. teda
(12.2)
Stratégia zodpovedajúca maximínu sa nazýva stratégia maximin. Hráč IN záujem o zníženie výhier hráča A; výber stratégie IN., berie do úvahy maximálny možný zisk pre A. Označme
Medzi všetkými číslami β. vyberme si toho najmenšieho,
a zavolajte β najvyššia cena hry, alebo minimax výhra (minimax). Toto garantovaná strata pre hráča B. teda
(12.4)
Stratégia zodpovedajúca minimaxu sa nazýva minimax stratégiu.
Princíp, ktorý diktuje hráčom, aby si zvolili „najopatrnejšie“ stratégie minimaxu a maxima, sa nazýva princíp minimax. Tento princíp vyplýva z rozumného predpokladu, že každý hráč sa snaží dosiahnuť cieľ opačný ako jeho súper. Stanovme spodnú a hornú cenu hry a zodpovedajúce stratégie v úlohe 12.1. Zvážte platobnú maticu
od problému 12.1. Pri výbere stratégie L, (prvý riadok matice) minimálne výhry sa rovná a, =min(-l; 1) = -1 a zodpovedá stratégii β1 hráča IN. Pri výbere stratégie L 2 (druhý riadok matice) je minimálna výhra A 2 = min(l; -1) = -1, dosiahne sa stratégiou IN.,.
Zaručiť sa maximálna výhra pre akúkoľvek hráčsku stratégiu IN, t.j. nižšia cena hry a = max(a, a2) = = max(-l; -1) = -1, hráč A môže zvoliť akúkoľvek stratégiu: Aj alebo A 2, t.j. niektorá z jeho stratégií je maximálna.
Výber stratégie B, (stĺpec 1), hráča IN chápe, že hráč A bude reagovať stratégiou A 2, aby ste maximalizovali svoje výhry (prehra IN). Preto je maximálna strata hráča IN keď zvolí stratégiu B, rovná sa β, = kontrola (-1; 1) = 1.
Podobne aj maximálna strata hráča B (výhra A) keď si zvolí stratégiu B2 (stĺpec 2) sa rovná β2 = max(l; -1) = 1.
Teda pre akúkoľvek hráčsku stratégiu A garantovaná minimálna strata hráča B sa rovná β = = πιίη(β1, β2) = min(l; 1) = 1 - horná cena hry.
Akákoľvek stratégia hráča B je minimax. Po pridaní tabuľky 12,1 čiara β; a stĺpec a;, dostaneme tabuľku. 12.2. Na priesečníku doplnkových riadkov a stĺpcov si zapíšeme hornú a dolnú cenu hier.
Tabuľka 12.2
Vo vyššie uvedenom probléme 12.1 sú horné a dolné ceny hry odlišné: a F β.
Ak sa horná a dolná cena hry zhodujú, potom všeobecný význam horná a dolná cena hry α = β = υ sa nazýva čistá cena hry, alebo za cenu hry. Minimax stratégie zodpovedajúce cene hry sú optimálne stratégie, a ich totalita - optimálne riešenie, alebo rozhodnutie hry. V tomto prípade prehrávač A dostane garantované maximum (nezávisle od správania hráča) IN) odmena je υ a hráč IN dosiahne minimálnu garantovanú (bez ohľadu na správanie hráča A) stratu υ. Hovoria, že riešenie hry má stabilita, tie. ak sa jeden z hráčov drží svojho optimálna stratégia, potom nemôže byť pre druhého výhodné odchýliť sa od jeho optimálnej stratégie.
Pár čistých stratégií A. a B. dáva optimálne riešenie hry práve vtedy, ak príslušný prvok y je súčasne najväčší vo svojom stĺpci a najmenší v riadku. Táto situácia, ak existuje, sa nazýva sedlový bod(podobne ako povrch sedla, ktorý sa jedným smerom ohýba hore a druhým smerom dole).
Označme A* A IN*– dvojica čistých stratégií, ktoré dosahujú riešenie hry v probléme sedlového bodu. Predstavme si výplatnú funkciu prvého hráča pre každú dvojicu stratégií: P(A:, IN-) = a y. Potom z podmienky optimality v sedlovom bode platí dvojitá nerovnosť: P(Aj, B*)<Р(А*, В*)<Р(А", В ), čo je spravodlivé pre všetkých i = 1, 2, ..., m;j = 1, 2, ..., P. Naozaj, výber stratégie A* prvý hráč s optimálnou stratégiou IN" druhý hráč maximalizuje minimálnu možnú výplatu: P(A*, B")> P(A G IN"), a výber stratégie B" druhý hráč s optimálnou stratégiou prvého minimalizuje maximálnu stratu: P(D, IN*)<Р(А", В).
12.2. Určte spodnú a hornú cenu hry danú platobnou maticou
Má hra sedlovú pointu?
Tabuľka 12. 3
Riešenie. Je vhodné vykonávať všetky výpočty v tabuľke, ktorá okrem matice R, je zadaný stĺpec a; a reťazec)
