MiniRisk – hra pro dlouhé zimní večery
Minirisk je jednoduchá hra pro dva až pět hráčů, ve které soupeři draží karty s různou hodnotou pomocí zajímavého druhu aukce. Cílem hry je s omezenými prostředky získat karty s co možná nejvyšší hodnotou. To ale není vždy tak jednoduché, protože při sestavování nabídky hráči neznají nabídky svých soupeřů a navíc není vždy pravda, že vítězí nejlepší nabídka.
Samozřejě nemám v úmyslu nikoho nutit, aby takovou jednoduchou a veskrze nezáživnou hru hrál osobně, hra ale dostane poněkud jiné dimenze, pokud se na ni podíváte očima člověka, který se zajímá o umělou inteligenci. Aukce v této hře je zajímavá tím, že vyhrává nejvýše jeden (vylučuje spolupráci hráčů) a co víc – nevyhrává nejlepší nabídka, ale nejlepší jedinečná nabídka. A aby toho nebylo málo, hraje se i o karty se zápornou hodnotou. Ty pochopitelně nikdo nechce, a proto je získá hráč, který dal nejnižší jedinečnou nabídku.
Ale proč o ní píšu – před Vánoci Jirka vytvořil jednoduchý server, který umožńuje nechat proti sobě hrát přes síť několik hráčů. K Jirkovu serveru jsou přibaleni i tři počítačoví klienti, ale hlavně je součástí třída v Javě, do které stačí pro implementovat několik metod a máte vlastního agenta. O technické záležitosti jako je komunikace se serverem už se postará ona.
Pravidla hry
Hru hrají vždy alespoń dva hráči, zhora jejich počet omezený není, ale pět hráčů se ukazuje jako rozumné maximum. Každý hráč na začátku hry dostane platební karty v hodnotě 1 až 15 – jednu od každé hodnoty. Na stůl mezi všechny hráče se položí rubem nahoru promíchaný balíček 15 výherních karet, tentokrát v hodnotách -5, -4, …, -1, 1, 2, 3, …, 10.
Hra má vždy 15 kol. V každém kole se napřed otočí lícem nahoru vrchní výherní karta z balíčku. Poté všichni hráči vyberou, platební kartu, pomocí které chtějí otočenou výherní kartu vydražit, a tu položí rubem nahoru před sebe tak, aby ji ostatní hráči neviděli. Pak všichni najednou otočí své platební karty a vyřadí se platební karty, které nabídlo více hráčů najednou. Například pokud hrají tři hráči a za výherní kartu 10 nabídnou platební karty v hodnotě 15, 15 a 14, tak se karty s hodnotou 15 vyřadí a hráči, kteří je nabídli již výherní kartu 10 nemůžou získat.
Pokud je hodnota dražené karty kladná, získá výherní kartu hráč, který za ni nabízí nejvyšší cenu. Pokud hodnota dražené karty je záporná, získá ji hráč, který nabídl cenu nejnižší. Pokud po vyřazení duplicitních nabídek na stole nezbyde žádná platební karta, bude výherní karta vydražená v následujícím kole spolu s další otočenou výherní kartou (pro posuzování, jestli vyhrává nejvyšší, nebo nejnižší nabídka se používá součet hodnot obou dražených karet).
Turnaje
Protože ve hře je zastoupena náhoda (a kvůli učícím-se hráčům), nestačí pro posouzení hráče sehrát jednu partii. Jako rozumné minimum bych bral 200 her, kdy už se náhodné jevy začnou rozpouštět do pravděpodobnostních rozložení a kdy učící-se hráči dostanou šanci předvést, co všechno se dokážou naučit.
Každý účastník turnaje se účastní všech her a mezi jednotlivými hrami si zachovává paměť, takže si může (chce-li uspět, tak musí) pamatovat jak reagovali jeho soupeři a podle toho odhadovat jejich další kroky.
Vedení turnajů je zcela v režii serveru, stejně jako počítání celkového score, kontrola cheatování a vyhlášení vítězů na konci.
Počítačoví hráči
Teorii už známe, taže se můžeme pustit do praktického hraní. Chci říci programování. Pro testování kvalit nového hráče jsou k dispozici tři již existující.
Hráč s pevnou strategií
Je nejjednodušší hráč ve hře. Platební karty má předem přiřazené k výherním poměrně rozumným způsobem tak, aby vyhrál proti náhodnému hráči a proti hráčům hrajícím opravdu špatně. Pro hráče, kteří používají učící algoritmy by neměl být problém proti němu uhrát většinu karet.
Hráč s náhodnou strategií
Karty pro každý tah vybárá zcela náhodně z těch, které mu ještě zbyly. S trochou snahy by ho měl porazit každý… a pokud ne, je něco asi špatně 
Na druhou stranu přítomnost několika náhodných hráčů někdy dokáže turnajem docela zahýbat.
Hráč postavený na reinforcement learning
Učí se reakce svých soupeřů pomocí reinforcement learning algoritmu a v každém kroku odhaduje nejpravděpodobnější kroky svých soupeřů.
Prostor pro další zlepšení… a pro vás
Rádi bychom udělali turnaj, ve kterém by bylo víc "rozumných" hráčů, kteří používají různé algoritmy a zkusili porovnat jejich výkonnost. V současné době je nejlepší hráč s reinforcement learningem, ale to je spíš jednooký mezi slepými – všichni naši hráči zatím hrají reaktivně bez toho, aby si plánovali akce pro další tahy.
My máme v plánu svoje hráče dál vylepšovat, ale budeme rádi když se do přidají i další a pokusí se překonat naše výtvory a vytvořit co možná nejlepšího hráče. Tučné ceny na vítěze nečekají, ale nehynoucí slávy by se tu pro vás snad trochu našlo 
February 5th, 2007 at 13:28
Update 5. 2. 2007
Přidal jsem naivního Monte-Carlo hráče. Naivní ve smyslu, že považuje své a soupeřovy budoucí akce za náhodné jevy s rovnoměrným pravděpodobnostním rozložením.
Idea je ověřit si, že tudy cesta nevede
To abychom se vyhli budoucím překvapením (Co kdyby?).
Výkonově se NaiveMCL řadí před náhodného, ale za reaktivního hráče.
Jestli se nepletu, má Ondra v rukávu něco lepšího. Btw., co s tvým
MemoryClientem?February 5th, 2007 at 13:32
Ad “jednoduchá a nezáživná hra”
Jednoduchá na pravidla jistě. Nezáživná možná při dvou hráčích. Při pěti už dochází k časté shodě nabídek a může vyhrát i nabídka nejnižší. Odhadnout akce čtyř protihráčů už je nesnadné a hru to příjemně okoření.
February 9th, 2007 at 00:30
O Monte-Carlo hráči rád slyším, vyzkouším.
MemoryClientbude, ale víc k tomu teď říct nemůžu. A není to tím, že bych nechtěl.