Glosář pojmů počítačových šachů - Glossary of computer chess terms

Šachový počítač

Toto je seznam termínů používaných v počítačové šachy.

DOPOLEDNE

algoritmus
Přesně definovaný postup krok za krokem pro provedení úkolu. Vidět algoritmus.
alfa
V vyhledávacím algoritmu minimax může minimální hodnota, kterou může pohybovaná strana dosáhnout, podle variací, které byly dosud vyhodnoceny.
prořezávání alfa – beta
Algoritmus, který snižuje počet uzlů prohledávaných algoritmem minimax. Toto zdokonalení je nezbytné, aby bylo praktické prohledávat velké herní stromy, například ty v šachu. Vidět prořezávání alfa – beta.
pole
Seznam uložený v paměti počítače, jehož položky lze rychle načíst pomocí číselného rejstříku.
umělá inteligence
AI
Odvětví počítačové vědy zabývající se reprodukcí nebo napodobováním myšlení na lidské úrovni v počítačích. Hraní her bylo jednou z prvních oblastí výzkumu AI. Vidět umělá inteligence.
Zdokonalení prořezávání alfa-beta, které dále zrychluje vyhledávání tím, že zohledňuje pouze úzké okno, obvykle na základě zkušeností. Hledání v nulovém okně, vyhledávání v nulovém okně a vyhledávání skautů jsou názvy extrémních případů, kdy jsou alfa a beta nastaveny na stejnou hodnotu.
beta
V vyhledávacím algoritmu minimax může maximální hodnota, kterou může pohybovaná strana dosáhnout, na základě dosud vyhodnocených variací.
bit
Binární číslice, 0 nebo 1. Nejmenší část informace, kterou může počítač uložit nebo s ní manipulovat
bitová deska
Pole 64 bitů, každý bit představuje čtverec šachovnice. S každou bitovou deskou se používá několik bitových desek, které zaznamenávají konkrétní charakteristiku, například všechna pole obsazená určitým typem figurky nebo všechna pole, která jsou napadena.
větvící faktor
Počet možností, které je třeba vzít v úvahu na každé úrovni vyhledávacího stromu.
hrubou silou
Přístup k řešení problémů, který se spoléhá spíše na rychlý počítačový hardware než na elegantní algoritmy.
tah kandidáta
Pohyb vybraný při počátečním pozorování polohy jako hodný další analýzy. Algoritmus alfa-beta může být efektivnější, pokud je seznam přesunů kandidátů správně uspořádán tak, aby byly nejprve zohledněny nejlepší pohyby. Vidět tah kandidáta.
Rozšíření vyhledávacího algoritmu, které pokračuje od koncového uzlu, přičemž se berou v úvahu pouze zachycení, která lze provést každou stranou.
odříznout
Odstranění větve stromu prohledávání, aniž byste jej museli prohledávat. Toto je prořezávací akce algoritmu alfa-beta.
vyhodnocovací funkce
Algoritmus použitý k vyhodnocení příznivosti polohy. Protože většině šachových pozic nelze přiřadit přesnou hodnotu (vyhrané, ztracené nebo vylosované), jedná se o heuristiku založenou na faktorech, jako je materiální bilance, prostorová výhoda, pohyblivost figurek, struktura pěšce, bezpečnost krále atd. Většina hodnotících funkcí vrací a číselná hodnota v pěšcích a zlomcích pěšce představující výhodu, kterou má bílá v dané pozici. Nula znamená, že pozice je vyvážená a záporné hodnoty znamenají, že černá je posouzena jako vpřed. Vidět vyhodnocovací funkce.
Hledání, ve kterém jsou prozkoumány všechny větve herního stromu. Kvůli vysokému větvícímu faktoru šachu není vyhledávání na celou šířku obecně praktické, kromě případů, kdy na desce zůstává několik figurek, takže možné pozice jsou výrazně omezeny.
herní strom
Všechny možné pozice, které by mohly vzniknout ze všech legálních tahů z dané pozice.
heuristický
Metoda používaná k řešení problému, u kterého není zaručeno, že bude optimální nebo správná, použitá, když je metoda pro přesné řešení problému neznámá nebo nepraktická. Heuristiku lze použít v počítačových šachech k vyhodnocení pozic a vedení vyhledávacího algoritmu.
horizont efekt
Důsledek, že pro většinu pozic je nepraktické, aby vyhledávací algoritmus prohledával celou cestu až k závěru hry. Počítač může udělat špatný tah, protože není schopen vidět důsledky ani o jednu vrstvu nad maximální hloubku vyhledávání. Efekt obzoru byl v prvních letech počítačových šachů velkým problémem, ale dnes je méně problémem, protože moderní šachové stroje mohou prohledávat mnoho tahů hluboko i ve složitých pozicích. Vidět horizont efekt.
iterativní prohlubování
Vyhledávací algoritmus, který nejprve prohledává hloubku N vrstev, poté pomocí výsledků tohoto hledání změní pořadí kandidátů, kteří provedou vyhledávání N + 1 vrstvy. Vidět iterativní prohlubování hloubkového vyhledávání.
zabijácká heuristika
Předpoklad, že tah ( zabijácký tah), který způsobil omezení vyhledávání v jiné větvi herního stromu ve stejné hloubce, může způsobit omezení v současné poloze. Díky tomu bude prořezávání alfa-beta efektivnější. Vidět zabijácká heuristika.
algoritmus minimax
Základní algoritmus používaný k vyhledávání herních stromů. Na každé úrovni ve stromu hry si hráč, který se má pohybovat, vybere možnost, která maximalizuje minimální výhodu, která bude výsledkem jakékoli z možných odpovědí soupeře. Vidět algoritmus minimax.
přesunout generátor
Modul, který vytváří seznam tahů, které mají být zváženy z určité pozice. To je obvykle součástí softwaru šachového motoru, ale některé šachové počítače provedly generování tahů v hardwaru.

N – Z

úvodní kniha
Databáze tahů, které se mají hrát v šachové šachtě od začátku hry. Tyto pohyby lze vybrat přímo z úložiště počítače, takže nevyžadují vyhledávání.
vrstva
Tah buď bílý, nebo černý, tedy poloviční tah. Úplný tah je dvouvrstvý. Vidět vrstva.
hlavní variace
Nejlepší nebo správná hrací linie; varianta nejvýhodnější pro současného hráče za předpokladu, že každý hráč zvolí nejlepší tahy.
prořezávání
Eliminace větví ve stromu hry bez jejich prohledávání.
Označení tahů, které jsou legální na základě všech kritérií s výjimkou vystavení šeku. Generátory přesunu hardwaru, například generátory Kráska, produkovat pseudo-legální pohyby. Musí být otestovány, aby bylo zajištěno, že pohybová strana nebude pod kontrolou.[1]
Rozšíření vyhledávacího algoritmu, které bude pokračovat v prohledávání větve kolem toho, co by za normálních okolností bylo nejhlubší částí hledání (koncový uzel), dokud není dosaženo klidové polohy, kde nejsou možné žádné záchyty a ani král není pod kontrolou. Tuto techniku ​​lze použít k minimalizaci nebezpečí efektu horizontu.
vyvrácení
Tah, který ukazuje, že předchozí uvažovaný tah by byl špatný.
hloubka hledání
Počet vrstev, na které se prohledává herní strom.
Hledání, při kterém jsou na každé úrovni herního stromu zkoumány pouze některé možnosti; kontrast s vyhledáváním na celou šířku.
Shannonovo číslo
Odhadovaná spodní hranice šachové složitosti herního stromu. V roce 1950 Claude Shannon odhadoval, že jich je přibližně 10120 odchylky od výchozí pozice v šachu.
koncový uzel
koncová poloha
Nejhlubší část hledání na konkrétní větvi herního stromu. Funkce vyhodnocení se aplikuje na koncové uzly k přiřazení hodnoty této větvi.
transpoziční tabulka
Záznam pozic a jejich vyhodnocení, jak byly nalezeny v dřívější části vyhledávání. Transpoziční tabulka šetří výpočet tím, že umožňuje vyhledání hodnoty polohy, když je opět dosažena v jiném pořadí tahů, než aby bylo nutné ji znovu vypočítat. Vidět transpoziční tabulka.
strategie typu A.
Hrubou silou, vyhledávání na celou šířku zvážení všech možných legálních tahů na každé úrovni vyhledávacího stromu. Vytvořil Claude Shannon v roce 1949. Kontrast s strategie typu B..
strategie typu B.
Selektivní vyhledávání, s ohledem na určité řádky hlouběji než ostatní. Vytvořil Claude Shannon v roce 1949. Kontrast s strategie typu A..
variace
Konkrétní sekvence tahů, často používaná k popisu budoucích možností ve hře, spíše než tahy, které se hrály k dosažení aktuální polohy. Vidět variace.
okno
Rozdíl mezi alfa a beta v algoritmu vyhledávání alfa-beta. Postupem hledání se okno zmenšuje. Při hledání aspirace je okno nastaveno na úzkou hodnotu. Nejextrémnější případ, vyhledávání v nulovém okně, se také nazývá vyhledávání v nulovém okně nebo skautské vyhledávání.

Reference

  1. ^ Frey 1983 s. 203.
  • Levy, David; Novorozenec, Monty (1991), Jak počítače hrají šachy, Počítačová věda, ISBN  0-7167-8239-1
  • Welsh, David (1984), Počítačové šachy, Wm. C. Brown, ISBN  0-697-09900-8
  • Condon, Joseph H.; Thompson, Ken (1983). „Kapitola 9: Belle“. Frey, Peter W. (ed.). Šachová dovednost v člověku a stroji. New York: Springer-Verlag. 201–210. ISBN  978-0-387-90815-1.