Șahul pe computer este un termen popular din domeniul cercetării inteligenței artificiale , adică crearea de software și calculatoare speciale pentru jocul de șah . De asemenea, termenul „șah pe computer” este folosit pentru a se referi la un joc împotriva unui program de șah pe computer, un joc de programe între ele. Începând cu anii 2000, chiar și cei mai puternici jucători umani nu au nicio șansă împotriva programelor de șah [1] .
Istoria mașinilor de șah este mai veche decât istoria computerelor. Ideea unei mașini de joc de șah datează din secolul al XVIII-lea. În jurul anului 1769, a apărut mașina de șah Mechanical Turk . A fost destinat distracției Reginei Maria Tereza. Aparatul a jucat foarte bine - înăuntrul ei era un jucător de șah puternic, care a făcut mutările.
Crearea automatelor mecanice de șah a încetat odată cu apariția computerelor digitale la mijlocul secolului al XX-lea. În 1951, Alan Turing a scris algoritmul Turochamp , cu care o mașinărie putea juca șah, doar inventatorul însuși acționând ca o mașină. Această prostie a primit chiar și numele - „Mașina de hârtie a lui Turing”. O persoană i-a luat mai mult de jumătate de oră pentru a face o mișcare. Algoritmul a fost mai degrabă condiționat, și chiar și înregistrarea jocului, unde „mașina de hârtie” a lui Turing a pierdut în fața unuia dintre colegii săi, a fost păstrată [2] . Din cauza lipsei de acces la un computer, programul nu a fost niciodată testat în funcțiune.
În această perioadă, în 1951, matematicianul Claude Shannon a scris prima sa lucrare despre programarea șahului. El a scris: „ Deși poate să nu aibă nicio semnificație practică, întrebarea în sine este teoretic interesantă și să sperăm că soluția acestei probleme va servi drept impuls pentru soluționarea altor probleme de natură similară și de importanță mai mare ”. Shannon a remarcat, de asemenea, existența teoretică a celei mai bune mișcări în șah și imposibilitatea practică de a găsi una.
Următorul pas în dezvoltarea programării de șah a fost dezvoltarea la laboratorul nuclear Los Alamos în 1952 pe un computer MANIAC I cu o frecvență de ceas de 11 kHz a unui program de șah pentru a juca pe o tablă 6x6, fără participarea elefanților. Se știe că acest computer a jucat un singur joc împotriva unui jucător de șah puternic, a durat 10 ore și s-a încheiat cu victoria șahului. Un alt joc a fost jucat împotriva unei fete care învățase recent să joace șah. Mașina a câștigat la a 23-a mutare, pentru vremea lui a fost o mare realizare.
În 1957, Alex Bernstein a creat primul program de joc pe o tablă de șah standard și cu participarea tuturor pieselor [3] .
O dezvoltare importantă pentru șahul pe computer a avut loc în 1958, când Allen Newell , Cliff Shawși Herbert Simon a dezvoltat un algoritm de reducere a arborelui de căutare numit „ tăieri alfa-beta ” [3] [4] pe care sunt construite funcțiile de căutare ale tuturor programelor moderne puternice.
În 1967, într-un meci de patru jocuri, un program creat la Institutul de Fizică Teoretică și Experimentală (ITEP) a învins programul de șah al Universității Stanford cu 3-1. Potrivit marilor maeștri care au jucat cu programul, acesta a jucat cu puterea categoriei a treia de șah . [5]
La primul Campionat Mondial de șah printre programe de calculator, în august 1974, la Stockholm ( Suedia ) , programul Kaissa , creat în 1971 de angajații Institutului de Probleme de Control al Academiei de Științe a URSS, a câștigat toate cele patru jocuri și a devenit primul campion mondial. dintre programele de șah, programele de depășire „Șah 4”, „Haos” și „Ribbit”, care au obținut câte 3 puncte. La campionat au participat 13 mașini din 8 țări ale lumii, care și-au transmis prin telefon deplasările în sala campionatului operatorului.
Prima mașină care a atins nivelul de maestru de șah a fost , în 1983 de Joe Condon și Thompson . Belle a fost primul computer conceput exclusiv pentru a juca șah. Evaluarea sa oficială Elo a fost 2250, făcând-o cea mai puternică mașină de șah a timpului său.
În 1994, Garry Kasparov a pierdut un turneu blitz din Munchen în fața programului Fritz 3 . Programul a depășit, de asemenea, Viswanathan Anand , Boris Gelfand și Vladimir Kramnik . Marele maestru Robert Huebner a refuzat să joace împotriva programului și a pierdut automat. Kasparov a jucat al doilea meci cu Fritz și a câștigat cu 4 victorii și 2 remize.
În februarie 1996, Garry Kasparov a învins supercomputerul de șah Deep Blue cu 4-2. Acest meci este notabil deoarece primul joc a fost câștigat de Deep Blue , devenind automat primul computer care a învins un campion mondial de șah în termeni de turneu. Deep Blue a calculat 50 de miliarde de poziții la fiecare trei minute, în timp ce Kasparov a calculat 10 pozitii pentru acelasi timp. Deep Blue avea 200 de procesoare . De atunci, pasionații de șah și inginerii informatici au creat multe mașini de șah și programe de calculator.
În 1997, Deep Blue a câștigat o revanșă (2 victorii, 3 remize, 1 înfrângere) și a devenit primul computer care l-a învins pe cel mai puternic jucător de șah din lume. Kasparov nu a mai putut recupera, deoarece IBM a abandonat alte competiții, considerând misiunea finalizată.
Calculatoarele de șah sunt acum disponibile la un preț foarte mic. Au apărut multe programe open source, în special Crafty , Fruit și GNU Chess , care pot fi descărcate gratuit de pe Internet și pot învinge mulți jucători profesioniști de șah. Cele mai bune programe comerciale și gratuite precum Shredder , Fritz sau Komodo sunt deja cu mult peste nivelul campionilor umani. Motorul cu sursă deschisă Stockfish este foarte bine clasat pe listele de evaluare a computerelor, cum ar fi CEGT , CCRL , SCCT și CSS , datorită dezvoltării și testării în colaborare a multor oameni [6] .
Primele motive pentru informatizarea șahului au fost dorința de a se distra, de a crea programe pentru turnee de șah pe computer și de a efectua cercetări științifice care să permită o înțelegere mai profundă a capacității cognitive umane. Pentru primele două scopuri, șahul pe computer a fost un succes fenomenal: au trecut mai puțin de cincizeci de ani de la primele încercări de a crea un program de șah care să poată concura în condiții egale cu cei mai buni jucători de șah.
Alexander Kronrod a definit rolul șahului pe computer cu binecunoscuta frază: „Șahul este musca de fructe a inteligenței artificiale ”. Analogia se află la suprafață: șahul este un intelectual necondiționat, dar în același timp o sarcină clar formalizată, simplă ca structură și compactă, adică este un obiect convenabil de cercetare de laborator în inteligența artificială, la fel ca o muscă de fructe datorată. la dimensiunea sa mică, fertilitatea și generațiile de schimbare rapidă este un obiect de laborator convenabil pentru studierea eredității. Într-adevăr, multe metode și domenii cunoscute de inteligență artificială au fost testate pe șah, inclusiv metode de optimizare a enumerației (evitarea „ exploziei combinatorii ” la calcularea opțiunilor cu câteva mișcări înainte), recunoașterea modelelor , sisteme expert , programare logică .
Cu toate acestea, spre surprinderea și supărarea multora, șahul a adus oamenii puțin mai aproape de a crea mașini cu inteligență asemănătoare omului. Programele moderne de șah, de fapt, s-au oprit în stadiul cel mai primitiv al activității intelectuale: explorează un număr mare de mișcări posibile pentru ambii jucători, folosind diverse metode de trunchiere a arborelui de enumerare, inclusiv o funcție de evaluare relativ simplă . În combinație cu bazele de date care stochează deschideri și jocuri finale precalculate gata făcute, datorită vitezei și memoriei computerelor moderne, aceste metode oferă deja un computer care joacă șah la nivel de mare maestru. Din aceste motive, șahul pe computer nu mai are la fel de mult interes academic. Rolul „Drosophila a inteligenței artificiale” a fost preluat de alte jocuri mintale , cum ar fi, de exemplu, Go . Mult mai mult decât în șah, cantitatea de enumerare a opțiunilor din astfel de jocuri limitează capacitatea de a folosi metode simple și impune oamenilor de știință să aplice abordări mai speculative jocului. .
Dezvoltatorii de programe de șah trebuie să ia o serie de decizii atunci când le scriu. Acestea includ:
Vezi si:
Un computer de șah este un dispozitiv specializat pentru jocul de șah . Folosit de obicei pentru divertisment și exersare a jucătorilor de șah în absența unui partener uman, ca mijloc de analiză a diferitelor situații de joc, pentru computere concurente între ele.
Calculatoarele de șah pentru consumatori sunt de obicei realizate sub forma unei table de șah cu un afișaj și un set de taste pentru a efectua acțiunile de joc necesare. În funcție de design, placa poate să nu fie conectată în niciun fel la partea computerului și să nu aibă electronică, sau invers, poate fi un afișaj care afișează o reprezentare grafică a situației de joc.
De la mijlocul anilor 1980, computerele de șah de consum au fost produse în URSS " Elektronika IM -01 ", " Elektronika IM-05 ", " Elektronika IM-29 " (" Partener de șah "), " Intellect-01 ", " Intellect " -02" , "Debut", "Phoenix", "100 de ani de Novosibirsk" și altele.
Majoritatea programelor se bazează pe metoda de enumerare a mișcării, există programe bazate pe metode euristice. O încercare de a crea un program real de șah bazat pe algoritmul unui maestru de șah a fost făcută de fostul campion mondial M. Botvinnik și programatorii săi asistenți B. Shtilman și A. Reznitsky.
O mare descoperire în dezvoltarea programelor de șah a venit odată cu utilizarea rețelelor neuronale . De exemplu, în 2017, DeepMind a creat un program de rețea neuronală care, după ce a învățat singur timp de câteva ore, a reușit să învingă cei mai buni algoritmi de șah. Într-o serie de 100 de jocuri împotriva lui Stockfish , AlphaZero nu a pierdut niciodată și a câștigat 25 de jocuri cu alb și trei jocuri cu negru. Algoritmul AlphaZero a fost creat pe baza programului AlphaGo , care a devenit anterior campion absolut în jocul Go . Algoritmul AlphaZero seamănă mai mult cu modul în care o persoană joacă șah. Ia în considerare mai puține posturi decât alte programe. Potrivit autorilor, se estimează 80 de mii de poziții pe secundă, față de 70 de milioane pe secundă pentru Stockfish. Spre deosebire de AlphaGo, AlphaZero este capabil să învețe mai multe sarcini-jocuri simultan, și nu doar unul. AlphaZero nu a fost învățat jocul, ci a oferit doar cunoștințe de bază despre regulile jocului. AlphaZero s-a jucat apoi cu el însuși și a dezvoltat tactici pe cont propriu [7] [8] .
Prima cercetare privind programarea șahului a fost făcută în 1950 de matematicianul american Claude Shannon , care a imaginat cu succes două metode principale de căutare posibile care ar putea fi utilizate și le-a numit „Tipul A” și „Tipul B”.
Programele de tip A folosesc așa-numita abordare „forță brută” , învățând fiecare poziție posibilă la o adâncime fixă folosind algoritmul Minimax . Shannon a susținut că această metodă ar fi nepractică din două motive.
În primul rând, cu aproximativ treizeci de mișcări posibile într-o poziție tipică, este nevoie de aproximativ 12,5 minute pentru a afla aproximativ 753 de milioane de poziții ale nodurilor (calculând aproximativ trei mișcări înainte pentru ambele părți), chiar și în cazul „foarte optimist” când computerul poate evalua un milion de poziții pe secundă (a fost nevoie de patruzeci de ani pentru a realiza acest lucru).
În al doilea rând, programele de tip A au neglijat așa-numita problemă a stării statice încercând să evalueze poziția la începutul unui schimb de piese sau alte secvențe importante de mișcări (cum ar fi combinațiile tactice). Prin urmare, Shannon a presupus că, cu algoritmul de tip A, numărul de poziții de examinat va crește enorm, ceea ce ar încetini semnificativ programul. În loc să irosească puterea de procesare a computerului pentru a investiga mișcările proaste sau nesemnificative, Shannon a sugerat utilizarea programelor de tip B. Această metodă are două îmbunătățiri:
Acest lucru a oferit programelor capacitatea de a calcula mișcări importante la o mai mare profunzime și de a le face într-un timp rezonabil. Prima abordare a trecut testul timpului: toate moderne[ când? ] programele aplică o căutare „calmă” în urmă înainte de a evalua o poziție.
Programele computerizate de șah tratează mișcările de șah ca pe un arbore de joc. În teorie, ei ar trebui să evalueze toate pozițiile care vor apărea după toate mișcările posibile, apoi toate mișcările posibile după acele mișcări și așa mai departe. Fiecare mișcare a unui jucător se numește „ nod ”. Enumerarea mutărilor continuă până când programul atinge adâncimea maximă a căutării sau determină că a fost atinsă poziția finală (de exemplu, șahmat sau impas ). Deja pe baza evaluării postului alege cea mai bună strategie. În fiecare poziție, numărul de mișcări posibile ale jucătorului este aproximativ egal cu 35. Pentru o analiză completă a patru jumătăți de mișcări (două mișcări ale fiecărui jucător), este necesar să se exploreze aproximativ un milion și jumătate de posibilități, pentru șase - aproape două miliarde. Analiza 3 mișcări înainte este foarte puțin pentru un joc bun.
Programatorii încearcă să limiteze numărul de mișcări care trebuie rezolvate în moduri diferite ( tăierea arborelui de căutare - tăierea arborelui jocului ). Cea mai populară este tăierea alfa-beta , care nu ia în considerare pozițiile care au un scor mai mic decât cele deja evaluate.
Implementarea software aproximativă:
private int AlphaBeta ( int color , int Depth , int alpha , int beta ) { if ( Depth == 0 ) return Evaluate ( color ); int bestmove ; Mișcări vectoriale = GenerateMoves (); pentru ( int i = 0 ; i < se mișcă . dimensiune (); i ++ ) { makeMove ( se mișcă . get ( i )); eval = - AlphaBeta ( - culoare , Adâncime - 1 , - beta , - alfa ); unmakeMove ( muta . get ( i )); if ( eval >= beta ) return beta ; if ( eval > alpha ) { alpha = eval ; if ( Adâncime == defaultDepth ) { bestmove = se mișcă . obține ( i ); } } } returnează alfa ; }Primul exemplu de apel:
AlphaBeta ( 1 , 6 , Integer . MIN_VALUE , Integer . MAX_VALUE );La primul apel, metoda (funcția) este apelată cu fereastra maximă. În apelurile recursive, variabilele alfa și beta sunt schimbate cu inversarea semnului și „îngustează” masa de căutare.
A doua metodă comună este aprofundarea iterativă . În primul rând, arborele jocului este străbătut la o anumită adâncime, după care sunt evidențiate câteva mișcări cele mai bune. Programul evaluează apoi aceste mișcări în raport cu o profunzime mai mare pentru a afla mai multe despre consecințele lor. Aceasta operatie se repeta pana la cel mai bun curs posibil din punct de vedere al programului. Această abordare vă permite să renunțați rapid la un procent considerabil de opțiuni de joc nepromițătoare. De exemplu, nu are sens să investighezi ce se întâmplă dacă schimbi o regină cu un pion când există mișcări mai bune în poziție.
Un element important al algoritmilor de șah este sistemul de evaluare a poziției . Este imposibil să evaluăm poziția cu absolut exactitate, deoarece pentru aceasta ar fi necesar să analizăm trilioane de secvențe de mișcări de la începutul până la sfârșitul jocului. Dacă ar exista o funcție care ar face posibilă estimarea fiabilă a poziției, sarcina de a juca șah ar fi simplificată pentru a evalua fiecare dintre cele câteva zeci de mișcări disponibile în prezent și nu ar fi nevoie să se calculeze mișcări ulterioare.
Prin urmare, evaluarea postului de către program este foarte aproximativă, deși funcțiile de evaluare ale programelor sunt îmbunătățite constant. Funcțiile de evaluare evaluează de obicei pozițiile în sutimi de pion. Aceste funcții evaluează doar câțiva parametri simpli:
Funcțiile de evaluare a poziției sunt ineficiente atunci când situația de pe tablă se schimbă dramatic cu fiecare mutare, când, de exemplu, are loc un schimb de piese sau se efectuează un fel de combinație de șah. De aici provine conceptul de stare statică ( repaus ) și orizontul de calcul . În stare statică, pe tabla de șah are loc o luptă de poziție lentă, iar orizontul de calcul demn de atenție este foarte larg. Aceasta înseamnă că schimbarea decisivă nu va veni într-un viitor care poate fi ușor de prevăzut. Într-o astfel de situație, funcțiile de evaluare a poziției sunt mai importante decât încercările de a calcula posibile opțiuni.
Într-o situație dinamică, un joc bazat pe funcția de evaluare a poziției poate duce la decizii complet eronate. În cazul extrem, dacă programul are un orizont de calcul reglat scurt și ia în considerare doar o evaluare a poziției pe termen scurt, atunci sfârșitul poate veni chiar în momentul în care are loc schimbul de matci, iar una dintre ele poate deja fi bătut, iar al doilea nu a fost încă înlocuit. Evaluarea unei astfel de stări de către program duce la o concluzie complet eronată că unul dintre jucători are un avantaj uriaș, în timp ce acesta va dispărea într-o singură mișcare, ceea ce, însă, programul nu îl vede. Dacă statul nu este încă static, trebuie să continuați schimbul până la capăt și să evaluați situația când nu mai sunt posibile schimbări radicale. Oamenii în general disting în mod intuitiv între aceste două situații – programele de șah, pe de altă parte, trebuie să aibă un set de condiții care să le permită să schimbe modul în care funcționează în stări statice și dinamice.
Este mai dificil să evaluezi mișcările din deschidere . Majoritate[ cât? ] programele folosesc biblioteci de deschidere scrise în prealabil, care au un anumit număr mic de mișcări inițiale și răspunsuri la un anumit număr de mișcări, care nu este constant, deoarece depinde de tipul de deschidere.
Chiar și în anii 1970 și 80, întrebarea a rămas deschisă când un program de șah va fi capabil să-i învingă pe cei mai puternici jucători de șah. În 1968, marele maestru internațional David Levy a pariat că niciun computer nu l-ar putea învinge în următorii zece ani. El a câștigat un pariu învingând Chess 4.7 (cel mai puternic la acea vreme) în 1978 , dar știa că nu a trecut mult timp până când computerele vor învinge campionii mondiali. În 1989, programul Deep Thought l-a învins pe Levy.
Dar programele erau încă mult sub nivelul campionului mondial pe care Garry Kasparov l-a demonstrat când l-a învins de două ori pe același Deep Thought în 1991.
Acest lucru a durat până în 1996, când a avut loc un meci între Kasparov și computerul Deep Blue al IBM , unde campionul a pierdut primul său joc. Pentru prima dată, un program de șah pe computer a învins un campion mondial sub controlul standard al timpului. Cu toate acestea, Kasparov și-a schimbat stilul de joc, câștigând trei și egalând două dintre cele cinci jocuri rămase. În mai 1997, o versiune îmbunătățită a Deep Blue l-a învins pe Kasparov cu un scor de 3,5-2,5. În 2003, a fost realizat un film documentar care a explorat reproșurile lui Kasparov cu privire la posibila utilizare a unui jucător de șah de către IBM, numit „Meciul s-a încheiat: Kasparov și mașina” ( Eng . Game Over: Kasparov and the machine ). Filmul a susținut că câștigul mult-așteptat al lui Deep Blue a fost manipulat pentru a crește valoarea de piață a IBM. În parte, aceste acuzații au fost justificate. Regulile au permis dezvoltatorilor să schimbe programul între jocuri. Deep Blue a fost schimbat între jocuri pentru a înțelege mai bine stilul de joc al lui Kasparov de către aparat, ajutând la evitarea capcanei finale în care programul a căzut de două ori.
IBM a demontat Deep Blue după meci, de atunci acest computer nu a mai fost jucat o dată. Ulterior, au avut loc alte meciuri Man vs Machine.
Odată cu creșterea puterii de calcul, programele de șah care rulează pe computerele personale au început să atingă nivelul celor mai buni jucători de șah. În 1998, programul Rebel 10 l-a învins pe Viswanathan Anand , care era atunci numărul 2 mondial. Cu toate acestea, nu toate jocurile au fost jucate cu controale de timp standard. Din cele opt jocuri din meci, patru au fost jucate cu control blitz (cinci minute plus cinci secunde per mutare), pe care Rebel le -a câștigat cu 3-1. Încă două jocuri au fost cu control semi-blitz (cincisprezece minute fiecare), pe care programul le-a câștigat și el (1,5-1). În cele din urmă, ultimele două jocuri s-au jucat cu controlul timpului standard al turneului (două ore pentru 40 de mutări și o oră pentru restul mutărilor), iar aici Anand a câștigat cu scorul de 0,5-1,5. Până atunci, în jocurile rapide, computerele jucau mai bine decât oamenii, dar cu controlul clasic al timpului, avantajul unui computer față de un om nu era încă atât de mare.
În 2000, programele comerciale de șah Junior și Fritz au reușit să tragă meciuri împotriva foștilor campioni mondiali Garry Kasparov și Vladimir Kramnik .
În octombrie 2002, Vladimir Kramnik și Deep Fritz au concurat într-un meci de opt meciuri în Bahrain . Meciul s-a încheiat la egalitate. Kramnik a câștigat al doilea și al treilea joc folosind tactici tradiționale anti-computer - jucând cu atenție, urmărind un avantaj pe termen lung pe care computerul nu îl poate vedea în arborele său de căutare. Totuși, Fritz a câștigat al cincilea joc după gafa lui Kramnik. Mulți comentatori ai turneului au considerat al șaselea joc foarte interesant. Kramnik, având o poziție mai bună la începutul jocului de mijloc , a încercat să sacrifice o piesă pentru a crea un atac tactic puternic (o astfel de strategie este foarte riscantă împotriva computerelor). Fritz a găsit o apărare puternică și acest atac a înrăutățit semnificativ poziția lui Kramnik. Kramnik a predat jocul, crezând că jocul a fost pierdut. Cu toate acestea, analizele ulterioare au arătat că Fritz era puțin probabil să fi putut aduce jocul la câștigurile sale. Ultimele două meciuri s-au încheiat la egalitate.
În ianuarie 2003, Garry Kasparov a jucat împotriva programului Junior din New York . Meciul s-a încheiat cu scorul de 3-3.
În noiembrie 2003, Garry Kasparov a jucat cu X3D Fritz . Meciul s-a încheiat cu scorul de 2-2.
În 2005, Hydra , un sistem hardware și software special de șah cu 64 de procesoare, l-a învins pe Michael Adams - șahista care la acea vreme era al șaptelea cel mai bun jucător de șah Elo din lume - într-un meci de șase jocuri cu un scor de 5,5. -0,5 (deși pregătirea acasă a lui Adams a fost mult mai mică decât cea a lui Kasparov în 2002). Unii comentatori credeau că Hydra va avea în sfârșit un avantaj incontestabil față de cei mai buni jucători de șah.
În noiembrie-decembrie 2006, campionul mondial Vladimir Kramnik a jucat cu programul Deep Fritz . Meciul s-a încheiat cu victoria mașinii cu scorul de 2-4.
Mai multe baze de date Endgame
Calculatoarele sunt folosite pentru a analiza unele poziții ale jocului final . Astfel de baze de date final de joc sunt create folosind retrospectiva , pornind de la pozițiile în care rezultatul final este cunoscut (de exemplu, unde o parte a fost șahmat) și văzând ce alte poziții se află la distanța de mișcare, apoi o îndepărtare de acestea și așa mai departe. Ken Thompson , cunoscut în calitate de proiectant șef al sistemului de operare UNIX , a fost un pionier în acest domeniu.
Jocul final a fost mult timp o slăbiciune vizibilă a programelor de șah, deoarece profunzimea căutării a fost insuficientă. Astfel, chiar și programele care au jucat puterea unui maestru nu sunt capabile să câștige în pozițiile finale, unde chiar și un jucător de șah moderat puternic ar putea forța o victorie.
Dar rezultatele analizei computerizate i-au surprins uneori pe oameni. În 1977, mașina de șah Belle a lui Thompson , folosind bazele de date de final de joc de rege+turnă versus rege+regina, a reușit să atragă teoretic meciuri pierdute împotriva jucătorilor de șah cu titlu.
Majoritatea maeștrilor au refuzat să joace împotriva computerului într-un joc final daen versus turn , dar Walter Brown a acceptat provocarea. Poziția a fost configurată în așa fel încât teoretic a fost posibil să câștigi în 30 de mutări cu un joc impecabil. Brown a primit două ore și jumătate pentru cincizeci de mișcări. După patruzeci și cinci de mutări, Brown a fost de acord cu o remiză, neputând câștiga în ultimele cinci mutări. În poziția finală, Brown a putut șahmat doar după șaptesprezece mutări.
În 2002 au fost publicate formate majore de baze de date final, inclusiv Edward Tablebases , De Koning Endgame Database și Nalimov Endgame Tablebases , pe care multe programe de șah le suportă acum, cum ar fi Rybka , Shredder și Fritz . Jocurile finale cu cinci piese sau mai puțin au fost analizate complet. Jocurile finale cu șase piese au fost analizate, cu excepția pozițiilor din cinci piese împotriva unui rege singuratic. Mark Burzhutsky și Yakov Konoval au analizat câteva finalizări cu șapte piese. În toate aceste baze de date finale, rocarea este considerată imposibilă.
Bazele de date sunt generate prin păstrarea în memorie a estimărilor de poziție care au avut loc până acum și folosind aceste rezultate pentru a reduce arborele de căutare dacă astfel de poziții apar din nou. Simpla oportunitate de a reține scorurile tuturor pozițiilor atinse anterior înseamnă că factorul limitativ în rezolvarea unui joc final este pur și simplu cantitatea de memorie pe care o are computerul. Odată cu creșterea capacității memoriei computerului, jocurile finale de complexitate crescută vor fi rezolvate mai devreme sau mai târziu.
Un computer care folosește o bază de date de final de joc va putea, odată ce ajunge la o poziție în ele, să joace impecabil și să determine imediat dacă poziția este câștigătoare, pierdere sau egală, precum și găsirea modului cel mai rapid și mai lung de a obține un rezultat. Cunoașterea unei estimări exacte a poziției este, de asemenea, utilă atunci când crește puterea computerului, deoarece va permite programului să aleagă modalități de atingere a obiectivului în funcție de situație [adică simplificarea și schimbul pentru a obține o poziție clar examinată].
Calculatoarele sunt vizibil înaintea oamenilor în manevre tactice scurte care se află în adâncimea căutării programului. Mai ales periculoasă în astfel de cazuri este regina, care este perfectă pentru manevre pe termen scurt. Prin urmare, într-un joc împotriva computerului, oamenii fac adesea o încercare de a determina programul să facă schimb de matci. Acest lucru se întâmplă, de exemplu, atunci când o persoană își înrăutățește în mod deliberat poziția la începutul jocului, iar computerul o consideră benefică pentru el. Dacă programul stabilește evaluarea poziției ca fiind preferabilă pentru el însuși, atunci cel mai probabil va schimba piese, iar acest lucru este benefic pentru persoană. Desigur, programatorii au aflat despre astfel de „trucuri” și acest lucru este luat în considerare în cele mai recente versiuni ale programelor lor.
În schimb, jucătorii de șah trebuie să joace împotriva computerului cu manevre pe termen lung pe care programul nu le poate vedea în adâncimea de căutare. De exemplu, Kramnik a câștigat împotriva lui Deep Fritz cu un avans de pion trecut pe termen lung, ale cărui beneficii Fritz le-a descoperit prea târziu.
Succesul programelor de șah sugerează că este posibil să scrieți programe care se joacă la fel de bine în alte jocuri, cum ar fi shogi sau go .
Algoritmi similari, probabil, ar putea fi folosiți în timp ce jucați alte soiuri de șah. În shogi, există mai multe mișcări posibile, avantajul material înseamnă mult mai puțin, dar avantajul pozițional este mult mai semnificativ. Sunt construite sisteme complexe pentru a garanta siguranța regelui, dar nu este ușor pentru un computer să evalueze aceste sisteme. Numărul de piese din acest joc este constant și, prin urmare, jocul nu devine mai ușor în timp, ceea ce face imposibilă crearea unei baze de jocuri finale. De asemenea, nu există stări complet statice aici, deoarece jocul este redus la o luptă de poziție pe tot parcursul timpului. Prin urmare, scrierea unui program bun pentru a juca shogi este mult mai dificilă decât scrierea unui program de șah, deși multă experiență în jocurile de șah poate fi aplicată acestui joc. .
Go a devenit o adevărată provocare pentru programatori . Complexitatea calculării Go este cu câteva ordine de mărime mai mare decât în șah. La fiecare pas, sunt posibile aproximativ 200-300 de mișcări, în timp ce o evaluare statică a vieții grupurilor de pietre este practic imposibilă. O mișcare aici poate distruge complet întregul joc, chiar dacă celelalte mișcări au avut succes. Prin urmare, algoritmii care au avut succes pentru a juca șah nu sunt suficienți pentru a juca Go la nivel profesional. Cu toate acestea, în octombrie 2015, AlphaGo , un program de calculator dezvoltat de Google DeepMind , a câștigat pentru prima dată în lupta împotriva profesioniștilor Fan Hui 2-dan . Și în martie 2016, a câștigat un meci cu Lee Sedol , un profesionist de 9 dani, cu scorul de 4-1.
| Şah | |
|---|---|
| Articole principale | |
| Inventarul de șah | |
| regulile de șah | |
| Glosar de termeni | |
| Tactici de șah | |
| Strategia de șah | |
| debutează | |
| Finalul jocului | |
| Site-uri de șah |
|
| Programe de șah | |