Skakprogram

	-en	b	c	d	e	f	G	H
8.									8.
7.									7.
6.									6.
5									5
4.									4.
3									3
2									2
1									1
	-en	b	c	d	e	f	G	H

To-dimensionelle skakbræt, som vist på skærmen ved mange skakfrontender

Et skakprogram er et computerprogram, der er i stand til at spille skak . Det kører enten på pc'er eller på skakcomputere specielt fremstillet til at spille skak . Udviklingen af ​​skakprogrammer er en disciplin inden for computerskak .

Mens hele funktionaliteten blev kombineret i et program i tidligere skakprogrammer, består moderne skaksoftware normalt af to dele: den såkaldte motor - det egentlige skakprogram, der beregner de træk, computeren spiller - og skakfronten , displayet og brugerinteraktionen tager over. Der er to udbredte open skak kommunikations -protokoller til kommunikation mellem skak motor og forenden : den XBOARD protokollen og den nyere Universal Chess interface (UCI). Positionerne og spillene gemmes i proprietære formater eller i det åbne bærbare spilnotationsformat (PGN).

Aktuelle programmer

Et af de mest kendte gratis skakprogrammer er Crafty , et open source -projekt af Robert Hyatt . Et andet kraftfuldt skakprogram er Fruit , der blev nummer to i verdensmesterskabet i computerskak i 2005. Op til version 2.1 er Fruit også tilgængelig under en open source -licens, ligesom Glaurung 2.1, der er omtrent den samme styrke.

Open source -programmet Stockfish kom fra Glaurung. Den fås til forskellige operativsystemer med 32-bit eller 64-bit arkitektur og er et af de mest kraftfulde skakprogrammer nogensinde. På grund af sin åbne udvikling er Stockfish ikke mistænkt for plagiat. Det er gratis tilgængeligt.

Siden 2014 har ranglisterne , der bestemmes ved hjælp af spil mellem programmerne, været head to head af det kommercielle program Komodo og open source -udviklingen Stockfish beskrevet ovenfor.

Det kommercielle program Houdini har været et af de bedste spil i årevis, men det er kontroversielt. Programmøren af ​​skakprogrammet Rybka hævder, at kildekoden blev stjålet fra ham, og at forskellige, meget kraftfulde skakprogrammer ( IPPOLIT -familien) blev oprettet på dette grundlag , herunder Houdini. Der er ikke fremlagt beviser - i det mindste offentligt - for denne påstand. Programmøren af ​​skakprogrammet Rybka siges at være baseret på frugt. På grund af denne kontrovers blev Houdini - ligesom nogle andre programmer i Ippolit -familien - midlertidigt ikke opført af forskellige operatører af ranglister. I programmets videre forløb blev Rybka klassificeret som et plagiat af Fruit , hvorved Rybka blev frataget alle titler og succeser. Rybka -programmøren blev udelukket fra alle computerskaksturneringer for livet. Houdini, på den anden side, som igen er meningen at være baseret på Rybka, blev derefter kendt for at være den mest magtfulde skak motor og blev anvendt til analyse sammen med frontend akvarium ved World Chess Championships.

For begyndere er der en skalerbar motor, der kan begrænses i rating som Ufim.

José - skakdatabase og skakfrontend

En brugergrænseflade kaldet en skakfront er også påkrævet for nem betjening. XBoard -programmet kan f.eks. Bruges til dette formål . Det kører under operativsystemerne Microsoft Windows (under navnet WinBoard ), Unix / Linux og Amiga og leveres sammen med GNU Chess . En grafisk Java -baseret skakfrontend -databasefunktion er også under GPL -udgivne José . En anden populær brugergrænseflade på Windows til mere end 250 skakprogrammer er Arena , som fås som freeware. Der er også andre freeware, der er velegnede til begyndere, såsom Arasan . KDEs skakfront er Knights.

Ambitiøse spillere tyer ofte til kommercielle programmer, der udover det rene skakspil også tilbyder mange ekstra muligheder, såsom spilanalyse og skaktræning. Shredder og Fritz programmerne burde være meget velkendte . Disse programmer distribueres blandt andet af Hamburg -virksomheden ChessBase , der i stigende grad dominerer det (europæiske) marked for professionel skaksoftware. Rybka -programmet har siden 2005 skabt overskrifter i specialblade og computerfora. Rybka har stærke positionelle og strategiske skakfærdigheder og er derfor tættere på den menneskelige måde at spille på end de fleste andre skakprogrammer. Rybka førte de vigtigste computer -skakrangeringer - hvor Houdini ikke var opført - med 50-150 point foran. Skak stormestre som Anand , Topalow eller Morosewitsch brugte Rybka til analyse, nu bruges Stockfish , Critter eller Houdini oftere.

Du kan nu spille skak i høj kvalitet på mobiltelefoner , PDA'er og andre håndholdte . For eksempel på Palm OS-baserede enheder er OpenChess et gratis skakprogram, der giver dig mulighed for at vælge mellem flere skakmotorer.

Med det gratis ChessV -program kan du også prøve forskellige skakspil .

konstruktion

De vigtigste komponenter i en skak-program er det farten generator, den evaluering funktion og et program del for at styre søgningen og udvælgelsen af det næste træk. Fra den nuværende position (spilsituation) udfører programmet en iterativ dybde-første søgning . I hver iteration, det udfører forskellige move sekvenser i rækkefølge, evaluerer positionerne nået (blade af søgetræet ) med evalueringen funktion og på grundlag af disse blade værdier, det vurderer de indre knudepunkter søgetræet og dermed også bevægelserne der i hvert tilfælde er i overensstemmelse med minimax -princippet fører til en knude. Efter den sidste iteration spiller det det højest værdsatte træk i rodnoden (som repræsenterer den aktuelle position).

Et vigtigt træk ved et skakprogram er den type intern board -display, som alle andre komponenter i programmet bruger.

Toggenerator og internt borddisplay

	-en	b	c	d	e	f	G	H
8.									8.
7.									7.
6.									6.
5									5
4.									4.
3									3
2									2
1									1
	-en	b	c	d	e	f	G	H

Eksemplet på
spilpositionen, der bruges i alle følgende repræsentationer : 1. e4 e5 2. Nc3

Bevægelsesgeneratoren genererer en liste over alle lovlige (regelkompatible) træk i en bestemt position (mulige bevægelser af spillebrikkerne). I startpositionen er 20 træk mulige (16 bondebevægelser, 4 ridderbevægelser), i det videre forløb af spillet kan du regne med et gennemsnit på omkring 40 lovlige træk i hver position, i slutspillet mindre. Bevægelsesgeneratoren skal også tage højde for komplicerede træk som f.eks. Kastning , pantændringer og en-passant slag .

Som regel lader man toggeneratoren beregne alle pseudo-juridiske træk, dvs. det vil sige, at kongernes styre ignoreres; z. B. et sådant træk kunne flytte kongen til en truet plads. Dette gør toggeneratoren betydeligt lettere og hurtigere. De ulovlige træk sorteres senere efter den del af programmet, der styrer søgningen: Et træk var ulovligt, hvis den følgende flytningsliste indeholder et træk, der besejrer kongen.

For at kode tallene bruges følgende heltal i eksemplerne:

Implementeringen af ​​toggeneratoren er tæt forbundet med det interne kortdisplay. Der er fire vigtige repræsentanter her:

12 × 10 repræsentation

Spillet er kortlagt til et endimensionelt, 120-element array . Indekset (tal i parentes) kører normalt linje for linje, her fra 0 (øverst til venstre) til 119 (nederst til højre). Ud over de 64 gyldige felter indeholder arrayet felter, som et stykke ville nå, når det forlod tavlen, og som danner en kant omkring det almindelige bræt. En vis værdi (her −1) er gemt på disse kantkanter, og hvis et stykke skulle bevæge sig ind på en firkant med denne post, betyder det, at det ville forlade tavlen med det. Dette kan let stilles spørgsmålstegn ved, da du alligevel skal kontrollere, om målpladsen er optaget af dit eget stykke, hvilket ville gøre flytningen ulovlig. Denne teknik gør toggeneratoren hurtig og let. Venstre og højre kant på hver side behøver kun at være en firkant, for en ridder, der trækker sidelæns fra brættet, lander altid enten på venstre eller højre kantrække.

Ved at tilføje følgende konstanter til et feltindeks kan de mulige målfelter for et tal på dette felt bestemmes.

Lad os se på den sorte ridder på firkant 27 (Ng8). Tilføjelse af disse konstanter til 27 resulterer i de potentielle målkvadrater: 6, 8, 15, 19, 35, 39, 46 og 48. Hvis værdien i målfeltet er −1, er flytningen ikke mulig, fordi ridderen ville bevæge sig over kanten. Hvis værdien er 1 eller 10 til 14, er der et hvidt stykke på feltet, der kan fanges, og hvis det er lig med nul, er det muligt at flytte til det tomme felt. Ridderen kan derfor foretage tre forskellige træk på målrummene 35, 46 og 48, som tilføjes til flyttelisten. Hvis trækgeneratoren kun skulle generere lovlige træk - og ikke alle pseudo -lovlige træk, skal du stadig være opmærksom på, om ridderen er bundet, eller om der er en skakkommando, som du skal afværge.

Det ligner de andre typer figurer. Dem med lange skridt (dronning, biskop, tårn) kan ikke hoppe over et besat rum. Efter at dette er nået, er der ikke mulighed for yderligere bevægelse i denne retning, og du kan gå videre til den næste retning.

Mens toggeneratoren er ganske enkel og hurtig, er de statiske evalueringsfunktioner langsommere.

8 × 8 repræsentation

8 × 8 -repræsentationen er tættest på menneskesynet. GNU Chess- programmet brugte dem op til version 4. Brættet er modelleret som et endimensionelt array, som det er tilfældet med 12 × 10, her med et indeksområde fra 0 til 63 (alternativt 1 til 64). Et todimensionalt array virker tættere, men er langsommere, fordi et felt her skal betegnes med to tal (række og linje), skal der tilføjes en konstant til både når man genererer trækket, og når man får adgang til et felt, skal adresseberegningen med to indeks er mere kompliceret.

Toggeneratoren er normalt mere kompleks og langsommere end med 12 × 10 -displayet, da specialtilfældene ved kanten skal behandles separat. Den statiske evalueringsfunktion fungerer dog mere effektivt, da rækken og linjen, som et felt er placeret på, kan bestemmes med hurtige bitoperationer : OG betjening af indekset med 7 resultater i linjen og skift til højre med 3 bit resulterer i rækken (med række-for-række feltarrangement og indeksområde 0 til 63). Med 12 × 10 -tavlen skal du derimod dividere med 10. Scorefunktionen har ofte brug for disse oplysninger, f.eks. B. til dobbeltbønder eller Isolani -genkendelse .

Selv med 8 × 8 -tavlen kan tog genereres hurtigt og nemt ved hjælp af bordadgang, hvilket dog øger hukommelsesforbruget betydeligt. GNU Chess bruger et todimensionalt array nextpos med 64 x 64 elementer for hver type figur , hvis poster beregnes på forhånd. Hvis du indekserer det med startfeltet f af et stykke og en af ​​dets målfirkanter, kan du aflæse det næste målfelt for stykket. nextpos (f, f) returnerer det første målfelt . For de langtrinnende stykker er der også array nextdir , hvorfra det næste målfelt læses, når målfeltet er optaget (første felt i en ny bevægelsesretning). Hvis der ikke længere er et målfelt, returnerer begge værdien f.

En anden mulighed er et tredimensionelt array, der indeholder alle målfelter for alle felter og figurtyper, som denne figur kan nå fra dette felt. Det tredje indeks kører over disse målfelter. Hukommelsesforbruget er lavere her, især hvis der bruges et todimensionalt array af pointers, som hver især peger på en bunke array af den passende størrelse, svarende til det forskellige antal målfelter. Posterne er i to dele: den første del er målfeltindekset og den anden er antallet af felter, der følger i arrayet, der skal springes over, hvis målfeltet er optaget (eller direkte det næste indeks i arrayet).

0x88 repræsentation

Dette er en videreudvikling af 8 × 8 -displayet. I tilfælde af line-by-line display med 16 felter pr. Linje, danner det venstre område med 8 x 8 felter skakbrættet, det rigtige område med 8 x 8 felter bruges ikke. Hvis et tal ville bevæge sig over kanten, kan dette genkendes af bit-by-bit OG betjening af målfeltindekset med det hexadecimale tal 0x88 (= 136). Hvis resultatet er nul, angiver feltindekset et gyldigt felt, ellers ville stykket forlade tavlen. Rækken og linjen i et felt kan beregnes på samme måde som 8 × 8 -tavlen ved at flytte 4 bits til højre eller ANDing med 7.

Med denne repræsentation kan du også bruge indeksforskellen mellem to firkanter til at afgøre, om og med hvilket stykke det er muligt at flytte fra en firkant til den anden. For eksempel er et tårnbevægelse kun muligt, hvis forskellen ligger i området -7 til 7 eller et multiplum af 16. Dette er ikke muligt med repræsentationen 8 × 8 eller 10 × 12, fordi kriteriet også opfyldes af feltpar, der ikke tillader et tilsvarende træk. Kvadraterne h4 og a5 har for eksempel en indeksforskel på mindre end 8, selvom der ikke er mulig at flytte et tårn.

Bitboards

Nogle moderne skakprogrammer, såsom Rybka , Crafty eller GNU Chess 5, bruger bitboards . Disse kan implementeres særlig effektivt på 64-bit computerarkitekturer , hvor antallet af bits i et register / ord svarer til antallet af felter. Hver bitposition i et ord tildeles et felt på brættet, og bit på den position giver en indikation af det tilsvarende felt.

Følgende eksempel viser positionen efter træk 1. e4 e5 2. Nc3 med otte 64-bit registre. Registret Bindeholder en 1-bit, hvor der er en bonde (af enhver farve) på det tilsvarende felt. Der er også et register for hver af de andre typer figurer. WEIog SCHangive, hvor en hvid eller sort figur er placeret. For overskuelighedens skyld er bits med værdien 0 repræsenteret ved -.

         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--- -------- -------- -------- --------

Med hurtige bitvise operationer kan oplysninger om positionen nu beregnes parallelt for alle felter. For eksempel kan T & WEIalle positioner af de hvide tårne ​​bestemmes af AND -operationen , og det ((B & SCH) >> 8) & ~(WEI | SCH)giver et lidt mønster med de felter, hvorpå en sort bonde kan bevæge sig med et enkelt trin. >> Den bitskift til højre (med den nedre ende) betegner den ~ negation og | OR link.

Evalueringsfunktioner

Den Evalueringsfunktionen leverer heuristisk evaluering af en stilling uden bestemmelse af efterfølgere. Det består af et materiale og en positionel komponent. Positionskomponenten supplerer den materielle, da stykkernes styrke også afhænger af deres positioner indbyrdes. Forenklede evalueringsfunktioner kan også udføres af menneskelige spillere, men dette har kun historisk betydning. Computerprogrammer viser meget ofte evalueringen af ​​en spilsituation numerisk (i såkaldte bondeenheder ), hvor positive værdier angiver fordele og negative værdier angiver ulemper for en bestemt spiller.

materiale

Ved materialescoring lægges værdier sammen for brikkerne på brættet. Den omtrentlige værdi af stykketyperne i ¹ ⁄ ₁₀₀ bondeenheder er angivet i følgende tabel.

De hvide stykker (eller dem i partiets tur) tælles som positive, og de sorte brikker (eller dem fra den følgende part) tælles som negative. Kongen behøver ikke tælles, da begge parter har en konge hver for hele spillet.

position

Den positionelle bestemmer stilling, er en opgave af større kompleksitet, de forskellige skakprogrammer adskiller sig klart fra hinanden. Det er stadig en velbevaret hemmelighed i kommercielle programmer. Ved positionsevaluering forsøger man at evaluere positioner ud fra skakrelevante parametre. Skakrelevante parametre kan groft inddeles i kongesikkerhed, bondestruktur, kontrollerede og truede felter samt brikudvikling. For eksempel er en position, hvor tårnene stadig er indsnævret mellem riddere og bonde vurderet dårligere end en, hvor tårnene allerede er på åbne linjer.

Inden for disse kategorier er der stort set alle antal parametre (for bonde strukturer for eksempel bestået brikker , dobbelt bønder , håndtag , væddere , Isolani , bonde kæder , for kong sikkerhed, for eksempel: kan kongen slottet let til venstre eller højre Kan han ophold? i midten? Er bønder foran kongen?). Det er fornuftigt først at udtrække disse parametre fra den givne position på en værdineutral måde. Skakprogrammører står over for beslutningen om, hvor meget beregningstid de skal bruge på positionskomponenten i en sofistikeret evalueringsfunktion, og hvilke parametre der endda bør medtages: Jo dybere skakprogrammerne kan analysere søgetræet, jo hurtigere konvertering af positionel fordele i materielle fordele bliver synlige.

Statisk evalueringsfunktion

Hvis et skakprogram effektivt kan bestemme værdierne af disse parametre pr. Position, skal de vægtes i forhold til hinanden. Vægtningen af ​​positionskomponenten kan foretages delvist automatisk ved at analysere skakdatabaser eller ved at spille mod andre skakprogrammer. Hvis dette sker forud for programudviklingen, taler man om en statisk evalueringsfunktion. Simpelthen strukturerede evalueringsfunktioner bruger positionsvægte til de seks bondetyper til positionskomponenten, men de viser sig anderledes for åbnings-, midter- og slutspillet.

Bortset fra i grænseoverskridende tilfælde såsom slutspil eller makker- eller dødvande situationer, kan evalueringsfunktionen ikke levere objektivt korrekte resultater. Ved at kombinere materialet og positionelle komponenter til et enkelt evalueringsnummer muliggør evalueringsfunktionen sortering og valg af det "bedste" eller "værste" træk.

Dynamisk evalueringsfunktion

Evalueringsfunktionen implementeres som regel af programmereren og ændres ikke længere under spillet. En udvidet mulighed er at bestemme sammenlignelige positioner fra en skakdatabase under spillet og dermed optimere vægtningen af ​​positionsparametrene. Dette er mere i tråd med den menneskelige tilgang. En erfaren spiller tager hensyn til kriterier som f.eks. Kongesikkerhed eller beståede bønder, også under hensyntagen til kendte spil og deres resultater.

Kontrol af søgning og togvalg

Grundlæggende er kontrollen med søgningen baseret på spiltræet . Den indeholder, begyndende med den aktuelle position (rodnode), alle tiltrækninger af den tiltrækkende person, derefter igen alle mulige responsbevægelser fra den følgende person og så videre, i hvert tilfælde op til at nå en slutposition (makker, dødvande, teknisk trækning eller gentagelse af positioner). Spiltræet er normalt alt for stort til at blive fuldstændigt beregnet, så programmet er begrænset til en del af det (søgetræ).

I det enkleste tilfælde fungerer programmet efter A -strategien , dvs. Det vil sige, at den beregner alle mulige togsekvenser op til en bestemt dybde (antal på hinanden følgende tog), som er begrænset af computerkraften og den tilgængelige tid. Hver position, der opstår, evalueres. Hvis det ikke er en slutposition som f.eks. En skakmat, bruges den heuristiske evalueringsfunktion. Med Minimax -algoritmen vurderes bevægelserne i rodpositionen, og det højest rangerede træk spilles.

Da antallet af stillinger, der skal undersøges, vokser eksponentielt med dybden, på den anden side medfører en højere dybde en tilsvarende forbedring af færdighedsniveau, er et helt arsenal af accelerationsforanstaltninger opfundet i de cirka 50 års programudvikling, som kan opdelt i to grupper. Nogle forsøger at reducere søgetræets størrelse ved hjælp af generelle datalogiske algoritmer , for eksempel:

• Alpha-Beta Search (Negamax-procedure)
• Hash -tabel til påvisning af togændringer
• Nul bevægelse søgning

Alfa-beta-søgningen afbryder dele af søgetræet, der ikke skal tages i betragtning ved bestemmelsen af ​​det højest bedømte træk i rodnoden. Denne teknologi sparer meget: Med god implementering er den opnåelige dybde næsten fordoblet.

Den begrænsede beregningsdybde gør det ofte muligt for programmet at overse en taktisk kombination. For at afbøde dette uddyber du individuelle interessante trækforløb, f.eks. I henhold til skakregler eller træk, der svækker modstanderens kongestilling for lettere at opdage makkerkombinationer. Den såkaldte recapture heuristic uddyber flytte sekvenser, der indeholder en exchange for bedre at kunne estimere konsekvenserne af exchange. Metoden til entydige udvidelser ( tyske  "isolerede udvidelser" ) uddyber søgen efter tvungne (tvungne) sekvenser af træk, dvs. i tilfælde, hvor der kun er et "rimeligt" svar for en eller begge sider.

Yderligere teknikker til acceleration er brugen af ​​forenklede evalueringsfunktioner i henhold til flytteordrer, der vurderes at have lidt nytte, samt den inkrementelle evaluering, som ikke altid genberegner værdien af ​​en position, men opdaterer den, når et træk foretages lavet. Nogle programmer udfører en stor del af evalueringsarbejdet ved at analysere røddernes position og lagre resultaterne i datastrukturer, som derefter forenkler og fremskynder evalueringen af ​​arkene betydeligt (f.eks. Figurfelttabeller).

Nogle programmer beregner ikke (eller ikke altid) alle træk, der er mulige i en position ( B -strategi ). Togernes værdier estimeres heuristisk, hvorefter kun de højt vurderede er inkluderet i søgetræet. Dette efterligner en menneskelig spillers adfærd. Søgetræet bliver betydeligt mindre, men du risikerer, at heuristen nogle gange overser et godt træk. Disse procedurer er meget vanskeligere at implementere end A -strategien. De kan heller ikke let overføres til andre spil som f.eks.Go , fordi kriterierne for at vælge et træk er helt forskellige.

Du må ikke afbryde beregningen og foretage bladevalueringen, når partiet er midt i en bytte; dette ville resultere i en forvrænget materialebalance. Hvis en part lige har besejret et dækket stykke og er bedømt her, modtager du en falsk materiel overvægt for denne fest. Et middel, der ofte bruges, er den såkaldte hvilesøgning: I en position på bladet beregner man alle slag, og derefter igen kun slagene i svaret osv., Hvorved de mindre lovende streger normalt afbrydes, og maksimal længde af Impact -sekvensen begrænset, så det hele ikke tager for lang tid. I hver position, der nås på denne måde, udføres håndevalueringen af ​​den heuristiske evalueringsfunktion, og positionens værdi er maksimum for håndværdien og værdierne for træk. Håndværdien står for værdierne for de ikke-slagende træk, fordi det kan være, at hvert slag er en fejl, og det er bedst ikke at fange her.

Biblioteker og databaser

Åbner bibliotek

Skak spilles et stykke tid i konkurrence, hvilket betyder, at der kun er et defineret tidsrum til rådighed for et antal træk. Mange skakprogrammer er derfor udstyret med et åbningsbibliotek, hvor der gemmes et stort antal "gode" trækordrer i skakspillets åbningsfase. I den indledende fase af skakspillet kigger programmet op i dette bibliotek, hvilket træk er det mest egnede i en bestemt position på brættet. Denne "kontrol" er hurtigere end beregning af trækket. Den computertid, der er gemt på denne måde, er derefter tilgængelig for programmet i senere faser af spillet. Processen med at gemme bestyrelsesposter inklusive de "gode" træk er kun nyttig til åbningen og slutspillet, da antallet af bestyrelsesposter stadig er håndterbart her. Åbningsbiblioteker med kommercielt tilgængelige programmer vokser i størrelse. De er for det meste genereret fra mesterspil. Dette indebærer en risiko for, at ubemærket fejl accepteres, at programmet ikke ville spille baseret på egne beregninger.

Koordineringen af ​​åbningsbiblioteket med den evalueringsfunktion, der blev brugt senere i spillet, spiller en stor rolle i spillestyrken.

Endgame database

I slutspillet , når der kun er få stykker tilbage på brættet, kan du på forhånd beregne det optimale træk ved hjælp af en fuld analyse ( brute force -metode ). Der er ganske få slutspilspositioner, hvor menneskelig tænkning, men også computeranalyse i realtid, ville blive fuldstændig overvældet. Mange skakprogrammer bruger derfor slutdatabaser, der indeholder alle mulige positioner med 3, 4, 5, 6 eller endda 7 brikker samt deres resultat (hvis spillet er optimalt). Oprettelsen af ​​slutspildatabaser går tilbage til Ken Thompson . De første seksstenfigurer blev fuldt ud beregnet af Lewis Stiller i 1991, og alle syvstensfigurer er blevet registreret siden 2012.

Skakdatabase

Skakdatabaser indeholder spillede spil. De hjælper f.eks. Med at studere åbninger og forberede sig på den næste modstander.

Åbningsbiblioteker kan genereres fra databasen til skakprogrammer. Det er også muligt at bestemme sammenlignelige positioner fra en skakdatabase under spillet og at optimere positionelle evalueringsparametre (se ovenfor) under hensyntagen til spillets gang, der er registreret der (dynamisk evalueringsfunktion).

historie

Skakprogrammets historie er meget nært knyttet til skakcomputerens historie og kan normalt ikke behandles separat. Kun udviklingen af ​​de grundlæggende algoritmer er beskrevet her. For de medieeffektive konkurrencer med spillere i verdensklasse i de seneste år, se Skakcomputere i spillet mod mennesker .

Konrad Zuse

Fra 1942 til 1945 skrev Konrad Zuse verdens første skakprogram på sit nyudviklede programmeringssprog, Plankalkül . Sproget blev først implementeret i 1970'erne.

Alan Turing

Den britiske matematiker og kodebryder Alan Turing udviklede en metode, der tildeler en værdi til ethvert muligt træk. Det bedste træk skal altid beregnes. Turings skakprogram var baseret på følgende principper:

• Hvert stykke modtog en bestemt værdi: bonde = 1; Jumper = 3; Løber = 3,5; Tårn = 5; Queen = 10 og King = 1000 (så dette aldrig kunne ofres).
• Alle hvide bevægelser og alle sorte modbevægelser blev undersøgt. Hvis White var i stand til at lave et slag, så blev alle slag af modstanderen, alle efterfølgende slag af White osv. Undersøgt, indtil positionen var "død", det vil sige indtil der ikke var flere slag og ingen makker. Der blev foretaget et tal i de resulterende positioner og det valgte træk, der fik mest materiale eller tabte mindst. Men da de fleste af de tilgængelige valg til valg leverede det samme resultat (tæt på nul), især i åbningsfasen, indførte Turing også nogle positionelle evalueringskriterier, såsom mobilitet (mulige træk), mulighed for at ramme, castling eller trussel om skakmat.

	-en	b	c	d	e	f	G	H
8.									8.
7.									7.
6.									6.
5									5
4.									4.
3									3
2									2
1									1
	-en	b	c	d	e	f	G	H

Position efter det 29. træk

Da der ikke var nogen egnede programmerbare lommeregnere på det tidspunkt, måtte Turing selv beregne hvert træk i hånden på papir, hvilket betød meget tid. I det mindste blev det funktionelle princip indlysende, ifølge hvilket alle nutidens skakprogrammer stadig fungerer. Det første parti af hans "papirmaskine" fandt sted i 1952 og bør angives her som et eksempel:

Turings papirmaskine - 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 ville få biskoppen 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

Der er også implementeringer til nutidens computere til "papirmaskinen".

Claude Shannon

Den 9. marts 1949 holdt Claude Shannon et foredrag, der var afgørende for udviklingen af ​​skakprogrammer på Bell Laboratories . Der beskrev han det interne tavledisplay, træsøgningen , evalueringsfunktionen og flytningssøgningen ved hjælp af Minimax -algoritmen . Han har allerede givet to forskellige strategier til at bestemme det bedste træk: A-strategi og B-strategi .

Dietrich Prinz

I november 1951 oprettede Dietrich Günter Prinz fra University of Manchester et program til Ferranti-Mark-I-Computer (GB), der løste en todelt parringsopgave på 15 minutter. Programmet anses for at være det første løsningsprogram i skakhistorie.

John von Neumann

-en b c d e f 6. 6. 5 5 4. 4. 3 3 2 2 1 1 -en b c d e f

udgangsposition

John von Neumann klassificerede skakspillet i sin spilteori som et to-person nul-sumspil med komplet information. Denne klasse af problemer (herunder tic-tac-toe ) kan løses med minimax-algoritmen . Skak er imidlertid for komplekst til helt at kunne gennemgå søgetræet. Skakprogrammer er derfor afhængige af tilnærmelsesmetoder.

John von Neumanns skakprogram blev afsluttet i midten af ​​1950'erne og kørte på MANIAC I-rørcomputeren , der blev oprettet i 1950 . For enkelthedens skyld blev det kun spillet på et 6 × 6 bræt. Programmet spillede i alt tre kampe: den første mod sig selv, den tabte en anden mod en stærk skakspiller, selvom sidstnævnte gav ham en dronning, og den tredje vandt den mod en ung kvinde, der kun havde spillet skak i en uge og især for dette Havde trænet spil.

-en b c d e f 6. 6. 5 5 4. 4. 3 3 2 2 1 1 -en b c d e f

Position efter det 21. træk

MANIAC I - Man, Los Alamos, 1956:

(6 × 6 bræt uden biskop, intet dobbelt trin eller kastel)

1. d3 b4 2. Nf3 d4 3. b3 e4 4. Ne1 a4 5. bxa4 (5. Nd2 sammen med 6. Nc4 + Nxc4 7. bxc4 med godt spil) 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 (for at forhindre 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

For første gang har et menneske tabt til et skakprogram. Denne forenklede variant af skak kaldes også Los Alamos Chess .

I 1957 implementerede IBM -medarbejderen Alex Bernstein et skakprogram på en IBM 704, der spillede efter standardreglerne. Den valgte de syv mest sandsynlige træk i hver position og foretog en søgning efter 4 halvtræk, hvilket krævede cirka 8 minutters beregningstid. Bernstein modtog støtte fra den amerikanske stormester Arthur Bisguier under udviklingen . Programmet tabte til skakmesteren Edward Lasker uden chance , men han certificerede computeren til at være et acceptabelt amatørniveau.

I 1958 blev alfa-beta-søgningen opdaget af Allen Newell , John Clifford Shaw og Herbert A. Simon og bragte et kæmpe boost i ydeevnen.

Richard Greenblatt

	-en	b	c	d	e	f	G	H
8.									8.
7.									7.
6.									6.
5									5
4.									4.
3									3
2									2
1									1
	-en	b	c	d	e	f	G	H

Skakmat efter det 37. træk

Det første program til at deltage i menneskelige turneringer var Mac Hack , udviklet af Richard Greenblatt på MIT fra 1965 til 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

Fra 1967 til 1970 var der et boom i skakprogrammering, der kulminerede i det første mesterskab i skak i historien , som blev afholdt af Association for Computing Machinery (ACM) . Vinderen blev Chess 3.0 .

Peter Jennings

I 1976 udviklede Peter Jennings Microchess til KIM-1 hjemmecomputeren. Programmet blev solgt over 50.000 gange i 1979, hvilket gjorde det til det første kommercielt succesrige mikrocomputerprogram. På grund af RAM -hukommelsen på kun 1152 bytes blev castling , en passant og bondekonvertering ikke implementeret.

Ken Thompson

Ken Thompson udviklede den berømte Belle -skakmaskine i 1979 , som arbejdede med et åbningsbibliotek og hashtabeller .

Feng-hsiung Hsu

Det første computerprogram, der slog en regerende verdensmester i skak i et almindeligt turneringsspil, var Deep Blue . Udviklet af IBM på grund af ophidselse og under ledelse af den unge computerforsker Feng-Hsiung Hsu, besejrede dette program den 10. februar 1996 til en tilpasset og optimeret til skakcomputerhardware, som også stammer fra IBM, dengang verdensmester Kasparov i en karakteriseret kendt blive del . Garry Kasparov kunne vinde konkurrencen 4-2. Imidlertid tog en forbedret version af Deep Blue denne forhindring den 11. maj 1997 og opnåede en samlet sejr over Kasparow med 3,5: 2,5 i en anden konkurrence med det sjette turneringsspil. Deep Blue blev demonteret og malet efter den spektakulære sejr. Programmets oprindelse blev senere beskrevet i en bog af opfinderen.

Chrilly Donninger og Ulf Lorenz

Den første, der efter Deep Blue flyttede til konstruktionen af ​​specialiserede skakhardwarekomponenter som grundlag for et skakprogram, var den østrigske skakprogrammør "Chrilly" Donninger, der tidligere havde deltaget i computerskaksturneringer i årevis med sit pc -program. Fra 2002 designede han en skakcomputer med hardware, han selv modificerede, som han oprindeligt kaldte Brutus. Finansiering af ChessBase trak sin støtte tilbage efter den dårlige præstation ved en turnering i Graz i 2003; Christian Donninger og Ulf Lorenz forfulgte oprindeligt projektet på egen hånd under det nye navn Hydra . I 2004 fandt Donninger og Lorenz en ny sponsor fra De Arabiske Emirater, PAL Computer Systems . I samme år slog Hydra den daværende computer -verdensmester Shredder . I juni 2005 fandt en konkurrence sted under turneringsforhold mod den britiske stormester Michael Adams , derefter syvende på verdensranglisten, som Hydra vandt med en overlegen score på 5,5: 0,5. Dette svarer til en turneringspræstation på over 3100 Elo -point, mere end nogen nogensinde har opnået. I denne version med 64 processorer var Hydra i øjeblikket det mest kraftfulde eksisterende skak-computersystem i verden.

Aktuelle udviklinger

Fordelingen af ​​beregningsindsatsen over mange individuelle delprocesser, som kan køre parallelt og dermed bruge multi-processorsystemer fornuftigt, er ikke triviel på grund af træsøgningen og er et aktuelt forskningsområde inden for skakprogrammering (se Hydra ).

Inden for konventionelle pc-skakprogrammer har parallel brug af flere processorkerner været mulig i en årrække og sker gennem de såkaldte "dybe versioner" af de respektive motorer. Denne udvikling fulgte med den stigende spredning af den tilsvarende pc-hardware med multi-core processorer. Det samme gælder nu for operativsystemer med 64-bit arkitektur og specielle skakprogramversioner, der med fordel understøtter dem eller kører hurtigere på dem end 32-bit versionerne.

En muligvis ny trend er brugen af ​​et særligt stort antal CPU'er, men i modsætning til Hydra på basis af konventionelle computere, kombineret til såkaldte klynger. Turneringsindsatser på motorerne Toga og Rybka på klyngehardware er blevet kendt.

Konkurrencer

Der er forskellige konkurrencer , hvor skakprogrammer måler hinanden med hensyn til deres færdighedsniveau, sjældent også mod menneskelige skakspillere. En af de vigtigste er verdensmesterskabet i (åbent) computerskak, World Computer Chess Championship (WCCC), der har været afholdt siden 1974 og er åbent for alle former for hardware og software . Den ældste begivenhed var North American Computer Chess Championship (NACCC), der blev afholdt fra 1970 til 1994 . Derudover var der fra 1980 til 2001 et særligt verdensmesterskab i skak kun for mikrocomputere , World Microcomputer Chess Championship (WMCCC).

Elo -bedømmelser

Skakprogrammer kan også få et Elo -nummer, der beskriver deres færdighedsniveau. Til sammenligning: En verdens skakmester i dag er i størrelsesordenen Elo 2850. Elo -tallene i computerrangeringer kan ikke let sammenlignes med menneskelige skakspillere, da de næsten udelukkende blev bestemt gennem spil mellem computere. Med hensyn til værdiansættelsens absolutte størrelse er der ingen kalibrering mellem præstationsskalaer for menneskelige mesterspillere og skakprogrammer; dette ville kræve meget mange seriøse konkurrencespil mellem de to grupper af spillere. Det betyder, at talniveauet i rene computerklassificeringslister nødvendigvis skal være baseret på en plausibel eller praktisk antagelse, og de konkrete resultater af programmerne mod hinanden bestemmer blot rangeringen og afstandene mellem deres vurderinger.

På grund af de grundlæggende forskellige metoder for mennesker og computerprogrammer, når man spiller skak, betyder et højt niveau af dygtighed mod et andet skakprogram ikke nødvendigvis en tilsvarende bedre præstation mod en menneskelig modstander. Konkurrencer mellem skakprogrammer siger derfor kun noget om niveauet for spil mod mennesker i begrænset omfang. Imidlertid har praksis vist, at et højt niveau af færdigheder mod programmer normalt også betyder en høj grad af dygtighed mod mennesker. Rybka -programmet var i stand til at vinde mod forskellige stormestre - nogle med et bondehandicap  . Andre programmer er nu endnu stærkere.

En vurdering af skakprogrammers og skakcomputers spilstyrke er også mulig ved hjælp af en række skakproblemer. For eksempel består en test kaldet BT2450 af 30 positioner, for hvilke det respektive løsningsflyt kan findes. Ud fra de nødvendige tidspunkter for alle positioner beregnes en BT2450 testværdi, som i begrænset omfang kan sammenlignes med Elo -antallet af menneskelige spillere. Der er nu andre, nogle gange mere omfattende og / eller mere vanskelige tests, der er oprettet og brugt inden for computerskakfællesskabet.

Se også

• Computer Chess Rating Lists (CCRL)
• Forsyth-Edwards notation (FEN)

kilder

1. ↑ CCRL 40/4. Hentet 9. januar 2021.
2. ↑ CCRL 40/40. Hentet 9. januar 2021.
3. ↑ CCRL 404FRC. Hentet 9. januar 2021.
4. ↑ CEGT 40/4. Hentet 9. januar 2021.
5. ↑ CEGT 40/20. Hentet 9. januar 2021.
6. ↑ CEGT rangliste. Hentet 9. januar 2021.
7. ^ Herbert Braun: Påstand om plagiat mod verdensmestre i computerskak. I: Heise.de. 1. marts 2011, adgang til 9. januar 2021 . 
8. ↑ Niyas Khasanov: Ufim. I: WBEC-Ridderkerk.nl. Hentet 9. januar 2021 . 
9. ↑ Jon Dart: Arasan skak. I: ArasanChess.org. Hentet 9. januar 2021 . 
10. ↑ Riddere. I: Sourceforge.net. Hentet 9. januar 2021 . 
11. ↑ Lomonosov Endgame bordbaser. I: chessok.com. Hentet 9. januar 2021 . 
12. ↑ Velkommen til online 7-mands bordbaser. I: tb7.chessok.com. Hentet 9. januar 2021 . 
13. ^ Raúl Rojas et al. (FU Berlin): Konrad Zuses Plankalkül - Dens tilblivelse og en moderne implementering. ( Memento af 23. april 2012 i internetarkivet ). I: zib.de. Konrad Zuse internetarkiv. Hentet 9. januar 2021.
14. ↑ ^{a b c} Dieter Steinweder, Frederic A. Friedel: Skak på pc'en. Markt und Technik, Haar f. München 1995, ISBN 3-87791-522-1 , s. 33-35.
15. ^ Frederic Friedel: Rekonstruktion af Turings "Papirmaskine". I: ChessBase .com. 23. september 2017, adgang til 9. januar 2021.
16. ↑ Eric van Reem: Drømmen om computerskak. Lidt historie om computerskak. I: scrkuppenheim.de. Januar 2003, adgang 9. januar 2021.
17. ^ Feng-hsiung Hsu: Bag Deep Blue. Princeton University Press, Princeton / Oxford 2002, ISBN 0-691-09065-3 .
18. ↑ Lars Bremer: Computerskak: Stormester i Hydra udklasset. I: Heise.de. 28. juni 2005, adgang til 9. januar 2021 . 
19. ↑ Ratingliste. I: ssdf.bosjo.net. 31. december 2020, adgang til 9. januar 2021 . 

litteratur

• Rainer Bartel, Hans-Joachim Kraas, Günther Schrüfer: Den store computer skakbog . Data Becker, Düsseldorf 1985, ISBN 3-89011-117-3 (god introduktion til programmering af computerskak med eksempler i BASIC ).
• Computerskak og spil (CSS). 1/1986 til 6/2004 (derefter kun online); Magasin hovedsageligt om computerskak.
• Claude Shannon : Programmering af en computer til at spille skak. I: Filosofisk magasin. 1950/41, s. 256-257.
• Claude Shannon: Programmering af en computer til at spille skak. I: Scientific American. 2/1950, s. 48-51.
• Dieter Steinwender , Frederic A. Friedel : Skak på pc'en. Markt und Technik, Haar bei München 1995, ISBN 3-87791-522-1 (historie om computerskak, didaktisk skakprogram med kilder i BASIC og C , inkl. CD).

Weblinks

• Side af Ed Schröder. ( Memento fra 30. januar 2010 i internetarkivet ). Forfatter til Rebel og ProDeo, en masse oplysninger om computerskak og detaljerede beskrivelser af Rebel 's indre virke. ( Memento fra 31. maj 2010 i internetarkivet ). (Engelsk).
• Skakprogram Micro-Max. Skakprogram i C med mindre end 2000 byte kildekode (engelsk).
• Verdens første skakprogram som en moderne Java -applet.
• B. Monien, U. Lorenz, D. Warner: Alfabetets algoritme. Hvordan får jeg min computer til at spille skak? ( Memento fra 15. december 2015 i internetarkivet ). 2006.
• 9. verdensmesterskab i computerskak fra 14. til 20. juni 1999 i Paderborn. Rapport om TeleSchach .
• Online fortsættelse af det tidligere magasin Computerschach und Spiele.
• SSDF -computerrangering.
• CEGT -rangering.
• Mikrochess - det første mikrocomputer -skakprogram.
• Wiki til skakprogrammering (engelsk). ( Memento fra 20. januar 2010 i internetarkivet ).