"Každý typ stopy nakoniec ponúkol celý zaujímavý problém na štúdium."
The Witness je kuriózna, persnickety hra. Na jednej strane je ohlasovaný ako šampión domýšľavosti. Na druhej strane je široko chválený pre svoju matematickú zložitosť. Pravidlá Svedka sú zmapované symbolmi na šachovnicových mriežkach, a hoci vyzerajú celkom jednoducho, deje sa toho oveľa viac, než sa na prvý pohľad zdá – až natoľko, že niektorí študujú, čo presne sťažuje problémy Svedka na doktorandskej úrovni.
Erik Demaine, profesor informatiky na MIT, sa primárne zameriava na výskum a výučbu a často ich kombinuje tým, že zadáva študentom úlohy riešiť otvorené problémy v skupinách. Demaine k tomu využíva vysoko kolaboratívny štýl výskumu tzv superspolupráca.
Podľa stránky Demaine – prepojenej vyššie – je superspolupráca inovatívnou výskumnou metódou, kde výskumníci riešia zložité problémy bez obáv o autorstvo alebo ego. Je to doslova superspolupráca v tom, že pozitívna a efektívna tímová práca má prednosť pred individuálnym vkladom. Ak vás to obzvlášť zaujíma, nižšie som vložil video triedy vyučovanej pomocou modelu superspolupráce.
Demaine bol jedným z hlavných autorov článku z roku 2018 s názvom Kto je svedkom The Witness?, ktorá poskytuje exemplárny prípad superkolaboratívneho výskumu a súčasne extrapoluje to, čo robí The Witness hrou, ktorú sa oplatí študovať doktorandským matematikom a počítačovým vedcom: predovšetkým jej náročnosť.
Pre tých, ktorí nie sú oboznámení s pojmom „svedok“ v matematickom kontexte, je to špecifická hodnota včlenená do existenciálneho vyhlásenia – v podstate je to entita používaná na rozlíšenie medzi niečím existujúcim, niečím existujúcim aspoň v jednom prípade a niečím existujúcim za určitých okolností. podmienky. V prípade The Witness má malý svedok čo do činenia so spôsobmi, akými sa hádanky skutočne riešia – ide o to, ktorá stratégia je úspešná a aká cesta (cesty) cez mriežku to predstavuje.
Takže, kto je svedkom The Witness? Ako sa ukázalo, je to pozoruhodne ťažké povedať – a preto je to také akademicky lákavé.
Demainov tím často študuje hry, aby hľadal účinné algoritmy a analyzoval výpočtovo neriešiteľné problémy ako prostriedok na sledovanie inovatívnych riešení, ktoré sú často odvodené z ľavého poľa.
„Vo všeobecnosti sme sa chceli pokúsiť vymedziť hranicu medzi výpočtovo jednoduchými a výpočtovo náročnými aspektmi hádaniek The Witness,“ hovorí Demaine. "Niektoré hádanky používajú jeden typ kľúča, zatiaľ čo iné používajú zmes typov kľúčov. Chceli sme pochopiť, ktoré zmesi robia hádanky, ktoré sú ťažko riešiteľné pre počítače, a teda pravdepodobne [aj] ťažké pre ľudí, a ktoré sú v skutočnosti ľahko riešiteľné pre počítače – aj keď to neznamená, že sú nevyhnutne ľahké pre ľudí. “
„Pri analýze hádaniek týmto spôsobom je to vo všeobecnosti zriedkavé, takže prípad monominoes bol celkom vzrušujúci,“ dodáva.
Kontrola tvrdosti je jedným z kľúčových cieľov výskumu a výučby Demaine. Umenie dokázať tvrdosť je ťažké: zahŕňa nájdenie dôkazu, prečo je problém ťažký, jeho transformáciou alebo redukciou do samostatnej problémovej formy. Popri tom sa objavia zaujímavé algoritmy, ktoré sa dajú použiť inde – zápasenie s výpočtovo náročnými riešeniami na zjednodušenie, čo znamená dospieť k niečomu, čo sa v konečnom dôsledku ľahšie používa, a ešte viac skomplikovať to, čo je pod kapotou.
Adam Hesterberg je ďalším výskumníkom pripísaným na Kto je svedkom The Witness? Hoci bol doktorandom matematiky na MIT, keď začal spolupracovať s Demaine, teraz študuje informatiku na postdoktorandskej úrovni. Pre neho The Witness vyzeral „výpočtovo zaujímavý“.
„The Witness som nehral, kým sme sa nerozhodli pracovať na jeho výpočtovej zložitosti, hoci robím podobné logické hádanky,“ hovorí mi. „Mám rád stolové hry, buď hry na ekonomický manažment zdrojov v nemeckom štýle ako Gaia Project alebo čokoľvek od Vlaady Chvátila, po ktorom som pomenoval svoj byt. Naša výskumná skupina príležitostne píše články o iných hrách.“
Demainova skupina začala pracovať na Kto je svedkom The Witness? v roku 2016, dva roky predtým, ako bol publikovaný ako FUN (z International Conference of Fun with Algorithms) príspevok v roku 2018. Nakoniec by to vyvrcholilo úplným časopisom, ktorého spoluautormi by bolo 10 akademikov z troch katedier na MIT, a jeden univerzite v Nemecku.
Nezameriavajú sa však len na The Witness: Demainova skupina zápasí s výpočtovými systémami aj v rôznych iných hrách, pričom zvyčajne používa rovnaké dôkazy tvrdosti, aby dokázala obtiažnosť a objavila alternatívne algoritmy.
„Výpočtová zložitosť hier a hlavolamov je mojou srdcovou témou, ktorú študujem približne od roku 2000,“ vysvetľuje Demaine. „Moja prvá práca bola o Clickománia, ktoré my nedávno znovu navštívené. "
Demaine ukazuje na svoje papiere Tetris je NP-kompletný – čo znamená, že to môže byť vyriešené reštriktívnou triedou vyhľadávacích algoritmov hrubou silou – a Super Mario Bros. je kompletný PSPACE, ktorý je oveľa komplexnejší – ako niektoré z jeho doteraz najobľúbenejších úspechov v tejto oblasti. Čím však The Witness vyniká? „Keď vyšiel The Witness, zdalo sa, že je to prirodzená hra, ktorá ponúka množstvo rôznych typov hádaniek a tipov,“ vysvetľuje Demaine. „Pretože súčasťou hrania hry je zisťovanie, čo indície vlastne znamenajú, najprv sme skupinu varovali, že budeme študovať The Witness, a povzbudili tých, ktorí sa chcú vyhnúť spoilerom, aby si hru zahrali a prišli na veci sami.
"O pár týždňov neskôr sme skočili do analýzy a každý typ stopy nakoniec ponúkol celý zaujímavý problém na štúdium."
Jeffrey Bosboom, ktorý je doktorandom na MIT od roku 2011 a je spoluautorom Who svedkovia The Witness?, sa s The Witness prvýkrát stretol, keď bol predstavený počas jedného z týždňových stretnutí tímu o superspolupráci. „To znamená, že som bol rozmaznaný väčšinou typov hádaniek,“ hovorí mi. „Nemám však pocit, že by som bol rozmaznaný, čo by znížilo môj pôžitok, keď som to hral; úvodné hádanky v každej oblasti sú aj tak didaktické a stále bolo zábavné cítiť prechod od explicitných vedomostí (schopnosť povedať niekomu význam symbolu) k implicitným vedomostiam (pozerať sa na hádanku a okamžite rozpoznať, aké musí byť riešenie ).“
Jednou z najneobvyklejších vecí na hádankách The Witness je, že niektoré majú Sigma_2-complete, poznamenáva Demaine. Pre tých, ktorí si nie sú istí, čo to znamená – čo som ja určite bol! – Sigma_2-úplnosť sa vzťahuje na bod v polynómovej hierarchii, ktorý sa vyznačuje množstvom rôznych úrovní zložitosti riešenia problémov.
NP-úplnosť zahŕňa riešenie problémov pomocou hrubej sily; Sigma_2-úplnosť je o krok vyššie; a úplnosť PSPACE je opäť zložitejšia, súvisí s polynomiálnym časom (množstvo času, ktorý počítač potrebuje na vyriešenie problému) a časovou zložitosťou (výpočtová zložitosť času, ktorý počítač potrebuje na spustenie špecifický algoritmus).
Je to trochu ťažké analyzovať, ale podľa hádaniek Demaine The Witness – aspoň tie, ktoré obsahujú „protilátky“, ku ktorým sa dostanem za minútu – sú pevne zasadené do stredu troch, existujú ako „úroveň od obvyklej úplnosti NP, pričom je ďaleko pod úplnosťou PSPACE, ktorá je spoločná pre hádanky, ktoré vyžadujú exponenciálne veľa pohybov – ako napríklad posuvné bloky alebo špička“.
Záchytné body označené v článku ako „protilátky“, čo sú logické pravidlá, ktoré rušia účinok iných záchytných bodov v rovnakej oblasti danej hádanky, majú vlastný kvalifikátor „nevyhnutnosti“, ktorý si vyžaduje trochu hypotetickejší prístup k riešeniu problémov. . To zvyšuje výpočtovú zložitosť a poskytuje zaujímavú škálu problémov, ktoré je možné transformovať do seba s cieľom prísť s novými, efektívnymi algoritmami (transformácia jedného problému do inej formy je tiež kvalitou úplnosti Sigma_2).
