Matematičari su pokušali da dokažu koliko je The Witness težak – sa iznenađujućim rezultatima

“Svaka vrsta traga je na kraju ponudila cijeli zanimljiv problem za proučavanje.”

The Witness je radoznala, pronicljiva igra. S jedne strane, najavljuje se kao šampion pretencioznosti. S druge strane, naširoko je hvaljen zbog svoje matematičke složenosti. Pravila Svjedoka su mapirana simbolima na mreži šahovske ploče, i iako izgledaju prilično jednostavno, dešava se mnogo više nego što se na prvi pogled čini – toliko da neki proučavaju šta tačno otežava probleme svjedoka na doktorskom nivou.

Erik Demaine, profesor informatike na MIT-u, prvenstveno se fokusira na istraživanje i nastavu, a često kombinuje to dvoje dajući studentima zadatak da rješavaju otvorene probleme u grupama. Da bi to učinio, Demaine koristi visoko kolaborativni stil istraživanja tzv supercolaboration.

Prema Demaineovom sajtu – na kojem se nalazi gore – supersaradnja je inovativna istraživačka metoda u kojoj istraživači rješavaju složene probleme bez brige o autorstvu ili egu. To je, bukvalno, supersaradnička, jer pozitivan i efikasan timski rad ima prednost nad individualnim doprinosom. Ako ste posebno zainteresirani, ispod sam ugradio video o času koji se podučava korištenjem superkolaborativnog modela.

Demaine je bio jedan od glavnih autora rada iz 2018. pod nazivom Ko svjedoči svjedoku?, koji pruža uzoran slučaj superkolaborativnog istraživanja dok istovremeno ekstrapolira ono što The Witness čini igrom vrijednom proučavanja za doktorske matematičare i informatičare: prvenstveno, njenu težinu.

Za one koji nisu upoznati s pojmom “svjedok” u kontekstu matematike, to je specifična vrijednost koja se nalazi u egzistencijalnoj izjavi – u osnovi, to je entitet koji se koristi za razlikovanje između nečega postojećeg, nečega što postoji u barem jednom slučaju, i nečega postojećeg s obzirom na određene uslovima. U slučaju svjedoka, svjedok u malim slovima ima veze s načinima na koje se zagonetke zapravo rješavaju – radi se o tome koja je strategija uspješna i koji put(i) kroz mrežu to predstavlja.

Dakle, ko svjedoči svjedoku? Kako se ispostavilo, to je izuzetno teško reći – i zato je tako akademski primamljivo.

Demaineov tim često proučava igre kako bi potražio efikasne algoritme i analizirao računarski nerješive probleme kao sredstvo praćenja inovativnih rješenja koja se često izvode iz lijevog polja.

„Uopšteno govoreći, želeli smo da pokušamo da ocrtamo granicu između računarski lakih i računarski teških aspekata zagonetki The Witnessa“, kaže Demaine. “Neke zagonetke koriste jednu vrstu traga, dok druge koriste mješavinu tipova tragova. Želeli smo da razumemo koje mešavine čine zagonetke koje je računarima teško rešiti, a samim tim i verovatno [takođe] teške za ljude, a koje je računarima zapravo lako rešiti – iako to ne znači da su one nužno lake za ljude. ”

„Potonje je generalno retko kada se zagonetke analiziraju na ovaj način, tako da je slučaj monomina bio prilično uzbudljiv“, dodaje on.

Provjera tvrdoće je jedan od ključnih ciljeva Demaineovog istraživanja i nastave. Umjetnost dokazivanja tvrdoće je teška: ona uključuje pronalaženje dokaza zašto je problem težak transformacijom ili svođenjem u zaseban problematični oblik. Usput se otkrivaju zanimljivi algoritmi koji se mogu primijeniti na drugim mjestima – hvatanje u koštac s računski teškim rađa rješenja za pojednostavljenje, što znači da se dođe do nečega što je na kraju lakše za korištenje daljnjim kompliciranjem onoga što je ispod haube.

Adam Hesterberg je još jedan istraživač zaslužan za knjigu Ko svjedoči svjedoku? Iako je bio doktorant matematike na MIT-u kada je počeo da radi sa Demaineom, sada studira računarstvo na postdoktorskom nivou. Njemu je Svjedok izgledao "kompjuterski zanimljivo".

„Nisam igrao The Witness dok nismo odlučili da poradimo na njegovoj računskoj složenosti, iako radim slične logičke zagonetke,“ kaže mi. „Volim društvene igre, bilo igre za upravljanje ekonomskim resursima u njemačkom stilu kao što je Gaia Project ili bilo što od Vlaade Chvátila, po kojem sam nazvao svoj stan. Naša istraživačka grupa povremeno piše radove o drugim igrama.”

Demaineova grupa je započela rad na filmu Ko svjedoči svjedoku? 2016., dvije godine prije nego što je objavljen kao FUN (sa Međunarodne konferencije zabave sa algoritmima) rad 2018. Na kraju će kulminirati punim radom u časopisu čiji su koautori 10 akademika iz tri odsjeka MIT-a i jednog univerziteta u Nemačkoj.

Međutim, nisu fokusirani samo na The Witness: Demaineova grupa se takođe bori sa računarskim sistemima u nizu drugih igara, obično primenjujući iste dokaze tvrdoće kako bi dokazala poteškoće i otkrila alternativne algoritme.

„Računarska složenost igara i zagonetki je tema koja mi je draga u srcu koju proučavam od oko 2000. godine“, objašnjava Demaine. “Moj prvi rad je bio o Clickomania, koji mi nedavno revidirano. "

Demaine pokazuje na svoje papire Tetris je NP-kompletan – što znači da se može riješiti restriktivnom klasom algoritama pretraživanja grube sile – i Super Mario Bros. je PSPACE-kompletan, što je mnogo složenije – kao neka od njegovih najpopularnijih dostignuća u ovoj oblasti do sada. Ali po čemu se Svedok ističe? „Kada je The Witness izašao, činilo se kao prirodna igra za rješavanje, nudeći niz različitih tipova zagonetki/tragova u sebi“, objašnjava Demaine. “Budući da je dio igranja igre otkrivanje što tragovi zapravo znače, prvo smo upozorili grupu da ćemo proučavati svjedoka i ohrabrili one koji žele izbjeći spojlere da igraju igru ​​i sami shvate stvari.

“Nekoliko sedmica kasnije, skočili smo u analizu i svaki tip traga je na kraju ponudio cijeli zanimljiv problem za proučavanje.”

Jeffrey Bosboom, koji je doktorant na MIT-u od 2011. godine i koautor Ko je svjedok Svjedoka?, prvi put se susreo sa Svjedokom kada se o njemu govorilo tokom jedne od sedmičnih sesija supersaradnje tima. „To znači da sam bio razmažen za većinu tipova zagonetki“, kaže mi. “Ali ne osjećam se da sam razmažen umanjio moje uživanje dok sam ga igrao; uvodne zagonetke u svakoj oblasti su ionako didaktične, a i dalje je bilo zabavno osjetiti prijelaz od eksplicitnog znanja (mogućnost da se nekome kaže značenje simbola) do implicitnog znanja (gledanje zagonetke i odmah prepoznavanje koje rješenje mora biti ).”

Jedna od najneobičnijih stvari u vezi s The Witnessovim zagonetkama je da su neke od Sigma_2-potpune, napominje Demaine. Za one koji nisu sigurni šta to znači – što sam svakako bio! – Sigma_2-potpunost se odnosi na tačku u polinomskoj hijerarhiji, koja karakteriše niz različitih nivoa složenosti rešavanja problema.

NP-potpunost uključuje rješavanje problema korištenjem grube sile; Sigma_2-potpunost je korak dalje od toga; i PSPACE-potpunost je opet složenija, jer ima veze s polinomskim vremenom (količinom vremena potrebnog računaru da riješi problem) i vremenskom složenošću (proračunska složenost količine vremena potrebnog računaru da pokrene specifični algoritam).

Malo je teško raščlaniti, ali prema zagonetki svjedoka Demainea – barem one koje sadrže “antitijela”, do kojih ću doći za minut – čvrsto su usađene u sredinu od tri, koje postoje kao “nivo u odnosu na uobičajenu NP-potpunost, dok je daleko ispod PSPACE-potpunosti uobičajene za zagonetke koje zahtijevaju eksponencijalno mnogo poteza – poput kliznih blokova ili špica”.

Tragovi označeni kao "antitijela" u radu, a to su logička pravila koja poništavaju učinak drugih tragova u istoj regiji date slagalice, imaju inherentni kvalifikator "neophodnosti" koji zahtijeva malo hipotetičkiji pristup rješavanju problema. . Ovo povećava složenost računanja i pruža zanimljiv niz problema koji se mogu transformisati jedan u drugi kako bi se došli do novih, efikasnih algoritama (transformacija jednog problema u drugi oblik je takođe kvalitet Sigma_2-potpunosti).

Original članak