Motor de șah

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Un motor de șah (sau, cu termenul larg utilizat în limba engleză, motor de șah ) este un program de calculator care implementează back-end-ul unui software de joc de șah . Motorul este componenta care analizează poziția și produce o listă de mișcări optime, prin intrare și ieșire în format textual și este de obicei utilizat în combinație cu o interfață grafică care implementează în schimb interacțiunea cu utilizatorul, arătând grafic poziția pe bord și vă permite să efectuați mișcările prin mouse sau tastatură.

Motorul poate fi folosit pentru a juca împotriva unui adversar care poate fi un om, un alt motor sau el însuși, pentru a analiza o anumită poziție sau pentru a analiza ulterior un întreg joc care a fost deja jucat. Sunt disponibile motoare comerciale, freeware și open source . Un motor de șah este un exemplu tipic de inteligență artificială slabă , adică un software de inteligență artificială care este capabil să abordeze doar singura problemă specifică pentru care a fost dezvoltat.

Istorie

Mai multe automate dedicate jocului de șah au fost deja realizate în timpul secolului al XVIII-lea . Unele au fost pur și simplu escrocherii bine lucrate, conduse de fapt de ființe umane , precum „ Turcul ”, „ Mephisto ” și „ Ajeeb ”. Alte automate erau reale și funcționale (cum ar fi „ El Ajedrecista ”), dar numai în poziții extrem de simple.

Dezvoltarea reală a inteligenței artificiale în domeniul șahului va avea loc numai după nașterea informaticii . Un pionier în dezvoltarea informaticii aplicate șahului a fost un inginer și, în mod surprinzător, unul dintre cei mai puternici jucători de șah din secolul al XX-lea : sovieticul Michail Botvinnik . [1] Botvinnik a studiat un algoritm care ar putea face alegeri inteligente în selectarea mișcărilor, obținând rezultate pozitive în situații destul de complexe, dar insuficiente pentru a crea un software de șah valid.

Primul computer capabil să învingă un jucător uman în condiții de reglementare a fost Deep Thought . Mașina, proiectată de informaticianul chinez IBM Feng-hsiung Hsu , l-a învins pe șahistul David Levy în 1989 , câștigând o provocare lansată de acesta din urmă pentru a stimula dezvoltarea computerelor de șah, care a constat în găsirea unui computer capabil să-l bată într-un meci din patru sau șase jocuri. Deep Thought a fost astfel primul motor de șah care a concurat oficial la nivelul unui GM uman. În același an, Deep Thought s-a confruntat cu Garri Kasparov , de la care a fost învins cu un 2-0 sec.

Kasparov este cel mai bine amintit pentru un alt meci oficial, împotriva computerului IBM Deep Blue , disputat în 1996 , când jucătorul rus era campion mondial în frunte și primul în clasamentul FIDE Elo. Victoria lui Deep Blue în primul joc a provocat senzație, dar Kasparov a câștigat meciul cu 3 victorii și 2 remize. [2] Revanșa, un meci de șase jocuri jucat în anul următor, a fost decisă în ultimul joc decisiv, câștigat de calculatorul care a câștigat, prin urmare, meciul pentru 3.5-2.5. Computerul a fost retras ulterior de IBM, [3] respingând cererea lui Kasparov de revanșă.

Un alt meci de talie mondială a avut loc în octombrie 2002 , când Vladimir Kramnik (de asemenea campion mondial în exercițiu) a remizat un meci de opt jocuri, cunoscut sub numele de Brains în Bahrain , împotriva motorului de șah Deep Fritz 7 . [4]

În februarie 2003 , Kasparov a remizat, de asemenea , un meci în șase jocuri împotriva programului Deep Junior , iar în noiembrie al aceluiași an a tras un alt meci împotriva programului X3D Fritz din New York. [5] Fritz a câștigat al doilea joc, Kasparov al treilea. Prima și a patra s-au încheiat la egalitate. A fost primul meci oficial de șah jucat în întregime în realitatea virtuală.

Printre ultimele capitole referitoare la meciul om-computer, a fost meciul „eveniment” dintre campionul mondial de atunci Vladimir Kramnik și software-ul Deep Fritz , desfășurat la sfârșitul lunii noiembrie 2006 . Meciul de pe durata celor șase jocuri a înregistrat victoria computerului cu un rezultat de 4 la 2 (patru remize și două victorii ale computerului). [6] Neobișnuit epilogul celui de-al doilea joc, în care campionul mondial nu a observat o amenințare elementară de nebunie într-o mișcare de computer, un eveniment foarte rar la aceste niveluri.

Din a doua jumătate a anilor 2000 , motoarele de șah au depășit definitiv capacitățile umane, reușind să învingă în mod sistematic cei mai puternici jucători și au devenit un instrument important în analiza și instruirea jucătorilor umani.

La sfârșitul anilor 2010 , au fost dezvoltate noi abordări în proiectarea algoritmilor pentru jocul de șah. Prima demonstrație de fezabilitate a acestor noi tehnici a fost prezentată în 2017 de DeepMind odată cu dezvoltarea AlphaZero , iar rezultatele au fost reproduse ulterior de proiecte open source, cum ar fi Leela Chess Zero și de produse comerciale.

Principiile de funcționare

Un motor de șah constă din trei componente principale: reprezentarea poziției, algoritmul de căutare și funcția euristică utilizată pentru a evalua o poziție.

Reprezentarea poziției este modul în care motorul codifică poziția pe tabla de șah intern, în general printr-o placă de biți , împreună cu informații auxiliare, cum ar fi trăsătura, posibilitatea de aruncare sau captură en passant și numărul de mișcări trecute de la ultima captură (relevantă pentru aplicarea regulii de cincizeci de mutări ).

Calitatea unei poziții este evaluată printr-o funcție euristică, care asociază o valoare numerică fiecărei poziții: zero indică paritatea, valorile pozitive indică avantajul albului, valorile negative ale negru și importanța avantajului depinde de valoare absolută. De obicei, o valoare a unității corespunde aproximativ unui pion de avantaj. În mod tradițional, funcțiile euristice sunt implementate manual și bazate pe cunoștințele umane ale jocului, deși abordările bazate pe tehnici de învățare automată își găsesc aplicația.

Software-ul tradițional de șah se bazează pe variante de căutare în copac minimax cu tăiere alfa-beta pentru a determina mișcarea optimă la fiecare viraj, iar principalele puncte critice ale diferiților algoritmi care determină puterea motoarelor individuale sunt tehnica de tăiere și funcția euristică . . Această abordare este supusă efectului orizontului și determină limita în viziunea strategică a motoarelor: deși de neegalat în jocul tactic , motoarele tradiționale se luptă să aibă o viziune clară a efectelor pe termen lung ale fiecărei mișcări, în analiza căreia oamenii sunt în schimb de obicei pricepuți.

Printre abordările alternative, o posibilitate este reprezentată de tehnicile de învățare profundă care au înregistrat progrese semnificative în anii 2010 . În special, s-au obținut câteva rezultate promițătoare cu căutarea arborelui Monte Carlo condusă de o rețea neuronală convoluțională profundă , pregătită pentru întărire . În decembrie 2017 DeepMind a introdus AlphaZero , un algoritm care implementează această abordare pentru a concura într-o varietate de jocuri de societate , inclusiv șah, și promite o forță superioară software-ului tradițional cu un stil mai asemănător cu cel uman. [7] Această metodă a fost reimplementată la scurt timp după motorul open source Leela Chess Zero, un proiect care a început la începutul anului 2018 și care în scurt timp a atins un nivel de putere comparabil cu cele mai puternice motoare tradiționale. [8]

Intrarea și ieșirea mișcărilor au loc de obicei printr-un protocol text, cum ar fi interfața șah universală (UCI) sau protocolul de comunicare a șahului motorului [9] , care vă permite să controlați motorul prin interfețe grafice care implementează același protocol.

În etapele inițiale și finale ale jocului, motorul poate folosi și baze de date care îi sporesc puterea de joc. La început se folosește un repertoriu („carte de deschidere”, în carte de deschidere în limba engleză) obținut prin selectarea caracteristicilor inițiale ale unui număr mare de jocuri. Formatele obișnuite de carte de deschidere includ CTG, formatul proprietar ChessBase , ABK, utilizat de Arena și BIN, utilizat de PolyGlot. În final, motoarele pot folosi bazele de masă , care oferă rezultatul corect al jocului pentru fiecare poziție care conține până la un anumit număr predeterminat de piese, împreună cu secvența de mișcări care duce la acest rezultat. Există baze de masă complete de până la șapte bucăți, care necesită totuși o cantitate considerabilă de memorie ( 140 TB ), deci în practică se folosesc baze de masă din șase piese (1,4 TB). Ca alternativă la bazele de masă, motorul poate folosi o bază de biți , care conține doar rezultatul pornind de la fiecare poziție fără a raporta mișcările necesare, necesitând o cantitate mult mai mică de memorie.

Puterea jocului

Programele moderne de șah au forță de joc supraomenească. Primul computer capabil să bată un maestru uman într-un meci în condiții de reglementare a fost Deep Thought, care în 1989 l-a învins pe maestrul internațional David Levy . Punctul de cotitură este considerat a doua întâlnire dintre IBM Deep Blue și Garri Kimovič Kasparov , disputată în 1997, când pentru prima dată un computer l-a învins pe campionul mondial în exercițiu într-un meci. La începutul anilor 2000 au existat mai multe meciuri în condiții de reglementare și fără handicap între motoare și jucători umani la cele mai înalte niveluri încheiate într-o remiză, cum ar fi Brains în Bahrain și X3D Fritz , iar în anii următori puterea tot mai mare a software-ului și a creșterea puterii de calcul a hardware-ului comercial a adus motoarele de șah la un nivel de joc mult superior celor mai buni maeștri umani.

Există clasamente Elo care compară puterea motoarelor de șah, obținute jucând motoarele unul împotriva celuilalt cu același hardware. Clasamentele diferite sunt, în general, diferențiate de diferența de cadență a jocului. Clasamentul editat de Svenska schackdatorföreningen (SSDF) [10] este unul dintre primele de acest gen și include date din 1984, care documentează evoluția istorică a forței de joc. Alte clasamente includ CEGT , [11] CCRL, [12] CSS [13] și WBEC. [14] Elo- ul diferitelor clasamente evoluează independent și nu este comparabil, la fel cum nu este comparabil cu Elo-ul din jocul uman (de exemplu, Elo FIDE ).

Evenimente

Asociația Internațională a Jocurilor pe Computer , recunoscută de FIDE [15] , a organizat Campionatul Mondial de șah pe computer din 1977 și diverse organizații naționale, precum Computerschaak Vereniging Nederland (CSVN) și Svenska schackdatorföreningen (SSDF), sau alte entități private organizează sau au organizat turnee internaționale, precum Turneul internațional de șah pe computer , Campionatul olandez de șah pe computer deschis , Campionatul internațional de șah pe computer din Paderborn și, în Italia, Campionatul italian pentru programele de șah . Astfel de evenimente tradiționale implică de obicei participarea personală a dezvoltatorilor, utilizarea hardware-ului la discreția participanților și cerințe stricte pentru originalitatea software-ului. În anii 2010, alte evenimente independente, cu organizare mai modernă și cerințe de participare mai puțin oneroase, și-au asumat o importanță mai mare, în special Campionatul de top pentru șah (TCEC), considerat de facto campionatul de șah pe computer. [16]

Notă

  1. ^ (EN) Partea a III-a de programare a șahului: generația de mișcare (François Dominic Laramée) , gamedev.net la 6 ianuarie 2011. Accesat la 13 februarie 2011 (depus de „url original 12 februarie 2009).
  2. ^ (EN) IBM Research pe research.ibm.com. Adus la 13 februarie 2011 .
  3. ^ (EN) IBM Research pe research.ibm.com. Adus la 13 februarie 2011 .
  4. ^ (RO) Fritz se apără să tragă jocul 8 și meciul! Scor final: 4-4 , pe chessbase.com , Știri ChessBase . Adus la 13 februarie 2011 .
  5. ^ (RO)Kasparov vs X3D Fritz meciul se termină cu 2-2 după patru remize , pe chessbase.com, ChessBase News . Adus la 13 februarie 2011 .
  6. ^ (EN)Kramnik vs Deep Fritz: Computer câștigă meciul cu 4: 2 , pe chessbase.com, ChessBase News . Adus la 13 februarie 2011 .
  7. ^ (EN) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis, Un algoritm general de învățare pentru întărire care stăpânește șah, shogi și Go through self-play , în Știință , vol. 362, nr. 6419, 7 decembrie 2018, pp. 1140-1144, DOI : 10.1126 / science.aar6404 .
  8. ^ Arhiva TCEC , pe tcec.chessdom.com . Adus la 31 ianuarie 2019 (arhivat din original la 3 mai 2015) .
  9. ^ (EN) Tim Mann și HGMuller,Protocolul de comunicare a motorului de șah pe gnu.org. Adus la 28 septembrie 2016 .
  10. ^ Lista de evaluare SSDF , pe ssdf.bosjo.net , SSDF , 26 septembrie 2008. Accesat la 13 ianuarie 2017 .
  11. ^ CEGT 40/20 , pe husvankempen.de , Turneul Chess Engines Grand Tournament , 28 martie 2010. Accesat la 13 ianuarie 2017 (arhivat din original la 8 martie 2011) .
  12. ^ CCRL 40/40 - Lista completă , pe computerchess.org.uk , 6 martie 2010. Accesat la 13 ianuarie 2017 .
  13. ^ Computerschach und Spiele - Eternal Rating . Computerschach.de , Computerschach und Spiele , 18 martie 2007. Accesat la 21 mai 2008 .
  14. ^ Listă de evaluare BayesianElo a WBEC Ridderkerk , la wbec-ridderkerk.nl . Adus 20.07.2008 .
  15. ^ ratings.fide.com , https://ratings.fide.com/fide_directory.phtml?list=966 .
  16. ^ TCEC: Superfinal Houdini vs Komodo , la en.chessbase.com, ChessBase .
    «De-a lungul anilor," Competiția de motoare de șah Thoresen "(TCEC) a devenit Campionatul Mondial de Calculatoare neoficial [...]» .

Bibliografie

  • Ciancarini, Paolo. Jucătorii artificiali . Milano, Mursia, 1992. ISBN 88-425-1319-9 .
  • Hsu, Feng-hsiung. În spatele Deep Blue: în spatele computerului care l-a învins pe campionul mondial la șah . Princeton, Princeton University Press, 2002. ISBN 0-691-09065-3 .
  • Opfermann, Hans Carl. Șah cu computerul . Milano, Mursia, 1982.
  • Pachman, Ludek și Kuhnmund, Vas I. Șahul computerizat . Londra, Routledge & Kegan, 1986. ISBN 0-7100-9785-9 .

linkuri externe

  • (RO) Proiectele de șah Winboard ale lui Jim Ablett - Descărcați motorul de șah gratuit și open source, compilat de Jim Ablett
  • ( RO ) WBEC Ridderkerk - Colecție de motoare gratuite , lansări noi, turnee, liste de rating și forumuri de discuții
  • ( EN ) Wiki de programare a șahului , la chessprogramming.wikispaces.com .
  • (EN) Talkchess - forum
  • ( EN ) CCRL - Evaluarea principalelor motoare de șah, actualizată lunar
  • ( EN ) IPON - Evaluarea principalelor motoare de șah în diferitele versiuni și pentru un singur timp de joc (5m + 3s pe mișcare). Mereu actualizat
  • ( EN ) CEGT - Evaluarea principalelor motoare în diferitele versiuni și pentru diferitele durate de joc
  • ( EN ) ICGA - site-ul oficial al Asociației Internaționale a Jocurilor pe Computer
Şah Portalul șahului : accesați intrările Wikipedia referitoare la șah