A számítógépes sakk egy népszerű kifejezés a mesterséges intelligencia kutatás területéről , amely szoftverek és speciális számítógépek létrehozását jelenti a sakkozáshoz . A "számítógépes sakk" kifejezést egy számítógépes sakkprogram elleni játszmára, a programok egymás közötti játékára is használják. A 2000-es évek óta a legerősebb emberi játékosoknak sincs esélyük a sakkprogramokkal szemben [1] .
A sakkgépek története régebbi, mint a számítógépek története. A sakkjátékgép ötlete a XVIII. századra nyúlik vissza. 1769 körül jelent meg a Mechanical Turk sakkgép . Mária Terézia királynő szórakoztatására szánták. A gép nagyon jól játszott - volt benne egy erős sakkozó, aki megtette a mozdulatokat.
A mechanikus sakkautomaták létrehozása a 20. század közepén a digitális számítógépek megjelenésével megszűnt. 1951-ben Alan Turing megírta a Turochamp algoritmust , mellyel egy gép tudott sakkozni, csak maga a feltaláló működött gépként. Ez a hülyeség még a "Turing papírgépe" nevet is kapta. Az embernek több mint fél órába telt egy mozdulat megtétele. Az algoritmus meglehetősen feltételes volt, sőt a játék felvétele is megmaradt, ahol Turing „papírgépe” elveszett egyik kollégájával szemben [2] . A számítógéphez való hozzáférés hiánya miatt a program működését soha nem tesztelték.
Ez idő tájt, 1951-ben, Claude Shannon matematikus írta meg első dolgozatát a sakkprogramozásról. Azt írta: " Bár gyakorlati jelentősége nincs, de maga a kérdés elméletileg érdekes, és reméljük, hogy ennek a problémának a megoldása lendületet ad más, hasonló jellegű és nagyobb jelentőségű problémák megoldásának ." Shannon felhívta a figyelmet arra is, hogy elméletileg létezik a legjobb lépés a sakkban, és hogy gyakorlatilag lehetetlen ilyet találni.
A sakkprogramozás fejlesztésének következő lépése a Los Alamos -i atomlaboratóriumban 1952-ben egy 11 kHz-es órajelű MANIAC I számítógépen egy 6x6-os táblán játszható sakkprogram kifejlesztése volt 1952-ben, elefántok részvétele nélkül. Ismeretes, hogy ez a számítógép egy partit játszott egy erős sakkozó ellen, 10 órán át tartott, és a sakkozó győzelmével ért véget. Egy másik játszmát játszottak egy lány ellen, aki nemrég tanult meg sakkozni. A gép a 23. lépésnél nyert, a maga idejében nagy teljesítménynek számított.
1957 -ben Alex Bernstein megalkotta az első programot a szabványos sakktáblán való játékhoz, minden figura részvételével [3] .
A számítógépes sakk egyik fontos fejleménye 1958-ban történt, amikor Allen Newell , Cliff Shawés Herbert Simon kifejlesztett egy keresési fa redukciós algoritmust, az úgynevezett " alpha-beta pruning " [3] [4] , amelyre az összes erős modern program keresési funkciója épül.
1967-ben egy négy játszmából álló mérkőzésen az Institute for Theoretical and Experimental Physics (ITEP) programja 3-1-re verte a Stanford Egyetem sakkprogramját. A programmal játszó nagymesterek szerint a harmadik sakkkategória erejével játszott . [5]
Az 1974 augusztusában Stockholmban ( Svédország ) megrendezett I. számítógépes programok közötti sakkvilágbajnokságon a Kaissa program , amelyet 1971-ben hoztak létre a Szovjetunió Tudományos Akadémia Irányítási Problémái Intézetének munkatársai, mind a négy játszmát megnyerte, és az első világbajnok lett. sakkprogramok közül a „Chess 4”, „Chaos” és „Ribbit” előzési programok, amelyek 3-3 pontot értek el. A bajnokságon a világ 8 országából 13 autó vett részt, amelyek a bajnoki csarnokba való lépéseiket telefonon továbbították az operátornak.
Az első gép, amely elérte a sakkmesteri szintet, a volt , 1983-ban Joe Condon és Thompson készített el . A Belle volt az első számítógép, amelyet kizárólag sakkozásra terveztek. Hivatalos Elo minősítése 2250 volt, ezzel korának legerősebb sakkgépe.
1994-ben Garri Kaszparov elveszített egy torna villámjátékot Münchenben a Fritz 3 programmal szemben . A program felülmúlta Viswanathan Anandot , Boris Gelfandot és Vladimir Kramnikot is . Robert Huebner nagymester nem volt hajlandó a program ellen játszani, és automatikusan veszített. Kaszparov a második meccset Fritzcel játszotta, és 4 győzelemmel és 2 döntetlennel nyert.
1996 februárjában Garri Kaszparov 4-2 -re legyőzte a Deep Blue sakk-szuperszámítógépet. Ez a meccs figyelemre méltó, mivel az első játszmát a Deep Blue nyerte , így automatikusan az első számítógép lett, amelyik sakkvilágbajnokot győzött le a verseny szempontjából. A Deep Blue hárompercenként 50 milliárd pozíciót számolt ki, míg Kaszparov 10-et pozíciók ugyanannyira. A Deep Blue 200 processzorral rendelkezett . Azóta a sakkrajongók és számítástechnikai mérnökök számos sakkgépet és számítógépes programot készítettek.
1997-ben a Deep Blue visszavágót nyert (2 győzelem, 3 döntetlen, 1 vereség), és lett az első számítógép, amely legyőzte a világ legerősebb sakkozóját. Kaszparov már nem tudott megtérülni, mert az IBM a küldetést befejezettnek tekintve felhagyott a további versenyekkel.
A sakk számítógépek most nagyon alacsony áron kaphatók. Számos nyílt forráskódú program jelent meg, nevezetesen a Crafty , a Fruit és a GNU Chess , amelyek ingyenesen letölthetők az internetről , és sok profi sakkozót legyőzhetnek. A legjobb kereskedelmi és ingyenes programok, mint a Shredder , a Fritz vagy a Komodo már jóval az emberi bajnokok szintje felett vannak. A Stockfish nyílt forráskódú motor magas helyezést ért el az olyan számítógépes minősítési listákon, mint a CEGT , CCRL , SCCT és CSS , köszönhetően a sok ember közös fejlesztésének és tesztelésének [6] .
A sakk számítógépesítésének első motívumai a szórakozás, a számítógépes sakkversenyek programjainak készítése és az emberi kognitív képességek mélyebb megértését lehetővé tevő tudományos kutatások voltak. Az első két célt tekintve a számítógépes sakk fenomenális sikert aratott: kevesebb mint ötven év telt el az első kísérletek óta, hogy olyan sakkprogramot hozzanak létre, amely egyenlő feltételekkel versenyezhetne a legjobb sakkozókkal.
Alexander Kronrod a számítógépes sakk szerepét a jól ismert mondattal határozta meg: "a sakk a mesterséges intelligencia gyümölcslégye ". A hasonlat a felszínen rejlik: a sakk egy feltétel nélkül intellektuális, ugyanakkor világosan formalizált, egyszerű felépítésű és kompakt feladat, vagyis a mesterséges intelligencia laboratóriumi kutatásának kényelmes tárgya, akárcsak a gyümölcslégy. kis méretének, termékenységének és gyors generációváltásának köszönhetően kényelmes laboratóriumi tárgy az öröklődés vizsgálatához. Valójában a mesterséges intelligencia számos jól ismert módszerét és területét tesztelték a sakkon, beleértve a felsorolás optimalizálására szolgáló módszereket (a „ kombinatorikus robbanás elkerülése” az opciók kiszámításakor több lépéssel előre), mintafelismerést , szakértői rendszereket , logikai programozást .
Sokak meglepetésére és bánatára azonban a sakk kevéssé hozta közelebb az embereket az emberhez hasonló intelligenciával rendelkező gépek létrehozásához. A modern sakkprogramok valójában megálltak az intellektuális tevékenység legprimitívebb szakaszában: hatalmas számú lehetséges lépést kutatnak mindkét játékos számára, a felsorolási fa különböző csonkítási módszereivel, beleértve egy viszonylag egyszerű kiértékelési funkciót is . Az előre kiszámított, kész nyitásokat és végjátékokat tároló adatbázisokkal kombinálva, a modern számítógépek sebességének és memóriájának köszönhetően ezek a módszerek már nagymesteri szinten sakkozó számítógépet biztosítanak. Ezen okokból kifolyólag a számítógépes sakk iránt már nincs akkora tudományos érdeklődés. A "mesterséges intelligencia Drosophila" szerepét más elmejátékok vették át , mint például a Go . Sokkal inkább, mint a sakkban, az ilyen játékokban a lehetőségek felsorolásának mennyisége korlátozza az egyszerű módszerek alkalmazásának lehetőségét, és megköveteli a tudósoktól, hogy spekulatívabb megközelítéseket alkalmazzanak a játékban. .
A sakkprogramok fejlesztőinek számos döntést kell meghozniuk azok megírásakor. Ezek tartalmazzák:
Lásd még:
A sakk számítógép egy speciális eszköz a sakkozáshoz . Általában a sakkozók szórakoztatására, gyakorlására használják emberi partner hiányában, különféle játékhelyzetek elemzésére, számítógépek egymással való versengésére.
A fogyasztói sakkszámítógépek általában sakktábla formájában készülnek, kijelzővel és kulcskészlettel a szükséges játékműveletek végrehajtásához. Kiviteltől függően előfordulhat, hogy a tábla semmilyen módon nem csatlakozik a számítógép részhez, és nincs benne elektronika, vagy fordítva, lehet, hogy egy kijelző, amely grafikusan jeleníti meg a játék helyzetét.
Az 1980-as évek közepe óta a Szovjetunióban fogyasztói sakkszámítógépeket gyártanak " Elektronika IM -01 ", " Elektronika IM-05 ", " Elektronika IM-29 " ("Sakkpartner"), "Intellect-01", "Intellect" -02" , "Debütálás", "Phoenix", "100 éves Novoszibirszk" és mások.
A programok többsége a mozdulatsoros módszerre épül, vannak heurisztikus módszereken alapuló programok. M. Botvinnik exvilágbajnok és segédprogramozói, B. Shtilman és A. Reznitsky kísérletet tettek egy igazi sakkprogram létrehozására egy sakkmester algoritmusa alapján .
A sakkprogramok fejlesztésében nagy áttörést jelentett a neurális hálózatok használata . Például 2017-ben a DeepMind létrehozott egy neurális hálózati programot , amely több órás önálló tanulás után képes volt legyőzni a legjobb sakk-algoritmusokat. A Stockfish elleni 100 meccses sorozatban az AlphaZero soha nem veszített, és 25 meccset nyert fehérrel és három meccset feketével. Az AlphaZero algoritmust az AlphaGo program alapján hozták létre , amely korábban abszolút bajnok lett a Go játékban . Az AlphaZero algoritmus inkább arra hasonlít, ahogyan az ember sakkozik. Kevesebb pozíciót vesz figyelembe, mint más programok. A szerzők szerint másodpercenként 80 ezer pozíciót becsül, míg a Stockfish esetében 70 millió másodpercenként. Az AlphaGo-val ellentétben az AlphaZero több feladatot-játékot is képes megtanulni egyszerre, és nem csak egyet. Az AlphaZero-t nem tanították meg a játékra, csak alapvető ismereteket adott a játékszabályokról. Az AlphaZero ezután önmagával játszott, és saját maga alakított ki taktikát [7] [8] .
A sakkprogramozással kapcsolatos első kutatást 1950-ben Claude Shannon amerikai matematikus végezte , aki sikeresen elképzelt két fő lehetséges keresési módszert, amelyek használhatók, és elnevezte ezeket "A típusnak" és "B típusnak".
Az A típusú programok az úgynevezett "nyers erő" megközelítést alkalmazzák , minden lehetséges pozíciót meghatározott mélységig megtanulva a Minimax algoritmus segítségével . Shannon azzal érvelt, hogy ez a módszer két okból nem lenne praktikus.
Először is, ha egy tipikus helyzetben körülbelül harminc mozgás lehetséges, körülbelül 12,5 percet vesz igénybe körülbelül 753 millió csomóponti pozíció megtanulása (mindkét oldalra körülbelül három lépéssel előre számolva), még abban a "nagyon optimista" esetben is, amikor a számítógép képes értékelni. egymillió pozíció másodpercenként (negyven év kellett ehhez).
Másodszor, az A típusú programok figyelmen kívül hagyták az úgynevezett statikus állapot problémát azáltal, hogy megpróbálták értékelni a pozíciót a figurák cseréje vagy más fontos lépések (például taktikai kombinációk) kezdetén. Ezért Shannon abból indult ki, hogy az A típusú algoritmussal óriási mértékben megnő a vizsgálandó pozíciók száma, ami jelentősen lelassítja a programot. Ahelyett, hogy a számítógép feldolgozási erejét pazarolta volna a rossz vagy jelentéktelen lépések kivizsgálására, Shannon B típusú programok használatát javasolta. Ennek a módszernek két fejlesztése van:
Ez lehetővé tette a programok számára a fontos lépések nagyobb mélységben történő kiszámítását, és azt ésszerű időn belül. Az első megközelítés kiállta az idő próbáját: minden modern[ mikor? ] a programok a záró "nyugodt" keresést alkalmazzák a pozíció értékelése előtt.
A számítógépes sakkprogramok a sakklépéseket játékfaként kezelik. Elméletileg értékelniük kell az összes lehetséges lépés után bekövetkező összes pozíciót, majd minden lehetséges lépést ezek után, stb. Egy játékos minden lépését " csomópontnak " nevezzük. A lépések számbavétele addig folytatódik, amíg a program el nem éri a keresés maximális mélységét, vagy meg nem állapítja, hogy elérték a végső pozíciót (például matt vagy patthelyzet ). Már a pozíció megítélése alapján választja ki a legjobb stratégiát. Minden pozícióban a játékos lehetséges lépéseinek száma megközelítőleg 35. Négy féllépés (minden játékos két lépése) teljes elemzéséhez körülbelül másfél millió lehetőséget kell feltárni, hatnál - csaknem kétmilliárd. A 3 lépéssel előre végzett elemzés nagyon kevés egy jó játékhoz.
A programozók különböző módokon próbálják korlátozni a rendezendő lépések számát ( a keresőfa levágása - játékfa metszése ). A legnépszerűbb az alfa-béta metszés , amely nem veszi figyelembe azokat a pozíciókat, amelyek alacsonyabb pontszámmal rendelkeznek, mint a már értékeltek.
Hozzávetőleges szoftver implementáció:
private int AlphaBeta ( int color , int Mélység , int alfa , int béta ) { if ( Mélység == 0 ) return Kiértékelés ( szín ); int bestmove ; Vektormozgások = GenerateMoves ( ); for ( int i = 0 ; i < mozog . méret (); i ++ ) { makeMove ( mozog . get ( i )); eval = - AlfaBeta ( - szín , Mélység - 1 , - béta , - alfa ); unmakeMove ( mozog . get ( i )); if ( eval >= béta ) return béta ; if ( eval > alfa ) { alpha = eval ; if ( Depth == defaultDepth ) { bestmove = mozog . kap ( i ); } } } return alpha ; }Példa az első hívásra:
AlphaBeta ( 1 , 6 , egész szám . MIN_ÉRTÉK , egész szám . MAX_VALUE );Az első híváskor a metódus (függvény) a maximális ablakkal kerül meghívásra. A rekurzív hívások során az alfa és a béta változókat előjelfordítással cserélik fel, és "szűkítik" a keresési tömeget.
A második elterjedt módszer az iteratív elmélyítés . Először a játékfát egy bizonyos mélységig bejárják, majd néhány legjobb lépést kiemelnek. A program ezután mélyebben értékeli ezeket a lépéseket, hogy többet megtudjon a következményeikről. Ezt a műveletet addig ismételjük, amíg a program szempontjából a lehető legjobb pálya nem lesz. Ez a megközelítés lehetővé teszi, hogy gyorsan eldobja a kilátástalan játéklehetőségek jelentős százalékát. Például nincs értelme megvizsgálni, mi történik, ha egy dámát gyalogra cserélünk, amikor jobb lépések vannak a pozícióban.
A sakk algoritmusok fontos eleme a pozícióértékelő rendszer . A pozíciót nem lehet teljesen pontosan felmérni, mert ehhez több billió mozdulatsort kellene elemezni a játék elejétől a végéig. Ha lenne olyan függvény, amely lehetővé tenné a pozíció megbízható becslését, akkor a sakkozási feladat leegyszerűsödne a jelenleg elérhető több tucat lépés mindegyikének értékelésére, és nem kellene további lépéseket számolni.
Ezért a pozíció program általi értékelése nagyon közelítő, bár a programok értékelési funkcióit folyamatosan fejlesztik. Az értékelési funkciók általában a gyalog századrészében értékelik a pozíciókat. Ezek a függvények csak néhány egyszerű paramétert értékelnek:
A pozíciókiértékelő funkciók hatástalanok, ha a táblán lévő helyzet minden lépéssel drámaian megváltozik, ha például bábucserére kerül sor, vagy valamilyen sakkkombinációt hajtanak végre. Innen származik a statikus állapot ( nyugalmi állapot ) fogalma és a számítási horizont . Statikus állapotban lassú helyzetharc folyik a sakktáblán, és igen széles a figyelemre méltó számítási horizont. Ez azt jelenti, hogy a döntő változás nem egy könnyen előrelátható jövőben következik be. Ilyen helyzetben a pozíciókiértékelési függvények fontosabbak, mint a lehetséges opciók kiszámításának kísérletei.
Dinamikus helyzetben a pozícióértékelő funkcióra épülő játék teljesen hibás döntésekhez vezethet. Extrém esetben, ha a programnak rövidre hangolt számítási horizontja van, és csak egy rövid távú pozícióértékelést vesz figyelembe, akkor pont abban a pillanatban jöhet el a vég, amikor megtörténik a királynők cseréje, és az egyik már meg kell verni, a másodikat pedig még nem cserélték ki. Egy ilyen állapot program általi értékelése arra a teljesen téves következtetésre vezet, hogy az egyik játékosnak óriási előnye van, miközben az egy mozdulattal eltűnik, amit azonban a program nem lát. Ha az állapot még nem statikus, akkor folytatni kell a cserét a végéig, és értékelni kell a helyzetet, amikor már nincs lehetséges radikális változás. Az emberek általában intuitív módon megkülönböztetik ezt a két helyzetet – a sakkprogramoknak viszont rendelkezniük kell olyan feltételekkel, amelyek lehetővé teszik számukra, hogy megváltoztassák működésüket statikus és dinamikus állapotban.
A nyitásban a mozgásokat nehezebb értékelni . Többség[ mennyit? A ] programok előre megírt nyitókönyvtárakat használnak, amelyekben van egy bizonyos kis számú kezdeti lépés és egy bizonyos számú lépésre a válasz, ami nem állandó, mert a nyitás típusától függ.
Még az 1970-es és 80-as években is nyitva maradt a kérdés, hogy mikor lesz képes egy sakkprogram legyőzni a legerősebb sakkozókat. 1968-ban David Levy nemzetközi nagymester fogadott, hogy a következő tíz évben egyetlen számítógép sem tudja legyőzni őt. 1978 -ban nyert egy fogadást azzal, hogy legyőzte a sakkot (az akkoriban a legerősebb) 4,7-et , de tudta, hogy nem sok idő telik el ahhoz, hogy a számítógépek legyőzzék a világbajnokokat. 1989-ben a Deep Thought program legyőzte Levyt.
De a programok még mindig jóval alatta maradtak a világbajnoki szintnek, amelyet Garri Kaszparov mutatott be, amikor 1991-ben kétszer legyőzte ugyanazt a Deep Thoughtot .
Ez egészen 1996-ig tartott, amikor is Kaszparov és az IBM Deep Blue számítógépe közötti mérkőzés zajlott , ahol a bajnok elvesztette első meccsét. Számítógépes sakkprogram most először győzött le egy világbajnokot normál időkontroll mellett. Kaszparov azonban megváltoztatta a játékstílust: a hátralévő öt meccsből hármat megnyert, kettőt pedig döntetlenre ért. 1997 májusában a Deep Blue továbbfejlesztett változata 3,5-2,5 ponttal legyőzte Kaszparovot. 2003-ban dokumentumfilm készült, amely Kaszparov szemrehányásait dolgozta fel egy sakkozó esetleges IBM általi használatára vonatkozóan, "A meccsnek vége: Kaszparov és a gép" címmel ( Eng . Game Over: Kasparov and the machine ). A film azt állította, hogy a Deep Blue sokat hangoztatott győzelmét az IBM piaci értékének növelése érdekében csalták ki. Ezek a vádak részben jogosak voltak. A szabályok lehetővé tették a fejlesztők számára, hogy a játékok között módosítsák a programot. A Deep Blue -t a játékok között cserélték, hogy a gép jobban megértse Kaszparov játékstílusát, így elkerülhető a végjáték csapdája , amelybe a program kétszer is beleesett.
Az IBM a meccs után leszerelte a Deep Blue-t, azóta egyszer sem játszották le ezt a számítógépet. Ezt követően további Ember vs. Machine mérkőzésekre került sor.
A számítási teljesítmény növekedésével a személyi számítógépeken futó sakkprogramok a legjobb sakkozók szintjét kezdtek elérni. 1998-ban a Rebel 10 program legyőzte Viswanathan Anandot , aki akkor a világ második helyezettje volt. Azonban nem minden játékot játszottak szabványos időszabályzóval. A meccs nyolc játékából négyet villámvezérléssel játszottak (öt perc plusz öt másodperc lépésenként), amit Rebel 3-1-re megnyert. Még két játék félvillanyvezérléssel zajlott (egyenként tizenöt perc), amit a program meg is nyert (1,5-1). Végül az utolsó két játszmát normál versenyidő-ellenőrzéssel játszották (két óra 40 lépésre, egy óra a többi lépésre), és itt Anand nyert 0,5-1,5 ponttal. Akkoriban a gyors játékokban a számítógépek jobban játszottak, mint az emberek, de a klasszikus időszabályozás mellett a számítógép előnye még mindig nem volt olyan nagy az emberrel szemben.
2000-ben a Junior és Fritz kereskedelmi sakkprogramok döntetlent tudtak dönteni a korábbi világbajnokok, Garri Kaszparov és Vlagyimir Kramnyik ellen .
2002 októberében Vlagyimir Kramnik és Deep Fritz nyolcmeccses mérkőzésen versenyzett Bahreinben . A mérkőzés döntetlennel zárult. Kramnik a második és a harmadik játékot hagyományos számítógép-ellenes taktikával nyerte meg – óvatosan játszott, és hosszú távú előnyre törekedett, amelyet a számítógép nem láthat a keresőfájában. Ennek ellenére Fritz megnyerte az ötödik játszmát Kramnik baklövése után. Sok versenykommentátor nagyon izgalmasnak nevezte a hatodik meccset. A középjáték elején jobb helyzetben lévő Kramnik megpróbált feláldozni egy darabot, hogy erős taktikai támadást hozzon létre (egy ilyen stratégia nagyon kockázatos számítógépekkel szemben). Fritz erős védelmet talált, és ez a támadás jelentősen rontotta Kramnik helyzetét. Kramnik feladta a játékot, és azt hitte, hogy a meccs elveszett. A későbbi elemzések azonban azt mutatták, hogy Fritz valószínűleg nem tudta volna megnyerni a játékot. Az utolsó két meccs döntetlennel zárult.
2003 januárjában Garri Kaszparov a Junior program ellen játszott New Yorkban . A mérkőzés 3-3-as eredménnyel zárult.
2003 novemberében Garri Kaszparov az X3D Fritz -zel játszott . A mérkőzés 2-2-es eredménnyel zárult.
2005-ben a Hydra , egy speciális sakkszoftver és -hardverrendszer 64 processzorral, 5,5 ponttal legyőzte Michael Adams sakkozót, aki akkoriban a világ hetedik legjobb Elo sakkozója volt. -0,5 (bár Adams hazai felkészülése jóval alacsonyabb volt, mint Kaszparové 2002-ben). Egyes kommentátorok úgy vélték, hogy Hydra végre tagadhatatlan előnyben lesz a legjobb sakkozókkal szemben.
2006 novemberében-decemberében a világbajnok Vlagyimir Kramnik a Deep Fritz programmal játszott . A mérkőzés az autó győzelmével ért véget, 2-4-re.
További Endgame adatbázisok
Számítógépeket használnak bizonyos végjátékhelyzetek elemzésére . Az ilyen végjáték-adatbázisok utólagosan jönnek létre , azokból a pozíciókból indulva ki, ahol a végeredmény ismert (pl. ahol az egyik oldalt mattot tették), és megnézik, hogy milyen más pozíciók vannak mozgási távolságon belül, majd egy távolodik ezektől, és így tovább. Ken Thompson , ismert a UNIX operációs rendszer vezető tervezőjeként úttörő volt ezen a területen.
A végjáték már régóta a sakkprogramok észrevehető gyengesége, mivel a keresés mélysége nem volt elegendő. Így még a mester erejét játszó programok sem képesek nyerni a végjátékban, ahol egy közepesen erős sakkozó is kikényszeríthetné a győzelmet.
De a számítógépes elemzés eredményei néha meglepték az embereket. 1977-ben Thompson Belle sakkgépe a király+bástya versus király+királynő végjáték-adatbázisait felhasználva elméletileg vesztes végjátékokat tudott kivonni a címzett sakkozók ellen.
A legtöbb nagymester megtagadta, hogy a számítógép ellen játsszon a dáma kontra bástya végjátékban , de Walter Brown elfogadta a kihívást. A pozíciót úgy alakították ki, hogy elméletileg 30 mozdulattal lehetett nyerni hibátlan játékkal. Brown két és fél órát kapott ötven lépésre. Negyvenöt mozdulat után Brown beleegyezett a döntetlenbe, mivel az utolsó öt lépésben nem tudott nyerni. A végső pozícióban Brown csak tizenhét mozdulat után tudott mateot.
2002 - ben megjelentek a főbb végjáték - adatbázis - formátumok , köztük az Edward Tablebases , a De Koning Endgame Database és a Nalimov Endgame Tablebases , amelyeket ma már számos sakkprogram támogat , mint például a Rybka , a Shredder és a Fritz . Az öt vagy kevesebb darabból álló végjátékokat teljes mértékben kielemezték. A hatfős végjátékokat a magányos király elleni ötfős helyzetek kivételével elemezték. Mark Burzhutsky és Yakov Konoval hét darabbal elemzett néhány végjátékot. Ezekben a végjáték-adatbázisokban az öntés lehetetlennek tekinthető.
Az adatbázisok úgy jönnek létre, hogy a memóriában tárolják az eddig előfordult pozícióbecsléseket, és ezekkel az eredményekkel csökkentik a keresési fát, ha ilyen pozíciók ismét előfordulnak. Az a puszta célszerűség, hogy megjegyezzük az összes korábban elért pozíció pontszámát, azt jelenti, hogy a végjáték megoldásának korlátozó tényezője egyszerűen a számítógép memóriája. A számítógépes memória kapacitásának növekedésével a megnövekedett összetettségű végjátékok előbb-utóbb megoldódnak.
Egy végjáték-adatbázist használó számítógép a bennük lévő pozíció elérésekor hibátlanul tud játszani, és azonnal megállapítja, hogy nyerő, vesztes vagy döntetlen a pozíció, valamint megtalálja a leggyorsabb és leghosszabb utat az eredmény eléréséhez. A pontos pozícióbecslés ismerete a számítógép erősségének növelésekor is hasznos, mivel így a program a szituációtól függően megválaszthatja a cél elérésének módjait [vagyis egyszerűsítéssel és cserével, hogy egyértelműen vizsgált pozíciót kapjunk].
A számítógépek észrevehetően megelőzik az embereket a rövid taktikai manőverekben, amelyek a program keresésének mélységébe esnek. Különösen veszélyes ilyenkor a királynő, amely tökéletes a rövid távú manőverekhez. Ezért a számítógép elleni játék során az emberek gyakran megpróbálják rávenni a programot királynők cseréjére. Ez történik például akkor, ha valaki a játék elején szándékosan ront a pozícióján, és a számítógép ezt előnyösnek tartja számára. Ha a program előnyben részesíti a pozíció értékelését, akkor nagy valószínűséggel darabokat cserél, és ez előnyös az ember számára. Természetesen a programozók tanultak az ilyen "trükkökről", és ezt figyelembe veszik programjaik legújabb verzióiban.
Ehelyett a sakkozóknak olyan hosszú távú manőverekkel kell játszaniuk a számítógép ellen, amelyeket a program nem láthat a keresési mélységén belül. Például Kramnik nyert Deep Fritz ellen egy hosszú távú átadott gyalogelőleggel, amelynek előnyeit Fritz túl későn fedezte fel.
A sakkprogramok sikere azt sugallja, hogy lehet olyan programokat írni, amelyek más játékokban is ugyanolyan jól játszanak, mint például a shogi vagy a go .
Hasonló algoritmusok talán más sakkfajták játszásakor is használhatók. A shogiban több a mozgási lehetőség, az anyagi előny sokkal kevesebbet jelent, de a pozíciós előny sokkal jelentősebb. Komplex rendszerek készülnek a király biztonságának garantálására, de számítógépnek nem könnyű ezeket a rendszereket értékelni. Ebben a játékban a darabok száma állandó, ezért a játék idővel nem válik könnyebbé, lehetetlenné téve a végjátékok bázisának létrehozását. Itt sincsenek teljesen statikus állapotok, mert a játék egész idő alatt pozícióharcba süllyed. Ezért jó programot írni shogi játékhoz sokkal nehezebb, mint egy sakkprogramot, bár a sakkjátszmák terén szerzett sok tapasztalat felhasználható erre a játékra. .
A Go igazi kihívássá vált a programozók számára . A Go számítás bonyolultsága több nagyságrenddel nagyobb, mint a sakkban. Minden lépésnél körülbelül 200-300 mozdulat lehetséges, míg a kőcsoportok életének statikus felmérése gyakorlatilag lehetetlen. Itt egy lépés teljesen tönkreteheti az egész játékot, még akkor is, ha a többi lépés sikeres volt. Ezért a sakkozáshoz sikeres algoritmusok nem elegendőek a Go professzionális szintű játékához. 2015 októberében azonban a Google DeepMind által fejlesztett AlphaGo számítógépes program először nyert go-ban a 2 danos profi Fan Hui ellen . 2016 márciusában pedig egy meccset nyert Lee Sedollal , egy 9 danos profival, 4-1-re.
| Sakk | |
|---|---|
| Főbb cikkek | |
| Sakkleltár | |
| sakkszabályok | |
| Fogalmak szójegyzéke | |
| Sakk taktika | |
| Sakkstratégia | |
| debütál | |
| Végjáték | |
| Sakkoldalak |
|
| Sakk programok | |