Grafika Logika dozná ještě jistých změn.

Mám mnoho nepěkných vlastností, a sveřepost, či spíše umanutost, mezi nimi zaujímá jedno z předních míst. Když se rozhodnu, že něco chci dokázat, obětuji pro to cokoliv, často v hodnotě, která přesahuje hodnotu dosaženého mnohonásobně, ale prostě – já to chci a nic jiného neřeším a nechci vidět.

Přesně tak je to s Logikem: místo, abych si připustil, že hardware PMD 85 na hru s pěti posicemi a osmi barvami nestačí, strávím dva týdny programováním takového řešení, které hru do malé paměti PMDčka vměstná a všechny překážky objede.

Stalo se a program se tedy blíží završení.

Jak jsem uvedl minule, celý strom řešení se do paměti nevejde a musel jsem tudíž vymyslet, jak z něj vzít pouze část a zbytek nechat stroj dopočítat.

V první fasi jsem se rozhodl, že ponechám ve stromu ty uzly, kde zbývá nejvýš n kombinací, pro dostatečné malé n (jež jsem po úvaze zvolil rovno osmi). Tyto kombinace PMD spočítá a se zbytkem si už nějak poradí.

Jenže ouha: strom (resp. podstrom) je sice malý, v komprimované representaci zabírající nějaké 3 KiB, avšak ono nějak se ukázalo neřešitelně složitým. Jde o takové situace, které odpovídají např. uzlu #10238. V něm zbývají čtyři možnosti, 00035, 00017, 00016 a 00010. Vidíme, že ať vezmu kteroukoli z možností, skore poskytnuté hráčem za všech okolností k řešení v dalším tahu nepovede. Optimální řešení je zvolit 00160, jak soubor gen1.txt správně uvádí. Vidíme, že to opravdu funguje: každý kod dá jiný výsledek a v příštím tahu dostaneme pět černých kolíků; za 1/4 šanci úspěchu obětovanou v tomto tahu dostáváme stoprocentní šanci, resp. jistotu úspěchu, v tahu následujícím, což je dobrý obchod i z hlediska počtu pravděpodobnosti.

Knuthův algorithmus umí toto řešení vypočítat, avšak jak jsme vysvětlili, na PMD ho nelze provádět, protože předpokládá vyzkoušet všech 2¹⁵ – (počet již uskutečněných pokusů) kombinací, což je v čase, po který je hráč ochoten čekat na pokus počítače, neřešitelné. Dospěl jsem tedy ke kompromisu a do stromu doplnil vedle těch uzlů, ve kterých zbývá více než osm kombinací, rovněž ty, kde se optimální kombinace nenachází mezi zbývajícími; Knuthův algorithmus tyto kombinace preferuje, proto mám jistotu, že přidány budou jen ty uzly, kde je volba cizí kombinace pro minimalisaci délky řešení nezbytná. Znamená to dalších cca tisíc uzlů a další 3 KiB délky programu, ale to mohu obětovat. Zbývají mi tak pouze ty uzly, kde je optimálním pokusem některá ze zbývajících kombinací, a mezi nimi, pokud je znám, už se mohu pomocí Knuthova algorithmu rozhodnout.

No dobře, příště mu vymyslím něco těžšího.

Pokud je znám. A to je poslední překážka před dokončením programu. Zde obětuji dalších 8 KiB programu a místo cyklu přes všech 32768 kombinací budu testovat pouze čtvrtinu, přičemž program pro test shody jsem optimalisoval k maximální efektivitě (rutina check_match v souboru game.s).

V jednom místě tak bude uživatel muset na počítač několik sekund počkat, a to je snesitelné.

Jakmile program dokončím, vystavím ho jako obvykle na těchto stránkách, s tím, že může být případně přiložen k mé psychiatrické dokumentaci jako jasný doklad mé duševní poruchy.

Aktualisováno.
Verse k betatestování: logik-1.0-1.ptp

Nakonec jsem z ohleduplnosti k hráči zvolil poněkud jiný přístup, prohloubil podstrom až do úrovně posledních dvou uzlů (17 KiB) a nechal počítač prohledávat celý prostor kodů, bez akcelerace (pro kterou by mi stejně nezbylo místo). Hráč tak má pocit, že počítač se při hře namáhá, i když ve skutečnosti jen mechanicky prochází kody a hledá poslední dvojici, což snižuje hráčovu frustraci a motivuje ho to k další hře.

Komentovat články mohou pouze registrovaní uživatelé; prosím, zaregistrujte se (v pravém sloupci dole)