Am o problemă: de câțiva ani nu mai pot să dorm sau să trăiesc normal în propria mea casă, din cauza vacarmului infernal din cartier. Poliția Locală refuză să facă ceva. Încep să mă tem pentru sănătatea mea fizică pe termen lung.
Am scris o pagină detaliată despre asta.
Dacă aveți idei, aș fi tare curios să le aflu. Și v-aș fi recunoscător pentru un share / retweet la acea pagină.
Nu mai pot să dorm Read More »
Acest articol este din categoria „Cătălin este adorabil când încearcă să povestească despre chestiile lui de geek pe un blog care se vrea atehnic”. 🙂 Dar am vești fascinante dintr-un capitol care m-a interesat ani de zile, și pentru care am și programat pe bucățele vreo 6 luni cu normă întreagă (estimativ). Așa că să-mi fie permis!
Jocul de antișah a fost rezolvat. Mark Watkins, un matematician de la Universitatea din Sydney, a reușit să demonstreze că albul câștigă (începutul este 1. e3). Rezultatul este o demonstrație online, dar și un articol științific superb în care Mark își prezintă munca.
Despre antișah am tot scris pe blogul ăsta, poate nu destul raportat la cât am urmărit subiectul în toți acești ani. Este o variantă a șahului cu aceleași piese și pe aceeași tablă, dar scopul este să îți pierzi toate piesele (iar captura este obligatorie). Interesul meu pentru antișah a început în 2001, când eram student la MIT și niște colegi de-ai mei au primit ca proiect la un curs să scrie un program care să joace antișah. Mi s-a părut un subiect interesant, așa că am scris și eu un program.
Ulterior am aflat despre serverul de șah FICS (freechess.org), care are marele avantaj că primește nu doar oameni, ci și programe. Așa am intrat într-o comunitate de jucători și programatori care practicau și studiau acest joc. N-am devenit niciodată bun la el, dar m-a interesat programarea. Programul meu, Nilatac, a fost unul dintre cele mai bune la vremea lui. La cerere, am creat și o versiune mai slabă a lui, CatNail, pentru ca începătorii să aibă cu cine juca. Până astăzi, CatNail a jucat peste 1,1 milioane de partide și a fost online 80% din timp în ultimii 15 ani. La un moment dat am încercat să rescriu de la zero programul, mai robust. Am ajuns până la genunchiul broaștei, dar am apucat măcar să scriu o tabelă de finaluri care dă strategia perfectă pentru orice poziție cu maxim 5 piese.
Comunitatea de antișah suspecta de multă vreme (dinainte de anul 2000) că albul poate câștiga orice partidă, iar 1. e3 era mutarea favorită. Ce înseamnă asta? Înseamnă că pentru orice apărare a negrului albul trebuie să dea un răspuns câștigător. Iar asta se poate întâmpla la prima mutare, la a doua, la a treia…, și pe oricare din aceste linii jocul trebuie să ducă la o poziție în care albul și-a dat toate piesele. Rezultatul demonstrației este, așadar, un fel de arbore de posibilități care se ramifică pornind de la poziția inițială, iar „frunzele” arborelui sunt poziții finale în care albul câștigă.
Unele apărări ale negrului sunt aproape folclorice, căci orice începător învață rapid să le evite (1. … d5 și 1. … d6 – luați o tablă de șah și vedeți dacă puteți forța victoria albului pe aceste linii!). Încă vreo 10 răspunsuri posibile pot fi demonstrate ușor cu un program nu prea deștept. Altele însă se lasă greu demonstrate. De exemplu, sunt mândru că Nilatac a reușit să demonstreze în premieră linia 1. e3 Nh6. Este principala mea contribuție în domeniu. Dar, pe de altă parte, nu a fost în stare să demonstreze linia 1. e3 c6 decât ajutat cu lingurița. Câteva apărări (în special 1. … b6 și 1. … c5) nu se lăsau demonstrate, deși mai mulți oameni lucrau la asta.
Cam în acest stadiu era înțelegerea noastră despre joc când Mark a început să lucreze la propriul său program prin 2011. Povestea lui despre cum a procedat, peste ce obstacole a dat și cum le-a depășit este captivantă. De exemplu, există linii foarte „mlăștinoase”, în care negrul își poate prelungi agonia cu zeci sau sute de mutări. Acolo algoritmul de rezolvare se poate păcăli când decide ce mutări ale albului sunt „promițătoare” și poate pierde luni de zile analizând o linie care, de fapt, nu duce la victorie. În fiecare din aceste (multe) situații, Mark s-a consultat cu jucători umani. Flerul acestora, bazat pe experiența a zeci de mii de partide jucate, a indicat adesea o mutare surprinzătoare pe care algoritmul nu o analizase în profunzime și care, la o analiză mai adâncă, putea fi demonstrată în doar câteva ore sau zile.
La final, bucățile din demonstrație pe care le-a descoperit Mark au fost cam de 3-4 ori mai mari decât toate demonstrațiile făcute anterior de toate programele, puse la un loc.
De ce este rezultatul ăsta important? În primul rând pentru că antișahul este cel mai complex joc rezolvat vreodată. Poate ați auzit că, cu ajutorul calculatoarelor, omenirea a reușit să demonstreze jocuri tot mai complexe de-a lungul timpului (dame, țintar, hex, parțial reversi). Antișahul este considerabil mai complex decât următorul pe listă (damele). E drept, comparația nu este chiar corectă, căci la antișah albul câștigă, pe când damele se termină remiză. Asta înseamnă că, pentru fiecare mutare a negrului, la antișah este suficient să găsești o mutare câștigătoare a albului, pe când la dame fiecare variantă trebuie considerată. Dar realitatea rămâne că spațiul de poziții posibile la antișah este mult mai mare decât la dame. Efortul total pentru antișah a fost undeva la 200-300 de procesor-ani.
Una peste alta, sunt mândru că am avut ocazia să contribui puțin la rezolvarea acestui joc. Sunt și un pic nostalgic, căci de ani de zile îmi doream să mă întorc la programarea de antișah, ca să pun umărul la asaltul final asupra demonstrației. Dar mereu am ales să mă ocup de proiecte mai „serioase”. Și acum iată că nu mai este cazul. Dar e bine și așa, am o tentație mai puțin care să mă distragă de la dexonline. 🙂
Antișahul a fost rezolvat Read More »