Šachový program

	A	b	C	d	E	F	G	H
8. místo									8. místo
7. místo									7. místo
6. místo									6. místo
5									5
4. místo									4. místo
3									3
2									2
1									1
	A	b	C	d	E	F	G	H

Dvourozměrná šachovnice zobrazená na obrazovce mnoha šachovými partiemi

Šachový program je počítačový program , který je schopen hrát šachy . Běží buď na PC, nebo na šachových počítačích speciálně vyrobených pro hraní šachů . Vývoj šachových programů je disciplínou počítačových šachů .

Zatímco v dřívějších šachových programech byla celá funkčnost sloučena do jednoho programu, moderní šachový software se obvykle skládá ze dvou částí: takzvaného motoru - skutečného šachového programu, který vypočítává tahy hrané počítačem - a šachového frontendu , displeje a interakce uživatele převezme. Pro komunikaci mezi šachovým modulem a frontendem existují dva široce používané otevřené šachové komunikační protokoly : protokol XBoard a novější Universal Chess Interface (UCI). Pozice a hry se ukládají v proprietárních formátech nebo ve formátu otevřeného přenosného zápisu her (PGN).

Aktuální programy

Jeden z nejlepších známých volných šachových programů je lstivý , An open source projekt by Robert Hyatt . Dalším mocným šachovým programem je Fruit , který v roce 2005 obsadil druhé místo v mistrovství světa počítačových šachů . Až do verze 2.1 je Fruit k dispozici také pod licencí open source, stejně jako Glaurung 2.1, což je přibližně stejná síla.

Open source program Stockfish vzešel z Glaurungu. Je k dispozici pro různé operační systémy s 32bitovou nebo 64bitovou architekturou a je jedním z nejvýkonnějších šachových programů vůbec. Stockfish kvůli svému otevřenému vývoji není podezřelý z plagiátorství. Je k dispozici zdarma.

Od roku 2014 vedou žebříčky , které jsou určeny pomocí her mezi programy, v čele s komerčním programem Komodo a vývojem open source Stockfish popsaným výše.

Komerční program Houdini je už léta jedním z nejlepších hraní, ale je kontroverzní. Programátor šachového programu Rybka tvrdí, že mu byl ukraden zdrojový kód a že na tomto základě byly vytvořeny různé, velmi silné šachové programy ( rodina IPPOLIT ), včetně Houdiniho. Pro toto tvrzení nebyl poskytnut - alespoň veřejně - žádný důkaz. Programátor šachového programu Rybka prý vychází z Ovoce. Kvůli této kontroverzi nebyl Houdini - stejně jako některé další programy rodiny Ippolit - dočasně zařazen různými operátory žebříčkových seznamů. V dalším průběhu programu byla Rybka klasifikovány jako plagiátorství u ovoce , čímž byla Rybka zbaven všech titulů a úspěchů. Programátor Rybka dostal doživotně zákaz všech šachových turnajů v počítači. Na druhé straně Houdini, který má zase vycházet z Rybky, byl tehdy uznán jako nejsilnější šachový motor a byl použit k analýze společně s frontendovým akváriem na mistrovství světa v šachu.

Pro začátečníky existuje škálovatelný engine, který může být omezen v hodnocení, jako je Ufim.

José - šachová databáze a šachové rozhraní

Pro pohodlné ovládání je také vyžadováno uživatelské rozhraní zvané šachový frontend. K tomuto účelu lze použít například program XBoard . Běží pod operačními systémy Microsoft Windows (pod názvem WinBoard ), Unix / Linux a Amiga a je dodáván společně s GNU Chess . Grafická šachová frontendová databázová funkce založená na Javě je také pod José publikována GPL . Dalším populárním uživatelským rozhraním ve Windows pro více než 250 šachových programů je Arena , která je k dispozici jako freeware. Existuje také další freeware, který je vhodný pro začátečníky, například Arasan . Šachový front KDE je Knights.

Ambiciózní hráči se často uchylují ke komerčním programům, které kromě čisté šachové hry nabízejí také mnoho dalších možností, jako je analýza hry a šachový trénink. Programy Shredder a Fritz by měly být velmi dobře známé . Tyto programy distribuuje mimo jiné hamburská společnost ChessBase , která stále více dominuje (evropskému) trhu s profesionálním šachovým softwarem. Program Rybka se od roku 2005 dostává na titulky odborných časopisů a počítačových fór . Rybka má silné poziční a strategické šachové schopnosti, a proto je lidskému způsobu hraní bližší než většina ostatních šachových programů. Rybka vedl nejdůležitější žebříček počítačových šachů - v němž nebyl uveden Houdini - s náskokem 50–150 bodů. Šachoví velmistři jako Anand , Topalow nebo Morosewitsch používali Rybku k analýze, mezitím se častěji používají Stockfish, Critter nebo Houdini.

Nyní můžete hrát kvalitní šachy na mobilních telefonech , PDA a dalších handheldech . Na Palm OS-založené zařízení, například OpenChess je volný šachový program, který vám umožní vybrat si mezi několika šachových motorů.

S bezplatným programem ChessV si můžete také vyzkoušet různé šachové hry .

konstrukce

Hlavními součástmi šachového programu jsou krok generátor, vyhodnocovací funkce a program součástí pro řízení vyhledávání a výběr dalšího pohybu. Počínaje aktuální pozicí (herní situací) program provede iterativní hloubkové vyhledávání . V každé iteraci provádí různé posloupnosti posloupností v pořadí, vyhodnocuje dosažené pozice (listy vyhledávacího stromu ) pomocí vyhodnocovací funkce a na základě těchto hodnot listů vyhodnocuje vnitřní uzly vyhledávacího stromu a tím i pohyby které v každém případě podle principu minimaxu vedou k uzlu. Po poslední iteraci hraje tah s nejvyšší hodnotou v kořenovém uzlu (který představuje aktuální pozici).

Důležitou vlastností šachového programu je typ vnitřního zobrazení desky, které používají všechny ostatní součásti programu.

Vlakový generátor a interní displej desky

	A	b	C	d	E	F	G	H
8. místo									8. místo
7. místo									7. místo
6. místo									6. místo
5									5
4. místo									4. místo
3									3
2									2
1									1
	A	b	C	d	E	F	G	H

Příklad
herní pozice použitý ve všech následujících zobrazeních : 1. e4 e5 2. Nc3

Generátor tahů generuje seznam všech legálních tahů (v souladu s pravidly) v určité poloze (možné pohyby hracích kamenů). Ve výchozí pozici je možné 20 tahů (16 tahů pěšce, 4 rytířské tahy), v dalším průběhu hry můžete počítat v průměru s přibližně 40 legálními tahy na každé pozici, v koncovce méně. Generátor tahů musí také vzít v úvahu komplikované pohyby, jako jsou rošády , změny pěšců a tahy kolem sebe .

Zpravidla nechává generátor vlaku vypočítat všechny pseudolegální pohyby, tzn. to znamená, že se nerespektuje vláda králů; z. B. takový krok by mohl krále přesunout na ohrožené pole. Díky tomu je generátor vlaku podstatně jednodušší a rychlejší. Nelegální tahy jsou později tříděny podle části programu, která řídí vyhledávání: Tah byl nezákonný, pokud seznam tahů, který následuje, obsahuje tah, který porazí krále.

Pro kódování čísel jsou v příkladech použita následující celá čísla:

Implementace generátoru vlaku úzce souvisí s interním zobrazením desky. Jsou zde čtyři důležití zástupci:

Zobrazení 12 × 10

Herní plán je mapován na jednorozměrné pole se 120 prvky . Index (čísla v závorkách) obvykle běží řádek po řádku, zde od 0 (vlevo nahoře) do 119 (vpravo dole). Kromě 64 platných polí obsahuje pole pole, kterých by figurka dosáhla při opuštění desky a která tvoří hranu kolem běžné desky. Na těchto hraničních polích je uložena určitá hodnota (zde −1), a pokud by se figurka přesunula na pole s tímto vstupem, znamená to, že by s ní nechala desku. To lze snadno zjistit, protože stejně musíte zkontrolovat, zda je cílový prostor obsazen vaším vlastním dílem, což by činilo nezákonný tah. Díky této technice je vlakový generátor rychlý a snadný. Levý a pravý okraj na každé straně musí být pouze jeden čtverec, protože rytíř, který táhne bokem z hrací plochy, vždy přistane buď na levé nebo pravé hranové řadě.

Přidáním následujících konstant do indexu pole lze určit možná cílová pole pro obrázek v tomto poli.

Podívejme se na černého rytíře na náměstí 27 (NG8). Sečtením těchto konstant do 27 získáme potenciální cílové čtverce: 6, 8, 15, 19, 35, 39, 46 a 48. Pokud je hodnota v cílovém čtverci −1, tah není možný, protože rytíř by se pohyboval přes okraj. Pokud je hodnota 1 nebo 10 až 14, je na poli bílý kus, který lze zachytit, a pokud je roven nule, je možný přesun do prázdného pole. Rytíř tedy může provést tři různé pohyby na cílových polích 35, 46 a 48, které jsou přidány do seznamu tahů. Pokud by generátor tahů měl generovat pouze legální tahy - a ne všechny pseudolegální tahy, stále musíte dávat pozor na to, zda je rytíř svázán, nebo zda existuje šachový povel, který musíte odrazit.

Podobné je to s ostatními typy postav. Ti s dlouhými kroky (královna, biskup, věž) nemohou přeskočit obsazený prostor. Poté, co toho bylo dosaženo, není v tomto směru již možný další pohyb a můžete přejít do dalšího směru.

Zatímco generátor vlaku je poměrně jednoduchý a rychlý, funkce statického vyhodnocení jsou pomalejší.

Zobrazení 8 × 8

Zobrazení 8 × 8 je nejblíže lidskému pohledu. Program GNU Chess je používal až do verze 4. Deska je modelována jako jednorozměrné pole, jak je tomu u 12 × 10, zde s rozsahem indexu od 0 do 63 (alternativně 1 až 64). Dvourozměrné pole se zdá být bližší, ale je pomalejší, protože zde musí být pole označeno dvěma čísly (řádek a řádek), do generování tahu musí být přidána konstanta a při přístupu k poli je výpočet adresy pomocí dva indexy jsou složitější.

Vlakový generátor je obvykle složitější a pomalejší než u displeje 12 × 10, protože speciální případy na okraji musí být řešeny samostatně. Statická vyhodnocovací funkce však funguje efektivněji, protože řádek a řádek, na kterém se pole nachází, lze určit rychlými bitovými operacemi : AND operace indexu se 7 výsledky v řádku a posunutí o 3 bity doprava vede k řádek (s uspořádáním polí řádek po řádku a rozsahem indexu 0 až 63). Na druhou stranu s deskou 12 × 10 musíte dělit 10. Funkce bodování tyto informace často potřebuje, např. B. pro rozpoznávání dvojitých pěšců nebo Isolani .

I s deskou 8 × 8 lze vlaky generovat rychle a snadno pomocí přístupu ke stolu, což však značně zvyšuje spotřebu paměti. GNU Chess používá pro každý typ obrázku dvourozměrné pole nextpos se 64 x 64 prvky, jejichž položky jsou vypočítány předem. Pokud jej indexujete počátečním čtvercem f figurky a jedním z jejích cílových polí, můžete odečíst další cílové pole pro figuru. nextpos (f, f) vrací první cílové pole. U kusů s dlouhým krokem je také pole nextdir , ze kterého se při obsazení cílového pole načte další cílové pole (první pole v novém směru pohybu). Pokud již neexistuje žádné cílové pole, vrátí obě hodnotu f.

Další možností je trojrozměrné pole, které obsahuje všechna cílová pole pro všechna pole a typy obrázků, na které tento obrázek může z tohoto pole dosáhnout. Třetí index běží přes tato cílová pole. Spotřeba paměti je zde nižší, zvláště pokud je použito dvourozměrné pole ukazatelů, z nichž každé ukazuje na hromádkové pole příslušné velikosti, odpovídající odlišnému počtu cílových polí. Záznamy jsou rozděleny na dvě části: první část je index cílového pole a druhá počet polí následujících v poli, které mají být přeskočeny, pokud je cílové pole obsazeno (nebo přímo další index v poli).

0x88 reprezentace

Jedná se o další vývoj displeje 8 × 8. V případě zobrazení řádku po řádku se 16 poli na řádek tvoří šachovnici levá oblast 8 x 8 polí, pravá oblast 8 x 8 polí se nepoužívá. Pokud by se obrázek pohyboval přes hranu, lze to poznat podle bitů po bitech A operace indexu cílového pole s hexadecimálním číslem 0x88 (= 136). Pokud je výsledek nula, index pole označuje platné pole, jinak by figurka opustila hrací plochu. Řádek a řádek pole lze vypočítat podobně jako na desce 8 × 8 posunutím 4 bitů doprava nebo ANDing pomocí 7.

S touto reprezentací můžete také použít indexový rozdíl mezi dvěma čtverci k určení, zda a s jakou figurkou je možný přesun z jednoho políčka na druhé. Například pohyb z věže je možný pouze tehdy, je -li rozdíl v rozsahu -7 až 7 nebo násobek 16. To není možné u reprezentace 8 × 8 nebo 10 × 12, protože toto kritérium splňují také páry polí, které neumožňují odpovídající pohyb. Čtverce h4 a a5 mají například indexový rozdíl menší než 8, přestože není možný žádný pohyb věží.

Bitboardy

Některé moderní šachové programy, například Rybka , Crafty nebo GNU Chess 5, používají bitboardy . Ty mohou být prováděny zejména efektivně na 64bitových počítačových architektur , kde počet bitů v několika registr / slovo odpovídá počtu oborů. Každá bitová pozice ve slově je přiřazena poli na desce a bit v této pozici udává odpovídající pole.

Následující příklad ukazuje pozici po tahech 1. e4 e5 2. Nc3 s osmi 64bitovými registry. Registr Bobsahuje 1-bit všude, kde je na příslušném poli pěšec (jakékoli barvy). Existuje také registr pro každý z ostatních typů figur. WEIa SCHoznačte, kde se nachází bílá nebo černá postava. Kvůli přehlednosti jsou bity s hodnotou 0 reprezentovány -.

         Reihe     8        7        6        5        4        3        2        1
         Linie  abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh
    Bitposition 63    56       48       40       32       24       16        8        0
 Registername   |      |        |        |        |        |        |        |        |
            |   |      |        |        |        |        |        |        |        |
Bauern      B   -------- 1111-111 -------- ----1--- ----1--- -------- 1111-111 --------
Türme       T   1------1 -------- -------- -------- -------- -------- -------- 1------1
Springer    S   -1----1- -------- -------- -------- -------- --1----- -------- ------1-
Läufer      L   --1--1-- -------- -------- -------- -------- -------- -------- --1--1--
Damen       D   ---1---- -------- -------- -------- -------- -------- -------- ---1----
Könige      K   ----1--- -------- -------- -------- -------- -------- -------- ----1---
Weiss     WEI   -------- -------- -------- -------- ----1--- --1----- 1111-111 1-111111
Schwarz   SCH   11111111 1111-111 -------- ----1--- -------- -------- -------- --------

Díky rychlým bitovým operacím lze nyní informace o poloze vypočítat pro všechna pole paralelně. Například T & WEIvšechny pozice bílých věží lze určit operací AND a ((B & SCH) >> 8) & ~(WEI | SCH)poskytuje bitový vzor s poli, na kterých se černý pěšec může pohybovat jediným krokem. Bit posun doprava (na spodním konci) označuje >> na  negaci a  do OR odkaz. ~|

Vyhodnocovací funkce

Funkce vyhodnocení přináší heuristické vyhodnocení pozice bez určení nástupce. Skládá se z materiálu a polohové komponenty. Polohová komponenta doplňuje materiál, protože pevnost kusů závisí také na jejich vzájemném umístění. Zjednodušené hodnotící funkce mohou provádět i lidští hráči, ale to má pouze historický význam. Počítačové programy velmi často ukazují hodnocení herní situace numericky (v takzvaných pěšcových jednotkách ), přičemž kladné hodnoty udávají výhody a záporné hodnoty naznačují nevýhody pro určitého hráče.

materiál

Pro bodování materiálu se hodnoty sečtou pro figurky na hrací ploše. Přibližná hodnota typů kusů v ¹ / ₁₀₀ pěšcových jednotkách je uvedena v následující tabulce.

Bílé figurky (nebo ty, které jsou na tahu strany) se počítají jako kladné a černé figurky (nebo ty z následující strany) se počítají jako negativní. Král není třeba počítat, protože obě strany mají po celou hru krále.

pozice

Poziční určit pořadí, je úkolem větší složitosti, různé šachové programy se od sebe liší v jasné. V komerčních programech zůstává dobře udržovaným tajemstvím. Při pozičním hodnocení se pokouší vyhodnotit pozice na základě šachově relevantních parametrů. Parametry relevantní pro šachy lze zhruba klasifikovat na králové zabezpečení, strukturu pěšců, kontrolovaná a ohrožená pole a také na vývoj figurek. Například pozice, ve které jsou věže stále zúžené mezi rytíři a pěšci, je hodnocena hůře než ta, ve které jsou věže již na otevřených liniích.

V těchto kategoriích existuje prakticky libovolný počet parametrů (pro struktury pěšců , například prošlé pěšce , dvojité pěšce , páky , berany , izolátory , řetězy pěšců ; například pro královskou bezpečnost: může královský hrad snadno doleva nebo doprava? Může zůstat ve středu? Jsou pěšci před králem?). Dává smysl nejprve extrahovat tyto parametry z dané pozice hodnotově neutrálním způsobem. Šachoví programátoři stojí před rozhodnutím, kolik výpočetního času by měli strávit na poziční komponentě sofistikované vyhodnocovací funkce a jaké parametry by měly být dokonce zahrnuty: Čím hlouběji mohou šachové programy analyzovat vyhledávací strom, tím dříve převede poziční výhody do výhod materiálu se stanou viditelnými.

Statická vyhodnocovací funkce

Pokud šachový program dokáže efektivně určit hodnoty těchto parametrů na pozici, musí být vzájemně porovnány. Vážení polohové složky lze provádět částečně automaticky analýzou šachových databází nebo hraním proti jiným šachovým programům. Pokud k tomu dojde před vývojem programu, hovoří se o funkci statického hodnocení. Jednoduše strukturované vyhodnocovací funkce používají poziční váhy pro šest typů pěšců pro poziční komponentu, ale pro úvodní, prostřední a koncovou hru se liší.

S výjimkou hraničních případů, jako jsou koncové hry nebo situace spojenectví nebo patové situace, nemůže funkce vyhodnocení poskytovat žádné objektivně správné výsledky. Sloučením materiálové a polohové složky do jednoho vyhodnocovacího čísla umožňuje vyhodnocovací funkce třídění a výběr „nejlepšího“ nebo „nejhoršího“ tahu.

Funkce dynamického hodnocení

Hodnotící funkce je zpravidla implementována programátorem a během hry se již nemění. Rozšířenou možností je určit srovnatelné pozice ze šachové databáze během hry a optimalizovat tak vážení pozičních parametrů. To je více v souladu s lidským přístupem. Zkušený hráč bere v úvahu kritéria, jako je zabezpečení krále nebo předané pěšce, a také zohledňuje známé hry a jejich výsledky.

Řízení vyhledávání a výběru vlaku

Ovládání vyhledávání je v zásadě založeno na herním stromu . Obsahuje, počínaje aktuální pozicí (kořenový uzel), všechny pohyby přitahující osoby, poté opět všechny možné pohyby odezvy následující osoby a tak dále, v každém případě až do dosažení koncové polohy (kamarád, patová situace, technická remíza) nebo opakování pozic). Herní strom je obvykle příliš velký na to, aby se dal úplně vypočítat, takže program je omezen na jeho část (vyhledávací strom).

V nejjednodušším případě program pracuje podle strategie A , tzn. To znamená, že vypočítá všechny možné sledy vlaků do určité hloubky (počet po sobě jdoucích vlaků), která je omezena výpočetním výkonem a dostupným časem. Každá pozice, která vznikne, je hodnocena. Pokud se nejedná o koncovou polohu, jako je mat, použije se funkce heuristického hodnocení. S algoritmem Minimax jsou tahy hodnoceny v kořenové pozici a je hrán nejvýše hodnocený tah.

Protože počet zkoumaných pozic exponenciálně roste s hloubkou, na druhou stranu vyšší hloubka přináší odpovídající zlepšení úrovně dovedností, za přibližně 50 let vývoje programu byl vynalezen celý arzenál akceleračních opatření, která lze rozdělena do dvou skupin. Někteří se snaží zmenšit velikost vyhledávacího stromu pomocí obecných algoritmů počítačové vědy, například:

• Hledání alfa-beta (postup Negamax)
• Hashovací tabulka pro detekci změn vlaku
• Hledání nulového pohybu

Hledání alfa-beta odřízne části vyhledávacího stromu, které nemusí být brány v úvahu pro určení nejvýše hodnoceného tahu v kořenovém uzlu. Tato technologie hodně šetří: Při dobré implementaci se dosažitelná hloubka téměř zdvojnásobí.

Omezená výpočetní hloubka často umožňuje programu přehlédnout taktickou kombinaci. Abyste to zmírnili, prohloubíte jednotlivé zajímavé sekvence tahů, například podle šachových pravidel nebo tahů, které oslabují soupeřovu královskou pozici, abyste snáze objevili kombinace kamarádů. Takzvaná heuristika rekapitulace prohlubuje pohybové sekvence, které obsahují výměnu, aby bylo možné lépe odhadnout důsledky výměny. Metoda singulárních rozšíření ( německy  „izolované rozšíření“ ) prohlubuje hledání vynucených (vynucených) sekvencí tahů, tedy v případech, kdy existuje pouze jedna „rozumná“ odpověď pro jednu nebo obě strany.

Dalšími technikami akcelerace je použití zjednodušených vyhodnocovacích funkcí podle tahových příkazů, které jsou považovány za málo užitečné, a také přírůstkové hodnocení, které ne vždy přepočítává hodnotu pozice, ale aktualizuje ji, když je tah vyrobeno. Některé programy dělají velkou část hodnotící práce tím, že analyzují polohu kořenů a ukládají výsledky do datových struktur, které pak značně zjednodušují a urychlují vyhodnocení listů (např. Tabulky polí s obrázky).

Některé programy (nebo ne vždy) nevypočítávají všechny pohyby, které jsou v pozici možné ( strategie B ). Hodnoty vlaků jsou heuristicky odhadnuty, poté jsou do vyhledávacího stromu zahrnuty pouze ty vysoce hodnocené. To napodobuje chování lidského hráče. Vyhledávací strom se výrazně zmenší, ale riskujete, že heuristika někdy dobrý krok přehlédne. Tyto postupy jsou mnohem obtížněji implementovatelné než strategie A. Nelze je snadno přenést ani do jiných her, jako je Go , protože kritéria pro výběr tahu jsou zcela odlišná.

Výpočet nesmíte přerušit a provést vyhodnocení listů, když je šarže uprostřed směny; to by mělo za následek zkreslenou materiálovou bilanci. Pokud strana právě porazila krytý kousek a je zde ohodnocena, obdržíte pro tuto stranu falešnou převahu. Nápravou, která se často používá, je takzvané klidové hledání: V poloze na listu se spočítají všechny tahy a pak opět jen tahy odpovědi atd., Přičemž méně slibné tahy se obvykle odříznou a maximální délka sekvence Impact je omezena, aby celá věc netrvala příliš dlouho. V každé takto dosažené poloze je vyhodnocení ruky prováděno heuristickou vyhodnocovací funkcí a hodnota polohy je maximum hodnoty ruky a hodnot tahů. Ruční hodnota znamená hodnoty netahajících tahů, protože se může stát, že každý úder je chybou a je nejlepší zde nezachytit.

Knihovny a databáze

Otevírání knihovny

Šachy se hrají po dobu soutěže, což znamená, že pro určitý počet tahů je k dispozici pouze definované množství času. Mnoho šachových programů je proto vybaveno otevírací knihovnou, do které je uloženo velké množství „dobrých“ tahových příkazů v úvodní fázi šachových her. V počáteční fázi šachové hry program vyhledá v této knihovně, který pohyb je nejvhodnější v konkrétní pozici na šachovnici. Tato „kontrola“ je rychlejší než výpočet tahu. Takto uložený výpočetní čas je pak k dispozici programu v pozdějších fázích hry. Proces ukládání pozic na desce včetně „dobrých“ tahů je užitečný pouze pro otevření a koncovou hru, protože počet pozic na desce je zde stále zvládnutelný. Otevírací knihovny komerčně dostupných programů rostou. Většinou jsou generovány z mistrovských her. S tím je spojeno riziko, že budou přijaty nepozorované chyby, které by program nemohl hrát na základě vlastních výpočtů.

Koordinace otevírací knihovny s funkcí hodnocení použitou později ve hře hraje velkou roli v síle hry.

Databáze koncových her

V koncovce , kdy na desce zbývá jen několik figurek, můžete předem vypočítat optimální tah pomocí úplné analýzy ( metoda hrubé síly ). Existuje poměrně málo pozic koncových her, ve kterých by lidské myšlení, ale také počítačová analýza v reálném čase byla zcela zahlcena. Mnoho šachových programů proto používá databáze koncových her, které obsahují všechny možné pozice se 3, 4, 5, 6 nebo dokonce 7 figurkami a také jejich výsledek (pokud je hra optimální). Vytváření databází koncových her sahá až ke Kenu Thompsonovi . Prvních šest kamenných figur vypočítal Lewis Stiller plně v roce 1991 a všech sedm kamenných figur je zaznamenáno od roku 2012.

Šachová databáze

Šachové databáze obsahují hrané hry. Pomáhají například se studiem vernisáží a přípravou na dalšího soupeře.

Otevírací knihovny lze vygenerovat z databáze pro šachové programy. Během hry je také možné určit srovnatelné pozice z šachové databáze a optimalizovat parametry hodnocení polohy (viz výše) s přihlédnutím k tam zaznamenanému průběhu hry (funkce dynamického hodnocení).

příběh

Historie šachového programu je velmi úzce spjata s historií šachového počítače a obvykle ji nelze zpracovat samostatně. Zde je popsán pouze vývoj základních algoritmů. Mediálně efektivní soutěže s hráči světové úrovně v posledních letech najdete v šachových počítačích ve hře proti lidem .

Konrad Zuse

V letech 1942 až 1945 napsal Konrad Zuse první šachový program na světě ve svém nově vyvinutém programovacím jazyce Plankalkül . Jazyk byl poprvé implementován v 70. letech minulého století.

Alan Turing

Britský matematik a lámač kódu Alan Turing vyvinul metodu, která každému možnému tahu přiřadí hodnotu. Vždy je třeba vypočítat nejlepší tah. Turingův šachový program byl založen na následujících principech:

• Každý kus získal určitou hodnotu: pěšec = 1; Propojka = 3; Běžec = 3,5; Věž = 5; Královna = 10 a Král = 1000 (aby to nikdy nebylo možné obětovat).
• Byly prozkoumány všechny bílé tahy a všechny černé protitahy. Pokud byl White schopen provést úder, pak byly zkoumány všechny údery soupeře, všechny následující tahy Whitea atd., Dokud pozice nebyla „mrtvá“, to znamená, dokud nedojde k žádným dalším úderům a žádnému kamarádovi. Ve výsledných pozicích byl proveden počet figur a byl vybrán tah, který získal nejvíce materiálu nebo nejméně. Protože však většina tahů, které jsou k dispozici pro výběr, přinesla stejný výsledek (téměř na nulu), zejména v úvodní fázi, Turing také zavedl některá kritéria pozičního hodnocení, jako je mobilita (možné pohyby), možnost zasažení, rošády nebo hrozba Šach mat.

	A	b	C	d	E	F	G	H
8. místo									8. místo
7. místo									7. místo
6. místo									6. místo
5									5
4. místo									4. místo
3									3
2									2
1									1
	A	b	C	d	E	F	G	H

Pozice po 29. tahu

Protože v té době neexistovaly žádné vhodné programovatelné kalkulačky, musel Turing vypočítat každý tah ručně na papíře sám, což znamenalo spoustu času. Ukázal se alespoň funkční princip, podle kterého všechny dnešní šachové programy stále fungují. První dávka jeho „papírenského stroje“ proběhla v roce 1952 a měla by zde být uvedena jako příklad:

Turingův papírenský stroj - Alick Glennie, Manchester, 1952

1. e4 e5 2. Nc3 Nf6 3. d4 Bb4 4. Nf3 d6 5. Bd2 Nc6 6. d5 Nd4 7. h4 Bg4 8. a4 Nxf3 + 9. gxf3 Bh5 10. Bb5 + c6 11. dxc6 0–0 12. cxb7 Rb8 13. Ba6 Da5 14. De2 Nd7 15. Rg1 Nc5 16. Rg5 Bg6 17. Bb5 Nxb7 18. 0–0–0 Nc5 19. Bc6 Rfc8 20. Bd5 Bxc3 21. Bxc3 Qxa4 22. Kd2 (22. h5 by mít biskupa 22.… Ne6 23. Rg4 Nd4 (23.… Rxb2 24. Bxb2 Rxc2 +) 24. Qd3 Nb5 25. Bb3 Qa6 26. Bc4 Bh5 27. Rg3 Qa4 28. Bxb5 Qxb5 29. Qxd6 Rd8 0: 1

Existují také implementace pro dnešní počítače pro „papírenský stroj“.

Claude Shannon

V Bell Laboratories 9. března 1949 měl Claude Shannon přednášku, která byla klíčová pro rozvoj šachových programů. Tam popsal interní zobrazení desky, vyhledávání stromů , vyhodnocovací funkci a vyhledávání tahů pomocí algoritmu Minimax . Už určil dvě různé strategie pro určení nejlepšího tahu: A-strategie a B-strategie .

Dietrich Prinz

V listopadu 1951 vytvořil Dietrich Günter Prinz z University of Manchester program pro Ferranti-Mark-I-Computer (GB), který vyřešil dvoudílný párovací úkol za 15 minut. Program je považován za první řešení v šachové historii.

John von Neumann

A b C d E F 6. místo 6. místo 5 5 4. místo 4. místo 3 3 2 2 1 1 A b C d E F

úvodní pozice

John von Neumann klasifikoval šachovou hru ve své teorii her jako hru dvou osob s nulovým součtem s úplnými informacemi. Tuto třídu problémů (včetně tic-tac-toe ) lze vyřešit algoritmem minimax . Šachy jsou však příliš složité na to, aby mohly úplně projít vyhledávacím stromem. Šachové programy jsou tedy závislé na aproximačních metodách.

Šachový program Johna von Neumanna byl dokončen v polovině 50. let minulého století a běžel na elektronkovém počítači MANIAC I zřízeném v roce 1950 . Kvůli jednoduchosti se hrálo pouze na desce 6 × 6. Program odehrál celkem tři hry: první proti sobě, další prohrál proti silnému šachistovi, ačkoli ten mu dal královnu, a třetí jej vyhrál proti mladé ženě, která šachy hrála jen týden a zvláště pro tuto hru vyškolenou.

A b C d E F 6. místo 6. místo 5 5 4. místo 4. místo 3 3 2 2 1 1 A b C d E F

Pozice po 21. tahu

MANIAC I - Muž, Los Alamos, 1956:

(Deska 6 × 6 bez biskupa, žádný dvojitý krok nebo rošáda)

1. d3 b4 2. Nf3 d4 3. b3 e4 4. Ne1 a4 5. bxa4 (5. Nd2 společně s 6. Nc4 + Nxc4 7. bxc4 s dobrou hrou) 5.… Nxa4 6. Kd2 Nc3 7. Nxc3 bxc3 + 8. Kd1 f4 9. a3 Rb6 10. a4 Ra6 11. a5 Kd5 12. Da3 Qb5 13. Da2 + Ke5 14. Rb1 Rxa5 15. Rxb5 Rxa2 16. Rb1 (prevence 16.… Ra1 mate) 16.… Ra5 17 . f3 Ra4 18. fxe4 c4 19. Nf3 + Kd6 20. e5 + Kd5 21. exf6D 21.… Nc5 (22. Qxd4 + Kc6 23. Ne5 mate.) 1: 0

Člověk poprvé propadl šachovému programu. Tato zjednodušená varianta šachů se také nazývá šachy Los Alamos .

V roce 1957 zaměstnanec IBM Alex Bernstein implementoval šachový program na IBM 704, který hrál podle standardních pravidel. Vybralo sedm nejpravděpodobnějších tahů v každé poloze a provedlo vyhledávání 4 polovičních tahů, což vyžadovalo asi 8 minut výpočetního času. Bernstein během vývoje získal podporu od amerického velmistra Arthura Bisguiera . Program bez šance prohrál s šachovým mistrem Edwardem Laskerem , ale počítač certifikoval jako přijatelnou amatérskou úroveň.

V roce 1958, hledání alfa-beta byla objevena pomocí Allen Newell , John Clifford Shaw a Herbert A. Simon a přinesl obrovský nárůst výkonu.

Richard Greenblatt

	A	b	C	d	E	F	G	H
8. místo									8. místo
7. místo									7. místo
6. místo									6. místo
5									5
4. místo									4. místo
3									3
2									2
1									1
	A	b	C	d	E	F	G	H

Mat po 37. tahu

Prvním programem, který se účastnil lidských turnajů, byl Mac Hack , vyvinutý Richardem Greenblattem na MIT v letech 1965 až 1967 .

Hubert Dreyfus - MacHack, MIT, 1967

1. e4 e5 2. Nf3 Nc6 3. Bc4 Nf6 4. Nc3 Bc5 5. d3 0-0 6. Ng5 Sa5 7. Bd5 c6 8. Bb3 Nxb3 9. cxb3 h6 10. Nh3 d5 11. exd5 Bg4 12. f3 Bxh3 13.gxh3 Nxd5 14.Nxd5 Qxd5 15. Bd2 Qxd3 16.b4 Be7 17.Rg1 e4 18.fxe4 Bh4 + 19.Rg3 Bxg3 + 20.hxg3 Qxg3 + 21. Ke2 Qxh3 22.Qg1 h5 23.Bc3 g6 24.Qf2 h4 25. Qf6 Qg4 + 26. Kd2 Rad8 + 27. Kc2 Qxe4 + 28. Kb3 De6 + 29. Qxe6 fxe6 30. Rh1 Rf4 31. Be1 Rf3 + 32. Ka4 h3 33. b5 Rd4 + 34. b4 cxb5 + 35. Kxb5 Ra3 36. Kc5 Rd5 + 37. Kc5 # 0: 1

Od roku 1967 do roku 1970 došlo k rozmachu v šachovém programování, který vyvrcholil prvním mistrovstvím v šachu počítačů v historii , které pořádala Asociace pro výpočetní techniku (ACM) . Vítězem se stal Chess 3.0 .

Peter Jennings

V roce 1976 Peter Jennings vyvinul Microchess pro domácí počítač KIM-1 . Do roku 1979 byl tento program prodán více než 50 000krát, což z něj činí první komerčně úspěšný mikropočítačový program. Vzhledem k tomu, že paměť RAM má pouze 1152 bajtů, nebyly implementovány převody rošád , en passantů a pěšců .

Ken Thompson

Ken Thompson vyvinul v roce 1979 slavný šachový automat Belle , který pracoval s otevírací knihovnou a hashtables .

Feng-hsiung Hsu

První počítačový program, který v běžné turnajové hře porazil úřadujícího mistra světa v šachu, byl Deep Blue . Vyvinutý společností IBM kvůli vzrušení a pod vedením mladé počítačové vědkyně Feng-Hsiung Hsu, tento program porazil 10. února 1996 na přizpůsobený a optimalizovaný pro šachový počítačový hardware, který také pochází od IBM, tehdejšího mistra světa Kasparova v charakterizovaný známý se stal součástí . Garry Kasparov dokázal vyhrát soutěž 4-2. Vylepšená verze Deep Blue však tuto překážku překonala 11. května 1997 a dosáhla celkového vítězství nad Kasparowem 3,5: 2,5 ve druhé soutěži se šestou turnajovou hrou. Po velkolepém vítězství byla Deep Blue rozebrána a zastavena. Původ programu byl později popsán v knize vynálezce.

Chrilly Donninger a Ulf Lorenz

Prvním, kdo se po Deep Blue přestěhoval ke konstrukci specializovaných šachových hardwarových komponent jako základu pro šachový program, byl rakouský šachový programátor „Chrilly“ Donninger, který se předtím se svým PC programem roky účastnil šachových turnajů v počítači. Od roku 2002 navrhl šachový počítač s hardwarem, který sám upravil a kterému původně říkal Brutus. Financování ChessBase stáhla svou podporu po špatném výkonu na turnaji v Grazu v roce 2003; Christian Donninger a Ulf Lorenz zpočátku pokračovali v projektu sami pod novým názvem Hydra . V roce 2004 našli Donninger a Lorenz nového sponzora z Arabských emirátů, PAL Computer Systems . Ve stejném roce Hydra porazila tehdejšího počítačového mistra světa Shreddera . V červnu 2005 proběhla za turnajových podmínek soutěž proti britskému velmistru Michaelovi Adamsovi , tehdy sedmému ve světovém žebříčku, který Hydra vyhrála s vynikajícím skóre 5,5: 0,5. To odpovídá turnajovému výkonu přes 3100 bodů Elo, což je více, než kdy kdokoli dosáhl. V této verzi se 64 procesory byla Hydra v současnosti nejsilnějším existujícím šachovým počítačovým systémem na světě.

Aktuální vývoj

Rozdělení výpočetního úsilí do mnoha jednotlivých dílčích procesů, které mohou běžet souběžně a tedy rozumně využívat víceprocesorové systémy, není kvůli vyhledávání stromů triviální a je aktuální oblastí výzkumu v šachovém programování (viz Hydra ).

V oblasti konvenčních šachových programů pro PC je paralelní používání několika procesorových jader možné již řadu let a probíhá prostřednictvím takzvaných „hlubokých verzí“ příslušných motorů. Tento vývoj navázal na rostoucí šíření odpovídajícího hardwaru PC s vícejádrovými procesory. Totéž nyní platí pro operační systémy se 64bitovou architekturou a speciálními verzemi šachových programů, které je výhodně podporují nebo na nich běží rychleji než 32bitové verze.

Možná novým trendem je použití obzvláště velkého počtu CPU, ale na rozdíl od Hydry na bázi konvenčních počítačů, kombinovaných do takzvaných klastrů. Turnajové sázky motorů Toga a Rybka na klastrový hardware se staly známými.

Soutěže

Existují různé soutěže, ve kterých se šachové programy navzájem měří, pokud jde o úroveň jejich dovedností, zřídka také proti lidským šachistům. Jedním z nejdůležitějších je (otevřené) mistrovství světa počítačových šachů , World Computer Chess Championship (WCCC), které se koná od roku 1974 a je otevřeno všem druhům hardwaru a softwaru . Nejstarší akcí bylo North American Computer Chess Championship (NACCC) pořádané v letech 1970 až 1994 . V letech 1980 až 2001 navíc probíhalo speciální mistrovství světa v šachu pouze pro mikropočítače , mistrovství světa v mikropočítačových šachech (WMCCC).

Hodnocení Elo

Šachovým programům lze také přidělit číslo Elo, které popisuje jejich úroveň dovedností. Pro srovnání: Dnešní mistr světa v šachu se pohybuje v rozmezí Elo 2850. Čísla Elo v počítačových žebříčcích nelze snadno srovnávat s lidskými šachisty, protože byla určena téměř výhradně prostřednictvím her mezi počítači. S ohledem na absolutní velikost hodnotových čísel neexistuje žádná kalibrace mezi výkonnostními stupnicemi lidských pánských hráčů a šachovými programy; to by vyžadovalo velmi početné seriózní soutěžní hry mezi oběma skupinami hráčů. To znamená, že úroveň čísel v čistě počítačových seznamech hodnocení musí nutně vycházet z věrohodného nebo praktického předpokladu a konkrétní výsledky programů proti sobě pouze určují pořadí a vzdálenosti mezi jejich hodnocením.

Vzhledem k zásadně odlišným metodám lidí a počítačových programů při hraní šachů nemusí vysoká úroveň dovedností proti jinému šachovému programu nutně znamenat odpovídajícím způsobem lepší výkon proti lidskému soupeři. Soutěže mezi šachovými programy proto říkají jen něco o úrovni hry proti lidem v omezené míře. Praxe však ukázala, že vysoká úroveň dovedností vůči programům obvykle také znamená vysokou míru dovedností vůči lidem. Program Rybka dokázal vyhrát proti různým velmistrům - někteří s hendikepem pěšce  . Ostatní programy jsou nyní ještě silnější.

Posouzení herní síly šachových programů a šachových počítačů je možné také pomocí sady sérií šachových úloh. Například test nazvaný BT2450 se skládá ze 30 pozic, pro které lze najít příslušný pohyb řešení. Z časů požadovaných pro všechny pozice se vypočítá testovací hodnota BT2450, kterou lze v omezené míře porovnat s počtem hráčů Elo. Nyní existují další, někdy rozsáhlejší a / nebo obtížnější testy, které jsou vytvářeny a používány v komunitě počítačových šachů.

Viz také

• Seznamy hodnocení počítačových šachů (CCRL)
• Forsyth-Edwards notace (FEN)

prameny

1. ↑ CCRL 40/4. Získaný 9. ledna 2021.
2. ↑ CCRL 40/40. Získaný 9. ledna 2021.
3. ↑ CCRL 404FRC. Získaný 9. ledna 2021.
4. ↑ CEGT 40/4. Získaný 9. ledna 2021.
5. ↑ CEGT 40/20. Získaný 9. ledna 2021.
6. ↑ CEGT žebříček. Získaný 9. ledna 2021.
7. ^ Herbert Braun: Plagiátorství obvinění proti počítačovým šachovým mistrům světa. In: Heise.de. 1. března 2011, přístup 9. ledna 2021 . 
8. ↑ Niyas Khasanov: Ufim. In: WBEC-Ridderkerk.nl. Získaný 9. ledna 2021 . 
9. ↑ Jon Dart: Arasanské šachy. In: ArasanChess.org. Získaný 9. ledna 2021 . 
10. ↑ Rytíři. In: Sourceforge.net. Získaný 9. ledna 2021 . 
11. ↑ Lomonosov Endgame Tablebases. In: chessok.com. Získaný 9. ledna 2021 . 
12. ↑ Vítejte v online 7místných tabulkách. In: tb7.chessok.com. Získaný 9. ledna 2021 . 
13. ↑ Raúl Rojas a kol. (FU Berlin): Konrad Zuses Plankalkül - Jeho geneze a moderní implementace. ( Memento z 23. dubna 2012 v internetovém archivu ). In: zib.de. Internetový archiv Konrad Zuse. Získaný 9. ledna 2021.
14. ↑ ^{a b c} Dieter Steinweder, Frederic A. Friedel: Šachy na PC. Markt und Technik, Haar nar. Mnichov 1995, ISBN 3-87791-522-1 , s. 33-35.
15. ↑ Frederic Friedel: Rekonstrukce Turingova „papírenského stroje“. In: ChessBase .com. 23. září 2017, přístup 9. ledna 2021.
16. ↑ Eric van Reem: Sen o počítačových šachách. Malá historie počítačových šachů. In: scrkuppenheim.de. Leden 2003, přístup 9. ledna 2021.
17. ↑ Feng-hsiung Hsu: Behind Deep Blue. Princeton University Press, Princeton / Oxford 2002, ISBN 0-691-09065-3 .
18. ↑ Lars Bremer: Počítačové šachy: Grandmaster of Hydra deklasován. In: Heise.de. 28. června 2005, přístup 9. ledna 2021 . 
19. ↑ Seznam hodnocení. In: ssdf.bosjo.net. 31. prosince 2020, přístup 9. ledna 2021 . 

literatura

• Rainer Bartel, Hans-Joachim Kraas, Günther Schrüfer: Velká počítačová šachová kniha. Data Becker, Düsseldorf 1985, ISBN 3-89011-117-3 (dobrý úvod do programování počítačových šachů s příklady v BASIC ).
• Počítačové šachy a hry (CSS). 1/1986 až 6/2004 (poté pouze online); Časopis převážně na téma počítačové šachy.
• Claude Shannon : Programování počítače pro hraní šachů. In: Filozofický časopis. 1950/41, s. 256-257.
• Claude Shannon: Programování počítače pro hraní šachů. In: Scientific American. 2/1950, s. 48-51.
• Dieter Steinwender , Frederic A. Friedel : Šachy na PC. Markt und Technik, Haar bei München 1995, ISBN 3-87791-522-1 (historie počítačových šachů, didaktický šachový program se zdroji v BASICU a C , vč. CD).

webové odkazy

• Stránka Ed Schröder. ( Memento z 30. ledna 2010 v internetovém archivu ). Autor Rebel a ProDeo, spousta informací o počítačových šachách a podrobné popisy vnitřního fungování Rebela. ( Memento z 31. května 2010 v internetovém archivu ). (Angličtina).
• Šachový program Micro-Max. Šachový program v C s méně než 2 000 bajty zdrojového kódu (anglicky).
• První šachový program na světě jako moderní Java applet.
• B. Monien, U. Lorenz, D. Warner: Abecední algoritmus. Jak dostanu počítač k hraní šachů? ( Memento z 15. prosince 2015 v internetovém archivu ). 2006.
• 9. mistrovství světa počítačových šachů od 14. do 20. června 1999 v Paderbornu. Zpráva na TeleSchach .
• Online pokračování bývalého časopisu Computerschach und Spiele.
• Pořadí počítačů SSDF.
• Pořadí CEGT.
• Microchess - první mikropočítačový šachový program.
• Wiki pro šachové programování (anglicky). ( Memento z 20. ledna 2010 v internetovém archivu ).