„Секој тип на индиции на крајот нуди цела интересен проблем за проучување“.
The Witness е љубопитна, непријатна игра. Од една страна, се најавува како шампион на претенциозноста. Од друга страна, тој е широко пофален за неговата математичка сложеност. Правилата на Сведокот се мапирани со симболи на мрежите на неговата шаховска табла, и иако изгледаат прилично едноставно, се случува многу повеќе отколку што се гледа - толку многу што некои проучуваат што точно ги отежнува проблемите на Сведокот на докторско ниво.
Ерик Демајн, професор по компјутерски науки на МИТ, првенствено се фокусира на истражување и настава, и често ги комбинира двете со задача на студентите да решаваат отворени проблеми во групи. За да го направите ова, Demaine користи високо колаборативен стил на истражување наречен суперсоработка.
Според страницата на Demaine – поврзана погоре – суперсоработката е иновативен метод на истражување каде што истражувачите решаваат сложени проблеми без грижа за авторството или егото. Тоа е, буквално, суперколаборативно, бидејќи позитивната и ефективна тимска работа има предност пред индивидуалниот придонес. Ако сте особено заинтересирани, вградив видео од час што се предава со помош на суперколаборативен модел подолу.
Демајн беше еден од главните автори на трудот од 2018 година наречен Кој е сведок на сведокот?, кој обезбедува примерен случај на суперколаборативно истражување додека истовремено го екстраполира она што го прави The Witness игра што вреди да се проучува за докторски математичари и компјутерски научници: првенствено, нејзината тешкотија.
За оние кои не се запознаени со поимот „сведок“ во математички контекст, тоа е специфична вредност што се подложува во егзистенцијална изјава - во основа, тоа е ентитет што се користи за да се направи разлика помеѓу нешто постоечко, нешто што постои барем во еден случај и нешто што постои со одредено Услови. Во случајот на Сведокот, сведокот со мали букви има врска со начините на кои всушност се решаваат загатките - се работи за тоа која стратегија е успешна и која патека(и) низ мрежата го претставува тоа.
Значи, кој е сведок на Сведокот? Како што се испоставува, неверојатно е тешко да се каже - и затоа е толку академски примамливо.
Тимот на Демајн често ги проучува игрите со цел да бара ефикасни алгоритми и да ги анализира пресметковно нерешливите проблеми како средство за следење на иновативни решенија кои често се изведуваат надвор од левото поле.
„Генерално, сакавме да се обидеме да ја разграничиме границата помеѓу пресметковно лесните и пресметковно тешките аспекти на загатките на Сведокот“, вели Демајн. „Некои загатки користат еден тип на трага, додека други користат мешавина од типови на индиции. Сакавме да разбереме кои мешавини прават загатки кои компјутерите се тешки за решавање, а со тоа веројатно [исто така] тешки за луѓето, а кои всушност се лесни за компјутерите - иако тоа не значи дека тие се нужно лесни за луѓето. ”
„Последното воопшто е ретко кога се анализираат загатките на овој начин, така што случајот со мономино беше прилично возбудлив“, додава тој.
Откривањето на цврстината е една од клучните цели на истражувањето и наставата на Демаин. Уметноста на докажување на цврстина е тешка: таа вклучува наоѓање доказ зошто проблемот е тежок преку негово трансформирање или намалување во посебна проблематична форма. На тој пат, откриени се интересни алгоритми кои можат да се применат на друго место - справувањето со компјутерски тешкото раѓа решенија за поедноставување, што значи да се дојде до нешто што на крајот е полесно да се користи со дополнително комплицирање на она што е под хаубата.
Адам Хестерберг е уште еден истражувач заслужен за Кој е сведок на сведокот? Иако бил докторант по математика на МИТ кога почнал да работи со Демајн, сега студира компјутерски науки на пост-докторско ниво. За него, Сведокот изгледаше „компјутерски интересно“.
„Не го играв The Witness додека не решивме да работиме на неговата пресметковна сложеност, иако правам слични логички загатки“, ми вели тој. „Ми се допаѓаат друштвените игри, или игрите за управување со економски ресурси во германски стил, како што е проектот Гаја или било што од Влада Чватил, по кого го именував мојот стан. Нашата истражувачка група повремено пишува трудови за други игри“.
Групата на Демајн започна со работа на Кој е сведок на сведокот? во 2016 година, две години пред да биде објавен како труд FUN (од Меѓународната конференција за забава со алгоритми) во 2018 година. универзитет во Германија.
Сепак, тие не се фокусирани само на Сведокот: групата на Демајн се справува со пресметковните системи во различни други игри, исто така, обично применувајќи ги истите докази за цврстина со цел да ја докаже тежината и да открие алтернативни алгоритми.
„Пресметувачката сложеност на игрите и загатките ми е драга тема што ја проучувам од околу 2000 година“, објаснува Демаин. „Мојот прв труд беше за Кликоманија, што ние неодамна повторно посетен".
Демајн укажува на неговите трудови Тетрисот е NP-комплетен – што значи дека може да се реши со рестриктивна класа алгоритми за пребарување на брутална сила – и Супер Марио Брос е комплетиран со PSPACE, што е многу покомплексно – како некои од неговите најпопуларни достигнувања во оваа област досега. Но, по што се издвојува The Witness? „Кога The Witness излезе, се чинеше како природна игра за справување, нудејќи различни видови загатки/индиции во неа“, објаснува Демајн. „Бидејќи дел од играњето на играта е да откриеме што всушност значат индициите, прво ја предупредивме групата што ќе ја проучуваме Сведокот и ги охрабривме оние што сакаа да избегнат спојлери да ја играат играта и сами да ги сфатат работите.
„Неколку недели подоцна, почнавме да анализираме и секој тип на индиции на крајот понуди цел интересен проблем за проучување“.
Џефри Босбум, кој е докторант на МИТ од 2011 година и коавтор на „Кој сведок на сведокот? „Тоа значи дека бев разгалена за повеќето видови загатки“, ми вели тој. „Но, не чувствувам дека сум разгалена, ми го намали уживањето кога го играв; воведните загатки во секоја област се во секој случај дидактички, и сепак беше забавно да се почувствува преминот од експлицитно знаење (да се биде во можност да се каже некому значењето на симболот) во имплицитно знаење (гледање на загатката и веднаш препознавање кое треба да биде решението )“
Една од најнеобичните работи за загатките на Сведокот е дека некои се Sigma_2-complete, забележува Демајн. За оние кои се малку несигурни што значи тоа - што секако бев! – Сигма_2-комплетноста се однесува на точка во полиномната хиерархија, која се одликува со разновидни различни нивоа на сложеност за решавање проблеми.
НП-комплетноста вклучува решавање на проблеми со користење на брутална сила; Sigma_2-комплетноста е чекор погоре од тоа; и PSPACE-комплетноста е повторно посложена, има врска со полиномното време (количината на време што му е потребно на компјутерот да реши проблем) и временската сложеност (пресметковната сложеност на времето што му е потребно на компјутерот да изврши специфичен алгоритам).
Малку е тешко да се анализира, но според Демајн, загатките на Сведокот - барем оние со „антитела“, до кои ќе стигнам за една минута - се цврсто засадени во средината на трите, кои постојат како „ниво од вообичаената NP-комплетност, додека е далеку под комплетноста на PSPACE, вообичаена за загатките кои бараат експоненцијално многу потези – како што се лизгачки блокови или Шпиц“.
Индициите означени како „антитела“ во трудот, кои се логички правила кои го поништуваат ефектот на другите индиции во истиот регион на дадена загатка, имаат својствен квалификатор за „нужност“ што бара малку похипотетички пристап за решавање на проблемите. . Ова ја зголемува комплексноста на пресметките и обезбедува интересна низа на проблеми кои можат да се трансформираат еден во друг со цел да се дојде до нови, ефикасни алгоритми (трансформирањето на еден проблем во друга форма е исто така квалитет на Sigma_2-целосност).
