margin-top: 125px; border: 1px solid gray; } -->

Problém plukovníka Blotta vyřešen

Pavel Houser , 02. březen 2016 12:00 0 komentářů
Problém plukovníka Blotta vyřešen

Počítačoví vědci na University of Maryland, Stanford University a Microsoft Research vyřešili v obecné rovině Problém plukovníka Blotta (Colonel Blotto), úlohu z teorie her známou od roku 1921. Autoři výzkumu uvádějí, že výsledek by mohl pomoci při tvorbě strategií v byznysu nebo v politice.

Problém plukovníka Blotta v nejjednodušší podobě vypadá třeba takto: Jeden z hráčů má k dispozici 6 jednotek, druhý 5, oba můžou své síly rozdělit na dvě pozice (a žádnou nesmí nechat prázdnou). Na příslušné pozici vyhraje ten, kdo ji obsadí více jednotkami, přičemž získá tolik bodů, kolik zde má jednotek soupeř (zajme/zničí je). Neuvažují se vlastní ztráty ani hodnota stanoviště. Zde se už mimochodem ukazuje i třeba vztah k systému amerických prezidentských voleb, vítěz bere všechny hlasy daného státu, i ty protivníka.

Hráči samozřejmě své tahy provádějí, aniž by viděli protivníkovi do karet, jinak by měl výraznou výhodu ten, kdo může reagovat na tah soupeře.

Jak byla úloha zadána výše, vyskytuje se na seminářích z teorie her a lineárního programování na VŠ. Na pohled se zdá, že úlohy tohoto typu musí vést jen k nekonečnému regresu (kdybych já věděl, co udělá on, udělal bych toto, jenže kdyby on věděl, že já vím, udělá něco jiného), tak to ale není. Hledáme, zda existují čisté strategie a tzv. sedlové body, počítáme výplatní matice (tabulka, kde řádky jsou možné strategie jedné strany a sloupce strategie druhé strany) a celkovou hodnotu hry. Složitější úlohy vedou obvykle ke smíšeným strategiím, kdy optimální je „zahrát tah s určitou pravděpodobností“ - předpokládáme více kole her. Populárním v češtině vyšlým úvodem do problematiky je třeba Ken Binmore: Teorie her (Dokořán 2014).

Popsaná verze je ale jen jednoduchou variantou, problém byl původně zadán obecně: Hráči jsou vždy 2 a mají omezené množství zdrojů (rozdíly mezi nimi mohou být různé), které dělí mezi x míst. Různé pozice mohou mít různou cenu i samy o sobě. Někdy se rozlišují útočníci a obránci (při stejném počtu jednotek vyhrávají obránci nebo výsledek může záviset na dalších proměnlivých faktorech).

Až dosud nebylo obecné řešení Blottova problému – a jeho nalezení je právě novinkou, kterou oznámili vědci z výše zmíněných institucí. Vedoucím projektu byl Mohammad Hajiaghayi z University of Maryland a výsledky byly prezentovány na setkání Association for the Advancement of Artificial Intelligence v arizonském Phoenixu.

Výzkumníci dokonce tvrdí, že správnost svého přístupu mohou srovnat s tím, jak se budou chovat kandidáti v amerických prezidentských volbách (zde jako faktor lze zahrnout i různé výchozí podmínky na jednotlivých stanovištích pro obě strany – tj. např. jak daný stát hlasoval minule), k tomu by samozřejmě byla potřeba čísla o rozdělení nákladů na kampaň v jednotlivých státech. I v obecné rovině popisuje hra ovšem střet dvou protivníků, takže třeba na současné republikánské primárky použitelná není. Při použití v byznysu je využití také pochopitelně omezeno na analýzu střetu dvou dominantních hráčů.

Zdroj: ScienceDaily a další


Komentáře


RSS 

Komentujeme

Zákaznické karty čekají změny

Pavel Houser , 17. leden 2017 13:00
Pavel Houser

Jedna z technologií, která se už po léta prakticky nezměnila, i když by mohla? Prý karty zákazníků d...

Více





Kalendář

06. 02.

07. 02.
konference G2B TechEd
15. 02. IDC Predictions 2017
22. 02. IT mezi paragrafy
RSS 

Zprávičky

Facebook postaví v Dánsku datové centrum

ČTK , 20. leden 2017 14:00

Americký provozovatel sociální sítě Facebook postaví v dánském městě Odense nové datové centrum, kte...

Více 0 komentářů

Americký Oracle převezme českou programátorskou firmu Apiary

ČTK , 20. leden 2017 12:00

Americký výrobce podnikového softwaru Oracle podepsal dohodu o převzetí české programátorské firmy A...

Více 0 komentářů

Internetová ekonomika za pět let posílila o 15 procent na 188 miliard

ČTK , 20. leden 2017 07:00

Objem internetové ekonomiky se předloni proti roku 2011 zvýšil o 15 procent na 188 miliard korun. Na...

Více 0 komentářů

Starší zprávičky

Facebook zřídí v Paříži svůj první inkubátor pro začínající firmy

ČTK , 19. leden 2017 14:00

Americká sociální síť Facebook zřídí v Paříži svůj první inkubátor pro začínající firmy, tzv. startu...

Více 0 komentářů

Toshiba prý zvažuje o osamostatnění své polovodičové divize

ČTK , 19. leden 2017 11:00

Japonská společnost Toshiba Corp. zvažuje oddělení svých aktivit v oblasti výroby polovodičů do samo...

Více 0 komentářů

Sněmovna uzákoní pravidla pro informační systémy veřejné správy

ČTK , 19. leden 2017 07:00

Sněmovna zřejmě uzákoní pravidla pro to, jaké funkční vlastnosti mají mít informační systémy ve veře...

Více 0 komentářů

ÚOOÚ za nevyžádaná obchodní sdělení uložil i půlmilionovou pokutu

ČTK , 18. leden 2017 14:00

Úřad pro ochranu osobních údajů (ÚOOÚ) v souvislosti s nevyžádanými obchodními sděleními udělil loni...

Více 0 komentářů