Odevzdávejte do 17.11. v jednom "soběstačném" PDF souboru!

Dobrovolný a nenárokový úkol, bonusovými body (kolem 1-20 i více) budou oceněny jen ta nejlepší řešení -- není limit na počet, ale jen na kvalitu.

 

Zadání příkladu

Čtverečky jsou hra dvou hráčů na čtvereckovaném papíře. Nejdříve se vytyčí hrací pole o velikosti m x n čtverečků a obtáhne se silnou čárou. Poté se hráči střídají, každý ve svém tahu obtáhne jednu libovolnou hranu libovolného čtverecku. Pokud některý z hráčů obtáhne ve svém tahu poslední neobtaženou hranu nějakého čtverečku, získává bod a hraje dále (tj. jeden tah navíc, avšak pokud opět uzavře čtvereček, hraje stále dále). Jakmile jsou obtaženy všechny hrany všech čtverečků v hracím poli, hra končí a vítězem se stává hráč s vyšším počtem bodů. Hranice hrací plochy se považuje za již obtaženou.

V ukázkové partii (obrázek nahoře) vítězí červený hráč 5 ku 4 (modrý začínal, ale ve svém druhém tahu udělal chybu, která umožnila červenému obtáhnout pět čtverečků po sobě).

Co tedy budete řešit za úkoly v tomto příkladě...:

1. Vaším "rozcvičkovým" úkolem je zjistit, jak dopadne hra na poli 1 x n. Pochopitelně předpokládejte, že oba hráči hrají chytře. Na čem všem záleží? Velmi krátce, stručně a výstižně popište a odůvodněte vítěznou strategii. Tato část je pro všechny řešitele povinná, nicméně za ni ještě žádné body udělovat nebudeme.
   

   

2. Hlavním bonusovým úkolem je teoreticky analyzovat strategii pro tuto hru v následujícím zjednodušeném případě, kdy jako (modrý) hráč hrajete Čtverecky proti (červenému) robotovi. Protihráč robot se řídí dvěma pravidly: Pokud robot můze uzavřít některý čtvereček, učiní takto, přečemž při více možnostech uzavření vybere náhodně. Pokud robot nemůže uzavřít žádný čtvereček, obtáhne náhodně jednu z hran, pro které platí, že součet již obtažených hran obou sousedících čtverečků je co nejmenší. Pro ilustraci - obrázek vpravo ukazuje zakroužkované možné hrany, kam bude robot hrát, neboť součet obtažených hran jejich obou sousedních čtverečků je 2, což je méně než součet 3 u zbylých 8 hran označených krížkem.
   • První poněkud slozitějším úkolem je otázka, jaká je situace (hráče proti výše popsanému robotovi) na hracím plánu 2 x n. Například pokud n=2, tak vždy vyhraje ten, který hraje jako druhý. Pokud n=3, pak dokáže hráč proti robotovi vyhrát, pouze pokud hraje první. Podívejte se na vyšší hodnoty n a zjistěte, zda existuje vítězná strategie pro hráče hrajícího proti robotovi v případe, že začíná hráč, i v případe, že hraje jako druhý. Jakých nejlepších výsledků jste schopni na jednotlivých hracích plánech dosáhnout? Pro jaká n dokážete vítěznou strategii najít a správně odůvodnit?
   • Druhá otázka je téměř shodná s první, jen budete (či se aspoň pokusíte) zkoumat hru na poli rozměrů 3 x n. Jak to dopadne tentokrát?
   • V další otázce se zameřte pouze na čtvercová hrací pole n x n. Pokuste se najít co nejvyšší n, pro která dokážete jako hráč s jistotou vyhrát (tj. podat přesnou a úplnou vítěznou strategii) proti robotovi v případe, že hrajete jako první. V jakém poměru bodů? Jako základní hodnoty, které byste měli vyrovnat a nebo překonat, stanovme 8:1 na poli 3 x 3 a 10:6 na poli 4 x 4. (Nebojte se pochlubit čísly ve fóru tohoto bonusového úkolu, at ostatní vidí, co je momentálne největší výzva!)
3. Výše uvedené otázky také můžete místo teoretické analýzy řešit vyčerpávajícím masivním výpočtem všech možných průběhů hry. V tom případě je mimo samotných výsledků nutné vyvinout, popsat a dokázat co nejefektivnější algoritmus prohledávání průběhu hry.

Jelikož se zde jedná o "otevřené" zadání, není třeba řešit všechny podotázky najednou, stačí správně udělat dostatečně zajímavou část z nich (a nejlépe se dostat dále, než ostatní).

Obecné poznámky

S upřesňujícími dotazy se obracejte na cvičící v diskuzi na IS.
Nezapomínejte, že se jedná o vaši vlastní tvůrčí práci! Při opodstatněném podezření z opisování vám nebudou uděleny žádné body. (Respektive z každé třídy příliš podobně vypadajících řešení bude kladně ohodnoceno jen to, které bylo odevzdáno první. V extrémních případech můžeme sáhnout k záporným prémiím a nebo dokonce pak může být přijímání veškerých řešení předčasně zastaveno.) Také nebudou hodnocena řešení, které nevyhoví zde uvedeným formálním specifikacím.

Ve správně zpracovaném projektu očekáváme, že nejprve teoreticky analyzujete problém; poté popíšete slovně postup / algoritmus, který použijete na jeho řešení, a nakonec shrnete všechny dosažené výsledky. Při "počítačovém" řešení algoritmy popisujte podle formálních zásad zavedených v první lekci a také co nejlépe zdůvodněte jejich správnost. Jako příloha (v tomtéž PDF souboru) musí být zahrnut výpis vašeho programového kódu s komentáři, pro naši kontrolu (ten ale nenahrazuje výše zmíněný popis algoritmu!). Na programovacím jazyku nezáleží. Přiložte jen ten "výkonný" kód, nezajímají nás hlavičky knihoven ani vstupně/výstupní operace. Při teoretickém řešení zase formálně sepište použitá tvrzení a všechna vaše nová tvrzení korektně dokažte.

Důležitá poznámka se také týká využívání cizích zdrojů. Ne, nemáme nic proti tomu, když si pomůcky pro řešení projektu vyhledáte v literatuře či nejspíše přímo na internetu. V praxi přece také nebudete všechno řešit sami od začátku, ale s výhodou využijete již nalezené poznatky, takže učit se vyhledávat potřebné informace je také součástí výuky. Je však vždy nutné úplně citovat všechny zdroje, ze kterých jste čerpali poznatky (nejlépe formou funkčního www odkazu). Takže na toto myslete, neboť zatajení citací je víc než dostatečným důvodem k zamítnutí vašeho řešení. A rozhodně neoceníme, pokud si pod "využíváním cizích zdrojů" představíte prosté opsání programu řešícího projekt, třeba od spolužáka. Vaše řešení projektu by mělo být skutečnou "nadstavbou" nad obecně dobře známými poznatky.

Mnoho zdaru a zábavy!