Druhá série dvacátého čtvrtého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

• Termín série: 19. prosince 2011 8:00
• Termín CodExové úlohy: 20. prosince 2011 8:00
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 24-2-1: Požární poplach
• 24-2-2: Centrální sklad
• 24-2-3: Odčítání
• 24-2-4: Odbočení vlevo
• 24-2-5: Logická formule
• 24-2-6: Závorky
• 24-2-7: Štětcování
• 24-2-8: Alfa-beta ořezávání a piškvorky

24-2-1 Požární poplach (11 bodů)

V lese hoří. Představme si les jako čtvercovou síť, na každém políčku je buďto skála (neprůchozí políčko), požár, nebo les. Požár se za jednotku času rozšíří na všechna sousední políčka, na kterých je ještě les.

Lesem je však potřeba bez úhony projít a nás zajímá, jak dlouho to ještě bude možné. Váš program dostane na vstupu nejprve rozměry lesa (R a S) a potom R řádků délky S složených ze znaků @ (oheň), # (skála) a . (les).

6 6
@#...@
.#.###
......
####.#
.....#
####..

@#@@@@
@#@###
@@@@@@
####@#
....o#
####..

Na výstupu vypíšete, kolik jednotek času bude les ještě průchozí zleva doprava. To znamená, že z alespoň jednoho políčka na levém okraji bude existovat cesta pouze nehořícím lesem do nějakého políčka na pravém okraji. Pohyb je povolen pouze svisle a vodorovně, nikoli šikmo.

Pro zobrazený vstup je správným řešením číslo 7 – oheň se rozhoří jako na druhém obrázku. O chvíli později by již hořelo i políčko označené o a les by byl neprůchozí.

Řešení

Jste jistě zvědavi, k čemu pasáčkovi byla ona slibovaná metoda. Jednoduše si po průchodu lesem spočítal, kolik ovcí mu zbylo a kolik ovcí uhořelo. Co jiného byste čekali?

* * *

Uplynulo mnoho vody v řece, přes kterou potom pasáček převedl ovce, aby neuhořely v rozsáhlém lesním požáru, než někoho napadlo počítat třeba přesouváním kuliček na počítadle. I to je však nástroj značně dávného původu.

Každý z nás snad někdy počítal na počítadle v první třídě, občas někdo slyšel o ruském sčotu.

Dovolme si malou odbočku. V Rusku bylo ještě před nějakou dobou naprosto běžné počítat na sčotech. Byl o ně tudíž velký zájem, a tak byly nedostatkovým zbožím.

Problém byl v chybně umístěném centrálním skladu. Velení armády totiž rozhodlo (sčoty byly strategickým zbožím), že všechny vyrobené sčoty se budou svážet do centrálního skladu do Moskvy a odtamtud distribuovat po celém Rusku.

24-2-2 Centrální sklad (9 bodů)

Pro zjednodušení si představme celé Rusko jako přímku. Na přímce leží N bodů – výrobců sčotů. Nalezněte ideální místo pro centrální sklad – takové, že průměrná vzdálenost mezi centrálním skladem a výrobci bude minimální.

Na vstupu je na prvním řádku číslo N a na druhém N čísel oddělených mezerou – souřadnic výrobců. Vypište jediné číslo – souřadnici centrálního skladu. Je-li více možných řešení, vypište libovolné z nich.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

Generální štáb vzápětí zjistil, že chyba byla nejen ve špatně umístěném centrálním skladu, ale i v centralizaci celého zásobování, takže sčoty byly nedostatkovým zbožím i nadále.

* * *

Zajímavým stupněm vývoje byly takzvané Napierovy kostky. John Napier na přelomu 16. a 17. století vynalezl zajímavou dřevěnou pomůcku, která usnadňovala zvláště násobení dlouhého čísla jednociferným.

Pomůcka obsahovala podlouhlé hranoly, pro každé číslo od 0 do 9 jeden, na kterých byly vhodně napsané násobky těchto čísel – postupně 0-násobek až 9-násobek. Když se pak poskládaly hranoly správně k sobě, stačilo už akorát přepočítat přenosy.

Zdroj: Wikipedia

24-2-3 Odčítání (7 bodů)

Následující program simuluje něco jako mechanické počítadlo… tedy aspoň jej simulovat má. Jestli to je pravda, ověřte vy.

Předložená funkce má odčítat dvě čísla a vracet jejich rozdíl. Její vstup má být zadán tak, že na pozici [0] je číslice nejvyššího řádu.

Varianta v C bere jako první dva parametry vstup, ve třetím vrací výstup a čtvrtý určuje, kolik cifer čísla mají. Program v Pythonu bere vstup ve svých parametrech a pole vrací přímo.

Zadání je v desítkové soustavě (cifry 0–9) a čísla musí mít stejně cifer, byť by jedno z nich mělo začínat nulami.

Když tedy chcete odčítat 635 - 21 v C, voláte

int p[] = {6, 3, 5};
int d[] = {0, 2, 1};
int v[3];
funkce(p, d, v, 3);

a v Pythonu jednoduše funkce([6,3,5], [0,2,1]).

V kódu nehledejte ani syntaktické chyby, ani podivný styl, ani jiné formální problémy. Vaším úkolem je dokázat nebo vyvrátit jeho správnost a v každém případě určit jeho složitost (časovou i paměťovou).

void funkce(int prvni[], int druhe[],
            int vysledek[], int delka) {
  int index = 0, i;
  for (i = 0; i < delka; ++ i)
    vysledek[i] = prvni[i] + 9 - druhe[i];
  vysledek[delka - 1] ++;
  while (index < delka) {
    if (vysledek[index] >= 10) {
      vysledek[index] -= 10;
      index --;
      if (index >= 0)
        vysledek[index] ++;
      else
        index ++;
    } else
      index ++;
  }
}

def funkce(prvni, druhe):
  vysledek = prvni[:]     # Kopie prvního pole
  for i in range(0, len(druhe)):
    vysledek[i] += 9 - druhe[i]
  vysledek[-1] += 1       # -1 = poslední prvek
  index = 0
  while index < len(vysledek):
    if vysledek[index] >= 10:
      vysledek[index] -= 10
      index -= 1
      if index >= 0:
        vysledek[index] += 1
      else:
        index += 1
    else:
      index += 1
  return vysledek

Řešení

24-2-4 Odbočení vlevo (7 bodů)

Pražské Vinohrady se vyznačují tím, že na žádné křižovatce není povoleno odbočit vlevo. Vždy se smí jet jen doprava a rovně. Alespoň to tvrdí zlí jazykové.

Obchodní cestující se potřebuje dostat z jednoho místa na Vinohradech na druhé. Vaším úkolem bude najít mu nejkratší cestu, přičemž je potřeba respektovat globální zákaz odbočení vlevo.

Na vstupu dostanete mapu Vinohrad – čtvrti s pravoúhlou soustavou ulic (což je podmnožina jednotkové čtvercové mřížky); dále pak start a cíl cesty (nějaké dva úseky ulic). Výstupem vašeho algoritmu bude itinerář sestávající z příkazů typu „jeď rovně“ a „odboč vpravo“.

Jednu možnou mapu Vinohrad jsme vám zde připravili jako příklad. Nějaký start a cíl si jistě vymyslíte sami.

Řešení

24-2-5 Logická formule (11 bodů)

V průkopnické době digitálních přístrojů řešili vývojáři a konstruktéři různé zajímavé úlohy. Například tuto.

Mějme zadaný neuzávorkovaný logický výraz, který obsahuje pouze nuly, jedničky, AND a OR. Například

Nalezněte, kolika různými způsoby je možno zadaný výraz úplně uzávorkovat, aby jeho hodnota byla 1, a kolika způsoby naopak dostaneme nulu. V našem příkladu by třikrát vyšla 0 a dvakrát 1:

Řešení

24-2-6 Závorky (13 bodů)

Mějme na začátku N levých závorek. Nyní nám začnou chodit příkazy „otoč závorku na pozici i“. Po každém takovém příkazu vypíšete, jestli je teď řetězec dobře uzávorkovaný.

Dobře uzávorkovaný řetězec levých a pravých závorek splňuje podmínku, že levé a pravé závorky je možno přirozeným způsobem spárovat.

Program si na začátku může něco předpočítat – na vstupu dostanete N, což bude počet závorek v řetězci. Potom bude postupně dostávat výše definované příkazy a hned je bude zpracovávat.

Nemůžete si tedy počkat, až dostanete třeba celou posloupnost příkazů, nebo je brát po několika. Vždy přijde příkaz a vy jej zpracujete. Pak teprve přijde další příkaz atd.

Řešení

24-2-7 Štětcování (10 bodů)

V době vydání IBM PC bylo potřeba vyrobit propagační plakát.

Grafici dostali podivné zadání (ale není se čemu divit vzhledem k tomu, jak vypadá například instrukční sada procesoru Intel 8088…) – plakát je potřeba nakreslit co největším štětcem.

Jak se kreslí štětcem velikosti K? Vybereme si na čtvercové síti libovolný čtverec velikosti K×K. Ten vybarvíme; postup opakujeme.

Obrázek je černobílý (tedy políčko je buďto vybarvené, nebo nevybarvené). Políčka je možno obarvit opakovaně.

Na vstupu dostanete obrázek jako tabulku 1 a 0; na výstupu vypište jedno celé číslo – K – maximální možnou velikost štětce.

Například pro uvedený obrázek platí K=2.

Řešení

IBM PC v podstatě vytlačil z trhu veškerou konkurenci. Jeho jednoduchá a modulární architektura spolu s procesory firmy Intel (8088 apod.) způsobila, že náklady na výrobu i opravy byly (na svou dobu) velmi nízké.

Navíc v podstatě všechny další procesory, které Intel vyvíjel, byly s 8088 zpětně kompatibilní, co se týče instrukční sady. Nebyl proto problém spustit starý program na novějších strojích, což byl další důvod masivního rozšíření této platformy.

I současné počítače v sobě v drtivé většině mají procesory, na kterých při troše vůle i prastaré programy půjdou spustit. Nebude to asi ani pohodlné, ani rychlé, nicméně s velkou pravděpodobností poběží.

Z notebooku s procesorem Intel Core 2 Duo se s vámi loučí autor příběhu

Jan „Moskyto“ Matějka

24-2-8 Alfa-beta ořezávání a piškvorky (14 bodů)

V prvním dílu jsme si představili minimaxový algoritmus. Zjistili jsme také, že je možno zrychlovat jeho běh tím, že neuvažujeme některé možné tahy vedoucí z aktuální pozice. Za to však platíme možným přehlédnutím (nepravděpodobně) optimálního tahu.

Pro jednoduchost si označme hráče táhnoucího v maximalizačních úrovních jako Max (to je ten, pro něhož hledáme nejlepší tah) a jeho soupeře Min (ten táhne v úrovních, kde se vybírá minimum hodnot ze synů).

Alfa-beta ořezávání je úprava minimaxu založená na jednoduchém pozorování, které znatelně urychluje průměrnou dobu běhu prohledávání, aniž by ovlivnilo výsledek.

Uvažme následující situaci:

Potřebuje stroj znát hodnotu pozice s otazníkem, aby mohl vrátit výsledek? Nikoliv, protože hodnota pozice v nadřazeném vrcholu už větší nebude, ať připočítáme cokoliv.

Proč tomu tak je? Když bude na pozici s otazníkem více než 5, tak minimem v této úrovni bude 5; v opačném případě bude minimum menší než 5.

Hodnota pozice v nadřazeném vrcholu tudíž bude maximálně 5, ale to už je méně než 7 – hodnota vedlejší pozice – takže pozice s otazníkem už rozhodování nikterak neovlivní.

Uvědomme si, jak je v dané pozici takové pozorování cenné – skutečně můžeme přestat počítat (říká se zaříznout) celou větev. Zkoumat ji by byla spousta práce.

Kdy přesně lze větev zaříznout? Pokud se nacházíme v minimalizační fázi a v libovolném vrcholu v maximalizační fázi na cestě ke kořeni prohledávacího stromu existuje už dopočítaný syn, který má vyšší hodnotu než aktuální minimum v této úrovni.

To vše obdobně pro vrcholy ve fázi maximalizační.

Nyní je vhodná chvíle přestat na chvíli číst a rozmyslet si, jestli opravdu všemu rozumíte. Zkuste si nakreslit složitější situaci a chvíli ji analyzujte.

Takové chování se příjemně implementuje za použití dvou proměnných, kterým budeme nečekaně říkat alfa a beta. Alfa bude maximum z dopočítaných synů v maximalizačních fázích a beta minimum z fází minimalizačních. S těmi pak bude stačit nově dopočítané hodnoty vrcholů porovnávat.

Na začátku zvolíme alfu jako -∞ (Max může prohrát) a betu jako +∞ (i Min může prohrát). V maximalizačních úrovních pak upravujeme dle hodnoty v synech alfu, v minimalizačních betu.

Jelikož alfa udává, jakou nejlepší hodnotu v prozkoumané části stromu může získat Max, a beta nejlepší nalezenou hodnotu pro hráče Min, platí v každém okamžiku, že alfa < beta. Když se tedy v průběhu výpočtu dostaneme s alfou nad betu (či s betou pod alfu), můžeme skončit prohledávání synů zkoumaného uzlu.

Znovu se zde ujistěte, jestli tušíte, proč si algoritmus může takové ořezávání dovolit.

K lepšímu pochopení může posloužit pseudokód.

def alfabeta(pozice, hloubka, alfa, beta, natahu):
  if hloubka == 0 or konec_hry(pozice)
    return hodnota(pozice)

  if natahu = Max:
    for p in mozne_tahy(pozice, Max):
      alfa = max(alfa, alfabeta(p, hloubka-1, alfa, beta, Min) )
      if beta <= alfa:
        break
    return alfa

  if natahu = Min:
    for p in mozne_tahy(pozice, Min):
      beta = min(beta, alfabeta(p, hloubka-1, alfa, beta, Max) )
      if beta <= alfa:
        break
    return beta

Alfa-beta ořezávání je nejúčinnější, jsou-li první prozkoumávané tahy nejlepší možné pro hráče, v jehož úrovni se nacházíme. Pak je možné větve pod ostatními tahy rychle zaříznout a minimax tak výrazně zrychlit. Máme-li však smůlu v seřazení tahů od nejhoršího, alfa-beta nám vůbec nepomůže.

Zkoumat na začátku dobré tahy ale samozřejmě není tak jednoduché – víme-li, které tahy jsou nejlepší, žádný minimax už nepotřebujeme. Rozhodně se nám ale vyplatí začít vymýšlet heuristiky pro generátory tahů, které se budou snažit nějak chytře předřazovat.

Často používaná je metoda killer move. Pamatujeme si, které tahy v jiných větvích výpočtu vedly k dobrým výsledkům, a ty pak upřednostňujeme při prohledávání.

Trochu jednodušší je iterativní prohlubování, při kterém prostě minimax pouštíme pro stále větší hloubku propočítávání, tj. nejdříve procházíme strom do hloubky 1, pak do hloubky 2, 3 atd. Kromě nejnižšího patra stromu používáme pro řazení tahů výsledky z předchozího výpočtu.

Neplýtváme časem, když některé části stromu prohledáváme vícekrát? Ne, protože exponenciální časová složitost minimaxu vede k tomu, že všechna hledání dohromady zpravidla zaberou méně času než to poslední, nejhlubší.

Piškvorková teorie

Poodstupme opět od vulgárního světa strojového prohledávání pozic. Matematika nám v minulém díle pomohla při analýze Nimu. Piškvorky jsou podobně jednoduše definovatelná hra – dokážeme vyřešit tu?

Záleží trochu, co přesně si pod piškvorkami představíme. Nejčastěji asi hru na neomezeném čtverečkovaném papíře, kde se střídáme v pokládání značek, přičemž výhry dosáhne hráč, který jich první vytvoří pět v řadě.

O takových piškvorkách tušíme, že v nich má výhodu začínající hráč. Jak ale velkou? Má vyhrávající strategii? Může alespoň vždy zabránit prohře? Jednoduchá, ale důležitá skutečnost zní: druhé tvrzení platí, začínající hráč v piškvorkách má neprohrávající strategii.

Představíme-li si pro spor, že druhý hráč má vyhrávající strategii (což je negace tvrzení „začínající hráč má strategii neprohrávající“), můžeme aplikovat přeslavný argument o kradení strategie.

První hráč by mohl svůj první tah zahrát libovolně na desku, zapomenout na něj (tj. nadále přemýšlet o desce, jako by tam nebyl) a potom hrát podle postulované vyhrávající strategie druhého hráče.

Onen libovolný tah by mu v žádných možných pokynech takové strategie nepřekážel – dostal-li by za úkol hrát na toto místo, učinil by prostě libovolný jiný tah a zapomněl by na ten.

Z toho však plyne, že vyhrávající strategii má jako hráč začínající (tj. zloděj), tak hráč druhý! To je spor, ke kterému jsme chtěli dospět. Vyhrávající strategie druhého hráče neexistuje, první hráč má strategii neprohrávající.

Argument je to slavný, protože je široce aplikovatelný – můžeme jej použít na všechny poziční hry, což je terminus technicus pro hry, ve kterých hráči trvale zabírají části herní plochy a vítězí hráč, který zabere některou z vítězných podmnožin těchto částí.

Nabízí se ohromně zajímavá otázka, má-li první hráč vyhrávající strategii, nebo je-li to remíza. Někde daleko před odpovědí na tuto otázku však možnosti současné matematiky končí. Pro modifikovanou variantu piškvorek, kde vyhrává řada osmi značek, je dokázáno, že bezchybná hra již remízou končí.

Úkol 1 [5b]

Určete a dokažte výsledek piškvorek, kde vyhrává řada čtyř značek.

Úkol 2 [9b]

Dokažte, že v piškvorkách, kde vyhrává řada devíti značek, má druhý hráč neprohrávající strategii. Nápověda: Rozdělení do párů.

Dobře, neomezená herní plocha může být háčkem. Pojďme hrát piškvorky na omezené desce n^d, což je d-rozměrná krychle o hraně n. Za vítěze budeme pokládat hráče, který první udělá sérii n značek ve stejném směru.

Pro n=3 a d=2 dostáváme známé tic-tac-toe, pro n=4, d=3 oblíbené trojrozměrné piškvorky…

Ani zde není situace příliš růžová a za to, že víme, že má v uvedených trojrozměrných piškvorkách začínající hráč vítěznou strategii, vděčíme dosti komplikovanému důkazu plného rozborů případů. Situace pro n=5, d=3 je zatím otevřená.

Řešení