Kámen-papír-nůžky
Úloha číslo: 3262
Najděte optimální smíšenou strategii pro hru Kámen-papír-nůžky simplexovou metodou.
Řešení
Výplatní matice této hry je: \( \begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \\ \end{pmatrix} \) my ji ale upravíme tak, aby všechny hodnoty byly nezáporné (tím se hra ve své podstatě příliš nezmění) \( A= \begin{pmatrix} 1 & 0 & 2 \\ 2 & 1 & 0 \\ 0 & 2 & 1 \\ \end{pmatrix} \)
Hledáme sloupcový vektor \(\mathbf x=(x_1,x_2,x_3)\), který je řešením úlohy (odpovídající poměrné volbě strategií kámen, papír a nůžky) \(A\mathbf x\le 1\) maximalizujíce výraz \(x_1+x_2+x_3\).
Jedničky na pravé straně odpovídají čistým strategiím protihráče, jeho smíšené strategie lze získat jako lineární (vlastně konvexní) kombinace čistých, proto můžeme provádět elementární úpravy.
Řešením je vektor \(\mathbf x=(1/3{,}1/3{,}1/3)\). (V obecném případě by bylo třeba vektor normalizovat). Optimální strategii pro druhého hráče lze odvodit z koeficientů v účelové funkci u nebázických (t.j. všech pomocných) proměnných – stačí tyto koeficienty znormovat na pravděpodobnostní vektor.
Vyzkoušejte si vyřešit i jiné hry!
