Sah-mat, inteligență artificială: ce ne învață experiența lui Garry Kasparov. Proiect educațional inteligență artificială Proiect educațional șah și inteligență artificială

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

postat pe http://www.allbest.ru/

DezvoltaresoftwaremodulartificialinteligentaPentrujocuriVşah

algoritm de inteligență computerizată de șah

• Introducere

Conceptul de „șah pe computer” este coeval cu știința cibernetică și cu secțiunea sa „inteligență artificială”. Șahul oferă un model ideal pentru studierea problemelor complexe, în special a celor care necesită enumerare. Dezvoltarea unui program de șah este considerată o problemă în dezvoltarea inteligenței artificiale din următoarele motive:

* există o convingere generală că problema este legată de problema inteligenței artificiale, deoarece șahul este considerat cel mai intelectual joc

* există un criteriu obiectiv pentru munca depusă - puterea programului de șah

* diferenţierea mai mare a acestui criteriu reprezintă posibilitatea de îmbunătăţire treptată a programului.

Unul dintre fondatorii ciberneticii și teoriei informației, Claude Shannon, a fost primul care a formulat regulile pentru alegerea unei mișcări pe tabla de șah încă din anii 50. În poziția analizată, toate opțiunile posibile sunt sortate la o anumită adâncime, iar pozițiilor rezultate li se atribuie un scor numeric folosind funcții obiective. Apoi procedura minimax se întoarce la poziția inițială, o evaluează și indică cea mai bună mișcare, în opinia mașinii.

Rolul unei persoane este de a stabili, prin evaluarea poziției, funcțiile țintă cât mai precis posibil. Aceste funcții au două componente - material și pozițional. Cu primul, totul este clar - superioritatea materială (în bucăți și pioni) este, de regulă, un argument foarte serios pentru a aprecia o poziție ca fiind cea mai bună. În plus, cu cât au mai puțin material pe placă ambele părți, cu atât estimarea este mai precisă.

Dar cu componenta pozițională totul este mult mai complicat: aici sunt luați în considerare mulți factori, de exemplu, locația pieselor și pionilor individuale, spațiul pe tablă, timpul pentru regruparea forțelor etc. Capacitatea de a evalua corect rolul a tuturor factorilor într-o anumită poziție a fost întotdeauna considerat unul dintre semnele priceperii jucătorilor de șah -a oamenilor.

Slăbiciunea jocurilor pe computer constă tocmai în abuzul de material și incapacitatea de a efectua o „căutare absolută” de opțiuni. În cărțile de șah din anii 70 și 80 puteți găsi un număr considerabil de exemple exemplare de oameni care se joacă cu mașini, când un maestru sau un mare maestru câștigă jocul cu ajutorul unor sacrificii frumoase de piese și pioni. Secretul este deja clar: pentru inteligența umană, spre deosebire de inteligența artificială, dominația factorilor poziționali asupra celor materiale era evidentă tocmai în acele momente în care se făceau sacrificii de material.

Pe măsură ce anii au trecut, odată cu creșterea vitezei computerului, profunzimea calculelor a crescut și, în același timp, au fost îmbunătățiți algoritmi care au îmbunătățit compilarea funcțiilor de evaluare a poziției. Și în a doua jumătate a anilor 90, computerele au început deja să concureze cu succes cu marii maeștri de top. Un eveniment de epocă pentru „cibernetica șahului” a avut loc în mai 1997. Calculatorul Deep Blue, creat de IBM, l-a învins pe însuși Garry Kasparov într-un meci de 6 jocuri. Calculatorul era echipat cu un cip special de șah, iar mașina se uita prin aproximativ 200 de milioane de poziții pe secundă. IBM Corporation a atras mulți mari maeștri pentru proiectul său; cele mai recente realizări ale teoriei șahului au fost folosite pentru a crea cei mai avansați algoritmi posibili. Și așa, așa cum sa menționat deja, în anii 90, programele de șah pentru computerele desktop au început să excludă computerele specializate.

În fiecare lună, puterea programelor de șah și puterea computerelor crește inexorabil, depășind chiar și cele mai sălbatice presupuneri ale optimiștilor. Chiar și acum 12-15 ani, discuții pe tema „Când va putea o mașină să învingă un mare maestru?” practic, sa rezumat la întrebarea „Este ea capabilă să facă asta în principiu?” Și dacă răspunsul „Poate” a fost încă obținut, atunci timpul a fost estimat în intervalul 15-25 de ani.

Realitatea a respins și aceste predicții. Totul s-a întâmplat mult mai repede! Deja la mijlocul anilor 90, s-a descoperit că sinteza „program de joc + computer” era capabilă să concureze cu un mare maestru.

Scopul lucrării este de a dezvolta și implementa un modul software de inteligență artificială pentru jocul de șah, care include:

1. cercetarea algoritmilor de joc existenti aplicabili jocului de sah

2. dezvoltarea unui algoritm pentru comportamentul unui adversar computerizat

3. determinarea parametrilor algoritmului pentru comportamentul adversarului computerului

4. implementare software, care include implementarea algoritmului de joc și dezvoltarea unei interfețe grafice

5. compararea software-ului dezvoltat cu analogii existente.

1 . Povestedezvoltareşahprograme

În 1951, Alan Turing a scris un algoritm care ar permite unei mașini să joace șah. Numai în acel moment inventatorul însuși a acționat ca o mașină. Tot în 1951, matematicianul Claude Shannon a scris primul său articol despre programarea șahului. El a descris două strategii pentru găsirea celei mai bune mișcări, ambele bazate pe o funcție de evaluare euristică puncte finale:

* tip A - enumerarea tuturor mișcărilor posibile la o adâncime fixă, cu un apel la sfârșitul funcției de evaluare (deoarece este imposibil de enumerat până la sfârșit)

* tip B - efectuează doar extinderea selectivă a anumitor linii, folosind cunoștințele acumulate în șah pentru a tăia ramuri neinteresante

Primul computer a fost proiectat de von Neumann pentru a efectua calcule complexe pentru crearea de arme nucleare. În 1950, a apărut primul eșantion, capabil să efectueze 10.000 de operații pe secundă. Unul dintre primele experimente cu dispozitivul a fost scrierea unui program de șah, cu toate acestea, șahul nu era standard - pe o tablă 6 * 6 fără episcopi.

Câțiva ani mai târziu, acest computer („MANIAC”) a jucat cu oamenii: un jucător de șah puternic a câștigat o victorie zdrobitoare, iar un începător a pierdut în 23 de mutări.

În 1957, pe IBM704 (42 kHz, 7 KB memorie), a fost implementat un program de tip B pe o placă completă, cu participarea tuturor pieselor. Aparatul a numărat 4 jumătăți de mișcare în 8 minute. Nivelul jocului este amator.

În 1962, Newell, Simon și Shaw au descoperit un algoritm numit alfa-beta, care nu dădea rezultate mai rele decât căutarea exhaustivă fără a explora toate opțiunile. Nu necesita cunoștințe speciale de șah și putea fi folosit pentru a rezolva orice problemă de căutare. Esența algoritmului este că în fiecare linie a jocului, pentru alb și negru, rezultatele lor maxime sunt urmărite, iar dacă la un moment dat negrul a primit deja un rezultat egal cu maximul alb atins anterior, atunci nu are rost să încerci. mai departe. Când căutarea revine la punctul în care a fost atins maximul lui White, rezultatul va fi în continuare respins.Toate programele moderne de șah se bazează pe una dintre versiunile îmbunătățite ale acestui algoritm.

Până în jurul anului 1973, toate programele de șah erau de tip B. Se bazau în principal pe generatoare de mișcări plauzibile, tăindu-le pe cele improbabile cu o evaluare statică. Odată cu apariția procesoarelor mai puternice, programatorii au început să treacă la tipul A. Primele au fost Teach și Chess4, acestea erau programe de „forță brută”, de îndată ce au atins o adâncime de 5 jumătăți de mișcare în etapa de mijloc a jocului. , au început să câștige concursuri cu programe de tip B.

În 1975, Robert Hyatt a început să dezvolte CrayBlitz, care pentru o lungă perioadă de timp a fost cel mai rapid program de șah și în perioada 1983-1989. - campioni mondiali printre programele de sah. A căutat aproximativ 40-50 de mii de poziții pe secundă (în 1983), ceea ce a fost o mare realizare pentru timpul său.

În 1977, Thompson și Condon de la Bell Labs au creat primul computer dedicat pentru șah. Ideea principală a fost implementarea unor părți ale programului de șah (generator de mișcări, funcție de estimare a poziției, detector de verificare etc.) la nivel hardware, ceea ce a eliminat întârzierile software în fiecare poziție fără a aștepta o creștere a puterii procesorului. Cele mai bune computere La acel moment, puteau examina până la 5 mii de poziții pe secundă, iar mașina lui Ken Thompson, numită Belle, procesa 180 de mii de linii pe secundă. Belle s-a putut gândi la poziții cu 8-9 jumătăți înainte, ceea ce l-a pus la nivelul unui maestru. A câștigat multe turnee de șah pe computer. Dar, în ciuda faptului că hardware-ul specializat este cu un ordin de mărime mai rapid decât o mașină obișnuită, programul CrayBlitz a jucat încă mai bine pe mașina ultramodernă de atunci.

În anii 90, Richard Lang, scriind exclusiv în limbaj de asamblare, a realizat un program de căutare selectivă foarte puternic, Genius. Până acum, acest program a ocupat în mod constant locurile 5-6 în campionatele mondiale de șah pe computer. Tot în anii 90, algoritmii de șah au început să se dezvolte semnificativ; a apărut euristica unei mișcări goale (NullMove) și tăierea selectivă a ramurilor de delimitare ale arborelui de căutare.

Ar trebui să luăm în considerare și cel mai faimos program de șah, super computerul de șah - Deep Blue. În 1987, Deep Blue a început ca o dezvoltare a studenților - a fost interesant pentru un grup de studenți capabili să-și încerce mâna, iar subiectul pentru o diplomă a fost excelent. Progresul tehnologiei a făcut posibilă realizarea primei versiuni de procesoare (numită ChipTest) foarte rapidă. A urmat o versiune îmbunătățită, numită Deep Thought. În acel moment, grupul a fost remarcat de departamentul de marketing al IBM și l-a abordat cu o ofertă care nu putea fi refuzată. Rezultatul a fost Deep Blue și Deep Blue II. Astfel, Deep Blue II este rezultatul a peste 10 ani de muncă a unui grup foarte capabil, care a inclus atât programatori/oameni hardware, cât și mari maeștri puternici. Toate lucrările au fost finanțate de IBM, așa că grupul avea resurse la care organizațiile academice nu visaseră niciodată. Deep Blue II se bazează pe puternicul server RS/6000 de la IBM. Serverul are 31 de procesoare convenționale; unul este declarat șef, alții 30 îi sunt subordonați. Există 16 procesoare de șah specializate conectate la fiecare procesor „de lucru”, deci sunt 480 de procesoare de șah în total. Întregul complex a procesat mai mult de un miliard de poziții pe secundă.

Pe 11 mai 1997, Deep Blue II l-a învins pe campionul mondial de șah Garry Kasparov într-un meci de 6 jocuri. După meciul cu campioana, Deep Blue a fost demontat.

După cum puteți vedea, de la primele și până la cele mai moderne programe, programele de șah au fost construite pe baza enumerarii posibilelor mișcări, dar au existat și încercări de a construi algoritmi mai „inteligenți”, diferiți de enumerare. Mulți jucători de șah celebri au încercat să dezvolte astfel de algoritmi, dar rezultatele nu au îndeplinit cerințele. De exemplu, Botvinnik M.M., fiind campion mondial și autor a numeroase lucrări despre teoria șahului, a petrecut peste 20 de ani creând un program de șah, dar programul nu s-a jucat niciodată.

Toți algoritmii de căutare pentru a găsi cea mai bună mișcare construiesc un arbore de joc și caută cea mai bună mișcare folosindu-l.

2. Sunt comuneconcepteteoriijocuri

2.1 Copacposibilpozitii

Să fie dat un arbore G orientat finit, mulțimea B a vârfurilor sale este compusă din două submulțimi disjunse B0 și B1 și se atribuie orice vârf p B care nu este începutul vreunei legături a acestui arbore. numar real Oe(p). Aceasta determină jocul a doi adversari cu informatii complete. Vârfurile arborelui orientat G aparținând submulțimii B0 se numesc poziții cu Alb de mutat, iar cele aparținând submulțimii B1 - poziții cu Negru de mutat; Legăturile acestui arbore se numesc mișcări albe sau negre, în funcție de care dintre subseturile B0 sau B1 îi aparține începutul. Dacă poziţia p B este asociată cu numărul Oe(p), se numeşte finală, iar Oe(p) se numeşte estimarea statică a acestei poziţii.

Un arbore direcționat G se numește arbore de joc.

Conform definiției, pentru orice poziție p B există o cale unică L(p0 > p1, p1 > p2, ..., pk > p) cu un început la rădăcina p0 a arborelui orientat Г și un sfârșit la poziția în cauză, o astfel de cale se numește lot care duce la poziția p.

Rădăcina p0 a arborelui jocului G este o poziție selectată. Aceasta este o poziție propusă programului, iar sarcina este de a găsi cea mai bună mișcare în ea. Pentru a face acest lucru, este suficient să determinați Oep0 și Oepi pentru toate pozițiile care sunt obținute de la p0 într-o singură mișcare. Determinarea estimării poziției inițiale p0 se realizează printr-o schemă de căutare exhaustivă, iar în teoria jocurilor acest algoritm se numește algoritm negamax.

Complexitatea arborelui jocului este calculată prin formula: w^d, unde w este numărul mediu de mișcări posibile și d este adâncimea arborelui.

Figura 1 - Arborele de poziții posibile

2.2 Principiuminimax

Acest algoritm este realizat folosind căutarea în profunzime. Adică, pentru fiecare vârf netraversat, este necesar să găsiți toate vârfurile adiacente netraversate și să repetați căutarea pentru ele. Ne întoarcem în vârful ultimei adâncimi și calculăm punctele câștigătoare în raport cu primul jucător. Apoi trecem de la nodul părinte la următorul nod copil (dacă există unul) și calculăm acolo punctele câștigătoare. Dacă numărul de noduri copil s-a încheiat, atunci căutăm minimul de puncte câștigătoare (dacă nivelul nodului părinte este impar) sau maximul (dacă este par). Nodul părinte deține punctul de câștig rezultat. Facem o căutare similară, dar ținând cont că nodul părinte este deja copil.

În frunzele copacului, punctele sunt calculate în raport cu primul jucător, adică. Se presupune că primul jucător caută să-și maximizeze profitul, iar al doilea jucător caută să minimizeze profitul primului jucător. Primul jucător câștigă dacă numărul de puncte din partea de sus a arborelui de nivel este mai mare decât zero.

Figura 2 - Căutare într-un arbore utilizând algoritmul minimax

Ca urmare, procesul folosit de program corespunde unor decizii alternante (calculator/uman), la fiecare tură calculatorul alege punctaj maxim. Soluția de întoarcere la rădăcina copacului este în mod clar cea mai bună alegere, presupunând că adversarul face și cele mai puternice mișcări în fiecare caz. Evaluarea statică se realizează numai pe nodurile de ultimul nivel (frunze de arbore) pentru poziţia calculatorului.

Acest algoritm efectuează o căutare completă a tuturor opțiunilor. Numărul de poziții luate în considerare va fi estimat ca W la puterea lui D, unde W este numărul aproximativ de mișcări într-o poziție, D este adâncimea de calcul. Pentru șah, W este aproximativ egal cu 40, ceea ce înseamnă că numărând pentru o adâncime de 4, trebuie să trecem prin 40^4 = 2560 mii de poziții, iar pentru o adâncime de 5 - 10240 mii de poziții.

Arborele de căutare crește exponențial. Astăzi, pe cele mai puternice procesoare cu cel mai optim cod, este posibil să se numere până la o adâncime de 6 într-o perioadă de timp estimată în mod realist. Aceasta este principala problemă în dezvoltarea algoritmilor de joc de șah, iar toate dezvoltările au ca scop reducerea combinațiilor luate în considerare.

Figura 3 prezintă o diagramă bloc a algoritmului minimax pentru selectarea celei mai bune mișcări; algoritmul prezentat returnează cea mai bună mișcare conform estimării obținute dintr-o analiză mai aprofundată. Diagrama bloc a algoritmului de căutare a estimărilor de profunzime este prezentată în Figura 4.

Figura 3 - Diagramă pentru alegerea celei mai bune mișcări

Figura 4 - Diagramă pentru căutarea estimărilor de adâncime mai întâi

Când apelăm algoritmul de căutare a unei estimări de adâncime mai întâi cu o adâncime necesară foarte mare, vom obține o estimare după o căutare completă a tuturor mișcărilor posibile.

2.3 Metodănegativmaxim(NegaMax)

În acest algoritm, evaluarea statică a poziției pentru una dintre părți este egală cu evaluarea statică a celeilalte părți cu semnul opus.

Figura 5 - Metoda maximă negativă

2.4 StaticnotapozitiiȘide bazăcerințeLaevaluarefuncții

O evaluare statică a unei poziții este o modalitate de exprimare obiectivă, cantitativă a sentimentului subiectiv pe care o persoană îl are atunci când privește o poziție, fără a analiza posibile modalități de dezvoltare a jocului. În programarea jocurilor, o estimare statică a poziției se numește funcția de calitate a poziției.

Dacă găsirea celei mai bune mișcări folosind un arbore de joc poate fi folosită cu succes egal pentru toate jocurile, atunci evaluarea statică a poziției este o parte specializată pentru un anumit joc. Specializarea sa determină stilul de joc al jucătorului artificial, factorii incluși în funcția de evaluare determină scopul căutării.

Compararea numărului cu poziția face posibil ca mașina să facă distincția între combinațiile bune și rele. Abilitatea de a distinge combinațiile bune de cele rele determină puterea unui jucător virtual. În jocurile cu două persoane, evaluarea este făcută de unul dintre jucători. Dacă funcția de notare returnează un scor bun pentru un jucător, ar trebui să returneze un scor rău pentru adversarul său. Această regulă este un criteriu de aplicabilitate a oricărei funcții de evaluare în algoritmii care implementează inteligența artificială.

Principala cerință pentru funcția de evaluare este simetria acesteia față de jucători, adică. trebuie îndeplinită o condiție – ceea ce este bun pentru un jucător este rău pentru altul. O funcție de punctare bună ar trebui să țină cont de principiile de bază ale strategiei de joc și să îndeplinească următoarele caracteristici:

* material - calculat direct ca diferență în numărul de figuri ale jucătorului, este posibil să adăugați coeficienți de ponderare pentru fiecare cifră specifică

* pozițional - arată calitatea plasării pieselor jucătorului

* dezvoltarea poziției - arată numărul de mișcări posibile ale jucătorului. Cu cât poziţia este mai bine dezvoltată, cu atât jucătorul are mai multe strategii posibile. Din acest motiv, este necesar să se controleze și să se reducă starea sa în inamic

* urmărirea sfârșitului jocului - în cazurile de câștig (capturarea regelui adversarului), ar trebui să dea scorul maxim, de obicei + infinit, în cazuri de pierdere (pierderea regelui), ar trebui să returneze scorul minim, de obicei - infinit

Pentru jocul de șah, este necesar să se țină cont de schimbarea aprecierii poziției, în funcție de stadiul jocului.

Funcția clasică de evaluare este o funcție a unora dintre caracteristicile de mai sus ale poziției de joc, adică funcția de evaluare este rezultatul total al evaluării poziției din diverse puncte de vedere.

Funcția de evaluare este diferită pentru toate jocurile, deoarece reflectă specificul jocului. Caracteristicile funcției de evaluare sunt selectate experimental.

Importanta caracteristicii selectate este esentiala. Importanța este determinată prin înmulțirea caracteristicii selectate cu coeficientul corespunzător. Acest coeficient trebuie să aibă o bază statistică.

Prin urmare, funcția de evaluare poate fi reprezentată astfel:

F(p) - functie de evaluare pentru pozitia p,

Coeficient de importanță pentru caracteristica i-a,

I-a caracteristică a poziţiei p.

2.5 Înscenaresarcini

În curs teza este necesar să se investigheze metodele și algoritmii existenți de implementare computerizată a jocului de șah, să se determine principalele avantaje și dezavantaje ale acestora pentru, pe baza cunoștințelor acumulate, să se selecteze un algoritm care să asigure cea mai bună funcționare a acestui sistem.

Pe baza rezultatelor tezei, este necesar să:

ь implementați algoritmii studiați în limbajul de programare C#

b implementați diferitele modificări ale acestora folosind module suplimentare

b efectuarea de experimente numerice pentru evaluarea calității modelelor dezvoltate, compararea modificărilor implementate, pentru a selecta cele mai bune

b dezvolta o interfață convenabilă și intuitivă

3. CercetatalgoritmiȘiadaosuri

3.1 Alpha Betatăiere

Taierea alfa-beta este un algoritm de căutare care încearcă să reducă numărul de noduri evaluate într-un arbore de căutare de către algoritmul minimax. Ideea principală este următoarea: dacă adversarul tău are un răspuns nefavorabil la una dintre mișcările tale, atunci este inutil să analizezi celelalte răspunsuri posibile ale lui la această mișcare, deoarece chiar dacă printre ele există altele mai favorabile pentru tine, adversarul nu va alege-le. Tăierea alfa-beta este o optimizare deoarece rezultatele algoritmului optimizat nu se modifică.

Figura 6 - Algoritmul de tăiere alfa-beta

Avantajul tăierii alfa-beta este de fapt că unele dintre ramurile subnivelurilor arborelui de căutare pot fi eliminate după ce cel puțin una dintre ramurile nivelului a fost luată în considerare complet. Deoarece tăierea are loc la fiecare nivel de cuibărit (cu excepția ultimului), efectul poate fi destul de semnificativ. Eficacitatea metodei este influențată semnificativ de sortarea preliminară a opțiunilor (fără enumerare sau cu enumerare la o adâncime mai mică) - la sortare, cu cât sunt luate în considerare mai multe opțiuni „bune” la început, cu atât mai multe ramuri „rele” pot fi tăiate. oprit fără o analiză exhaustivă. Căutarea minimax este pe primul loc în adâncime, așa că în orice moment este suficient să luăm în considerare nodurile de-a lungul unei singure căi în arbore.

Ideea cheie din spatele tăierii alpha-beta este să găsiți o mișcare care nu este neapărat cea mai bună, dar „suficient de bună” pentru a lua decizia corectă.

Parametrii alfa și beta sunt furnizați la intrarea acestui algoritm; ei se numesc fereastra de căutare. Acești parametri sunt responsabili pentru limitele de tăiere la primul nivel; pe măsură ce mergi mai adânc în arborele jocului, acești parametri se schimbă. Algoritmul alfa-beta cu parametrii alfa = + infinit și beta = - infinit (căutare cu forță brută cu o fereastră completă) oferă rezultatul exact același ca algoritmul negamax, adică căutare completă. Figura 7 prezintă o diagramă bloc a algoritmului alfa-beta pentru calcularea estimării de adâncime-prima poziţie.

Figura 7 - Diagramă alfa-beta pentru căutarea estimării în profunzime

3.1.1 Exemplustandardtăierea

Figura 8 - Exemplu de tăiere standard

Să ne uităm la un exemplu de limită standard alfa beta. În poziția A, alegem mutarea, prin urmare vom alege cea mai mare valoare din pozițiile B și C. Valoarea lui B a fost deja calculată - este 10. La calcularea poziției C, s-a dovedit că unul dintre noduri are un valoarea 5. În poziţia C, adversarul nostru va face mutarea, ceea ce înseamnă că va alege cea mai mică valoare. Rezultă de aici că valoarea poziției C va fi de la 5 și mai jos, prin urmare vom alege întotdeauna opțiunea B. Prin urmare, nu calculăm nodurile rămase C.

3 .1.2 Exempluîn profunzimetăierea

Figura 9 - Exemplu de tăiere adâncă

Să ne uităm la un exemplu de tăiere profundă. În poziţia A vom alege între mişcările din poziţia B şi C. Valoarea B=15. Începem calculul C. În poziția E, unul dintre noduri a dat valoarea 5. În poziția E, alegerea mișcării aparține adversarului, ceea ce înseamnă că valoarea finală a lui E va fi de la 5 și mai jos. Dacă valoarea lui C este egală cu E, atunci vom alege opțiunea B, deoarece este mai atractivă. Prin urmare, nu trebuie să cunoaștem valoarea exactă a poziției E, așa că toate celelalte ramuri care ies din ea sunt tăiate.

3 .2 Iterativpicaj(RepetatăAdâncirea)

Semnificația unui ventilator de căutare sau aprofundare iterativă este de a apela în mod repetat procedura de căutare la o adâncime fixă ​​cu adâncime în creștere până când se depășește limita de timp stabilită sau se atinge adâncimea maximă de căutare. Avantajul acestei metode este că nu trebuie să selectați în prealabil adâncimea de căutare; În plus, puteți utiliza întotdeauna rezultatul ultimei căutări finalizate. Valorile returnate de la fiecare căutare pot fi folosite pentru a ajusta fereastra de aspirație a următoarei căutări.

În general, tăierea alfa-beta este numită din vârful copacului pe interval (-?;+?). Cu toate acestea, folosind imersiunea iterativă o putem schimba.

Să presupunem că X este valoarea mișcării optime găsite la iterația anterioară, iar numărul Epsilon denotă diferența așteptată a rezultatelor dintre căutarea la adâncimea D-1 și adâncimea D. În continuare, numim pur și simplu tăiere alfa-beta din vârful arborelui cu intervalul așteptat: alphabeta(D, x-epsilon, x+epsilon).

1. Valoarea va fi returnată în intervalul (x-epsilon, x+epsilon) - aceasta este valoarea corectă, o putem folosi.

2. Valoarea va reveni în afara intervalului (x-epsilon, x+epsilon), este necesar să se repete calculul cu intervalul modificat.

Chiar dacă presupunem că metoda cutoff alfa-beta nu oferă niciun beneficiu, creșterea generală a timpului de analiză va fi de fapt relativ mică. Într-adevăr, dacă presupunem că numărul mediu de opțiuni la fiecare nivel este D, iar numărul de niveluri analizate este p, atunci căutarea iterativă la primul nivel, apoi la al doilea etc. la nivelul p, este echivalent (fără limite alfa-beta) cu vizualizarea pozițiilor D + + ...+.

Această sumă este egală, în timp ce numărul de poziții vizualizate într-o analiză convențională este egal. Raportul dintre aceste două numere pentru p mare este aproximativ egal și, prin urmare, aproape de 1 în cazurile în care D este suficient de mare

De asemenea, atunci când utilizați căutarea iterativă, puteți introduce controlul timpului, care va permite computerului să ofere o soluție satisfăcătoare în orice moment. Astfel, dacă timpul de gândire este limitat la 5 secunde, se va lua în considerare toate pozițiile până la nivelul 2, de exemplu, în 0,001 secunde, până la nivelul 3 în 0,01 secunde, până la nivelul 4 în 1 secundă și apoi, după pornire. analiza la nivelul 5 va fi obligată să se întrerupă din lipsă de timp. Cu toate acestea, computerul va avea deja o soluție destul de bună găsită la nivelul 4.

Ca rezultat, computerul este capabil să dea un răspuns într-un timp specificat (de exemplu, face 50 de mișcări în 2 ore). De asemenea, este evident că un program care acceptă o astfel de metodă va juca cu putere diferită pe diferite computere.

În ciuda faptului că unele ramuri ale copacului vor trebui verificate de mai multe ori, această metodă oferă un număr suficient de tăieturi.

3.3 Trieremișcări

Rezultatele tăierii alfa-beta sunt foarte influențate de ordinea în care sunt verificate mișcările. Să ne uităm la asta cu exemple:

În primul caz, vom efectua calculul prin sortarea mișcărilor „de la cel mai rău la cel mai bun”

Figura 10 - Limită alfa-beta cu mișcări „de la cel mai rău la cel mai bun”

După cum se poate vedea din exemplu, nici măcar o ramură a copacului nu a fost tăiată.

Acum haideți să sortăm mișcările „de la cel mai bun la cel mai rău”

Figura 11 - tăiere alfa-beta cu mișcări „de la cel mai bun la cel mai rău”

În circumstanțe optime, o căutare cu tăiere alfa-beta ar trebui să se uite la W^((D+1)/2) + W^(D/2) - 1 poziție. Aceasta este mult mai mică decât minimax.

Pentru a îmbunătăți eficiența tăierii alfa-beta, trebuie să vă gândiți la ce mișcări ar trebui explorate mai întâi. În aceste scopuri, se folosește așa-numita euristică ucigașă.

Ideea este că, dacă o mișcare a fost bună într-o parte a copacului, atunci dacă este posibil, merită să încerci să o verifici în altele (la aceeași adâncime). Pentru a face acest lucru, este introdusă o matrice în care sunt introduse câteva mișcări cele mai bune pentru fiecare adâncime; dacă există mișcări din acest tabel în poziția pentru adâncimea curentă, acestea sunt verificate mai întâi.

Pentru alte mișcări, algoritmul dă preferință mișcărilor cu verificări și capturi.

3 .4 Nega Scout(NegaScout)

NegaScout este un add-on pentru alpha beta. Acesta este un algoritm de căutare direcționată pentru a calcula valoarea minimax a unui nod.

NegaScout este cel mai popular algoritm de forță brută disponibil astăzi. Este extrem de simplu și oferă o oarecare accelerare (până la 50%) fără a introduce nicio eroare suplimentară în calcul. Se potrivește foarte bine cu atributele moderne ale programelor de șah - tabelele hash.

Acest algoritm are avantajul că nu va explora niciodată nodurile care pot fi tăiate de alfa-beta, dar unele ramuri pot fi examinate de mai multe ori.

Algoritmul NegaScout verifică primul nod cu o fereastră completă (Alpha, Beta), considerând că această opțiune este cea mai bună. Încearcă să taie următoarele noduri prin forță brută cu o fereastră zero, de exemplu. fereastra (Alpha, Alpha+1). Dacă rezultatul calculului îmbunătățește alfa, atunci aceasta înseamnă că 1 nod nu a fost cel mai bun și acest nod trebuie verificat cu fereastra completă, dar în loc de Alpha putem lua valoarea rezultată (Valoare, Beta). Codul pentru această metodă este prezentat mai jos:

public int NegaScout(Cell[,] CopyBoard, int Depth, int FinalDepth, int Alpha, int Beta, int PossibleMoves, bool IsMy)

int Valoare = 0, MaxValue = -1000, leight = 0;

Cell[,] Board = new Cell;

Punct[,] Mișcări = Punct nou;

Punct Move = Punct nou;

FindMoves(Muscări, ref leight, Board, true, true);

PossibleMoves = leight;

FindMoves(Muscări, ref leight, Board, false, true);

PossibleMoves += leight;

if ((Adancime == FinalDepth) || GameIsOver(Board, IsMy))

returnează Eval(Board, PossibleMoves);

return -1 * Eval(Board, PossibleMoves);

Găsiți Mișcări(Mișcări, referință, Board, HaveRequiredMove(Board, IsMy), IsMy);

int a = Alfa, b = Beta;

pentru (int i = 0; i< leight; i++)

CopyMove(Mutare, Mutare, i);

DoMove(Board, Move);

Valoare = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1*b, -1 * a, PossibleMoves, !IsMy);

dacă (Valoare>a && Valoare 0 && (adâncime

a = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1 * Beta, -1 * Value, PossibleMoves, !IsMy);

dacă (valoare > a)

CopyPosition(Board, CopyBoard);

După cum se poate vedea din descrierea de mai sus, pentru Nega Scout, deplasarea prin mișcări este o funcție importantă. Dacă aranjați toate mișcările „de la cel mai rău la cel mai bun”, atunci căutarea poate dura chiar mai mult decât minimax.

3 .5 Tabele de hash

3 .5 .1 Teorie

La șah, în timpul enumerarii, nu se obține un arbore de joc, ci un grafic - de foarte multe ori, după rearanjarea mutărilor, obținem aceeași poziție. Metoda de utilizare a tabelelor hash este de a stoca estimări ale pozițiilor deja luate în considerare. Pentru fiecare poziție, trebuie să-i stocați scorul (mai precis, scorul subarborelului de sub această poziție), adâncimea de căutare și cea mai bună mișcare. Acum, după ce am început să analizăm poziția, trebuie să aruncăm o privire - nu am întâlnit-o deja? Dacă nu te-am întâlnit, atunci facem ca înainte. Dacă l-am întâlnit, atunci ne uităm la profunzimea la care am analizat-o înainte. Dacă este același lucru de care avem nevoie acum, sau mai profund, atunci putem folosi vechea estimare și putem economisi timp. Dacă este mai puțin, atunci putem folosi totuși o parte din informații, și anume cea mai bună mișcare.

Cea mai bună mișcare pentru adâncimea N poate fi, de asemenea, cea mai bună mișcare pentru adâncimea N+1. Adică, pe lângă scopul său inițial, tabelul hash este util și pentru ordonarea mutărilor. Aprofundarea iterativă ajută, de asemenea, în mod neașteptat aici - când începem următoarea iterație, tabelul hash este umplut cu informații din cel precedent și până la un moment dat (până la adâncimea 1) toate pozițiile sunt pur și simplu acolo, cu cea mai bună mișcare la adâncimea N -1.

Un program care utilizează tabelele de aprofundare iterativă și hash va finaliza adesea toate iterațiile de la 1 la N de câteva ori mai repede decât dacă ar începe iterația N imediat, deoarece cu o probabilitate de 75% ea alege întotdeauna cea mai bună mișcare prima, iar cu o probabilitate de ~90% cea mai bună mutare este printre primele trei luate în considerare.

3 . 5 .2 Implementarea

Hashingul este una dintre cele mai puternice moduri de a îmbunătăți performanța computerului. Utilizarea tabelelor hash este instrumentul principal în programarea jocurilor de șah.

Tabelul hash este un tabel mare indexat, ale cărui celule stochează următoarele informații:

· 2 indici hash

· adâncimea de calcul pentru această mutare

· evaluarea acestei mutari

Alegerea algoritmului pentru calcularea indicelui hash al mișcării este cel mai important punct atunci când se utilizează algoritmi hash. Atunci când alegeți un algoritm pentru calcularea unui indice hash, trebuie luate în considerare două puncte importante:

Indicele ar trebui să reflecte cel mai bine informații unice de progres pentru a minimiza numărul de coliziuni

Indicele hash ar trebui să fie ușor de calculat

Un algoritm complex dă cea mai buna performanta numărul de coliziuni, dar sunt dificil de calculat și, prin urmare, ocupă mult timp CPU. Este necesar să se construiască un algoritm care să fie simplu de calculat, dar să aibă un număr minim de coliziuni.

Pentru calcularea indicelui au fost selectate operații cu niște măști generate aleatoriu.

Inițial, hash-ul măștii este umplut cu numere aleatorii. Pentru fiecare poziție se calculează 2 indici hash, primul este folosit pentru a căuta poziția în tabelul hash, al doilea este folosit pentru a verifica coliziunile.

Înainte de orice utilizare a informațiilor din tabelul hash, se verifică potrivirea celor doi indici hash; dacă nu se potrivesc, atunci a avut loc o coliziune și informația este ignorată.

Informațiile despre poziție ar trebui actualizate numai dacă adâncimea de redare curentă este mai mare decât ceea ce este deja stocat în tabelul hash.

Informațiile dintr-un hash pot fi de încredere numai dacă adâncimea din hash este mai mare decât adâncimea curentă de calcul.

3.6 Utilizarebibliotecidebutează

Algoritmul de utilizare a bibliotecilor de deschidere este utilizarea bazelor de date precalculate cu deschideri de joc, deoarece la începutul jocului cel mai mare număr posibile mișcări cu aceleași scoruri.

3 .7 Notapozitii

Când se dezvoltă un algoritm pentru estimarea poziției statice (funcția de calitate), există o incertitudine în alegerea între calitate și viteză. Funcțiile de evaluare calitativă bazate pe o bază statistică funcționează lent, dar oferă estimări foarte precise, unele chiar fără utilizarea forței brute, arătând înclinațiile inteligenței.

Funcțiile simple care țin cont de cele mai simple principii ale jocului funcționează mult mai rapid; nu oferă o evaluare precisă, dar permit o căutare profundă. Astfel, o evaluare precisă, dar lentă, poate fi inferioară uneia proaste, dar rapide.

Calitatea estimării este determinată de cantitatea de cunoștințe despre joc pe baza cărora se compară poziția cu numărul. Calitatea evaluării este direct proporțională cu viteza de lucru și cu cantitatea de cunoștințe. După cum arată 40 de ani de practică în crearea de programe de inteligență artificială, cantitatea de cunoștințe a unei funcții de evaluare este invers proporțională cu viteza acesteia.

Grafic, această dependență este descrisă în figură ca o familie de hiperbole.

Figura 12 - Exemplu de tăiere adâncă

Atunci când se dezvoltă o funcție de evaluare pentru șah, ar trebui să se țină cont de faptul că în șah estimările tuturor parametrilor depind de stadiul jocului.

Șahul este de obicei împărțit în etape: deschiderea - deschiderea jocului, jocul de mijloc - mijlocul jocului, finalul jocului - stadiu final. Pentru algoritm s-a decis împărțirea jocurilor în 3 etape în funcție de numărul de piese rămase pe tablă pentru jucătorul de pe computer. Inițial, jucătorii au 16 piese pe tablă. Tabelul arată dependența etapei jocului de numărul de piese rămase:

Tabelul 1 - Etapele jocului

3 . 7 .1 Materialnota

Avantajul material al unuia dintre jucători este considerat cel mai important parametru în teoria șahului, prin urmare evaluarea materială contribuie cea mai mare influență pentru evaluarea de ansamblu a postului. Scorul materialului se calculează ca suma coeficienților de ponderare a tuturor pieselor de pe tablă. Regele nu este inclus în scorul material, deoarece dacă regele este pierdut, jucătorul pierde automat. Estimarea ponderilor cifrelor este sarcina principală atunci când se construiește o funcție de evaluare. Pentru a determina ponderile cifrelor, s-a decis utilizarea unui algoritm de auto-învățare bazat pe un algoritm genetic. Greutățile pieselor nu depind de stadiul jocului. Un algoritm genetic este un algoritm de căutare euristică utilizat pentru a rezolva probleme de optimizare și modelare prin selectarea aleatorie, combinarea și variarea parametrilor doriti folosind mecanisme care amintesc de evoluția biologică, propuse pentru prima dată de Holland (1975).

3 . 7 . 2 Descrieremuncăgeneticalgoritm

Problema originală este codificată în așa fel încât soluția sa poate fi reprezentată ca un vector („cromozom”). Un anumit număr de vectori inițiali („populația inițială”) sunt creați aleatoriu. Acestea sunt evaluate folosind o „funcție de fitness”, prin care fiecărui vector i se atribuie o valoare specifică („fitness”), care determină probabilitatea de supraviețuire a organismului reprezentat de acel vector.

După aceasta, folosind valorile de fitness obținute, sunt selectați vectorii (selectarea) permisi pentru „încrucișare”. Acești vectori sunt aplicați „operatori genetici” (de obicei „încrucișare” și „mutație”), creând astfel următoarea „generație”. Sunt evaluați și indivizii din generația următoare, apoi se face selecția, se aplică operatori genetici etc.

Aceasta simulează un „proces evolutiv” care continuă timp de mai multe cicluri de viață (generații) până când criteriul de oprire al algoritmului este îndeplinit. Un astfel de criteriu ar putea fi:

Găsirea soluției optime;

Epuizarea numărului de generații alocat evoluției;

Epuizarea timpului alocat evoluției.

Algoritmii genetici servesc în primul rând pentru a găsi soluții în spații de căutare foarte mari și complexe.

Astfel, activitatea algoritmului genetic poate fi reprezentată în următoarea diagramă:

Figura 13 - Exemplu de tăiere adâncă

3 . 7 . 3 Etapemuncăgeneticalgoritm

Crearea unei populații inițiale - o populație inițială este creată aleatoriu; chiar dacă se dovedește a fi complet necompetitiv, algoritmul genetic îl va transforma în continuare rapid într-o populație viabilă. Astfel, la primul pas, nu trebuie să încercați prea mult să faceți indivizi prea adaptați; este suficient să corespundă formatului indivizilor din populație.

Selecția (selecția) - din întreaga populație este selectată o anumită proporție care va rămâne „în viață” în această etapă de evoluție. Încrucișarea (reproducția) - pentru a produce un descendent este nevoie de mai mulți părinți; De obicei, desigur, sunt necesare exact două. Reproducerea este definită diferit în diferiți algoritmi - depinde, desigur, de prezentarea datelor. Principala cerință pentru reproducere este ca descendenții sau descendenții să poată moșteni trăsăturile ambilor părinți „amestecându-le” într-un mod rezonabil de inteligent.

Mutațiile sunt modificări stocastice în parte ale indivizilor (cromozomi).

3 . 7 . 4 DefinițiecântarecifreCucu ajutorgeneticalgoritm

Cromozomul algoritmului genetic include ponderi piese de șah, cu excepția regelui.

Pentru a seta populația inițială, valorile cromozomilor sunt stabilite aleatoriu în interval, cu excepția greutăților pionului și reginei, valorile greutăților lor sunt fixe, pion - 100, damă - 1000.

Selectarea turneului este folosită pentru selecție. Aleatoriu 2 cromozomi joacă între ei, până la patru victorii, mergând primul pe rând. Câștigătorul duelului rămâne, învinsul este scos din populație.

La traversare se folosește metoda de trecere într-un singur punct.

2 părinți sunt luați la întâmplare, numărul cu care se va diviza cromozomul este selectat aleatoriu, diagrama este prezentată în Figura nr. 14. Ca rezultat, fiecare descendent va avea trăsături atât de la primul, cât și de la al doilea părinte.

Figura 14 - Exemplu de tăiere adâncă

Mutațiile sunt efectuate după cum urmează: cromozomii sunt selectați cu o anumită probabilitate, iar fiecare „genă” se schimbă la un număr aleatoriu în intervalul [-50; 50], cu excepția valorii estimărilor statice ale matcii și pionului.

Pentru valorile finale, greutățile rezultate sunt împărțite la 100.

3 . 7 . 5 Totalnota

Atunci când se evaluează o poziție, se acordă atenție celor 8 componente:

1. Forțele materiale ale rivalilor

2. Numărul câmpurilor aflate în luptă

3. Ocuparea câmpurilor cheie

4. Pioni trecuți

5. Pioni dublați

6. Rocarea

7. Avansarea pionului

8. Lanțuri de pioni [*1]

Numărul câmpurilor aflate în luptă este calculat la adâncimea copacului 2, din cauza costurilor mari de producție. Pentru fiecare pătrat care este lovit de o piesă de computer, se adaugă 1 punct la scorul de poziție; pentru câmpurile care sunt lovite de piesele jucătorului, se scade un punct. Valoarea rezultată este transmisă în partea de jos a arborelui ca parametru. Tot la adâncimea 2 se calculează puncte pentru lanțuri de pioni, pioni trecuți și dublați. Pentru prezența pionilor care se ating la stânga sau la dreapta, partea primește 1 punct. Un pion este considerat trecut dacă nu există pioni ai adversarului în dosarul său, precum și pe cei adiacente acestuia, care să-l împiedice să treacă până la capăt. Pioni dubli - 2 pioni de aceeași culoare stând pe același fișier. Pentru prezența pionilor dubli din lateral se scad 4 puncte, pentru prezența fiecărui pion trecut se adaugă 5 puncte. Există pătrate cheie în șah:

Figura 15 - Câmpuri cheie

Pentru completarea fiecăreia dintre ele se acordă încă 4 puncte.

Deoarece După rocare, regele este într-o poziție foarte stabilă; pentru o rocare perfectă, partea primește 3 puncte.

Cu cât un pion este mai aproape de ultimul său rang, cu atât este mai aproape de promovare. Pentru fiecare pătrat mutat înainte, la valoarea pionului se adaugă 1.

După calcularea numărului de puncte pentru ambele părți, se obține un scor final de poziție prin scăderea punctelor jucătorului din punctele adversarului computerului.

4 . Dezvoltareprogrames

4 .1 CerințeLaşahalgoritm

Atunci când dezvoltați un model de modul software pentru jocul de șah, ar trebui să luați în considerare următorii parametri:

* algoritmii de șah sunt foarte pretențioși în ceea ce privește performanța, iar puterea jocului programului depinde direct de performanța programului

* modulele software ar trebui să fie ușor de dezvoltat și testat

* interfața cu utilizatorul ar trebui să fie ușoară, ușor personalizabilă și scalabilă

4 .2 felurişahalgoritmi

Cel mai programe moderne poate fi împărțit în 3 categorii:

* Prima categorie este Căutători rapidi - ideea este că simplificând până la limită funcția de evaluare și optimizând cu atenție întregul program în ansamblu (ceea ce de obicei se realizează prin scrierea unui program în assembler), puteți crește numărul de poziții considerat de program (nps - noduri pe secundă) la un număr astronomic, de exemplu, până la 150-200k nps la P/200. Adică, programul cheltuiește aproximativ una până la două mii de comenzi de mașină pentru fiecare poziție. Aceasta include efectuarea unei mișcări dintr-o poziție anterioară în aceasta, evaluarea poziției, generarea de mișcări dintr-o poziție dată, logica de control etc. Au mai rămas doar firimituri pentru funcția de evaluare în sine - aproximativ o sută de comenzi. Programele se dovedesc a fi nebun de rapide și funcționează excelent în poziții tactice complexe și, de asemenea, rezolvă perfect problemele de combinație, dar au un joc pozițional slab

* A doua categorie este programele bazate pe cunoștințe. Aici toate eforturile sunt dedicate scrierii unei funcții complexe de evaluare. Se ia în considerare interacțiunea pieselor între ele, acoperirea regelui, controlul pozițiilor și aproape faza lunii. În termeni nps, programul rulează de 10-100 de ori mai lent decât căutările rapide, dar joacă șah pozițional bun. Mai exact, acest șah este bun doar atunci când nu există tactici profunde pe tablă, sau controlul timpului este astfel încât programul să aibă suficient timp pentru a calcula aceste tactici.

4 .3 ControltimpVşahalgoritmi

Cel mai important parametru în construirea unui algoritm de inteligență artificială pentru un adversar de șah este controlul timpului de mișcare. Puterea jocului unui program de șah depinde de controlul timpului. Înainte ca computerul să înceapă să „se gândească” la o mișcare, trebuie calculat timpul disponibil pentru computer.

Când se calculează timpul disponibil pentru o mutare, trebuie să pornești de la doi parametri:

* algoritmul pentru găsirea celei mai bune mișcări se bazează pe căutarea prin toate mișcările posibile până la o anumită adâncime și, prin urmare, depinde direct de timpul petrecut căutând. Cu cât folosim mai mult timp, cu atât computerul este mai puternic

* timpul de așteptare pentru un răspuns de la un adversar al computerului nu trebuie să fie prea lung. Ca bază, puteți lua regulile internaționale ale șahului, în care există mai multe tipuri de jocuri: blitz - 15 minute pe joc, rapid - 60 de minute pe joc, clasic - mai mult de 60 de minute pe joc.

Pe baza parametrilor solicitați, s-a decis să se calculeze timpul disponibil pentru mișcări înainte de începerea fiecărei mișcări de calculator folosind următoarea formulă: unde: timp - timp per mutare; full_game_time - timpul total de joc; avg_moves - numărul mediu de mișcări ale jucătorului într-un joc; collect_time - timp acumulat suplimentar; D - o ușoară reducere a timpului necesar pentru calcule suplimentare. Parametrii timpului total al jocului și numărul mediu de mișcări ale jucătorului în joc sunt doi parametri externi principali, prin modificarea cărora puteți modifica puterea jocului. Conform statisticilor portalului de șah TheChess.ru, numărul mediu de mișcări ale jucătorului pe joc este de 30, așa că s-a decis ca numărul mediu de mișcări ale jucătorului într-un joc să fie de 30. Astfel, timpul total al jocului este pus din exterior. La dezvoltarea unui algoritm pentru comportamentul unui adversar al computerului (inteligență artificială), au fost utilizați următorii algoritmi:

* algoritm de căutare iterativă, cu control al timpului

* algoritm de tăiere alfa-beta și Nega-Scout

* deschiderea bibliotecilor

* tabele de hash

* euristica ucigașului și istoriei au fost folosite pentru a sorta mișcările.

4 .4 Dezvoltatprogram

Toți algoritmii și completările de mai sus au fost implementați în program în limbajul de programare C#.

Capturile de ecran ale programului sunt prezentate mai jos:

Figura 16 - Selectarea culorilor

Figura 17 - Captură de ecran a programului

Figura 18 - Captură de ecran a programului

Când treceți mouse-ul peste o figură de culoarea sa, aceasta este evidențiată în alb. Când selectați o piesă de mutat, culoarea câmpului său devine portocaliu și toate celulele în care se poate muta piesa sunt evidențiate în alb. Când treceți mouse-ul peste o astfel de celulă, culoarea acesteia devine și portocalie.

În timpul jocului, mișcările finalizate sunt afișate în tabelul din stânga, iar jucătorul poate salva istoricul într-un fișier separat.

4 .5 Bazaciclucăutarecel mai bunprogres

Sarcina principală a ciclului de bază de căutare a celei mai bune mișcări este de a găsi și executa cea mai bună mișcare a adversarului computerului. Bucla folosește biblioteci de debut și căutare iterativă cu control al timpului. Figura 12 arată procesul de găsire a celei mai bune mișcări:

Figura 19 - Ciclul de bază al căutării celei mai bune mișcări

4 .6 Căutarecel mai bunprogresprimulnivel

Sarcina principală a algoritmului pentru găsirea celei mai bune mișcări de la primul nivel (răspunsul adversarului) este de a găsi cea mai bună mișcare a adversarului la primul nivel. Algoritmul se bazează pe algoritmul NegaScout, care utilizează estimarea depth-first pentru a determina estimarea mișcării curente. Figura 13 arată procesul algoritmului:

Figura 20 - Căutați cea mai bună mișcare de la primul nivel

4 .7 Găsindadâncevaluăriprogres

Sarcina principală de a găsi o estimare profundă este de a găsi o estimare a mișcării curente folosind algoritmul NegaScout, euristica de mișcare zero, date din tabelul hash și o estimare statică a poziției. Figura 14 prezintă procesul de calculare a estimării cursei de adâncime:

Figura 21 - Găsirea unei estimări profunde a mișcării

4.8 AlțiimodeleȘidiagrame

Modelul matematic al programului arată astfel:

Figura 22 - Model matematic

Din clasa abstractă Figura, sunt create 7 clase descendente care descriu acțiunile și proprietățile figurilor. Există, de asemenea, o clasă Empty, care indică faptul că celula este goală. Tabloul este o matrice de 64 de elemente Figure, fiecare dintre acestea putând deveni oricare dintre clasele descendente. O mutare este reprezentată în computer ca 4 numere - coordonatele (de la 1 la 8) ale punctului de început al mișcării și coordonatele punctului final al mișcării. Mai jos este diagrama de stare a programului:

Figura 23 - Diagrama de stare

5 . ExperimentalnotacalitateRrealizăridatealgoritmi

Algoritmii implementați au fost supuși unei analize comparative pentru a identifica configurația optimă din punct de vedere al vitezei și calității execuției. Experimentul a implicat o serie de turnee între fiecare pereche de implementări diferite.

5 .1 NotamuncăAlpha Betatăierea

Cu ajutorul acestui experiment, a fost necesar să se afle dacă a fost posibil să se realizeze o reducere a factorului de ramificare și, ca urmare, o îmbunătățire a vitezei algoritmului fără a pierde calitatea luării deciziilor cu privire la mutare. fiind facut.

Pentru a evalua calitatea algoritmului final, acest algoritm de căutare a fost comparat experimental cu o căutare folosind principiul minimax.

Tabelele prezintă coeficienți care demonstrează raportul dintre numărul de poziții căutate pentru algoritmi, precum și raportul dintre timpul alocat pentru efectuarea unei scanări date.

Tabelul 1 - Comparația performanțelor algoritmului de cutoff alfa-beta cu algoritmul minimax.

Rezultatele experimentale arată că tăierea alfa-beta este mult mai bună decât simpla căutare minimax.

5 .2 NotamuncăiterativscufundăriȘitrieremișcări

Pentru a evalua calitatea algoritmului, acest algoritm de căutare a fost comparat experimental cu tăierea Alpha-Beta și doar tăierea Alpha-Beta.

Documente similare

Descrierea regulilor jocului „Sea Battle”. Caracteristicile computerelor moderne și inteligența artificială. Crearea unei diagrame bloc generale a programului, aspectul acestuia. Variabile, proceduri și funcții necesare. Caracteristicile obiectelor utilizate în aplicație.

lucrare curs, adăugată 11.05.2012


Dezvoltarea, pe baza jocului „Puncte”, a unei abordări a programării „inteligenței artificiale” în jocurile de poziție și a posibilității utilizării acestei abordări pentru rezolvarea problemelor din domeniul economiei, managementului și altor domenii ale științei. Model de situație de joc.

teză, adăugată 21.07.2013


Diagrama structurală a unui modul software. Dezvoltarea unei diagrame a modulelor software și a unei interfețe cu utilizatorul. Implementarea unui modul software: cod program; descrierea operatorilor și funcțiilor utilizate. Vedere a unui formular de utilizator cu o matrice completată.

lucrare de curs, adăugată 09/01/2010


Studiu reguli generale jocuri de dame, instrucțiuni pentru utilizator și programator. Caracteristicile principalelor algoritmi care îndeplinesc sarcini din clasa Life Widget. Evaluarea mișcărilor computerului și omului. Construirea unui arbore de căutare pentru cea mai bună mișcare bazată pe evaluarea funcției.

test, adaugat 20.12.2012


Principalele etape de dezvoltare, principii de testare și depanare a modulului software „VFS”. Caracteristici ale designului în limbajul UML. Metode „Brute Force” și aplicarea lor în depanarea programelor. Factori nocivi prezenți la locul de muncă al programatorului.

teză, adăugată 03.07.2012


Analiza modelelor și metodelor de implementare a jocurilor intelectuale într-un sistem om-robot. Mediul de dezvoltare a coregrafiei. Algoritmi pentru modulul de recunoaștere, prelucrarea datelor, funcțiile modulului de joc. Testarea pachetului software, corectarea și editarea erorilor.

teză, adăugată 08.12.2017


Esența și problemele definirii inteligenței artificiale, principalele sarcini și funcții. Probleme filozofice de creare a inteligenței artificiale și de asigurare a siguranței umane atunci când se lucrează cu un robot. Alegerea unei căi pentru a crea inteligență artificială.

test, adaugat 12.07.2009


Program de joc „dame” pentru un joc între o persoană și un computer. Dezvoltarea algoritmilor, linia istorică de dezvoltare a problemelor. Diverse abordări ale sistemelor de construcție. Lista abreviată a programului și descrierea algoritmului. Componente ale inteligenței artificiale.

lucrare de curs, adăugată 26.03.2009


Construcție și analiză model matematic jocuri. Determinarea probabilității de detectare a navelor în toate locațiile posibile și diverse sisteme căutare. Dezvoltarea algoritmilor pentru inteligența artificială. Structura programului și componentele sale.

lucrare de curs, adăugată 22.12.2012


Conceptul de inteligență artificială ca abilitatea sistemelor automate de a prelua funcțiile individuale ale inteligenței umane. Sisteme experte în domeniul medicinei. Diverse abordări ale construirii sistemelor de inteligență artificială. Crearea rețelelor neuronale.

În urmă cu un an, programul AlphaGo l-a învins senzațional pe cel mai puternic jucător Go din lume, iar acum inteligența artificială AlphaZero a învins cel mai bine cotat motor de șah.

Stockfish, pe care majoritatea jucătorilor îl folosesc pentru antrenamentul acasă și câștigător al Campionatului TCEC 2016 și al Campionatului Software Chess.com 2017, a fost în mod clar mai slab. Într-un meci de 100 de jocuri, AlphaZero a câștigat 28 de victorii cu 72 de egaluri și nu a pierdut niciodată.

Apropo, AlphaZero a petrecut doar patru ore „învățând” șahul. Îmi pare rău, oameni buni, dar nu puteți ține pasul cu el.

Așa este - programatorii AlphaZero, dezvoltat de DeepMind, o divizie a Google, l-au creat pe baza " învățare automată”, mai precis, „învățare prin întărire”. Mai simplu spus, AlphaZero nu a studiat șahul în sensul tradițional. El nu are nici o carte de deschidere, nici mese finale, nici algoritmi complexi pentru evaluarea puterii pionilor centrali și de flancare.

Lucrarea lui poate fi comparată cu un robot care poate folosi mii de piese de schimb, dar nu cunoaște principiul motorului cu ardere internă - trece prin posibile combinații până când construiește un Ferrari, iar pentru asta durează mai puțin timp decât este necesar Urmărește trilogia Stăpânul Inelelor. În patru ore, programul a jucat multe jocuri cu sine, devenind propriul profesor.

Până acum, echipa de programare a rămas tăcută. Ei nu au comentat pentru Chess.com, invocând că raportul este „încă în curs de revizuire”, dar puteți citi textul integral aici. Echipa de cercetare include Demis Hassabis, un candidat la master din Anglia și co-fondator al DeepMind (achiziționat de Google în 2014). Hassabis, care a concurat în turneul tandem ProBiz la deschiderea London Chess Classic, este în prezent la conferința Neural Information Processing Systems din California, co-autorând o lucrare pe o altă temă.

Dar un jucător de șah cu o vastă experiență personală jucând împotriva computerelor de șah și-a împărtășit de bunăvoie opiniile cu Chess.com. GM Garry Kasparov nu este surprins că DeepMind a trecut de la Go la șah.

„Aceasta este o realizare remarcabilă, deși era de așteptat după AlphaGo”, a spus el pentru Chess.com. „Se apropie de abordarea umanoidă de tip B a șahului pe care clona Shannon și Alan Turing au visat să o înlocuiască cu forța brută.”

Ca o persoană, AlphaZero consideră mai puține poziții decât predecesorii săi. Raportul precizează că estimează „doar” 80 de mii de poziții pe secundă, față de cele 70 de milioane pe secundă ale lui Stockfish.

GM Peter-Heine Nielsen, de mult timp al doilea campion mondial GM Magnus Carlsen, și-a dezvăluit pasiunea, care îl apropie de președintele FIDE: extratereștrii. El a declarat pentru Chess.com: „După ce am citit raportul și, mai ales, am urmărit jocurile, m-am gândit: „Întotdeauna m-am întrebat cum ar fi dacă o specie mai inteligentă ar ateriza pe planeta noastră și ne-ar arăta abilitățile lor de șah. Cred că acum știu cum este.”

Am aflat și despre importanța avantajului de performanță, de macar, pentru inteligența artificială. 25 din cele 28 de victorii ale AlphaZero au fost câștigate cu alb (deși rezultatul de +3=47-0 cu negru împotriva Stockfish, al cărui rating depășește 3400, nu este nici el rău).

Raportul arată, de asemenea, cât de des a selectat motorul anumite deschideri pe măsură ce se antrena. Ne pare rău, fani ai Apărării Indiene a Regelui, dar sunteți în nefavoare. Interesul pentru Apărarea Franceză a scăzut și el în timp, dar dorința de a juca Queen's Gambit și, mai ales, Deschiderea Engleză a crescut.

Ce ai face dacă ai fi o creatură neobosită care tocmai ar fi stăpânit un joc cu 1.400 de ani de istorie? Să luăm încă una. După meciul cu Stockfish, programul AlphaZero a petrecut doar două ore pe „antrenament” și l-a învins pe „Elmo”, cel mai puternic dintre motoarele computerizate shogi.

Utilizarea acestui program inovator de auto-învățare nu se limitează, desigur, la jocuri.

„Întotdeauna s-a crezut că în șah sunt necesare prea multe cunoștințe empirice de la o mașină pentru ca aceasta să poată juca puternic de la zero, fără a folosi deloc cunoștințele umane”, a spus Kasparov. „Desigur, voi fi interesat să văd ce putem învăța despre șah cu AlphaZero, ceea ce deschide o promisiune enormă pentru învățarea automată în general - mașinile pot găsi modele pe care oamenii nu le pot găsi, cu implicații care se extind în mod clar dincolo de șah și alte jocuri - capacitatea unei mașini de a descoperi și de a depăși cunoștințele. a sistemelor închise complexe pe care omenirea le-a acumulat de-a lungul secolelor, „Este un instrument care schimbă lumea”.

Jurnaliștii Chess.com au întrebat opt ​​din zece participanți la turneul de la Londra despre părerile lor despre meciul din program. Un videoclip al interviului va fi postat ulterior pe site.

GM Hikaru Nakamura a criticat cel mai dur condițiile meciului. În prezent există o dezbatere aprinsă despre puterea de calcul a adversarilor, dar Nakamura crede că altceva era mai important.

Marele maestru american a numit meciul „nedrept”, arătând că motorul Stockfish trebuie să folosească cartea de deschidere pentru a funcționa optim. Nakamura nu crede că Stockfish ar fi câștigat meciul cu ajutorul ei, dar avantajul ar fi fost mult mai mic.

„Sunt sigur că însuși Domnul Dumnezeu nu ar fi marcat 75 la sută din puncte împotriva Stockfish cu alb fără nici un handicap”, a comentat el despre rezultatul AlphaZero cu alb: 25 de victorii și 25 de egaluri.

GM Larry Kaufman, consultant principal de șah pentru motorul Komodo, speră să vadă cât de bine funcționează noul program pe computerele personale fără a utiliza puterea de calcul a Google. De asemenea, a repetat obiecțiile lui Nakamura că Stockfish se juca fără cunoștințele sale obișnuite de deschidere.

„Desigur, este aproape de necrezut”, a spus el, „da, am auzit despre realizările AlphaGo Zero în jocul Go și mă așteptam să se întâmple așa ceva, având în vedere că echipa de dezvoltare include șahista Demis Hassabis. Cu toate acestea, nu este clar dacă programul AlphaZero va putea juca șah pe un computer obișnuit și cât de bine va face acest lucru. Dominanța modernă a motoarelor de șah care folosesc funcția minimax poate să se apropie de sfârșit, dar este prea devreme pentru a declara acest lucru. Merită să subliniem că în timpul antrenamentului, AlphaZero și-a creat de facto propria carte de deschidere, așa că ar fi mai corect să o folosești împotriva unui motor cu o carte bună de deschidere.”

Lăsând la o parte condițiile de meci, Nielsen se întreabă ce alte domenii ar putea aplica. acest tip Instruire.

„[Aceasta este] inteligență artificială modernă”, a spus marele maestru. „Se trece de la ceva de genul șahului la probleme demne Premiile Nobelși încă mai mult. Cred că am fost norocoși că au decis să petreacă patru ore jucând șah, dar consecințele acestei descoperiri sunt mult mai semnificative.”

Istoria dezvoltării automatizării și tehnologia calculatoarelor ciudat legat de șah. În secolul al XVIII-lea Mașinile de șah „gânditoare” serveau pentru trucuri și farse. Prima mașină cu inteligență artificială reală, creată în Spania la începutul secolului al XX-lea, a fost capabilă să facă șah-mat un jucător de șah care se juca cu un rege cu un rege și o turnă. Aparent, nu este o coincidență că una dintre primele sarcini cu adevărat intelectuale atribuite programatorilor în zorii tehnologiei informatice a fost să joace șah. Unul dintre cei care au creat primele programe de șah, doctor în științe tehnice, profesorul Vladimir Lvovich Arlazarov, vorbește despre programele de șah și despre legătura acestui joc străvechi cu dezvoltarea tehnologiilor de inteligență artificială.

– Vladimir Lvovich, cum ai venit la ideea că un computer poate rezolva probleme intelectuale?

– Când au aflat că calculatoarele nu pot doar să calculeze, așa cum a fost inventat de la bun început, că în spatele operațiilor aritmetice se află o acțiune logică care nu numai că îndeplinește funcții auxiliare în activitățile programelor de calculator, ci și cu ajutorul căreia este posibil să rezolvați probleme independente, a devenit Este clar: merită să încercați să puneți sarcini intelectuale pe computer. Undeva, de la sfârșitul anilor 40 până la sfârșitul anilor 50, acest lucru s-a discutat activ, mai mult, s-au pus întrebări semi-filosofice: poate computerele vor fi mai inteligente decât oamenii? Si apoi, ce? Și cu toată seriozitatea. În zilele noastre nu se pun astfel de întrebări; la urma urmei, au trecut 40 de ani. Apoi, în zorii tehnologiei informatice, ne-am dat seama doar ce pot face mașinile în principiu. Ne-am dat seama că creierul uman este un dispozitiv similar cu un computer și de o mie, un milion de ori mai puternic, dar este fundamental ușor diferit. A devenit clar că, cel puțin, majoritatea problemelor raționale pe care le rezolvă o persoană pot fi atribuite unei mașini. Prin urmare, puteți încerca să scrieți programe care rezolvă aceste probleme. Una, două, mii... la urma urmei, nici o persoană nu rezolvă un număr infinit de probleme. Și este posibil, ca să spunem așa, să programăm toată activitatea intelectuală a unei persoane.

– De ce ai decis să apelezi la joc?

– După cum am spus deja, s-a discutat pe larg dacă o mașină poate gândi. Cu toate acestea, este destul de clar că dacă despre care vorbim despre programatori, despre oameni care se ocupă nu cu filozofie, ci cu un computer real, atunci întrebarea nu este dacă o mașină poate face în mod fundamental ceva, ci în căutarea exemplelor în care mașinile rezolvă problemele intelectuale și cele care sunt accesibile și omul în activitatea sa intelectuală. Linia aici, desigur, nu este clară. Dar este clar că, dacă o persoană înmulțește numere de 20 de cifre, atunci nu are de-a face cu o sarcină profund intelectuală, deoarece pentru a o îndeplini este foarte ușor să găsești un algoritm banal care este cunoscut de fiecare școlar. Dar acele sarcini în care este absolut clar că o persoană nu are niciun algoritm a priori, dar totuși le rezolvă bine, le vom numi intelectuale. Primii concurenți pentru astfel de sarcini sunt jocurile, din simplul motiv că măcar regulile sunt clar enunțate. Sarcina este extrem de dificilă, dar regulile jocului sunt ușor de formulat și, astfel, funcțiile mașinii sunt ușor de determinat. Pe de altă parte, șahul este pentru oameni sarcină dificilă, despre care cumva nu s-a mai discutat și nu se discută acum.

– De ce ai ales șahul ca joc? Poate o tradiție?

– De ce doar șah? Am încercat jocuri de fond și alte jocuri. Dar șahul are multe avantaje față de alte jocuri. Dacă în jocurile simple o mașină bate o persoană, atunci acest lucru nu surprinde pe nimeni. Șahul este un joc dificil, iar o victorie pe computer este semnificativă. Apoi, în șah, spre deosebire de o serie de alte jocuri, există multe criterii de calitate diferențiabile, adică puteți determina: o mașină joacă bine, o mașină joacă mai bine, mai bine, mai bine. În multe alte jocuri, astfel de gradații sunt foarte greu de stabilit. În unele dintre ele, mașina fie este învățată să joace absolut exact și, prin urmare, își pierde imediat orice interes pentru joc, fie joacă extrem de prost. Și în șah, nu abstract, ci, ca să spunem așa, stăpânit, există atât de multe niveluri încât cu ajutorul lor poți determina clasa jocului unei mașini.

– Deci, este clar de ce șahul a fost una dintre primele și cele mai importante sarcini ale inteligenței artificiale. Ce metode au fost folosite pentru a o rezolva?

– Încă de la început am însușit treptat metodologia de rezolvare a problemei unui joc de șah. În principiu, șahul este un joc finit și se poate dovedi cu rigoare matematică că în orice poziție, în abstract, există cea mai bună mișcare pentru fiecare adversar și, prin urmare, un fel de rezultat. Prin urmare, este necesar să descriem un algoritm în care acest joc poate fi calculat până la finalizare. Singurul dezavantaj al unui astfel de algoritm este că necesită mult timp. Și nu suntem mai aproape de ordinele de timp necesare pentru a calcula, să zicem, șahul până la final din poziția de start. În ultimii cincizeci de ani, sarcina a rămas infinit de complexă în termeni de timp. Ei bine, infinitul minus zece este tot infinit. Dar dacă ai nevoie de timp, să zicem, de la 10 la a 100-a putere a anilor, și accelerezi mașina, să zicem, de 100 de ori și obții de la 10 la a 98-a putere a anilor, atunci este puțin probabil să fii mai ușor. Prin urmare, algoritmul principal este exhaustiv, banal: dacă fac asta, atunci inamicul are atât de multe posibilități. Opțiunile cresc exponențial și formează lanțuri. Dar numărul de poziții este în general finit și nu sunt atât de multe pe fiecare lanț. Lanțurile sunt combinate în copaci, care din nou nu sunt infiniti. Adevărat, ele cresc exponențial, iar numărul de lanțuri crește. Așadar, apare o întrebare importantă: este necesară o căutare completă, până la capăt - tuturor șahmat, impas, triple repetiții și alte finaluri ale jocului conform regulilor de șah? La urma urmei, dacă algoritmul duce la poziții care nu sunt necesare pe acest arbore, atunci poate că întregul arbore nu trebuie luat în considerare. Rețineți că într-o dispoziție în care Albul se împerechează într-o singură mișcare, puteți construi același copac infinit, dar nu trebuie să îl luați în considerare, este suficient să găsiți această singură mișcare. Poate aceeași situație se aplică șahului în general? În general, algoritmul de enumerare, enumerare a opțiunilor este legat de atât de multe probleme rezolvate de oameni, încât dacă am ști să-l organizăm într-un mod foarte original, atunci ar fi, într-un fel, ca inventarea roții pentru umanitatea - una dintre cele mai fundamentale descoperiri. Deci, forța brută ar putea fi, și poate este, o roată a inteligenței artificiale.

– Într-unul dintre articolele despre inteligența artificială, am citit că inteligența este capacitatea de a înțelege și de a alege. Desigur, a preda un computer să aleagă dintre multe opțiuni este foarte dificil. Dar sigur sunt posibile unele soluții specifice șahului?

- Da Da. Această problemă trebuia rezolvată rapid și eficient, iar în șah au ajuns rapid la următoarea formulare teoretică a întrebării: să ne uităm nu la un număr infinit de mutări, ci doar la câteva mutări înainte. Să spunem să ne uităm cu 5 mișcări înainte. Asta e mult. Dacă îți place șahul și 5 mutări nu ți se par suficiente, atunci hai să luăm 10. Și atunci mașina, 10 mutări, 20 de jumătăți de mișcare înainte, nu va face nicio greșeală și garantează că după 10 mutări nu vei avea mai puține. piese. Este clar că avem de-a face cu o mașină de joc puternică. Deci arborele jocului va trebui scurtat și problema rezolvată într-un spațiu mult mai limitat. O altă întrebare este că încearcă să ia în considerare acest copac incomplet, cu ajutorul metode matematice tăiere. Am vorbit deja despre una dintre ele: dacă există un partener într-o singură mișcare, nu este nevoie să te uiți la alte opțiuni. Alți algoritmi au o euristică, nu caracterul exact. În medie, funcționează corect, multe sunt absolut precise, dar pot fi și greșite. De exemplu, putem parcurge nu toate mișcările, ci doar capturile și le putem calcula cu mult înainte, deoarece capturile sunt puține. Adâncimea generală a mișcărilor este mică: nu puteți mânca mai mult de treizeci și două de bucăți. Prin urmare, lungimile lanțurilor sunt mici și există puține ramuri. Desigur, este clar că nu poți construi un joc numai pe capturi; trebuie să existe câteva considerații de poziție. Combinația de forțare (capturare, verificare) și considerații de poziție, precum și o anumită profunzime de căutare, este baza tuturor algoritmilor existenți și nu se schimbă prea mult. O altă întrebare: cum să selectez mișcările pe care le voi lua în considerare în continuare? Bazat doar pe criterii formale simple (capturare, verificare) sau pentru a conecta aceste mișcări, așa cum le place să spună jucătorilor de șah, cu un plan, să vină cu niște lanțuri care au o proprietate comună? În orice caz, s-au scris o mulțime de lucrări serioase despre asta, având uz practic. Nu degeaba companii destul de reputate sunt implicate în crearea de programe de șah.

– Când au apărut primele programe de șah?

– Programele adevărate de șah au apărut pentru prima dată undeva la sfârșitul anilor 50 în America, iar apoi undeva la începutul anilor 60 la noi în țară. Programele erau foarte slabe, pentru că pe atunci existau mașini extrem de primitive și gândirea noastră nu era încă obișnuită cu noutatea. Ne-am implicat în această afacere în jurul anului 1963. Apoi au fost niște meciuri pe mașinile noastre autohtone. După părerea mea, în 1967 a avut loc primul meci între URSS și SUA. Se numea așa, deși, desigur, s-a desfășurat între două echipe, și nu țări. A fost o potrivire între programul nostru, dezvoltat la Institutul de Fizică Teoretică și Experimentală, și programul lui John McCarthy, o persoană foarte faimoasă în lumea computerelor, unul dintre creatorii limbajelor de programare, care atunci era pasionat de programele de șah. Mișcările erau transmise prin telegraf, deoarece atunci nu existau rețele.

— Și cine a câștigat?

– Atunci am câștigat cu 3:1. S-au jucat 4 jocuri. S-a făcut o mișcare pe zi, pentru că americanii aveau programe mai puternice și mai profunde care au gândit mult timp și ne-am jucat pe diferite versiuni de programe care au gândit atât rapid, cât și încet. Victoria noastră a fost prima noastră realizare. Această direcție a început să se dezvolte treptat și a devenit deosebit de activă în anii 70. În jurul anului 1974, la Stockholm a avut loc primul campionat mondial dintre programele de șah. Au participat aproximativ opt programe, inclusiv al nostru. Și apoi am câștigat și am devenit primii campioni mondiali. De atunci, campionatele mondiale au avut loc regulat, la fiecare 3 ani. Am mai participat la ele de două ori - în 1977 și în 1980. Nu am câștigat nici un laur atunci, pentru că în 1977 am împărțit locurile 2 și 3 (au participat multe programe de șah, au fost chiar selecții regionale), iar în 1980 - 4 și 3. locul 5. În general, se întorceau încet înapoi. Adevărul este că până atunci s-au înregistrat deja progrese enorme în tehnologia computerelor și încă ne jucam pe computere destul de învechite. Și până în 1980, a devenit clar pentru noi că concurența pe mașinile pe care lucrăm și-a pierdut orice semnificație și, în general, munca în domeniul programelor de șah în Rusia a început să se destrame. Deși au existat destul de multe lucrări teoretice interesante. Puțin mai târziu, au creat, probabil, primul program care a făcut înconjurul lumii; ar putea juca cu absolut exactitate un joc final complex, adică o regină și un pion împotriva unei regine, sau un turn și un pion împotriva unei turne. Programul a considerat pur și simplu astfel de jocuri finale până la sfârșit, adică, în orice poziție, a dat o mișcare perfect corectă. Algoritmul a fost construit pe principii ușor diferite de enumerarea simplă, pe o inspecție completă a întregului set de poziții. Ei bine, atunci au făcut niște lucrări de această natură la șah. Și apoi ne-am luat rămas bun de la jocul practic, pentru că diferențele de viteze erau deja de sute de ori. Însă campionatele au continuat, iar dezvoltarea programelor de șah a avansat complet. nou nivel, de îndată ce totul a fost mutat pe PC. Ca urmare a comercializării pe scară largă, au început să fie investite sume uriașe de bani în programe de șah și totul a fost imediat clasificat. Și anterior au aparținut oamenilor de știință care, dacă nu sunt forțați în mod expres, nu își ascund realizările, ci, dimpotrivă, le promovează. În 1980, am simțit pentru prima dată că a venit vremea programării comerciale. Această lume este, desigur, unică. În primul rând, pentru că banii sunt investiți în el și, în al doilea rând, pentru că din el se extrag bani. Deși există reviste despre programele de șah, în ultimii 15 - 17 ani schimbul real de idei s-a diminuat foarte mult deoarece acestea au devenit o afacere imensă pe PC.

– Dar comerțul stimulează dezvoltarea pieței de software de șah?

– Anterior, competițiile de informatică erau programate pentru a coincide cu forumurile de tehnologie informatică. Există o astfel de organizație - IFI (Federația Internațională de Informatică) și, de obicei, campionatele mondiale sunt programate pentru a coincide cu congresul său. Acum au devenit evenimente complet independente, destul de prestigioase. Există deja sute și sute de astfel de programe. Însuși nivelul de programare și nivelul cunoștințelor noastre este deja de așa natură încât realizarea unui program simplu de șah nu este nici cea mai mică dificultate. Aceasta este munca normală a elevilor. Îl încredințez doar unui student. Învingerea unui program de șah a devenit, ca să spunem așa, un loc obișnuit.

– Dar, ca întotdeauna, nivelul inferior devine mai simplu, iar cel superior devine mai complicat?

- Asta este. Prin urmare, cele mai recente programe, cele care acum câștigă, în special, programul care l-a învins pe Kasparov, au devenit mult mai puternice. Profunzimea căutării a crescut semnificativ și, desigur, acesta este rezultatul progreselor noastre matematice și, parțial, pur și simplu al progresului tehnologiei computerelor. La urma urmei, dacă anterior considerarea a 1000 de poziții pe secundă era considerată mult, acum în acei copaci despre care am vorbit deja se iau în considerare mai mult de un milion de poziții. Și un milion în plus înseamnă mai multe niveluri de mișcări cu selecția corectă. Și fiecare nivel de adâncime de căutare întărește foarte mult programul. Fiecare nivel per mișcare înainte este aproximativ un rang și, să zicem, o adâncime de căutare de patru mișcări este al treilea rang, iar cinci mișcări este deja al doilea rang. Când ajungem la un nivel de 11-13 mutări, acesta este un nivel de master și este destul de dificil să continui să joci cu mașina. Desigur, americanii conduc acum pentru că știu să investească bani mari în astfel de lucruri.

– Orice program de inteligență artificială pentru luarea deciziilor are nevoie nu doar de mecanisme euristice, ci și de un fel de bază de cunoștințe. Care este relația dintre baza de cunoștințe și algoritmii care generează poziții în programele de șah?

– Nimeni nu poate spune cu certitudine, pentru că aceasta este o chestiune de speculații. Existau programe destul de puternice, cu cunoștințe pur și simplu minime, în mod deliberat minime, în special pentru a vedea ce ar putea fi stors din matematică pură. La un moment dat, acest lucru s-a datorat comercializării și mai ales faptului că au început să facă cele mai puternice programe posibile - indiferent de ce. Dar, parțial, datorită faptului că lucrul cu cunoștințe încorporate este o sarcină independentă, există o mulțime. În primul rând, a fost creată o carte de referință uriașă. Acum directoarele conțin sute de mii de poziții. Apoi, multă inteligență în șah este întotdeauna investită în evaluarea pozițiilor. Se reduce, desigur, la materialul de joc, care este banal, și la niște factori poziționali. Deci, factorii de poziție sunt pur inteligență de șah, care, desigur, este programată, dar aici o mulțime este stabilită și este îmbunătățită tot timpul. Și cu cât sunt implicați mai mulți factori, cu atât programul este mai puternic. Într-un fel, capacitatea de a evalua o poziție și profunzimea unei căutări sunt lucruri interschimbabile. Dacă am ști să evaluăm cu brio o poziție, atunci ar fi suficient să încercăm toate primele mișcări. Acesta este ca un exemplu extrem. Este clar că cel mai bun scor poziţia are un efect corespunzător mai mare asupra adâncimii căutării. Aceasta este a doua metodă, fundamentală. Există destul de multe programe în care inteligența de șah este încorporată în alegerea opțiunilor în sine, adică unele considerații pur șahiste, unele planuri. Există destul de multe astfel de considerente, ceea ce limitează sfera căutării. Aria lor de acțiune nu este foarte largă, iar datele intelectuale specifice șahului încetinesc căutarea. Apropo, Botvinnik a susținut cândva cu fermitate tocmai pentru lucruri intelectuale. Era un mare pasionat de șah de mașini și a contribuit cu câteva idei acolo. Deși nu a reușit niciodată să creeze un program funcțional, totuși, autoritatea sa era foarte mare în acel moment. Așadar, a fost foarte supărat că, în general, regia nu a fost atât de „intelectuală” pe cât și-ar dori el și s-a investit o cantitate foarte limitată de cunoștințe de șah pur în programe.

– Dar computerele specializate pentru șah? Se pare că acţionează tocmai prin metoda de generare?

- Desigur. În primul rând, în ceea ce privește generarea, căutarea este schematică. În al doilea rând, orice tabele de poziții nu sunt mai puțin importante, deoarece în șah repetarea pozițiilor este foarte mare. Te duci E4E6D4 sau D4E6E4 - poziția va fi aceeași, dar acestea sunt doar 3 jumătăți de mișcări. Și când începem să mergem mai adânc, repetarea pozițiilor este foarte mare. Al treilea, zona tehnica. De fapt, la un moment dat, am construit teorii despre care poziții schimbările locale nu pot duce în mod fundamental la modificări ale opțiunilor forțate, cum să creăm un fel de șabloane. Șabloanele pentru astfel de opțiuni se potrivesc bine în diverse scheme informatice pur tehnice. Desigur, diagramele de referință sunt foarte importante.

– Există vreo modalitate de a crea un aparat mental universal în care să pui o bază de cunoștințe - nu contează, poziții de șah sau orice altceva, regulile prin care trebuie să lucrezi cu aceste cunoștințe - și să obții rezultate adecvate din ea?

– Este clar că din punct de vedere constructiv, o astfel de sarcină nu poate fi rezolvată astăzi și nu este relevantă. Deși multe probleme intelectuale sunt acum rezolvate, cum ar fi recunoașterea textului. Puteți pune o bucată de text în scaner și o puteți obține pe ecran în Word. Se va citi de la sine, fiecare literă va fi recunoscută. De fapt, am făcut progrese în multe sarcini intelectuale. Unele dintre ele au fost deja rezolvate, altele sunt în curs de rezolvare. În unele moduri, funcționează comparativ mai bine decât cu participarea umană, în altele, este încă mai rău. Există multe exemple de probleme practice. În ceea ce privește mecanismul mental artificial universal, aceasta este mai degrabă o problemă filozofică decât una practică. La urma urmei, chiar și pentru un joc atât de simplu precum șahul, ne-a luat 30 - 40 de ani să realizăm ceva. Toată filozofia se bazează pe opinii. Toată lumea crede că are dreptate și poate că fiecare are dreptate în felul său. De exemplu, m-am ocupat toată viața mea de inteligență artificială și cred că creierul uman nu este altceva decât un computer mare, prin urmare, nu se poate spune că este fundamental imposibil să creezi unul similar cu acesta. Întrebarea este puterea sa, caracteristicile vitezei și umplerea acesteia cu cunoștințe. Nu este nimic de neînțeles aici. Acesta este punctul meu de vedere personal. Dar mai sunt si alte pareri. Desigur, dacă recunoaștem natura divină a omului, atunci trebuie să alegem una dintre cele două opțiuni epistemologice. Ori da, avem o natură divină, dar este cognoscibilă. În acest caz, nu vom putea reproduce cu adevărat ceea ce a putut să facă Domnul Dumnezeu, dar cel puțin vom putea să recreăm cel puțin parțial creațiile Sale. Sau stăm pe poziția agnosticismului și atunci este de necunoscut, iar întrebarea este complet eliminată. Se pare că creierul uman rezolvă unele probleme - și nimeni nu are nicio îndoială în acest sens. Dar nu putem ajunge din urmă cu creierul, pentru că, pe de o parte, a fost creat de Dumnezeu, iar pe de altă parte, nu suntem capabili să-l cunoaștem. Toate cele trei poziții sunt asociate cu credința, deoarece în realitate nu este necesar să se cunoască toate funcțiile creierului. Dacă facem o mașină cu aceeași putere ca un creier, atunci nu va mai avea nevoie să gândească ca un creier. Va funcționa diferit.

– În psihologie, din câte știu eu, dezvoltare intelectuala o persoană este definită de trei criterii: capacitatea de a abstractiza, de a crea o serie intelectuală și altceva... În ce măsură aceste capacități sunt realizate în inteligența artificială și sunt realizate deloc?

– Există o mulțime de programe care vizează în mod special crearea de concepte care abstrag din materialul actual existent. Astfel de programe funcționează bine. O altă întrebare este că o persoană știe să creeze aceste concepte, ca după propriile legi, pe care le inventează singur. Toate încercările noastre de a traduce aceste legi ale sale în limbajul algebrei logice se dovedesc a fi zadarnice. Oamenii au un mecanism de gândire mult mai puternic pe care pur și simplu nu îl cunoaștem. Nu știm să facem nimic „deloc”. Creăm formulările de care avem nevoie, dar nu le putem „exprima” în probleme precise ale mașinii. Totul se reduce cu dificultate la probleme mecanice și, chiar dacă se reduce, este lent. Probabil că încă nu știm modalități mai directe de a atinge obiectivul. Puteți pune orice în computer. Întrebarea este că o persoană este capabilă să manipuleze aceste cunoștințe tot timpul, dar încă nu știe cum să forțeze o mașină să facă același lucru din cauza volumului și vitezei limitate a datelor.

– Dar poate că nu are sens să forțezi o mașină să manipuleze cunoștințele?

– Aici sunt atinse atât aspectele imorale, cât și cele constructive. Suntem încă departe de mașinile de revoltă. Cu siguranță va fi suficientă liniște sufletească pentru viața mea și pentru a ta. Chiar și în zone limitate, nu am învățat încă cum să forțăm o mașină să manipuleze sarcini, chiar și pe cele pe care le poate rezolva. Ne-am stabilit o sarcină, iar ea gândește doar la comandă.

– Vladimir Lvovich, spune-mi, dacă acum ar fi din nou zorii tehnologiei informatice, ar merita să lucrezi la programe de șah? Au contribuit într-adevăr atât de mult la progres?

– Totuși, șahul ne extinde orizonturile. În programele de șah, sarcinile sunt stabilite, rezultatul este vizibil, îl evaluăm. Totuși, ar trebui să existe multe probleme rezolvate, interesante, care contribuie la progresul în calcul.

Fotografii din surse deschise

Noua inteligență artificială a devenit cel mai bun jucător de șah de pe Pământ în doar 4 ore de antrenament! (site-ul web)

Îți amintești ce senzație a provocat supercomputerul de șah „Deep Blue” în 1996, câștigând primul joc împotriva campionului rus Garry Kasparov? În ciuda faptului că compatriotul nostru încă a câștigat acest joc, a devenit clar chiar și atunci că inteligența artificială progresa rapid și va deveni într-o zi fermecător cel mai bun jucător de șah, după care ar fi inutil ca oamenii să se joace cu programul. Singura întrebare care a rămas a fost când se va întâmpla asta.

Reprezentanții celebrei corporații Google au spus că acest moment a venit în sfârșit. Potrivit experților, rețeaua neuronală AlphaZero pe care au dezvoltat-o ​​în doar 4 ore de auto-antrenament s-a transformat în cel mai virtuos și impecabil jucător de șah din întreaga istorie a acestui joc. O inteligență artificială super-puternică a învățat să joace șah, cunoscându-și doar regulile. După ce s-a jucat cu el însuși timp de 4 ore, robotul a învățat să joace perfect, învingând cu ușurință programul de șah Stockfish, care era considerat anterior cel mai perfect. Calculatoarele au jucat 100 de jocuri - AlphaZero a reușit să câștige 28 dintre ele și să atragă restul de 72. O rețea neuronală avansată care imită activitatea creierului uman este capabilă să-și asume riscuri și chiar să folosească un fel de intuiție.

Nu mai este nevoie să visezi la victoria asupra inteligenței artificiale.

Modelele anterioare AlphaZero au învățat jocul urmărind jucătorii de șah în direct. Dezvoltatorii au presupus că acest lucru ar ajuta inteligența artificială să înțeleagă mai bine strategiile de joc. De fapt, s-a dovedit că monitorizarea oamenilor nu face decât să încetinească dezvoltarea programului. Când rețeaua neuronală a fost lăsată în voie, abilitățile sale au crescut vertiginos. Acum, inginerii Google se gândesc cum să folosească astfel de tehnologii pentru un beneficiu real pentru umanitate, deoarece un joc de șah, chiar și cel mai magistral, nu are un scop practic.

În 1968, celebrul David Levy a pariat că niciun program nu îl va învinge în următorul deceniu. În tot acest timp, marele maestru a concurat constant cu diferite computere de șah și a câștigat împotriva lor de fiecare dată. În 1978, a învins cel mai puternic program de la acea vreme, Chess 4.7, câștigând un pariu. Din păcate, în aceste zile nu vor mai exista lupte atât de interesante - acum va trebui doar să aflăm cum o rețea neuronală fantastică a învins-o pe alta. Jucătorii de șah în viață nici nu mai pot visa să învingă astfel de monștri. Și acesta este doar începutul unor astfel de victorii ale AI asupra oamenilor...

Dezvoltat de inginerii de la Institutul de Tehnologie din Massachusetts. Fischer a șahmat computerul de trei ori și a câștigat o victorie necondiționată. În scrisorile sale, jucătorul de șah a scris că programele au făcut „greșeli grave” și a numit computerele în sine „piese inutile de fier”.

Dar în același an, Monty Newborn, unul dintre primii oameni de știință care a studiat șahul pe computer, a rostit cuvinte profetice:

„Marele maeștri veneau la turneele de șah pe computer să râdă. Acum vin să observe, iar în viitor vor studia acolo.”

Bobby Fischer după ce a învins computerul. Foto: Getty Images

Oamenii par să aibă un fel de dragoste înnăscută pentru jocurile minții. Când regele Carol I al Angliei a fost condamnat la moarte în 1649, a luat cu el două lucruri la executare - o Biblie și un set de șah. Celebrul artist al secolului XX Marcel Duchamp, aflat la apogeul carierei sale, a plecat brusc în Argentina și a început să sculpteze piese de șah din lemn și, în general, a devenit interesat de șah. În secolul al XIX-lea, în Japonia a avut loc o poveste misterioasă legată de jocul Go. Potrivit legendei, spiritele i-au spus unui jucător celebru trei mișcări geniale. Drept urmare, a reușit să câștige, iar după meci adversarul său a căzut la podea, s-a înecat cu sânge și a murit.

Calculatoarele sunt departe de tot acest misticism, dar în doar câteva decenii au studiat Jocuri ale mintii mai adânc decât a văzut omenirea în milenii. În 2014, compania a achiziționat DeepMind pentru 400 de milioane de dolari pentru „a desfășura cea mai extraordinară și mai complexă cercetare, al cărei scop final este dezvăluirea esenței inteligenței”. În special, oamenii de știință au vrut să învețe un computer să joace Go. Acest joc este mult mai complex decât șahul. În 1985, un magnat industrial din Taiwan a spus că va plăti 1,4 milioane de dolari pentru un program care ar putea învinge cel mai bun jucător Go. Magnatul a murit în 1997, iar trei ani mai târziu oferta sa a expirat - nimeni nu a putut revendica premiul.

Acum ar putea aparține programului DeepMind AlphaGo, care folosește rețele neuronale moderne. În urmă cu un an, a fost campioana internațională la Go, Lee Sedol. În luna mai a acestui an, ea l-a învins din nou pe cel mai bun jucător de la Go, precum și pe o echipă de alți cinci jucători profesioniști.

AlphaGo a devenit campion absolut. Dar la scurt timp după marile ei victorii, o așteaptă uitarea. La sfârșitul lunii mai, DeepMind a anunțat în liniște că AlphaGo părăsește scena competitivă. Pentru a marca ocazia, compania a publicat 50 de versiuni de jocuri pe care programul le-a jucat împotriva lui însuși. În viitor, DeepMind dorește să lanseze o lucrare finală de cercetare care va descrie eficiența algoritmului programului.

În ceea ce privește șahul, omenirea și-a pierdut palma cu 20 de ani înainte de aceste evenimente, când jucătorul de șah Garry Kasparov a pierdut în fața supercomputerului IBM Deep Blue. Chess and Go nu sunt singurele jocuri care se încearcă să învețe AI. Au încercat să-i învețe pe computere dame, table, reversi, poker și multe alte jocuri de societate. Iar inteligența umană nu se mai poate compara cu inteligența artificială. Acest lucru s-a datorat parțial dezvoltării tehnologiei. De exemplu, în 1997, computerul Deep Blue ocupa locul 259 pe lista celor mai rapide supercomputere din lume și putea efectua aproximativ 11 miliarde de operațiuni pe secundă. Acum, datorită algoritmilor moderni, chiar și smartphone-ul tău îl poate învinge pe Kasparov.

Garry Kasparov împotriva computerului Deep Blue. În stânga este unul dintre inginerii IBM Xiong Feixiong. Foto: Getty Images

Astfel de realizări AI au provocat emoții destul de umane în oameni: tristețe, depresie și disperare. După ce Lee Sedol a fost învins de AlphaGo, a suferit o criză existențială. „M-am îndoit de ingeniozitatea umană”, a recunoscut el după meci. „Am început să mă îndoiesc dacă toate mișcările Go pe care le știam sunt corecte.” Potrivit unui martor ocular, după înfrângere, Lee părea „bolnav din punct de vedere fizic”. Kasparov nu s-a simțit mai bine după ce a pierdut în fața computerului. Când s-a întors la hotel, s-a dezbrăcat pur și simplu, s-a întins în pat și s-a uitat la tavan.

„Computerul analizează unele poziții atât de profund încât joacă ca un zeu”, a spus Kasparov.

Deep Blue a arătat publicului pentru prima dată că un computer ar putea depăși oamenii în rezolvarea problemelor intelectuale. „A fost un șoc la acea vreme”, a spus Murray Campbell, co-creatorul Deep Blue. „Acum ne obișnuim treptat cu această idee.” Cu toate acestea, nu este clar ce așteaptă omenirea în viitor. Cum pot fi folosite realizările din jocuri în lumea reală? Răspunsul lui Campbell la această întrebare sună pesimist. „Este greu de găsit un exemplu bun al acestor progrese aplicate jocurilor de societate”, a spus el. - La începutul anilor '90, un angajat IBM pe nume Gerald Tesauro a încercat să învețe un AI să joace table și a făcut unele progrese în învățarea stimulativă. Acum metodele sale sunt adesea folosite în robotică. Cu toate acestea, cazul lui este mai degrabă o excepție de la regulă.”