Ordliste over vilkår for datamaskinsjakk - Glossary of computer chess terms

Sjakk datamaskin

Dette er en liste over begrep som brukes i datasjakk .

ER

algoritme
En nøyaktig definert trinn-for-trinn-prosedyre for å utføre en oppgave. Se algoritme .
alfa
I minimax-søkealgoritmen kan minimumsverdien som siden å bevege seg oppnå i henhold til variasjonene som er evaluert så langt.
alfa – beta-beskjæring
En algoritme som reduserer antall noder som søkes av minimax-algoritmen. Denne avgrensningen er viktig for å gjøre det praktisk å søke i store vilttrær som de som er i sjakk. Se alfa – beta-beskjæring .
matrise
En liste som er lagret i datamaskinens minne, og som raskt kan hentes med en numerisk indeks.
kunstig intelligens
AI
Datavitenskapens gren som omhandler reproduksjon eller etterlikning av menneskelig tanke i datamaskiner. Spilling var et tidlig forskningsområde i AI. Se kunstig intelligens .
En avgrensning til alfa-beta-beskjæring som ytterligere fremskynder søket ved å kun vurdere et smalt vindu, generelt basert på erfaring. Nullvindu-søk, null-vindus-søk og speider-søk er navn på det ekstreme tilfellet der alfa og beta er satt til samme verdi.
beta
I minimax-søkealgoritmen kan den maksimale verdien siden å bevege seg oppnå basert på variasjonene som er evaluert så langt.
bit
Et binært siffer, 0 eller 1. Det minste informasjonsstykket som kan lagres eller manipuleres av datamaskinen
bittavle
En rekke 64 biter, hver bit representerer en firkant av sjakkbrettet. Flere bittavler brukes med hvert brett som registrerer en spesiell egenskap, for eksempel alle rutene som er okkupert av en bestemt type brikke eller alle rutene som er angrepet.
forgreningsfaktor
Antall muligheter som må vurderes på hvert nivå i søketreet.
Ren styrke
En problemløsende tilnærming som er avhengig av rask datamaskinvare fremfor elegante algoritmer.
kandidatflytting
Et trekk valgt ved første observasjon av stillingen som verdig for ytterligere analyse. Alfa-beta-algoritmen kan være mer effektiv hvis kandidatflyttelisten er ordnet slik at de beste trekkene blir vurdert først. Se kandidatflytting .
En utvidelse til søkealgoritmen som fortsetter fra en terminalnode som kun tar hensyn til bilder som kan gjøres av hver side.
cutoff
Eliminering av en gren av søketreet uten å måtte søke i det. Dette er beskjæringsaksjonen til alfa-beta-algoritmen.
evalueringsfunksjon
Algoritmen som ble brukt for å evaluere fordelingen av en stilling. Siden de fleste sjakkstillinger ikke kan tildeles en nøyaktig verdi (vunnet, tapt eller trukket), er dette en heuristikk basert på faktorer som materialbalanse, romfordel, stykkmobilitet, bondeoppbygging, kongesikkerhet, etc. De fleste evalueringsfunksjoner returnerer en numerisk verdi i bønder og brøkdeler av en bonde som representerer fordelen som hvit anses å ha i den gitte posisjonen. Null indikerer at posisjonen er balansert, og negative verdier indikerer at svart bedømmes å være foran. Se evalueringsfunksjon .
Et søk der alle grenene av viltreet blir utforsket. På grunn av den høye forgreningsfaktoren i sjakk, er søk i full bredde generelt ikke praktisk bortsett fra når det er få stykker igjen på brettet, slik at de mulige stillingene reduseres kraftig.
spilltreet
Alle mulige stillinger som kan oppstå fra alle juridiske trekk fra den gitte stillingen.
heuristisk
En metode som brukes for å løse et problem som ikke garanteres å være optimal eller riktig, benyttes når en metode for den nøyaktige løsningen av problemet er ukjent eller upraktisk. Heuristikk kan brukes i datasjakk for å evaluere posisjoner og for å guide søkealgoritmen.
horisonteffekt
Konsekvensen av at det er upraktisk i de fleste posisjoner for søkealgoritmen å søke helt frem til avslutningen av spillet. Datamaskinen kan gjøre et dårlig trekk fordi den ikke klarer å se konsekvensene til og med et lag utover den maksimale søkedybden. Horisonteffekten var et stort problem i de første årene av datamaskinsjakk, men det er mindre av et problem i dag ettersom moderne sjakkmotorer kan søke mange trekk dypt selv i komplekse posisjoner. Se horisonteffekt .
iterativ fordypning
En søkealgoritme som først søker til en dybde av N- lag, og deretter bruker resultatene av det søket omorganiserer kandidaten for å utføre et søk til N + 1- lag. Se iterativ utdyping av dybde-første søk .
drapsmann heuristisk
Antagelse om at et trekk ( drapsmannens trekk ) som forårsaket et søkavskjæring i en annen gren av spilletreet med samme dybde, kan forårsake et avskjær i dagens posisjon. Dette kan gjøre alfa-beta-beskjæring mer effektiv. Se morderen heuristisk .
minimax algoritme
Den grunnleggende algoritmen som brukes til å søke på spilltrær. På hvert nivå i spilltreet velger spilleren som beveger seg muligheten for å maksimere den minste fordelen som vil resultere fra noen av motstanderens mulige svar. Se minimax algoritme .
flytte generator
Modulen som oppretter listen over trekk som skal vurderes fra en bestemt posisjon. Dette er vanligvis en del av programvaren for sjakkmotorer, men noen sjakkdatamaskiner har utført trekkgenerering innen maskinvare.

N-Z

åpningsbok
En database med trekk som skal spilles i sjakkåpningen fra begynnelsen av spillet. Disse trekkene kan velges direkte fra datamaskinlagring, og de krever ikke søk.
ply
Et trekk av enten hvitt eller svart, derav et halvt trekk. Et fullstendig trekk er to lag. Se ply .
hovedvariasjon
Den beste eller riktige spillelinjen; variasjonen som er mest fordelaktig for den nåværende spilleren forutsatt at hver spiller velger de beste trekkene.
beskjæring
Eliminering av grener i spilletreet uten å søke dem.
En betegnelse for trekk som er lovlige basert på alle kriterier bortsett fra eksponering for sjekk. Generatorer som flytter maskinvare, som Belle , produserer pseudo-juridiske trekk. Disse må testes for å sikre at de ikke setter den bevegelige siden i sjakk.
En utvidelse til søkealgoritmen som vil fortsette å søke i en gren forbi det som normalt ville vært den dypeste delen av søket (terminalnoden) inntil en hvileposisjon er nådd der ingen fanger er mulig og ingen av konge er i sjakk. Denne teknikken kan brukes for å minimere faren for horisonteffekten.
imøtegåelse
Et trekk som viser at det forrige trekket som ble vurdert, vil være dårlig.
søkedybde
Antall lag som spilletreet blir søkt til.
Et søk der bare noen muligheter blir undersøkt på hvert nivå av spilltreet; kontrast med søk i full bredde.
Shannon-nummer
Anslått nedre grense på sjakkens tre-kompleksitet. I 1950 anslo Claude Shannon at det er omtrent 10 120 variasjoner fra startposisjonen i sjakk.
terminalnode
terminalstilling
Den dypeste delen av søket på en bestemt gren av spilletreet. Evalueringsfunksjonen brukes på terminalnoder for å tilordne en verdi til den grenen.
transponeringstabell
En oversikt over stillinger og evalueringer av dem som ble funnet i en tidligere del av søket. En transponeringstabell sparer beregning ved å la verdien av en posisjon bli funnet opp når den nås igjen med en annen rekkefølge av trekk i stedet for å kreve at den beregnes på nytt. Se transponeringstabell .
type-A-strategi
Brute force, søk i full bredde med tanke på alle mulige lovlige trekk på hvert nivå av søketreet. Mynte av Claude Shannon i 1949. Kontrast med type B-strategi .
type-B-strategi
Selektiv søk , med tanke på visse linjer dypere enn andre. Mynte av Claude Shannon i 1949. Kontrast med type-A-strategi .
variasjon
En spesiell sekvens av trekk, ofte brukt for å beskrive fremtidige muligheter i et spill i stedet for trekkene som ble spilt for å nå den nåværende posisjonen. Se variasjon .
vindu
Forskjellen mellom alfa og beta i alfa-beta søkealgoritmen. Etter hvert som søket fortsetter, blir vinduet mindre. I et ambisjonssøk er vinduet satt til en smal verdi. Det mest ekstreme tilfellet, null-vindus søk , kalles også null-vindus søk eller speider søk .

referanser

  • Levy, David ; Newborn, Monty (1991), How Computers Play Chess , Computer Science, ISBN  0-7167-8239-1
  • Welsh, David (1984), Computer Chess , Wm. C. Brown, ISBN  0-697-09900-8
  • Condon, Joseph H .; Thompson, Ken (1983). "Kapittel 9: Belle". I Frey, Peter W. Chess Skill in Man and Machine . New York: Springer-Verlag. s. 201–210. ISBN  978-0-387-90815-1 .