{"id":435,"date":"2016-10-25T21:28:19","date_gmt":"2016-10-25T18:28:19","guid":{"rendered":"http:\/\/catalin.francu.com\/blog\/?p=435"},"modified":"2016-10-25T21:38:29","modified_gmt":"2016-10-25T18:38:29","slug":"antisahul-a-fost-rezolvat","status":"publish","type":"post","link":"https:\/\/catalin.francu.com\/blog\/2016\/10\/antisahul-a-fost-rezolvat\/","title":{"rendered":"Anti\u0219ahul a fost rezolvat"},"content":{"rendered":"

Acest articol este din categoria \u201eC\u0103t\u0103lin este adorabil c\u00e2nd \u00eencearc\u0103 s\u0103 povesteasc\u0103 despre chestiile lui de\u00a0geek<\/em> pe un blog care se vrea atehnic\u201d. \ud83d\ude42 Dar am ve\u0219ti fascinante dintr-un capitol care m-a interesat ani de zile, \u0219i pentru care am \u0219i programat pe buc\u0103\u021bele\u00a0vreo 6 luni cu norm\u0103 \u00eentreag\u0103 (estimativ). A\u0219a c\u0103 s\u0103-mi fie permis!<\/p>\n

Jocul de anti\u0219ah<\/a> a fost rezolvat. Mark Watkins<\/a>, un matematician de la Universitatea din Sydney, a reu\u0219it s\u0103 demonstreze c\u0103 albul c\u00e2\u0219tig\u0103 (\u00eenceputul este\u00a01.<\/strong> e3). Rezultatul este o demonstra\u021bie online<\/a>, dar \u0219i un articol \u0219tiin\u021bific<\/a>\u00a0superb \u00een care Mark \u00ee\u0219i prezint\u0103 munca.<\/p>\n

Despre anti\u0219ah am<\/a> tot<\/a> scris<\/a> pe blogul \u0103sta, poate nu destul raportat la c\u00e2t am urm\u0103rit subiectul \u00een to\u021bi ace\u0219ti ani. Este o variant\u0103 a \u0219ahului cu acelea\u0219i piese \u0219i pe aceea\u0219i tabl\u0103, dar scopul este s\u0103 \u00ee\u021bi pierzi toate piesele (iar captura este obligatorie). Interesul meu pentru anti\u0219ah a \u00eenceput \u00een 2001, c\u00e2nd eram student la MIT \u0219i ni\u0219te colegi de-ai mei au primit ca proiect la un curs<\/a> s\u0103 scrie\u00a0un program care s\u0103 joace anti\u0219ah. Mi s-a p\u0103rut un subiect interesant, a\u0219a c\u0103 am scris \u0219i eu un program.<\/p>\n

Ulterior am aflat despre serverul de \u0219ah FICS (freechess.org<\/a>), care are\u00a0marele avantaj c\u0103 prime\u0219te nu doar oameni, ci \u0219i programe. A\u0219a am intrat \u00eentr-o comunitate de juc\u0103tori \u0219i programatori care practicau \u0219i studiau acest joc. N-am devenit niciodat\u0103 bun la el, dar m-a interesat programarea. Programul meu, Nilatac<\/a>, a fost unul dintre cele mai bune la vremea lui. La cerere, am creat \u0219i o versiune mai slab\u0103 a lui, CatNail, pentru ca \u00eencep\u0103torii s\u0103 aib\u0103 cu cine juca. P\u00e2n\u0103 ast\u0103zi, CatNail a jucat peste 1,1 milioane de partide \u0219i a fost online 80% din timp \u00een ultimii 15 ani. La un moment dat am \u00eencercat s\u0103 rescriu de la zero programul, mai robust. Am ajuns p\u00e2n\u0103 la genunchiul broa\u0219tei, dar am apucat m\u0103car s\u0103 scriu o tabel\u0103 de finaluri<\/a> care d\u0103 strategia perfect\u0103 pentru orice pozi\u021bie cu maxim 5 piese.<\/p>\n

Comunitatea de anti\u0219ah suspecta de mult\u0103 vreme (dinainte de anul 2000) c\u0103 albul poate c\u00e2\u0219tiga orice partid\u0103, iar\u00a01.\u00a0<\/strong>e3 era mutarea favorit\u0103. Ce \u00eenseamn\u0103 asta? \u00censeamn\u0103 c\u0103 pentru orice ap\u0103rare\u00a0a negrului albul trebuie s\u0103 dea un r\u0103spuns c\u00e2\u0219tig\u0103tor. Iar asta se poate \u00eent\u00e2mpla la prima mutare, la a doua, la a treia…, \u0219i pe oricare din aceste linii jocul trebuie s\u0103 duc\u0103 la o pozi\u021bie \u00een care albul \u0219i-a dat toate piesele. Rezultatul demonstra\u021biei este, a\u0219adar, un fel de arbore de posibilit\u0103\u021bi care se ramific\u0103 pornind de la pozi\u021bia ini\u021bial\u0103, iar \u201efrunzele\u201d arborelui sunt pozi\u021bii finale \u00een care albul c\u00e2\u0219tig\u0103.<\/p>\n

Unele ap\u0103r\u0103ri ale negrului sunt aproape folclorice, c\u0103ci orice \u00eencep\u0103tor \u00eenva\u021b\u0103 rapid s\u0103 le evite\u00a0(1.<\/strong> … d5 \u0219i\u00a01.<\/strong> … d6 – lua\u021bi o tabl\u0103 de \u0219ah \u0219i vede\u021bi dac\u0103 pute\u021bi for\u021ba victoria albului pe aceste linii!). \u00cenc\u0103 vreo 10 r\u0103spunsuri posibile pot fi demonstrate u\u0219or cu un program nu prea de\u0219tept. Altele \u00eens\u0103 se las\u0103 greu demonstrate. De exemplu, sunt m\u00e2ndru c\u0103 Nilatac a\u00a0reu\u0219it s\u0103 demonstreze \u00een premier\u0103 linia\u00a01.<\/strong> e3 Nh6. Este principala mea contribu\u021bie \u00een domeniu. Dar, pe de alt\u0103 parte, nu a fost \u00een stare s\u0103 demonstreze linia\u00a01.\u00a0<\/strong>e3 c6 dec\u00e2t ajutat cu linguri\u021ba. C\u00e2teva ap\u0103r\u0103ri (\u00een special\u00a01.\u00a0<\/strong>… b6\u00a0\u0219i\u00a01.<\/strong> … c5) nu se l\u0103sau demonstrate, de\u0219i mai mul\u021bi oameni lucrau la asta.<\/p>\n

Cam \u00een acest stadiu era \u00een\u021belegerea noastr\u0103 despre joc c\u00e2nd Mark a \u00eenceput s\u0103 lucreze la propriul s\u0103u program prin 2011. Povestea lui despre cum a procedat, peste ce obstacole a dat \u0219i cum le-a dep\u0103\u0219it este captivant\u0103. De exemplu, exist\u0103 linii\u00a0foarte \u201eml\u0103\u0219tinoase\u201d, \u00een care negrul \u00ee\u0219i poate prelungi agonia cu zeci sau sute de mut\u0103ri. Acolo algoritmul de rezolvare se poate p\u0103c\u0103li c\u00e2nd decide ce mut\u0103ri ale albului sunt \u201epromi\u021b\u0103toare\u201d \u0219i poate pierde\u00a0luni de zile analiz\u00e2nd o linie care, de fapt, nu duce la victorie. \u00cen fiecare din aceste (multe) situa\u021bii, Mark s-a consultat cu juc\u0103tori umani. Flerul acestora, bazat pe experien\u021ba a zeci de mii de partide jucate, a indicat adesea o mutare surprinz\u0103toare pe care algoritmul nu o analizase \u00een profunzime \u0219i care, la o analiz\u0103 mai ad\u00e2nc\u0103, putea fi demonstrat\u0103 \u00een doar c\u00e2teva ore sau zile.<\/p>\n

La final, buc\u0103\u021bile din demonstra\u021bie pe care le-a descoperit Mark au fost cam de 3-4 ori mai mari dec\u00e2t toate demonstra\u021biile f\u0103cute anterior de toate programele, puse la un loc.<\/p>\n

De ce este rezultatul \u0103sta important? \u00cen primul r\u00e2nd pentru c\u0103 anti\u0219ahul este cel mai complex joc rezolvat vreodat\u0103. Poate a\u021bi auzit c\u0103, cu ajutorul calculatoarelor, omenirea a reu\u0219it s\u0103 demonstreze jocuri tot mai complexe de-a lungul timpului (dame, \u021bintar, hex, par\u021bial reversi). Anti\u0219ahul este considerabil mai complex dec\u00e2t urm\u0103torul pe list\u0103 (damele). E drept, compara\u021bia nu este chiar corect\u0103, c\u0103ci la anti\u0219ah albul c\u00e2\u0219tig\u0103, pe c\u00e2nd damele se termin\u0103 remiz\u0103. Asta \u00eenseamn\u0103 c\u0103, pentru fiecare mutare a negrului, la anti\u0219ah este suficient s\u0103 g\u0103se\u0219ti o mutare c\u00e2\u0219tig\u0103toare a albului, pe c\u00e2nd la dame fiecare variant\u0103 trebuie considerat\u0103. Dar realitatea r\u0103m\u00e2ne c\u0103 spa\u021biul de pozi\u021bii posibile la anti\u0219ah este mult mai mare dec\u00e2t la dame. Efortul total pentru anti\u0219ah a fost undeva la 200-300 de procesor-ani.<\/p>\n

Una peste alta, sunt m\u00e2ndru\u00a0c\u0103 am avut ocazia s\u0103 contribui pu\u021bin la rezolvarea acestui joc. Sunt \u0219i un pic nostalgic, c\u0103ci de ani de zile \u00eemi doream s\u0103 m\u0103 \u00eentorc la programarea de anti\u0219ah, ca s\u0103 pun um\u0103rul la asaltul final asupra demonstra\u021biei. Dar mereu am ales s\u0103 m\u0103 ocup de proiecte mai \u201eserioase\u201d. \u0218i acum iat\u0103 c\u0103 nu mai este cazul. Dar e bine \u0219i a\u0219a, am o tenta\u021bie mai pu\u021bin care s\u0103 m\u0103 distrag\u0103 de la dexonline. \ud83d\ude42<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Acest articol este din categoria \u201eC\u0103t\u0103lin este adorabil c\u00e2nd \u00eencearc\u0103 s\u0103 povesteasc\u0103 despre chestiile lui de\u00a0geek pe un blog care se vrea atehnic\u201d. \ud83d\ude42 Dar am ve\u0219ti fascinante dintr-un capitol care m-a interesat ani de zile, \u0219i pentru care am \u0219i programat pe buc\u0103\u021bele\u00a0vreo 6 luni cu norm\u0103 \u00eentreag\u0103 (estimativ). A\u0219a c\u0103 s\u0103-mi fie permis! […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[1],"tags":[],"class_list":["post-435","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/posts\/435","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/comments?post=435"}],"version-history":[{"count":7,"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/posts\/435\/revisions"}],"predecessor-version":[{"id":442,"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/posts\/435\/revisions\/442"}],"wp:attachment":[{"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/media?parent=435"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/categories?post=435"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/catalin.francu.com\/blog\/wp-json\/wp\/v2\/tags?post=435"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}