Utbildningsprojekt schack och artificiell intelligens. Towards Deep Blue: En steg-för-steg-guide för att skapa en enkel AI för att spela schack

Matchen är förlorad: datorn mot personen.

Kreativt tänkande, logik, erfarenhet är de egenskaper som gjorde det möjligt för en person att leda i "man-maskin"-kampen. Det verkade som att dessa fördelar alltid kommer att vara människans hemliga vapen, och datorn kommer att spela rollen som "att komma ikapp".

Men det tog ganska lång tid för artificiell intelligens att komma ikapp och för alltid överträffa människor på många områden, inklusive inom området intellektuell underhållning.

Artificiell intelligens slog människan: var och hur

Rubiks kub
Detta pussel är känt över hela världen. Miljontals människor försöker slutföra uppgiften och samla in kuben på rätt sätt, och vissa tävlar till och med i monteringshastigheten. Det mänskliga rekordet sattes av 14-årige Lucas Etter från USA, som löser pusslet på 4,904 sekunder. Otroligt, eller hur? Men detta resultat överträffades av roboten, som skapades av två entusiaster Jay Flatland och Paul Rose: resultatet av roboten är 1,047 sekunder.

Tack vare de inbyggda kamerorna, och det finns fyra av dem, utvärderar datorn positionen och väljer den bästa algoritmen för åtgärder. Systemet är baserat på Kotzebue-formeln (sammansättning i 20 drag). Knappast någon av personerna kommer att kunna lösa Rubiks kub snabbare än 1 sekund.
0:1 till förmån för artificiell intelligens.

"Othello"
Toppen av popularitet för detta spel faller i början av 70-talet av förra seklet. Kärnan i spelet är att placera marker på spelplanen (8 × 8 celler): du måste blockera raderna av motståndarens marker på båda sidor med marker av din färg, sedan ändrar markerna färg och går till motståndaren. Segern går till den som upptar det största området.

1980 var Hiroshi Inouye världsmästare i Othello och besegrade enkelt Moor-programmet med 5-1.
Senare lärde sig programmen att räkna ut motståndarens drag (med cirka 25 drag), och när den regerande världsmästaren Takeshi Murakami möttes i en revansch med Logistello-systemet 1997 blev ställningen förkrossande 0:6 till förmån för mjukvaran.

Backgammon
Artificiell intelligens har sin fördel i backgammon framför människor att tacka världsmästaren i korrespondensschack (och det finns sådana) Hans Berliner, som skrev BKG 9.8-programmet. Och 1979 visade sig programmet vara starkare än världsmästaren i backgammon Luigi Villa.

Man tror att datorn hade tur i det spelet (bra tärningar ramlade ut flera gånger), men ingen annan ville slåss i en upprepad revansch, speciellt eftersom mjukvaran har förbättrats upprepade gånger sedan den tiden.

Schack
Schacksystem började utvecklas i mitten av nittonhundratalet, utvecklingen tillhörde IBM. Men på grund av att programmet krävde seriösa och långa beräkningar fick denna satsning skjutas upp i 30 år. 1996 ställdes Garry Kasparov mot "schackhjärnan" - Deep Blue-datorn.

Matchen slutade till mannens fördel: 3 vinster, 2 oavgjorda, 1 förlust. Ett år senare upprepades matchen, och denna gång var Deep Blue mer förberedda. Ändå utvärderade systemet 200 miljoner positioner per sekund. Och även om Harry ville tjäna tillbaka senare, vägrade IBM, eftersom det ansåg att det var meningslöst.

Dam (ett slags pjäser)
Marion Tinsley var Checkers Champion under hela sin karriär. Och när han 1992 träffade ett system utvecklat vid University of Alberta (Kanada), var segern hans. Av 39 matcher - 4 vinster, 2 förluster och 33 oavgjorda.

Efter 2 år ägde en revansch rum, men Tinsley drog sig ur tävlingen på grund av hälsoproblem (vid tidpunkten för vägran fanns det 6 oavgjorda spel), och segern gick till systemet. Sedan det ögonblicket har artificiell intelligens blivit mycket starkare: 2007 tillkännagav kanadensarna skapandet av ett idealiskt system, och ingen från människor försöker överträffa det i pjäser.

Scrabble
Datorns triumf i det här spelet var lätt även i den allra första omgången: världsmästaren David Boyce slogs 2006 av robo-rivalen Quackle.

Förresten, det här programmet är tillgängligt på webben, och du kan mäta din styrka med det, och kanske kommer du att ge seger till "Man"-laget.

Gå
Det här spelet dök upp i det antika Kina för mer än två tusen år sedan, men trots en så lång erfarenhet av spelet förlorade människor fortfarande. På banan (19 × 19) placerar två spelare sina stenar (svart/vit), den som får fler poäng (marker räknas på en rad) vinner. Å ena sidan är allt enkelt, men intresset ligger i mängden möjliga alternativ och drag.

Det var också intressant för utvecklarna av AlphaGo (skapat i Googles regi) att skapa ett system som kan beräkna tusentals alternativ. Till en början försökte artificiell intelligens med annan mjukvara, och när 499 av 500 spel var för AlphaGo, tog den sig an den trefaldige europamästaren Fan Hui. Mästaren hade ingen chans: 5:0.

TV
Gillar du att svara på frågor om frågesporter? Utvecklarna av Watson-roboten från IBM kunde inte heller motstå, och 2011 agerade Watson som deltagare i Jeopardy! Trots att hans motståndare var showens rekordhållare - Brad Rutter och Ken Jennings - vann han, och miljonen dollar som vunnits donerades till välgörenhet.

Och även om datorn redan har visat sin intellektuella och logiska överlägsenhet gentemot människor, fortsätter den att utvecklas. Så Alibaba Group och Microsoft (utvecklingen genomfördes parallellt) introducerade artificiell intelligens, som visade sig vara starkare än en person när det gällde att förstå den lästa informationen.
Stanford University-testet är mer än 100 000 frågor baserade på femhundra artiklar från Wikipedia-biblioteket.

Den bästa indikatorn för en person är 82.304 poäng, resultatet av Alibaba är 82.44, Microsofts neurala nätverk är 82.605. resultaten tyder på att artificiell intelligens kan svara på alla frågor med hög noggrannhet, vilket gör att teknologier kan användas för att betjäna kunder, patienter, museibesökare etc.

Även dataspel dämpades av programmet. Programmet vann programmet: vem skulle ha trott att denna framtid är så nära? Det populära spelet Quake III, där spelarna är gladiatorer, är väldigt populärt inom eSport. Men de bästa här var inte människor, utan DeepMind-botteamet, skapat av en division av Google. Och även om striden hölls i en trunkerad version, enligt beräkningar, med en varians på 73 %, skulle boten vinna i vilken tävling som helst.

Är sådan överlägsenhet av artificiell intelligens farlig eller inte? Ingen kan svara säkert. Och i slutändan kommer det här svaret inte att vara nyckeln, för det viktigaste är inte det faktum att en person är sämre än en dator, utan om vi kan använda denna potential för vår egen fördel. Som vi kan se slår artificiell intelligens en person och lämnar ingen chans att vinna.

Historien om utvecklingen av automation och datorteknik är märkligt förknippad med schack. På XVIII-talet. "tänkande" schackautomater användes för trick och bluff. Den första apparaten med riktig artificiell intelligens, skapad i Spanien i början av 1900-talet, kunde schackmatta en schackspelare med en kung och ett torn. Tydligen är det ingen slump att en av de första verkligt intelligenta uppgifterna som tilldelades programmerare i början av datoranvändningen var schackspelet. En av dem som skapade de första schackprogrammen, doktor i tekniska vetenskaper, professor Vladimir Lvovich Arlazarov, pratar om schackprogram och kopplingen av detta uråldriga spel med utvecklingen av artificiell intelligensteknologi.

– Vladimir Lvovich, hur kom du på idén att en dator kan lösa intellektuella problem?

– När man fick reda på att datorer inte bara kan beräkna, som det uppfanns från första början, att bakom aritmetiska operationer finns en logisk operation som inte bara utför hjälpfunktioner i datorprogrammens aktiviteter, utan också med hjälp av som det är möjligt att lösa oberoende problem, blev det klart: det är värt att försöka lägga intellektuella uppgifter på datorn. Någonstans från slutet av 40-talet till slutet av 50-talet diskuterades detta aktivt, dessutom ställdes halvfilosofiska frågor: kanske datorer blir smartare än människor? Och sen då? Och på fullaste allvar. Nu ställs inte sådana frågor, trots allt har det gått 40 år. Sedan, vid beräkningens gryning, insåg vi först vad maskiner kunde göra i princip. Vi insåg att den mänskliga hjärnan är en enhet som liknar en dator, och tusen, en miljon gånger kraftfullare, men den är i grunden lite annorlunda. Det blev tydligt att åtminstone de flesta av de rationella problem som en person löser kan sättas framför en maskin. Därför kan du försöka skriva program som löser dessa problem. En, två, tusen ... trots allt löser en person inte ett oändligt antal problem. Och det är möjligt, så att säga, att programmera all intellektuell aktivitet hos en person.

– Och varför valde du att vända dig till spelet?

”Det har som sagt varit mycket diskussion om huruvida en maskin kan tänka. Det är dock helt klart att om vi pratar om programmerare, om människor som inte sysslar med filosofi, utan med en riktig dator, så är frågan inte om en maskin i grunden kan göra något, utan i sökandet efter exempel på var maskiner bestämmer intellektuella uppgifter, och de som är tillgängliga för en person i hans intellektuella verksamhet. Gränsen här är naturligtvis inte klar. Men det är uppenbart att om en person multiplicerar 20-siffriga nummer, hanterar han inte en djupt intellektuell uppgift, eftersom det är mycket lätt att hitta en trivial algoritm för dess implementering, som är känd för varje skolbarn. Men de uppgifter där det är helt klart att en person inte har någon a priori-algoritm, men han ändå löser dem väl, kommer vi att kalla intellektuella. De första utmanarna till rollen för sådana uppgifter är spel, av den enkla anledningen att åtminstone reglerna är tydligt formulerade. Uppgiften är extremt svår, och spelreglerna är lätta att formulera, och därmed är det lätt att bestämma maskinens funktioner. Å andra sidan är schack en svår uppgift för en person, som på något sätt aldrig har diskuterats och som inte diskuteras nu.

– Och varför valde du schack från spelen? Kanske en tradition?

Varför bara schack? Vi provade även crossfilmer och andra spel. Men schack har många fördelar jämfört med andra spel. Om en maskin i enkla spel slår en person, så förvånar detta ingen. Schack är ett svårt spel, och datorns seger är betydande här. Sedan i schack, till skillnad från ett antal andra spel, finns det många differentierbara kvalitetskriterier, det vill säga man kan avgöra: maskinen spelar bra, maskinen spelar bättre, bättre, bättre. I många andra spel är sådana graderingar mycket svåra att fastställa. I vissa av dem lärs maskinen antingen att spela absolut exakt, och därmed försvinner omedelbart allt intresse för spelet, eller så spelar den väldigt dåligt. Och i schack, inte abstrakt, men så att säga bemästrat, finns det så många nivåer att det med deras hjälp är möjligt att bestämma klassen för maskinens spel.

– Så det är tydligt varför schack var en av de första och viktigaste uppgifterna för artificiell intelligens. Vilka metoder användes för att lösa det?

– Redan från början bemästrades tekniken att lösa problemet med ett schackspel gradvis. I princip är schack ett ändligt spel, och med matematisk noggrannhet kan det bevisas att det i vilken position som helst finns ett abstrakt bästa drag för var och en av motståndarna, och därav ett resultat. Därför är det nödvändigt att beskriva en algoritm där detta spel kan beräknas till slutet. Den enda nackdelen med denna algoritm är att det tar lång tid. Och vi har inte kommit i närheten av de tidsordningar som behövs för att räkna ut, säg, schack till slutet från utgångsläget. Under de senaste femtio åren har uppgiften tidsmässigt förblivit oändligt komplex. Tja, oändlighet minus tio är fortfarande oändlighet. Men om du behöver tid, säg, 10 till 100:e potensen av år, och du snabbar upp bilen, säg, 100 gånger, och får 10 till 98:e potensen av år, då är det osannolikt att detta får dig att må bättre. Därför är huvudalgoritmen uttömmande, trivial: om jag går den här vägen har fienden så många möjligheter. Alternativen växer exponentiellt och bildar kedjor. Men antalet positioner är i allmänhet ändligt, och det finns inte så många av dem på varje kedja. Kedjor kombineras till träd, som återigen inte är oändliga. Det är sant att de växer exponentiellt och antalet kedjor ökar. Så en viktig fråga uppstår: behöver vi en fullständig, ända till slutet, uppräkning - till alla mattor, dödlägen, trippelrepetitioner och andra avslut av spelet enligt schackreglerna? När allt kommer omkring, om algoritmen leder till positioner som inte krävs på det här trädet, behöver kanske inte hela detta träd beaktas. Lägg märke till dig själv att i en disposition där vit schackmatt är i ett drag, kan du bygga samma oändliga träd, men du behöver inte tänka på det, men det räcker för att hitta detta enda drag. Kanske är situationen densamma inom schack i allmänhet? Generellt sett är algoritmen för uppräkning, uppräkning av alternativ relaterad till så många uppgifter lösta av en person att om vi kunde organisera det på något mycket originellt sätt, så skulle det på sätt och vis vara som uppfinningen av ett hjul för mänskligheten - en av grundläggande upptäckter. Så, uppräkning kan vara, och kanske är det, hjulet för artificiell intelligens.

– I en av artiklarna om artificiell intelligens läste jag att intelligens är förmågan att förstå och välja. Naturligtvis är det mycket svårt att lära en dator att välja mellan en mängd olika alternativ. Men visst är vissa lösningar som är specifika för schack möjliga?

- Jaja. Detta problem måste lösas snabbt och effektivt, och i schack kom man snabbt fram till följande teoretiska formulering av frågan: låt oss inte titta på ett oändligt antal drag, utan bara ett fåtal drag framåt. Låt oss säga att vi ser 5 steg framåt. Det här är mycket. Om du älskar schack och 5 drag verkar inte räcka för dig, så låt oss ta 10. Och sedan kommer maskinen för 10 drag, 20 halvdrag framåt inte att göra misstag i någonting och garanterar att du efter 10 drag inte har färre pjäser. Det är klart att vi har att göra med en stark spelmaskin. Så spelträdet måste reduceras och problemet lösas på ett mycket mer begränsat utrymme. En annan fråga är att de försöker överväga detta träd inte helt, med hjälp av matematiska beskärningsmetoder. Jag har redan pratat om en av dem: om det finns en schackmatt i ett drag finns det ingen anledning att titta på andra alternativ. Andra algoritmer är heuristiska, inte exakta. I genomsnitt fungerar de korrekt, många är absolut exakta, men de kan ha fel. Till exempel kan vi gå igenom inte alla drag, utan bara fångst, och beräkna dem långt framåt, eftersom det finns få fångster. Det totala djupet av rörelserna är litet: du kan inte äta mer än trettiotvå stycken. Därför är längderna på kedjorna små och det finns få grenar. Naturligtvis är det klart att man inte kan bygga ett spel på enbart fångster, det måste finnas några positionsöverväganden. Kombinationen av forcering (fånga, kontrollera) och positionsöverväganden, samt ett visst djup av uppräkning, är grunden för alla befintliga algoritmer, och det förändras inte mycket. En annan fråga: hur väljer jag de drag som jag kommer att överväga vidare? Baseras det bara på enkla formella kriterier (fånga, kontrollera) eller är det för att koppla dessa drag, som schackspelare gärna säger, med en plan, för att komma på någon form av kedjor som har någon form av gemensam egendom? Det har i alla fall skrivits en hel del seriösa verk med praktisk tillämpning om detta. Det är inte för inte som ganska välrenommerade företag är engagerade i skapandet av schackprogram.

– Och när dök de första schackprogrammen upp?

– Riktiga schackprogram dök först upp någonstans i slutet av 50-talet i Amerika, och sedan någonstans i början av 60-talet – i vårt land. Programmen var väldigt svaga, för då fanns det både extremt primitiva maskiner och vårt tänkande, som ännu inte var vant vid nyhet. Vi engagerade oss i denna verksamhet runt 1963. Sen på våra inrikesbilar blev det några matcher. Enligt min mening var det 1967 den första matchen mellan Sovjetunionen och USA. Det hette så, även om det naturligtvis skedde mellan två lag, och inte länder. Det var en matchning mellan vårt program, utvecklat vid Institutet för teoretisk och experimentell fysik, och programmet av John McCarthy, en mycket känd person i datorvärlden, en av skaparna av programmeringsspråk, som då var förtjust i schackprogram. Flytten sändes med telegraf, för då fanns inga nätverk.

- Och vem vann?

– Vi vann sedan med 3:1. Spelade 4 matcher. Ett drag gjordes om dagen, eftersom amerikanerna hade kraftfullare och djupare program som tänkte länge, och vi spelade på olika versioner av program som tänkte både snabbt och långsamt. Vår vinst var vår första prestation. Denna riktning började utvecklas gradvis och blev särskilt aktiv på 70-talet. Omkring 1974 hölls det första schack-VM i Stockholm. Cirka åtta program deltog, inklusive vårt. Och så vann vi också och blev första världsmästare. Sedan dess har världsmästerskap hållits regelbundet, vart tredje år. Vi deltog i dem 2 gånger till - 1977 och 1980. Vi vann inte Lavrov då, för 1977 delade vi 2:a och 3:e platserna (många schackprogram deltog, det fanns till och med regionala urval), och 1980 - 4:e och 5:e plats. I allmänhet rullade de långsamt tillbaka. Faktum är att vid den här tiden gjordes det redan stora framsteg inom datoranvändning, och vi spelade fortfarande på datorer som var ganska föråldrade. Och 1980 blev det klart för oss att tävlande på de maskiner som vi arbetar med hade förlorat all mening, och i allmänhet började arbetet med schackprogram att gå till intet i Ryssland. Även om det fanns en hel del intressanta teoretiska verk. Lite senare skapade de det första, kanske, programmet som gick runt i världen, hon visste hur man absolut exakt spelar ett komplext slutspel, det vill säga en dam och en bonde mot en dam, eller ett torn och en bonde mot ett torn . Programmet betraktade helt enkelt sådana slutspel till slutet, det vill säga i vilken position som helst gav det ett idealiskt korrekt drag. Algoritmen byggdes på principer som skiljer sig något från enkel uppräkning, på en fullständig inspektion av hela uppsättningen positioner. Nåväl, och så gjordes några verk av denna karaktär i schack. Och så sa vi adjö till det praktiska spelet, eftersom skillnaderna i hastigheter redan var hundratals gånger. Men mästerskapen fortsatte, och utvecklingen av schackprogram flyttade till en helt ny nivå, så snart allt flyttade till PC. Som ett resultat av utbredd kommersialisering började enorma summor pengar att investeras i schackprogram, allt blev omedelbart hemligt. Och tidigare tillhörde de forskare som, om de inte tvingas med avsikt, inte döljer sina prestationer, utan tvärtom sprider dem. 1980 kände vi för första gången att det var dags för kommersiell programmering. Den här världen är naturligtvis unik. För det första för att pengar investeras i det, och för det andra för att pengar utvinns från det. Även om det finns tidningar om schackprogram, men under de senaste 15 - 17 åren har det verkliga utbytet av idéer minskat avsevärt, eftersom de på PC har blivit en enorm verksamhet.

– Men handeln stimulerar utvecklingen av schackmjukvarumarknaden, eller hur?

– Tidigare var datortävlingar tidsbestämda att sammanfalla med datateknikforum. Det finns en sådan organisation - IFI (International Federation for Informatics) och, vanligtvis, var världsmästerskap tidsbestämda att sammanfalla med dess kongress. Nu har de blivit helt oberoende evenemang, ganska prestigefyllda. Det finns hundratals och hundratals sådana program. Själva programmeringsnivån och kunskapsnivån är redan sådan att det inte är den minsta svårighet att göra ett enkelt schackprogram. Detta är normalt elevarbete. Jag anförtror det bara till någon student. Att slå ett schackprogram har blivit så att säga en vardag.

– Men som alltid blir den lägre nivån enklare, medan den högre blir mer komplicerad?

- Det är allt. Därför har de senaste programmen, de som nu vinner, i synnerhet programmet som besegrade Kasparov, blivit mycket starkare. Sökdjupet har vuxit avsevärt och detta är naturligtvis resultatet av våra matematiska framsteg, och delvis bara datateknikens framsteg. När allt kommer omkring, om tidigare övervägande av 1000 positioner per sekund ansågs mycket, nu i de träd som vi redan har pratat om, övervägs mer än en miljon positioner. Och en extra miljon är flera nivåer av drag med rätt urval. Och varje nivå av sökdjup förbättrar programmet avsevärt. Varje steg ett steg framåt är ungefär en rang, och säg, ett sökdjup på fyra drag är den tredje rangen, och fem drag är redan den andra rangen. När vi når nivån 11–13 drag är detta en masternivå och det är ganska svårt att spela vidare med maskinen. Naturligtvis leder nu amerikanerna, för de vet hur man investerar stora pengar i sådant.

– Varje artificiell intelligensprogram för beslutsfattande behöver inte bara heuristiska mekanismer utan också någon form av kunskapsbas. Vad är förhållandet mellan kunskapsbasen och algoritmer som genererar positioner i schackprogram?

– Det kan ingen säga säkert, för det här är föremål för spekulationer. Det fanns program som var tillräckligt starka med bara minimal kunskap, medvetet minimal, specifikt för att se vad som kunde pressas ur ren matematik. Vid någon tidpunkt berodde detta på kommersialisering, och särskilt på det faktum att de började göra de mest kraftfulla programmen - det spelar ingen roll på bekostnad av vad. Men delvis på grund av att arbetet med inbäddad kunskap är en självständig uppgift finns det många. Först och främst skapades en enorm katalog. Nu är kataloger hundratusentals positioner. Sedan satsas alltid mycket schackintelligens på att utvärdera positioner. Det handlar förstås om spelmaterial, vilket är trivialt, och vissa positionsfaktorer. Så, positionella faktorer är rent schackintelligens, som naturligtvis är programmerad, men här läggs mycket av den och den förbättras ständigt. Och ju fler faktorer som satsas där, desto starkare blir programmet. På sätt och vis är förmågan att utvärdera positionen och djupet av uppräkningen utbytbara saker. Om vi ​​kunde utvärdera positionen på ett genialiskt sätt, då skulle det räcka för oss att prova alla första drag. Detta är som ett extremt exempel. Det är tydligt att en bättre positionsuppskattning har motsvarande större effekt på sökdjupet. Detta är den andra, grundläggande metoden. Det finns en hel del program där schackintellekt är inbäddat i valet av de alternativ som övervägs, det vill säga några rena schacköverväganden, vissa planer. Det finns en hel del sådana överväganden, vilket begränsar uppräkningsområdet. Omfattningen av deras åtgärder är inte särskilt bred, och intellektuellt-schackspecifika data saktar ner uppräkningen. Förresten, det var just för intellektuella saker som Botvinnik en gång mycket starkt förespråkade. Han var en stor entusiast av maskinschack och bidrog med några idéer till det. Även om han aldrig lyckades skapa ett fungerande program, var hans auktoritet då mycket hög. Så han var väldigt upprörd över att regien generellt sett inte var så "intellektuell" som han skulle önska, och en mycket begränsad mängd rent schackkunskaper satsades på programmen.

– Hur är det med specialiserade schackdatorer? De agerar tydligen precis genom generationsmetoden?

- Självklart, självklart. För det första, i betydelsen generation, är uppräkning schematisk. För det andra är alla positionstabeller inte mindre viktiga, för i schack är upprepningen av positioner mycket hög. Du går E4E6D4 eller D4E6E4 - positionen kommer att vara densamma, och det är bara 3 halva drag. Och när vi börjar gå djupare är repeterbarheten av positioner mycket hög. För det tredje det tekniska området. Faktum är att vi en gång byggde teorier om för vilka positioner lokala förändringar i grunden inte kan leda till en förändring av påtvingade alternativ, hur man skapar någon form av mallar. Mallarna för sådana alternativ passar bra in i olika rent tekniska system för en dator. Naturligtvis är referensdiagram mycket viktiga.

– Finns det några sätt att skapa en universell mental apparat i vilken man skulle kunna lägga en kunskapsbas - oavsett schackpositioner eller något annat, de regler enligt vilka man måste arbeta med denna kunskap - och få adekvata resultat av den?

– Det är klart att konstruktivt sett kan en sådan uppgift inte lösas i dag, det är inte aktuellt. Även om många intellektuella uppgifter nu löses, som till exempel textigenkänning. Du kan lägga ett textark i skannern och få det på skärmen i Word. Han kommer att läsa själv, varje bokstav känns igen. Faktum är att vi har avancerat i många intellektuella uppgifter. Vissa av dem är redan lösta, andra håller på att lösas. På vissa sätt blir det relativt sett bättre än med en persons medverkan, på vissa sätt är det ännu värre. Många praktiska exempel kan ges. När det gäller den universella artificiella tänkandemekanismen är detta mer ett filosofiskt problem än ett praktiskt. Trots allt, även för ett så enkelt spel som schack tog det oss 30 - 40 år att faktiskt uppnå något. Varje filosofi bygger på åsikter. Alla tror att han har rätt, och kanske har alla rätt på sitt sätt. Till exempel har jag hela mitt liv sysslat med artificiell intelligens och jag tror att den mänskliga hjärnan inte är något annat än en stor dator, därför kan det inte sägas att det är i grunden omöjligt att skapa en analog. Frågan är dess kraft, hastighetsegenskaper, i att fylla den med kunskap. Det finns inget obegripligt här. Detta är min personliga synpunkt. Men det finns andra åsikter också. Naturligtvis, om vi erkänner människans gudomliga natur, måste vi redan välja ett av två epistemologiska alternativ. Eller ja, vi har en gudomlig natur, men den är känd. I det här fallet kommer vi inte att verkligen kunna återskapa vad Herren Gud kunde göra, men vi kommer åtminstone delvis att kunna återskapa Hans skapelser. Eller så står vi på agnosticismens ståndpunkt, och då är det okänt, och frågan är helt borttagen. Det visar sig att den mänskliga hjärnan löser vissa problem – och här är det ingen som tvivlar. Men vi kan inte hinna med hjärnan, eftersom den å ena sidan skapades av Gud, och å andra sidan kan vi inte veta den. Alla tre positionerna är förknippade med tro, eftersom det i verkligheten inte är nödvändigt att känna till alla hjärnans funktioner. Om vi ​​gör en maskin lika kraftfull som hjärnan behöver den inte tänka som hjärnan. Hon kommer att arbeta annorlunda.

– Inom psykologin, så vitt jag vet, bestäms den intellektuella utvecklingen hos en person av tre kriterier: förmågan att abstrahera, skapa ett intellektuellt omfång och något annat... I vilken utsträckning realiseras dessa möjligheter inom artificiell intelligens och är insåg de överhuvudtaget?

– Det finns en hel del program som är specifikt inriktade på att skapa begrepp som abstraherar från det befintliga faktamaterialet. Sådana program fungerar bra. En annan fråga är att en person kan skapa dessa begrepp, så att säga, enligt sina egna lagar, som han uppfinner för sig själv. Alla våra försök att översätta dessa hans lagar till logikens algebras språk visar sig vara meningslösa. En person har en mycket kraftfullare tankemekanism som vi helt enkelt inte känner till. Vi kan inte göra någonting "överhuvudtaget". Vi skapar de formuleringar vi behöver, men vi kan inte "uttrycka" dem i exakta maskinproblem. Allt reduceras till mekaniska problem med svårighet, och även om det reduceras, så sakta. Förmodligen vet vi ännu inte mer direkta sätt att nå målet. Allt kan läggas in i en dator. Frågan är att en person kan manipulera denna kunskap hela tiden, men han vet fortfarande inte hur man får en maskin att göra detsamma på grund av den begränsade datavolymen och hastigheten.

"Men det kanske inte är meningsfullt att tvinga maskinen att manipulera kunskap?"

– Här berörs både omoraliska och konstruktiva aspekter. Vi är fortfarande långt ifrån de rebelliska maskinerna. För min ålder, och även för din, kommer det säkert att finnas tillräckligt med lugn. Även inom begränsade områden har vi ännu inte lärt oss hur man får maskinen att manipulera problem, inte ens de som den kan lösa. Vi sätter en uppgift, och hon tänker bara på kommando.

– Vladimir Lvovich, säg mig, om det var datorteknikens gryning igen, skulle det vara värt att göra schackprogram? Var de verkligen så gynnsamma för framsteg?

– När allt kommer omkring vidgar schack våra vyer. I schackprogram sätts uppgifter, resultatet syns, vi utvärderar det. Ändå måste det finnas många lösta, intressanta problem, som bidrar till framsteg inom datateknik.

Skicka ditt goda arbete i kunskapsbasen är enkelt. Använd formuläret nedan

Studenter, doktorander, unga forskare som använder kunskapsbasen i sina studier och arbete kommer att vara er mycket tacksamma.

Postat på http://www.allbest.ru/

Utvecklingprogramvaramodulartificiellintellektförspelischack

algoritm för schackdatorintelligens

• Introduktion

Begreppet "datorschack" är i samma ålder som vetenskapen om cybernetik och dess avsnitt "artificiell intelligens". Schack är en idealisk modell för att undersöka komplexa problem, särskilt de som kräver iteration över alternativ. Utvecklingen av ett schackprogram hänvisas till problemet med att utveckla artificiell intelligens av följande skäl:

* det finns en allmän uppfattning att problemet är relaterat till problemet med artificiell intelligens, eftersom schack anses vara det mest intellektuella spelet

* det finns ett objektivt kriterium för utfört arbete - styrkan i schackprogrammet

* Större differentiering av detta kriterium representerar möjligheten till en gradvis förbättring av programmet.

En av grundarna av cybernetik och informationsteori, Claude Shannon, redan på 1950-talet, var den första som formulerade reglerna för att välja ett drag på ett schackbräde. I den analyserade positionen sorteras alla möjliga alternativ till ett visst djup och en numerisk bedömning tilldelas slutpositionerna med hjälp av objektiva funktioner. Sedan rullar minimax-proceduren tillbaka till utgångsläget, utvärderar det och indikerar det bästa draget, enligt maskinens uppfattning.

En persons roll är att ställa in målfunktionerna så exakt som möjligt samtidigt som man utvärderar positionen. Dessa funktioner har två komponenter - material och positionell. Allt är klart med den första - en materiell fördel (i pjäser och bönder) är som regel ett mycket allvarligt argument för att utvärdera en position som den bästa. Dessutom, ju mindre material på tavlan på båda sidor, desto mer exakt är bedömningen.

Men med den positionella komponenten är allt mycket mer komplicerat: många faktorer beaktas här, till exempel särdragen i arrangemanget av individuella pjäser och bönder, utrymme på brädet, tid för omgruppering av krafter etc. Förmågan att korrekt bedöma rollen av alla faktorer i en viss position har alltid ansetts vara ett av tecknen på schackmästerskap -av människor.

Svagheten med datorspelet låg just i missbruket av material och oförmågan att utföra en "absolut uppräkning" av alternativ. I 1970- och 1980-talens schackböcker kan man hitta ett ansenligt antal exemplariska exempel på spelet av människor med maskiner, när en mästare eller stormästare vann ett parti med hjälp av vackra uppoffringar av pjäser och bönder. Hemligheten är redan klar: för det mänskliga intellektet, i motsats till det konstgjorda, var positionsfaktorernas dominans över materiella uppenbar just i de ögonblick då materiella uppoffringar gjordes.

Åren gick, med ökningen av datorns hastighet, ökade beräkningsdjupet, och samtidigt förbättrades algoritmer som förbättrade sammanställningen av funktioner för att utvärdera positioner. Och under andra hälften av 1990-talet började datorer framgångsrikt konkurrera med extraklassiga stormästare. En epokgörande händelse för "schackcybernetik" ägde rum i maj 1997. Skapad av IBM, besegrade Deep Blue-datorn Garry Kasparov själv i en 6-spelsmatch. Datorn var utrustad med ett speciellt schackchip, och maskinen skannade cirka 200 miljoner positioner per sekund. IBM Corporation lockade många stormästare för sitt projekt, de senaste prestationerna inom schackteorin användes för att skapa de mest perfekta algoritmerna. Och så, som redan nämnts, på 90-talet började schackprogram för stationära datorer tränga ut specialiserade datorer.

Varje månad ökar kraften hos schackprogram och datorernas kraft obönhörligt, och överträffar även optimisternas mest vågade antaganden. Till och med för 12-15 år sedan, diskussioner om ämnet "När kan en maskin slå en stormästare?" i princip kokas ner till frågan "Är hon kapabel att göra detta i princip?". Och om svaret "Kan" fortfarande lyckades få, beräknades tiden i intervallet 15-25 år.

Verkligheten har motbevisat dessa förutsägelser. Allt hände mycket snabbare! Redan i mitten av 1990-talet upptäcktes att syntesen "spelprogram + dator" kunde konkurrera med en stormästare.

Syftet med arbetet är att utveckla och implementera en mjukvarumodul för artificiell intelligens för schackspel, som inkluderar:

1. studie av befintliga spelalgoritmer tillämpliga på schackspel

2. utveckling av en algoritm för beteendet hos en datormotståndare

3. Bestämma parametrarna för datormotståndarens algoritmbeteende

4. mjukvaruimplementering, vilket inkluderar implementering av spelalgoritmen och utveckling av ett grafiskt gränssnitt

5. jämförelse av den utvecklade mjukvaran med befintliga analoger.

1 . Berättelseutvecklingschackprogram

1951 skrev Alan Turing en algoritm som skulle tillåta en maskin att spela schack. Först på den tiden fungerade uppfinnaren själv som en maskin. Också 1951 skrev matematikern Claude Shannon sin första uppsats om schackprogrammering. Han beskrev två strategier för att hitta det bästa draget, båda baserade på en heuristisk slutpunktsutvärderingsfunktion:

* typ A - uppräkning av alla möjliga drag till ett fast djup, med ett anrop i slutet av utvärderingsfunktionen (eftersom det är omöjligt att räkna upp till slutet)

* typ B - utför endast selektiv expansion av vissa linjer, använder ackumulerad schackkunskap för att beskära ointressanta grenar

Den första datorn designades av von Neumann för att utföra komplexa beräkningar vid skapandet av kärnvapen. 1950 dök det första provet upp, som kunde utföra 10 000 operationer per sekund. Ett av de första experimenten med apparaten var att skriva ett schackprogram, men schack var icke-standardiserat - på ett 6 * 6 bräde utan elefanter.

Några år senare spelade den här datorn ("MANIAC") med människor: en stark schackspelare vann en jordskredsseger och en nybörjare förlorade i 23 drag.

År 1957, på IBM704 (42 kHz, 7 KB minne), implementerades typ B-program på helpension, med deltagande av alla bitar. Maskinen räknade 4 halvslag på 8 minuter. Nivån på spelet är amatör.

1962 upptäcker Newell, Simon och Shaw en algoritm som kallas alfa-beta som inte ger sämre resultat än en uttömmande sökning utan att undersöka alla alternativ. Det krävde inga speciella schackkunskaper, och det kunde användas för att lösa alla uppräkningsproblem. Kärnan i algoritmen är att i varje rad i spelet, för vit och svart, spåras deras maximala resultat, och om svart vid någon tidpunkt redan har fått ett resultat som är lika med vits maximala uppnådda tidigare, så är det ingen mening i att slita vidare. När sökningen återgår till den punkt där det vita maximum nåddes kommer resultatet fortfarande att avvisas Alla moderna schackprogram är baserade på en av de förbättrade versionerna av denna algoritm.

Fram till omkring 1973 var alla schackprogram av typ B. De var huvudsakligen baserade på generatorer av rimliga förskjutningar, som skar bort osannolika med statisk utvärdering. Med tillkomsten av mer kraftfulla processorer började programmerare gå över till typ A. De första var Teach och Chess4, dessa var "brute force"-program, när de väl nådde ett djup på 5 halva drag av spelets mellanstadium, de började vinna tävlingar med typ B-program.

1975 börjar Robert Hyat utveckla CrayBlitz, som länge var det snabbaste schackprogrammet och under perioden 1983 till 1989. - världsmästare bland schackprogram. Han sökte efter cirka 40-50 tusen positioner per sekund (1983), vilket var en stor prestation för hans tid.

1977 skapade Thompson och Condon på Bell Labs den första dedikerade schackdatorn. Huvudtanken var att implementera vissa delar av schackprogrammet (flyttgenerator, positionsutvärderingsfunktion, kontrolldetektor, etc.) på hårdvarunivå, vilket eliminerade mjukvaruförseningar i varje position utan att vänta på en ökning av processorkraften. De bästa datorerna på den tiden kunde utforska upp till 5 000 positioner per sekund, och Ken Thompsons maskin, kallad Belle, bearbetade 180 000 linjer per sekund. Belle kunde tänka igenom positionerna 8-9 halva drag framåt, vilket placerade honom på en mästarenivå. Han vann många datorschackturneringar. Men trots att specialiserad hårdvara är en storleksordning snabbare än en konventionell maskin, spelade CrayBlitz-programmet bättre på en banbrytande maskin då.

På 1990-talet gjorde Richard Lang, som uteslutande skriver i assembler, ett mycket kraftfullt Genius selektivt sökprogram. Fram till nu har detta program konsekvent haft 5:e-6:e plats i världsmästerskapen i datorschack. Även på 90-talet började schackalgoritmer utvecklas starkt, null move heuristic (NullMove), selektiv beskärning av gränsgrenarna i uppräkningsträdet, dök upp.

Separat är det värt att överväga det mest kända schackprogrammet, schacksuperdatorn - Deep Blue. 1987 började Deep Blue som en elevutveckling - det var intressant för en grupp duktiga studenter att prova sig fram, och ämnet för diplomet är utmärkt. Teknikens framsteg gjorde det möjligt att göra den allra första versionen av processorer (kallade ChipTest) mycket snabbt. Nästa, förbättrade version, kallad Deep Thought, följde. I det ögonblicket uppmärksammades gruppen av IBMs marknadsavdelning och vände sig till dem med ett erbjudande som inte kunde vägras. Resultatet blev Deep Blue och Deep Blue II. Således är Deep Blue II resultatet av över 10 års arbete av en mycket kapabel grupp, som inkluderade både programmerare/hårdvara och starka stormästare. Allt arbete finansierades av IBM, så gruppen hade resurser som akademiska organisationer inte ens kunde drömma om. Deep Blue II är baserad på den kraftfulla IBM RS/6000-servern. Servern har 31 konventionella processorer; en förklaras hövding, 30 andra är underställda honom. 16 specialiserade schackprocessorer är anslutna till varje "fungerande" processor, så det finns totalt 480 schackprocessorer. Hela komplexet behandlade mer än en miljard positioner per sekund.

Den 11 maj 1997 besegrade Deep Blue II schackvärldsmästaren Garry Kasparov i en match med sex spel. Efter en match med mästaren demonterades Deep Blue.

Som du kan se, från det allra första och slutar med de mest moderna programmen, byggdes schackprogram på basis av uppräkning av möjliga drag, men det gjordes också försök att bygga mer "intelligenta" algoritmer, annorlunda än uppräkning. Många välkända schackspelare försökte utveckla sådana algoritmer, men resultaten uppfyllde inte kraven. Till exempel har M. M. Botvinnik, som är världsmästare och författare till många verk om schackteori, skapat ett schackprogram i mer än 20 år, men programmet har aldrig börjat spela.

Alla uppräkningsalgoritmer för att hitta det bästa draget bygger ett spelträd och letar efter det bästa draget baserat på det.

2. Allmänbegreppteorierspel

2.1 Trämöjligpositioner

Låt ett ändligt orienterat träd G ges, mängden B av dess hörn är sammansatt av två disjunkta delmängder B0 och B1, och varje vertex p B som inte är början på någon länk i detta träd tilldelas ett reellt tal Oe(p) . Detta definierar spelet för två motståndare med perfekt information. De hörn av det riktade trädet G som tillhör delmängden B0 kallas positioner med vit att flytta, och de som tillhör delmängden B1 kallas positioner med svart att flytta; länkarna i detta träd kallas vita eller svarta drag, beroende på vilken av delmängderna B0 eller B1 deras början tillhör. Om en position p B tilldelas ett nummer Oe(p) kallas den final och Oe(p) kallas den statiska utvärderingen av denna position.

Ett riktat träd G kallas ett spelträd.

Enligt definitionen finns det för varje position p B en unik väg L(p0 > p1, p1 > p2 , ..., pk > p ) som börjar vid roten p0 i det orienterade trädet Г och slutar vid positionen i fråga. , en sådan väg kallas ett spel som leder till positionen p .

Roten p0 i spelträdet G är den markerade positionen. Detta är den tjänst som erbjuds till programmet, och uppgiften är att hitta det bästa draget i det. För att göra detta räcker det att definiera Oep0 och Oepi för alla positioner som erhålls från p0 i ett drag. Uppskattningen av den initiala positionen p0 utförs av det uttömmande sökschemat, och i spelteorin kallas denna algoritm för negamax-algoritmen.

Spelträdets komplexitet beräknas med formeln: w^d, där w är det genomsnittliga antalet möjliga drag och d är trädets djup.

Figur 1 - Träd över möjliga positioner

2.2 Principminimax

Denna algoritm utförs med hjälp av djup-först-sökning. Det vill säga, för varje vertex som inte har passerats är det nödvändigt att hitta alla intilliggande hörn som inte har passerats och upprepa sökningen efter dem. Vi rullar tillbaka till toppen av det sista djupet och räknar ut poängen i förhållande till den första spelaren. Sedan, från dess överordnade nod, går vi till nästa underordnade nod (om någon) och beräknar vinstpoängen där. Om antalet underordnade noder är över, letar vi efter ett minimum av vinnande poäng (om nivån på föräldernoden är udda) eller ett maximum (om jämnt). Föräldernoden har den mottagna vinstpoängen. Vi gör en liknande sökning, men med tanke på att föräldranoden redan är ett barn.

I trädets löv räknas poängen i förhållande till den första spelaren, d.v.s. det antas att den första spelaren försöker maximera sin utdelning, och den andra spelaren - att minimera utdelningen för den första spelaren. Den första spelaren vinner om antalet poäng i toppen av nivåträdet är större än noll.

Figur 2 - Sök i trädet med minimaxalgoritmen

Som ett resultat motsvarar den process som används av programmet växlingen av beslut (dator / människa), vid varje drag väljer datorn maximal poäng. Lösningen som går tillbaka till trädets rot är helt klart det bästa valet, förutsatt att motståndaren också gör de starkaste dragen i varje fall. Statisk utvärdering utförs endast vid noderna på den sista nivån (trädets blad) för datorns position.

Denna algoritm utför en fullständig uppräkning av alla alternativ. Antalet övervägda positioner kommer att utvärderas som W i potensen av D, där W är det ungefärliga antalet drag i en position, D är beräkningsdjupet. För schack är W ungefär lika med 40, vilket betyder att, räknat till ett djup av 4, måste vi gå igenom 40^4 = 2560 tusen positioner och för ett djup på 5 - 10240 tusen positioner.

Sökträdet växer exponentiellt. Hittills, på de mest kraftfulla processorerna med den mest optimala koden, är det möjligt att räkna till ett djup av 6 under en realistiskt beräknad tidsperiod. Detta är huvudproblemet i utvecklingen av algoritmer för schackspelet, och all utveckling syftar till att minska de övervägda kombinationerna.

Figur 3 visar ett blockschema över minimaxalgoritmen för att välja det bästa draget, den presenterade algoritmen returnerar det bästa draget enligt uppskattningen som erhållits från en djupare analys. Blockschemat för algoritmen för att söka efter en uppskattning på djupet visas i figur 4.

Figur 3 - Flödesschema för att välja det bästa draget

Figur 4 - Flödesschema för att söka efter en uppskattning på djupet

När vi anropar algoritmen för att söka efter en uppskattning på djupet med ett mycket stort erforderligt djup får vi en uppskattning med en fullständig uppräkning av alla möjliga drag.

2.3 Metodnegativmaximal(NegaMax)

I denna algoritm är den statiska uppskattningen av positionen för en av parterna lika med den statiska uppskattningen av den andra sidan med motsatt tecken.

Figur 5 - Negativ maxmetod

2.4 statiskkvalitetpositionerochhuvudkravtillvärderingfunktioner

Statisk bedömning av en position är ett sätt att objektivt, kvantitativt uttrycka den subjektiva känsla som en person har när man tittar på en position, utan att analysera möjliga sätt att utveckla spelet. I spelprogrammering kallas en statisk positionsuppskattning en positionskvalitetsfunktion.

Om att hitta det bästa draget med hjälp av spelträdet kan tillämpas med lika framgång för alla spel, är statisk positionsutvärdering en del som är specialiserad för ett specifikt spel. Dess specialisering bestämmer spelstilen för den konstgjorda spelaren, faktorerna inbäddade i utvärderingsfunktionen bestämmer målet för uppräkningen.

Att matcha siffran med positionen gör det möjligt för maskinen att skilja mellan dåliga och bra kombinationer. Förmågan att skilja bra kombinationer från dåliga avgör styrkan hos en virtuell spelare. I spel för två personer görs utvärderingen av en av spelarna. Om utvärderingsfunktionen ger en bra poäng för en spelare måste den returnera en dålig poäng för hans motståndare. Denna regel är ett kriterium för tillämpligheten av alla utvärderingsfunktioner i algoritmer som implementerar artificiell intelligens.

Huvudkravet för utvärderingsfunktionen är dess symmetri med avseende på spelarna, d.v.s. villkoret måste vara uppfyllt - det som är bra för en spelare är dåligt för en annan. En bra utvärderingsfunktion bör ta hänsyn till de grundläggande principerna för spelstrategin och uppfylla följande egenskaper:

* material - beräknas direkt som skillnaden i antalet spelares siffror, det är möjligt att lägga till viktkoefficienter för varje specifik siffra

* positionell - visar kvaliteten på platsen för spelarens pjäser

* utvecklingen av positionen - visar antalet möjliga drag för spelaren. Ju bättre positionen är utvecklad, desto fler möjliga strategier har spelaren. Av denna anledning är det nödvändigt att kontrollera och minska dess tillstånd från fienden.

* hålla reda på slutet av spelet - i fall av vinst (att ta motståndarens kung), bör ge maximal poäng, vanligtvis + oändlighet, i fall av förlust (förlust av kungen), bör returnera minsta poäng, vanligtvis - oändlighet

För att spela schack måste man ta hänsyn till förändringen i bedömningen av positionen, beroende på spelets skede.

Den klassiska utvärderingsfunktionen är en funktion av några av ovanstående egenskaper hos spelpositionen, det vill säga utvärderingsfunktionen är det totala resultatet av utvärderingen av positionen ur olika synvinklar.

Utvärderingsfunktionen för alla spel är olika, eftersom den speglar spelets särdrag. Utvärderingsfunktionens egenskaper väljs experimentellt.

Vikten av den valda egenskapen är avgörande. Betydelsen bestäms genom att multiplicera den valda egenskapen med lämplig koefficient. Denna koefficient måste ha en statistisk motivering.

Därför kan utvärderingsfunktionen representeras enligt följande:

F(p) - utvärderingsfunktion för position p,

Koefficienten av betydelse för den i:te egenskapen,

I:e egenskapen för position sid.

2.5 iscensättninguppgifter

Under loppet av avhandlingen är det nödvändigt att undersöka de befintliga metoderna och algoritmerna för datorimplementering av schackspelet, för att fastställa deras huvudsakliga fördelar och nackdelar för att, baserat på den inhämtade kunskapen, välja en algoritm som säkerställer bästa funktion av detta system.

I slutet av examensarbetet måste du:

att implementera de studerade algoritmerna i programmeringsspråket C#

att implementera sina olika ändringar med hjälp av ytterligare moduler

att utföra numeriska experiment för att utvärdera kvaliteten på de utvecklade modellerna, jämföra de genomförda ändringarna för att välja den bästa

att utveckla ett användarvänligt och intuitivt gränssnitt

3. Forskatalgoritmerochtillägg

3.1 alfa betaklippning

Alfabetabeskärning är en sökalgoritm som försöker minska antalet noder som utvärderas i ett sökträd med minimaxalgoritmen. Huvudtanken är denna: om din motståndare har ett ogynnsamt svar för dig på ett av dina drag, då är det meningslöst att analysera hans andra möjliga svar på ditt drag, för även om det finns mer gynnsamma bland dem, är motståndaren kommer inte att välja dem. Alfabetabeskärning är en optimering, eftersom resultaten av den optimerade algoritmen inte förändras.

Figur 6 - Algoritm för alfa-betabeskärning

Fördelen med alfa-beta-beskärning är i själva verket att några av sökträdets undernivågrenar kan uteslutas efter att minst en av nivågrenarna har undersökts fullständigt. Eftersom klippning sker på alla häckningsnivåer (förutom den sista), kan effekten vara ganska betydande. Metodens effektivitet påverkas avsevärt av den preliminära sorteringen av varianter (utan eller med en sökning till ett mindre djup) - vid sortering, ju fler "bra" alternativ som övervägs i början, desto fler "dåliga" grenar kan skäras av utan en uttömmande analys. minimax-sökning är djupet först, så det räcker med att överväga noder längs en enda väg i trädet vid varje given tidpunkt.

Nyckelidén bakom alfa-beta-beskärning är att hitta ett drag som inte nödvändigtvis är det bästa, men "tillräckligt bra" för att fatta rätt beslut.

Parametrarna alfa och beta ges som input till denna algoritm, de kallas sökfönstret. Dessa parametrar är ansvariga för klippningsgränserna på den första nivån, när du går djupare in i spelträdet ändras dessa parametrar. Alfa-beta-algoritmen med parametrarna alfa = + oändlighet och beta = - oändlighet (brute force med fullt fönster) ger samma resultat som negamax-algoritmen, d.v.s. uttömmande sökning. Figur 7 visar ett blockschema över alfa-beta-algoritmen för beräkning av djuppositionsuppskattningen.

Figur 7 - Alpha-beta-flödesschema för djup-först-sökning

3.1.1 Exempelstandard-klippning

Figur 8 - Exempel på standardklippning

Låt oss titta på ett exempel på en vanlig alfa-beta-klippning. I position A väljer vi flytten, därför kommer vi att välja det största värdet från positionerna B och C. Värdet på B har redan beräknats - detta är 10. Vid beräkning av position C visade det sig att en av noderna har en värde på 5. I position C kommer vår motståndare att göra draget, vilket innebär att han väljer det minsta värdet. Det följer av detta att värdet på position C kommer att vara från 5 och lägre, därför kommer vi alltid att välja B-alternativet. Därför beräknar vi inte de återstående noderna C.

3 .1.2 Exempelpå djupetklippning

Figur 9 - Exempel på djupt snitt

Tänk på ett exempel på djupklippning. I position A kommer vi att välja mellan drag i position B och C. Värdet på B=15. Vi börjar räkna ut C. I position E gav en av noderna värdet 5. I position E tillhör valet av drag motståndaren, vilket innebär att slutvärdet på E blir från 5 och under. Om värdet på C visar sig vara lika med E, kommer vi att välja alternativ B, eftersom det är mer attraktivt. Därför behöver vi inte veta det exakta värdet på position E, så alla andra grenar som kommer ut ur den skärs av.

3 .2 iterativdyka(Itereradefördjupning)

Meningen med sökfläkten eller iterativ fördjupning är att upprepade gånger kalla iterationsproceduren till ett fast djup med ökande djup tills den inställda tidsgränsen överskrids eller det maximala sökdjupet uppnås. Fördelen med denna metod är att du inte behöver välja sökdjup i förväg; förutom det kan du alltid använda resultatet av den senast genomförda sökningen. Värdena som returneras från varje sökning kan användas för att justera aspirationsfönstret för nästa sökning.

I allmänhet kallas alfa-beta-beskärning från toppen av trädet med intervallet (-?;+?). Men med iterativ nedsänkning kan vi ändra det.

Antag att X är värdet av det optimala draget som hittades i föregående iteration, och Epsilon är den uppskattade skillnaden i resultat mellan sökning till djup D-1 och djup D. Därefter kallar vi helt enkelt alfa-beta beskärning från toppen av trädet med det förväntade intervallet: alphabeta(D, x-epsilon, x+epsilon).

1. Värdet kommer tillbaka i intervallet (x-epsilon, x+epsilon) - detta är rätt värde, vi kan använda det.

2. Värdet kommer tillbaka utanför intervallet (x-epsilon, x+epsilon), du måste upprepa beräkningen med ett ändrat intervall.

Även om man antar att alfa-beta cutoff-metoden inte ger någon vinst, är den totala ökningen av analystid faktiskt relativt liten. Faktum är att om vi antar att det genomsnittliga antalet alternativ på varje nivå är D, och antalet analyserade nivåer är p, då iterativ sökning till den första nivån, sedan till den andra, etc. till nivå p, motsvarar (utan alfa-beta cutoffs) att titta på D + + ...+ positioner.

Denna summa är lika, medan antalet positioner som visas i normalanalysen är lika. Förhållandet mellan dessa två tal för stort p är ungefär lika med och därför nära 1 i de fall D är tillräckligt stort

Vid användning av iterativ sökning kan även tidskontroll införas, vilket gör att datorn kan erbjuda en tillfredsställande lösning när som helst. Således, om tiden för reflektion är begränsad till 5 sekunder, kommer den att beakta alla positioner upp till nivå 2, till exempel på 0,001 sekunder, upp till nivå 3 - på 0,01 sekunder, upp till nivå 4 - på 1 sekund, och sedan , efter att ha startat analysen på nivå 5 kommer att tvingas avbryta på grund av tidsbrist. Men i det här fallet kommer datorn redan att ha en ganska bra lösning på nivå 4.

Som ett resultat kan datorn ge ett svar inom den angivna tiden (till exempel gör 50 drag på 2 timmar). Det är också uppenbart att ett program som stöder denna metod kommer att spela med olika styrkor på olika datorer.

Även om vissa grenar av trädet måste kontrolleras flera gånger, ger denna metod ett tillräckligt antal snitt.

3.3 Sorteringrör sig

Resultaten av alfa-beta-beskärning påverkas mycket av i vilken ordning dragen kontrolleras. Låt oss titta på detta med exempel:

I det första fallet kommer vi att utföra beräkningen genom att sortera dragen "från sämst till bäst"

Figur 10 - Alfabeta-klippning med rörelser "från sämst till bäst"

Som du kan se av exemplet så klipptes inte en enda trädgren.

Låt oss nu sortera rörelserna "från bäst till sämst"

Figur 11 - alfa-beta-klippning med bästa-till-sämsta drag

Under optimala omständigheter bör iteration med alfa-beta-klippning skanna W^((D+1)/2) + W^(D/2) - 1 position. Detta är mycket mindre än minimax.

För att öka effektiviteten av alfa-beta-klippning måste du tänka på vilka drag du ska utforska först. För dessa ändamål används den så kallade mördarheuristiken.

Tanken är att om flytten var bra i en del av trädet, om det är möjligt, är det värt att försöka kontrollera det i andra (på samma djup). För att göra detta läggs en array in där flera bästa drag för varje djup anges, om det finns drag från denna tabell i positionen för det aktuella djupet, kontrolleras de först.

För andra drag föredrar algoritmen drag med kontroller och fångar.

3 .4 Nega Scout(NegaScout)

NegaScout är ett tillägg för alfabeta. Detta är en riktad sökalgoritm för att beräkna minimaxvärdet för en nod.

NegaScout är den mest populära brute force-algoritmen idag. Det är extremt enkelt och ger en viss (upp till 50%) acceleration utan att införa ytterligare fel i beräkningen. Det går väldigt bra med schackprogrammens moderna attribut - hashtabeller.

Denna algoritm har fördelen att den aldrig kommer att utforska noder som kan trunkeras av alfa-beta, men vissa grenar kan övervägas flera gånger.

NegaScout-algoritmen kontrollerar den första noden med ett helt fönster (Alfa, Beta), och anser att detta alternativ är det bästa. Den försöker skära av följande noder genom uppräkning med ett nollfönster, d.v.s. fönster (Alpha , Alpha+1). Om resultatet av räkningen förbättrar alfa, betyder det att 1 nod inte var den bästa, och denna nod måste kontrolleras med ett helt fönster, men istället för Alpha kan vi ta det resulterande värdet (Value,Beta). Koden för denna metod ges nedan:

public int NegaScout(Cell[,] Copyboard, int Depth, int FinalDepth, int Alpha, int Beta, int PossibleMoves, bool IsMy)

int Value = 0, MaxValue = -1000, höjd = 0;

Cell[,] Board = ny cell;

Point[,] Flyttar = ny punkt;

Point Move = ny punkt;

FindMoves(Moves, ref höjd, Board, true, true);

PossibleMoves = höjd;

FindMoves(Moves, ref höjd, Board, false, true);

PossibleMoves += höjd;

if ((Djup == FinalDepth) || GameIsOver(Board, IsMy))

return Eval(Board, PossibleMoves);

return -1 * Eval(Board, PossibleMoves);

FindMoves(Moves, ref level, Board, HaveRequiredMove(Board, IsMy), IsMy);

int a = Alfa, b = Beta;

för (int i = 0; i< leight; i++)

CopyMove(Move, Moves, i);

DoMove(Bord, Flytta);

Värde = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1*b, -1 * a, PossibleMoves, !IsMy);

if (Värde>a && Värde 0 && (Djup

a = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1 * Beta, -1 * Value, PossibleMoves, !IsMy);

if (Värde > a)

CopyPosition(Board, CopyBoard);

Som du kan se från beskrivningen ovan är det en viktig funktion för Nega Scout att iterera över drag. Om du ordnar alla drag "från sämst till bäst", kan uppräkningen ta ännu mer tid än minimax.

3 .5 Hash tabeller

3 .5 .1 Teori

I schack, under uppräkningen, erhålls inte ett spelträd, utan en graf - mycket ofta, efter att ha omorganiserat dragen, får vi samma position. Tekniken att använda hashtabeller är att lagra en uppskattning av redan granskade positioner. För varje position måste du lagra dess uppskattning (mer exakt, uppskattningen av underträdet under denna position), sökdjupet och det bästa draget. Nu, efter att ha börjat analysera positionen, måste vi titta - men har vi redan träffat henne? Har ni inte träffats så gör vi som tidigare. Om vi ​​träffades, då ser vi till vilket djup vi demonterade det innan. Om det är samma som vi behöver nu, eller djupare, så kan du använda den gamla uppskattningen och spara tid. Om det är mindre kan vi fortfarande använda en del av informationen, nämligen det bästa draget.

Det bästa draget för djup N kan också vara det bästa draget för djup N+1. Det vill säga, förutom sitt ursprungliga syfte är hashtabellen också användbar för att beställa drag. Här hjälper iterativ fördjupning oväntat - när vi startar nästa iteration fylls hashtabellen med information från den föregående, och fram till någon punkt (upp till djup 1) är alla positioner helt enkelt där, med den bästa flytten till djup N -1.

Ett program som använder iterativ fördjupning och hashtabeller går ofta igenom alla iterationer från 1 till N flera gånger snabbare än om det startade iteration N direkt, eftersom med en sannolikhet på 75 % väljer hon alltid det bästa draget först, och med en sannolikhet på ~90 % är det bästa draget bland de tre första som övervägs.

3 . 5 .2 Genomförande

Hashing är ett av de mest kraftfulla sätten att förbättra datorns prestanda. Användningen av hashtabeller är huvudverktyget vid programmering av schackspel.

Hash-tabell - är en stor indexerad tabell, vars celler lagrar följande information:

2 hashindex

återgivningsdjup för detta drag

Utvärdering av denna flytt

Valet av algoritm för att beräkna hashindex för flytten är det viktigaste momentet när man använder hashalgoritmer. När du väljer en algoritm för att beräkna hashindex, finns det två viktiga punkter att tänka på:

Indexet bör återspegla den mest unika informationen om banan för att minimera antalet kollisioner

Hashindex ska vara lätt att räkna

En komplex algoritm ger de bästa indikatorerna på antalet kollisioner, men de är svåra att beräkna och tar därför mycket CPU-tid. Det är nödvändigt att konstruera en algoritm som är lätt att beräkna men som har det minsta antalet kollisioner.

För att beräkna indexet valdes en operation med några slumpmässigt genererade masker.

Inledningsvis är maskens hash fylld med slumpmässiga siffror. För varje position beräknas 2 hashindex, det första används för att slå upp positionen i hashtabellen, det andra används för att kontrollera kollisioner.

Innan information från hashtabellen används kontrolleras sammanträffandet av de andra hashindexen, om de inte stämmer överens har en kollision inträffat och informationen ignoreras.

Uppdatering av information om positionen bör endast utföras om det aktuella renderingsdjupet är större än vad som redan finns lagrat i hashtabellen.

Information från hashen kan endast litas på om djupet i hashen är större än det aktuella beräkningsdjupet.

3.6 Användandebibliotekdebuterar

Algoritmen för att använda bibliotek med öppningar är att använda förberäknade databaser med öppningar av spel, eftersom det i början av spelet finns det största antalet möjliga drag med samma poäng.

3 .7 Kvalitetpositioner

Vid utveckling av en algoritm för statisk positionsuppskattning (kvalitetsfunktion) finns en osäkerhet i valet mellan kvalitet och hastighet. Kvalitativa utvärderingsfunktioner baserade på en statistisk bas fungerar långsamt, men ger mycket exakta uppskattningar, vissa även utan användning av uppräkning, visar hur intelligensen är.

Enkla funktioner som tar hänsyn till spelets enklaste principer fungerar mycket snabbare, de ger inte en exakt uppskattning, men de låter dig göra en djup sökning. Således kan en korrekt men långsam uppskattning ge vika för en dum men snabb sådan.

Kvaliteten på bedömningen bestäms av mängden kunskap om spelet, utifrån vilken antalet jämförs med positionen. Kvalitetsfaktorn i bedömningen är direkt proportionell mot arbetshastigheten och mängden kunskap. Som den 40-åriga praktiken att skapa program med artificiell intelligens visar, är mängden kunskap om utvärderingsfunktionen omvänt proportionell mot dess hastighet.

Grafiskt visas detta beroende i figuren som en familj av hyperboler.

Figur 12 - Exempel på djupt snitt

När man utvecklar en utvärderingsfunktion för schack bör man ta hänsyn till att i schack beror utvärderingen av alla parametrar på spelets skede.

Schack är vanligtvis indelat i etapper: öppningen är öppningen av spelet, mellanspelet är mitten av spelet, slutspelet är slutskedet. För algoritmen beslöts att dela upp spelen i 3 steg enligt antalet pjäser som lämnats på spelplanen av datorspelaren. Till en början har spelarna 16 pjäser på brädet. Tabellen visar spelstadiets beroende av antalet återstående pjäser:

Tabell 1 - Stadier av spelet

3 . 7 .1 Materialkvalitet

En av spelarnas materiella överlägsenhet anses vara den viktigaste parametern i schackteori, därför har materialbedömningen störst inverkan på den övergripande bedömningen av positionen. Materialpoängen beräknas som summan av vikterna av alla pjäser på brädan. Kungen ingår inte i det materiella värdet, för om kungen går förlorad förlorar spelaren automatiskt. Att uppskatta siffrors vikter är huvuduppgiften vid uppbyggnaden av utvärderingsfunktionen. För att bestämma siffrornas vikter beslöt man att använda en självlärande algoritm baserad på den genetiska algoritmen. Vikten på pjäserna beror inte på spelets skede. En genetisk algoritm är en heuristisk sökalgoritm som används för att lösa optimerings- och modelleringsproblem genom att slumpmässigt välja, kombinera och variera de önskade parametrarna med hjälp av mekanismer som påminner om biologisk evolution, först föreslog av Holland (1975).

3 . 7 . 2 Beskrivningarbetegenetiskalgoritm

Det ursprungliga problemet är kodat på ett sådant sätt att dess lösning kan representeras som en vektor ("kromosom"). Ett antal initiala vektorer (den "initiala populationen") genereras slumpmässigt. De utvärderas med hjälp av en "fitness-funktion" varvid varje vektor tilldelas ett värde ("fitness") som bestämmer överlevnadssannolikheten för den organism som representeras av den vektorn.

Därefter, med hjälp av de erhållna konditionsvärdena, väljs vektorerna (selektion) som är tillåtna för "korsning". "Genetiska operatorer" (vanligtvis "korsning" och "mutation") appliceras på dessa vektorer, vilket skapar nästa "generation". Individer av nästa generation utvärderas också, sedan görs selektion, genetiska operatorer tillämpas osv.

Så modelleras en ”evolutionär process” som pågår under flera livscykler (generationer) tills kriteriet för att stoppa algoritmen är uppfyllt. Detta kriterium kan vara:

Att hitta den optimala lösningen;

Utmattning av antalet generationer släppta för evolution;

Utmattning av tid som avsatts för evolution.

Genetiska algoritmer tjänar främst till att söka efter lösningar i mycket stora, komplexa sökutrymmen.

Således kan operationen av den genetiska algoritmen representeras i följande diagram:

Figur 13 - Exempel på djupt snitt

3 . 7 . 3 Etapperarbetegenetiskalgoritm

Skapande av en initial population - en initial population skapas slumpmässigt; även om det visar sig vara helt okonkurrenskraftigt kommer den genetiska algoritmen ändå snabbt att överföra det till en livskraftig population. I det första steget kan man alltså inte särskilt försöka göra individer alltför anpassade, det räcker att de motsvarar formatet för befolkningens individer.

Urval (selektion) - en viss andel väljs från hela befolkningen, som kommer att förbli "levande" i detta skede av evolutionen. Korsning (reproduktion) - för att få fram en ättling behövs flera föräldrar; vanligtvis behövs det förstås exakt två. Replikering i olika algoritmer definieras olika - det beror naturligtvis på representationen av data. Huvudkravet för reproduktion är att avkomman eller avkomman ska kunna ärva båda föräldrarnas egenskaper, "blanda" dem på något någorlunda rimligt sätt.

Mutationer är en stokastisk förändring i en del av individer (kromosomer).

3 . 7 . 4 DefinitionvågarsiffrorMedhjälpgenetiskalgoritm

Kromosomen för den genetiska algoritmen inkluderar vikten av schackpjäser, med undantag för kungen.

För att ställa in den initiala populationen ställs kromosomvärdena in slumpmässigt i intervallet, förutom vikten av bonden och drottningen, värdena på deras vikter är fasta, bonden är 100, drottningen är 1000.

Turneringsurval används för urval. Slumpmässiga 2 kromosomer spelar sinsemellan, upp till fyra vinster, gå först i tur och ordning. Vinnaren av duellen står kvar, förloraren tas bort från befolkningen.

Vid korsning används metoden för enpunktskorsning.

2 föräldrar tas slumpmässigt, ett slumpmässigt antal väljs med vilket kromosomen ska delas, schemat visas i figur nr 14. Som ett resultat kommer varje barn att ha egenskaper från både den första och andra föräldern.

Figur 14 - Exempel på djupt snitt

Mutationer utförs enligt följande: kromosomer väljs med viss sannolikhet, och för dem ändras varje "gen" till ett slumpmässigt tal i intervallet [-50; 50], förutom värdet av de statiska utvärderingarna av drottningen och bonden.

För slutvärdena divideras de resulterande vikterna med 100.

3 . 7 . 5 Totalkvalitet

När man utvärderar en position ägnas uppmärksamhet åt 8 komponenter:

1. Rivalernas materiella styrka

2. Antal fält under strid

3. Ockupation av nyckelfält

4. Passerade bönder

5. Dubbla bönder

6. Slottning

7. Pantförskott

8. Pantkedjor [*1]

Antalet fält under attack beräknas på ett träddjup av 2, på grund av höga prestandakostnader. För varje ruta som datorpjäsen träffar läggs 1 poäng till positionspoängen, för de fält som slås av spelarens pjäser tas en poäng bort. Det resulterande värdet skickas till botten av trädet som en parameter. Även på djup 2 beräknas poäng för bondkedjor, godkända och dubbla bonde. För närvaron av angränsande bönder till vänster eller höger får sidan 1 poäng. En bonde anses vara en godkänd bonde om det inte finns några motståndares bönder på dess fil, såväl som på dess grannar, som kan hindra den från att nå slutet. Dubbla bönder - 2 bönder av samma färg som står på samma fil. För närvaron av dubbla bönder från sidan dras 4 poäng av, för närvaron av varje passerad bonde läggs 5 poäng till. Det finns nyckelfält i schack:

Figur 15 - Nyckelfält

För ockupationen av var och en av dem ges ytterligare 4 poäng.

Därför att efter castling är kungen i en mycket stabil position, för en perfekt castling får sidan 3 poäng.

Ju närmare en bonde är sin sista rang, desto närmare befordran är den. För varje cell som flyttas framåt läggs 1 till värdet på bonden.

Efter att ha beräknat antalet poäng för båda sidor, erhålls den slutliga bedömningen av positionen genom att subtrahera spelarens poäng från datormotståndarens poäng.

4 . Utvecklingprograms

4 .1 Kravtillschackalgoritm

När du utvecklar en modell av en mjukvarumodul för att spela schack, bör följande parametrar beaktas:

* schackalgoritmer kräver mycket prestanda, och kraften i programmets spel beror direkt på programmets prestanda

* Programvarumoduler ska vara lätta att utveckla och testa

* Användargränssnittet ska vara lätt, lätt anpassningsbart och skalbart

4 .2 Typerschackalgoritmer

De flesta moderna program kan delas in i tre kategorier:

* Den första kategorin Snabbsökare - tanken är att genom att förenkla utvärderingsfunktionen till det yttersta och noggrant optimera hela programmet som helhet (vilket vanligtvis uppnås genom att skriva ett program i assembler), kan du öka antalet positioner anses av programmet (nps - noder per sekund) till ett astronomiskt tal, som 150-200k nps vid P/200. Det vill säga, programmet spenderar ungefär ett till två tusen maskininstruktioner för varje position. Detta nummer inkluderar att flytta från den tidigare positionen till denna, utvärdera positionen, generera drag från denna position, kontrolllogik, etc. Bara smulor återstår till själva utvärderingsfunktionen – ett hundratal lag. Program är vansinnigt snabba och presterar utmärkt i komplexa taktiska positioner, och löser även perfekt kombinationsproblem, men har ett svagt positionsspel.

* Den andra kategorin är kunskapsbaserade program. Här läggs alla krafter på att skriva en komplex utvärderingsfunktion. Samspelet mellan bitarna med varandra, och kåpan för kungen, och kontrollen av positioner och nästan månens fas tas med i beräkningen. När det gäller nps är programmet 10-100 gånger långsammare än snabba sökningar, men spelar bra positionsschack. Mer exakt, dessa schack är bra bara när det inte finns någon djup taktik på brädet, eller tidskontrollen är sådan att programmet har tillräckligt med tid för att beräkna denna taktik.

4 .3 Kontrolleratidischackalgoritmer

Den viktigaste parametern för att bygga en artificiell intelligensalgoritm för en schackmotståndare är kontrollen av rörelsetiden. Styrkan i spelet i ett schackprogram beror på tidskontroll. Innan datorn "tänker" en flytt måste den tid som finns tillgänglig för datorn beräknas.

Vid beräkning av den tillgängliga tiden för en flytt måste två parametrar beaktas:

* Algoritmen för att hitta det bästa draget är baserad på en uppräkning av alla möjliga drag till ett visst djup, och beror därför direkt på den tid som spenderas på uppräkningen. Ju mer tid vi använder, desto hårdare spelar datorn

* väntetiden för en datormotståndares svar bör inte vara för lång. Som grund kan du ta de internationella schackreglerna, där det finns flera typer av spel: blitz - 15 minuter per spel, snabbt - 60 minuter per spel, klassiskt - mer än 60 minuter per spel.

Baserat på de erforderliga parametrarna beslutades det att beräkna den tid som är tillgänglig för drag innan varje datordrag startar med hjälp av följande formel: där: tid - tid för ett drag; full_game_time - total speltid; avg_moves - genomsnittligt antal spelarrörelser i ett spel; collect_time - ytterligare ackumulerad tid; D - en liten minskning av den tid som krävs för ytterligare beräkningar. Parametrarna för den totala tiden för spelet och det genomsnittliga antalet drag för spelaren i spelet är två huvudsakliga externa parametrar, genom att ändra vilken du kan ändra styrkan i spelet. Enligt statistiken från schackportalen TheChess.ru är det genomsnittliga antalet spelardrag per spel 30, så det beslutades att ta det genomsnittliga antalet spelardrag per spel lika med 30. Således är den totala tiden för spelet inställd från utsidan. När man utvecklade en algoritm för beteendet hos en datormotståndare (artificiell intelligens), användes följande algoritmer:

* Iterativ sökalgoritm, med tidskontroll

* alfa-beta urklippsalgoritm och Nega-Scout

* debutbibliotek

* hashtabeller

* Mördar- och historieheuristik användes för att sortera drag.

4 .4 Tagit framprogram

Alla ovanstående algoritmer och tillägg implementerades i programmet i programmeringsspråket C#.

Skärmdumpar av programmet ges nedan:

Figur 16 - Färgval

Figur 17 - Skärmdump av programmet

Figur 18 - Skärmdump av programmet

När du för musen över en form av dess färg markeras den i vitt. När en pjäs väljs för ett drag blir färgen på dess fält orange och alla celler som pjäsen kan flytta till är markerade i vitt. När du för musen över en sådan cell blir dess färg också orange.

Under spelets gång visas de perfekta dragen i tabellen till vänster, spelaren kan även spara historiken i en separat fil.

4 .5 BascykelSökDet bästaflytta

Huvuduppgiften för den grundläggande cykeln att hitta det bästa draget är att hitta och utföra det bästa draget för datormotståndaren. Cykeln använder öppningsbiblioteken och iterativ sökning med tidskontroll. Figur 12 visar processen för att hitta det bästa draget:

Figur 19 - Grundläggande sökslinga för bästa drag

4 .6 SökDet bästaflyttaförstnivå

Algoritmens huvuduppgift för att hitta det bästa draget på den första nivån (motståndarens svar) är att hitta motståndarens bästa drag på den första nivån. Algoritmen är baserad på NegaScout-algoritmen, som använder djupuppskattning för att bestämma poängen för det aktuella draget. Figur 13 visar processen för algoritmen:

Figur 20 - Hitta det bästa draget på den första nivån

4 .7 Fynddjupuppskattningarflytta

Huvuduppgiften med att hitta en djup uppskattning är att hitta uppskattningen av det aktuella draget med hjälp av NegaScout-algoritmen, nollrörelseheuristik, data från hashtabellen och en statisk positionsuppskattning. Figur 14 visar processen för att beräkna djupuppskattningen:

Figur 21 - Hitta en djup uppskattning av flytten

4.8 Övrigmodellerochdiagram

Den matematiska modellen för programmet ser ut så här:

Figur 22 - Matematisk modell

Från den abstrakta klassen Figur skapas 7 klasser av arvingar som beskriver figurernas handlingar och egenskaper. Det finns också en Empty-klass, vilket betyder att cellen är tom. Brädan är en uppsättning av 64 figurelement, som var och en kan bli vilken som helst av de härledda klasserna. Förflyttningen i datorn representeras som 4 siffror - koordinater (från 1 till 8) för startpunkten för flytten och koordinaterna för förflyttningens slutpunkt. Nedan är tillståndsdiagrammet för programmet:

Figur 23 - Tillståndsdiagram

5 . experimentellkvalitetkvalitetRanalyserdataalgoritmer

De implementerade algoritmerna utsattes för en jämförande analys för att identifiera den konfiguration som var optimal när det gäller hastighet och kvalitet för att göra ett drag. Under experimentet hölls ett antal turneringar mellan varje par av olika implementeringar.

5 .1 KvalitetarbeteAlfa Betaklippning

Med hjälp av detta experiment var det nödvändigt att ta reda på om det var möjligt att uppnå en minskning av förgreningsfaktorn och som ett resultat förbättra algoritmens hastighet utan att förlora kvaliteten på beslutsfattandet om flytten som görs .

För att bedöma kvaliteten på den slutliga algoritmen jämfördes denna sökalgoritm experimentellt med en sökning baserad på minimaxprincipen.

Tabellerna visar koefficienterna som visar förhållandet mellan antalet sökta positioner för algoritmerna, såväl som förhållandet mellan den tid som tilldelats för slutförandet av denna skanning.

Tabell 1 - Jämförelse av prestandan för alfa-beta-klippningsalgoritmen med minimaxalgoritmen.

Experimentella resultat visar att alfa-beta-klippning är mycket bättre än en enkel minimax-sökning.

5 .2 Kvalitetarbeteiterativdykningochsorteringrör sig

För att utvärdera kvaliteten på algoritmen jämfördes denna sökalgoritm experimentellt med Alpha-Beta-beskärning och bara Alpha-Beta-beskärning.

Liknande dokument

Beskrivning av spelets regler "sea battle". Funktioner hos moderna datorer och artificiell intelligens. Skapande av ett allmänt blockschema över programmet, dess utseende. Nödvändiga variabler, procedurer och funktioner. En egenskap hos de objekt som används i applikationen.

terminsuppsats, tillagd 2012-11-05


Utveckling på basis av spelet "Points" av ett tillvägagångssätt för programmering av "artificiell intelligens" i positionsspel och möjligheten att använda detta tillvägagångssätt för att lösa problem inom ekonomi, management och andra vetenskapsområden. spelsituationsmodell.

avhandling, tillagd 2013-07-21


Strukturdiagram av en mjukvarumodul. Utveckling av schemat för mjukvarumodulen och användargränssnittet. Implementering av programmodulen: programkod; beskrivning av de använda operatorerna och funktionerna. Visa användarformuläret med den ifyllda matrisen.

terminsuppsats, tillagd 2010-01-09


En studie av de allmänna reglerna för spelet av pjäser, användar- och programmeringsinstruktioner. Beskrivning av de huvudsakliga algoritmerna som utför uppgifter i klassen Life Widget. Utvärdering av dator- och mänskliga rörelser. Bygga ett sökträd för bästa drag baserat på utvärdering av funktioner.

test, tillagt 2012-12-20


Huvudstadier av utveckling, principer för testning och felsökning av programmodulen "VFS". Designfunktioner i UML-språket. Brute force-metoder och deras tillämpning vid programfelsökning. Skadliga faktorer som finns på arbetsplatsen för en programmerare.

avhandling, tillagd 2012-07-03


Analys av modeller och metoder för implementering av intellektuella spel i människa-robot-systemet. Utvecklingsmiljö för koreografi. Algoritmer för igenkänningsmodulen, databehandling, spelmodulfunktioner. Testning av mjukvarupaketet, korrigering och redigering av fel.

avhandling, tillagd 2017-12-08


Kärnan och problemen med att definiera artificiell intelligens, dess huvudsakliga uppgifter och funktioner. Filosofiska problem med att skapa artificiell intelligens och säkerställa mänsklig säkerhet vid arbete med en robot. Valet av sätt att skapa artificiell intelligens.

kontrollarbete, tillagt 2009-12-07


Spelprogram "checkers" för ett spel mellan en person och en dator. Utveckling av algoritmer, den historiska linjen för utveckling av problem. Olika tillvägagångssätt för att bygga system. Förkortad lista över programmet och beskrivning av algoritmen. Komponenter av artificiell intelligens.

terminsuppsats, tillagd 2009-03-26


Konstruktion och analys av den matematiska modellen av spelet. Bestämma sannolikheten för att upptäcka fartyg med alla möjliga platser och olika söksystem. Utveckling av algoritmer för drift av artificiell intelligens. Programmets struktur och dess komponenter.

terminsuppsats, tillagd 2012-12-22


Konceptet med artificiell intelligens som egenskaperna hos automatiska system för att ta på sig individuella funktioner av mänsklig intelligens. Expertsystem inom medicinområdet. Olika tillvägagångssätt för att bygga artificiell intelligens. Skapande av neurala nätverk.

Tyvärr finns det inga bättre algoritmer för schack än uppräkningen av väldigt många positioner. Visserligen är uppräkningen i ordning (och inte en) optimerad, men det är ändå en stor uppräkning. För att söka efter ett svarsdrag byggs ett träd med det ursprungliga draget vid roten, kanter - drag-svar och noder - nya positioner.

Det är lätt att förklara hur nästa drag väljs i elementära algoritmer. På din tur väljer du ett drag (enligt din åsikt) som kommer att ge störst nytta (maximerar din fördel), och motståndaren, på sitt nästa drag, försöker välja ett drag som ger honom mest nytta (maximerar hans fördel och minimerar din). En algoritm med denna princip kallas minimax. I varje steg tilldelar du en positionsuppskattning till varje nod i trädet (mer om det senare) och maximerar den på ditt eget drag, och minimerar den på din motståndares drag. Algoritmen under drift måste gå igenom alla noder i trädet (det vill säga genom alla möjliga spelpositioner i spelet), det vill säga den är tidsmässigt helt olämplig.
Nästa förbättring är alfa-beta-klippning (gren- och gränsmetoden).

Av namnet följer att algoritmen skär av med två parametrar - alfa och beta. Huvudidén med klippning är att vi nu kommer att behålla klippintervallet (nedre och övre gränser - alfa respektive beta - din K.O.) och vi kommer inte att överväga uppskattningar av alla noder som inte faller in i intervallet underifrån ( eftersom de inte påverkar resultatet - dessa är bara sämre drag än de som redan hittats), och själva intervallet kommer att minska när de bästa dragen hittas. Även om alfa-beta-klippningen är mycket bättre än minimixen, är dess körtid också mycket lång. Om vi ​​antar att det i mitten av spelet finns ungefär 40 olika drag på ena sidan, så kan tiden för algoritmen uppskattas till O(40^P), där P är dragträdets djup. Naturligtvis, med minimax kan det finnas en sådan sekvens av att överväga drag när vi inte gör några klipp, då kommer alfa-beta-klippet helt enkelt att förvandlas till ett minimax. I bästa fall kan alfa-beta-beskärning undvika att kontrollera roten av alla drag i minimax. För att undvika en lång körtid (med en sådan O-stor komplexitet av algoritmen) görs sökningen i trädet med något fast värde och noden utvärderas där. Denna uppskattning är en mycket stor uppskattning av nodens verkliga uppskattning (det vill säga, itererar till slutet av trädet, och där blir resultatet "vinn, förlora, oavgjort"). När det gäller att utvärdera en nod finns det bara ett gäng olika metoder (du kan läsa det i länkarna i slutet av artikeln). Kort sagt - då räknar jag förstås spelarens material (enligt ett system - med heltals bonde - 100, riddare och biskop - 300, torn - 500, dam - 900; enligt ett annat system - reellt i delar från ett) + position på brädet för denna spelare. När det gäller positionen är det här en av mardrömmarna med att skriva schack börjar, eftersom programmets hastighet främst kommer att bero på utvärderingsfunktionen och, mer exakt, på utvärderingen av positionen. Det finns redan någon i så mycket. För parade turer, spelaren +, för att täcka kungen med sina egna bönder +, för en bonde nära andra änden av brädet +, etc., och de hängande pjäserna, den öppna kungen, etc. minus positionen. etc. – Man kan skriva en massa faktorer. Här, för att bedöma positionen i spelet, byggs en bedömning av spelarens position, som gör ett drag, och bedömningen av motsvarande position för motståndaren subtraheras från den. Som de säger, ett foto är ibland bättre än tusen ord, och kanske en bit pseudo C#-kod skulle också vara bättre än förklaringar:

Enum CurrentPlayer(Jag, motståndare); public int AlphaBetaPruning (int alpha, int beta, int djup, CurrentPlayer currentPlayer) ( // värdet av aktuell nod int värde; // räkna aktuell nod ++nodesSearched; // få motsatt till currentPlayer CurrentPlayer opponentPlayer = GetOppositePlayerTo(currentPlayer); / / genererar alla drag för spelare, vilken tur är att göra drag / / drag, genererade med denna metod, är fria från drag // efter att ha gjort vilken nuvarande spelare som skulle vara i checklistan moves = GenerateAllMovesForPlayer(currentPlayer); // gå igenom dragen för varje drag i drag ( MakeMove(move); ++ply; // Om djupet är stilla, fortsätt att söka djupare om (djup > 1) värde = -AlphaBetaPruning (-beta, -alpha, djup - 1, opponentPlayer); else // Om inget djup kvar (bladnod), utvärdera det positionsvärdet = EvaluatePlayerPosition(currentPlayer) - EvaluatePlayerPosition(motståndarenSpelare); RollBackLastMove(); --ply; if (värde > alfa) ( // Detta draget är så bra att det orsakade en cutoff av viloträdet if (värde >= beta) return beta; alfa = värde; ) ) if (moves.Count == 0) ( // om inga drag, än position är schackmatt eller om ( IsInCheck(currentPlayer)) return (-MateValue + ply); annars returnerar 0; ) return alpha; )

Jag tror att några förklaringar om koden inte kommer att vara överflödiga:

• GetOppositePlayerTo() ändrar helt enkelt CurrentPlayer.Me till CurrentPlayer.Opponent och vice versa
• MakeMove() gör nästa drag från listan med drag
• ply - en global variabel (del av klassen) som innehåller antalet halvpass som gjorts på ett givet djup

Ett exempel på att använda metoden:

(ply = 0; nodesSearched = 0; int score = AlphaBetaPruning(-MateValue, MateValue, max_depth, CurrentPlayer.Me); )
där MateValue är ett tillräckligt stort tal.
Parametern max_depth är det maximala djupet till vilket algoritmen kommer att sjunka i trädet. Man bör komma ihåg att pseudokoden är rent demonstrativ, men ganska fungerande.

Istället för att komma på en ny algoritm har de som främjar alfa-betabeskärning kommit på många olika heuristiker. Heuristiken är bara ett litet hack som ibland ger en mycket stor hastighetsökning. Det finns många heuristiker för schack, man kan inte räkna alla. Jag kommer bara att ge de viktigaste, resten finns i länkarna i slutet av artikeln.

Först tillämpas en mycket välkänd heuristik "noll drag". I ett lugnt läge får motståndaren göra två drag istället för ett, och efter det undersöks trädet till ett djup (djup-2), och inte (djup-1). Om det, efter att ha utvärderat ett sådant underträd, visar sig att den nuvarande spelaren fortfarande har en fördel, är det ingen idé att överväga underträdet ytterligare, eftersom spelaren efter nästa drag bara kommer att förbättra sin position. Eftersom sökningen är polynom är hastighetsökningen märkbar. Ibland händer det att fienden jämnar ut sin fördel, då måste du överväga hela underträdet till slutet. Ett tomt drag behöver inte alltid göras (till exempel när en av kungarna är i schack, i zugzwang eller i ett slutspel).

Vidare används idén för att först göra ett drag, där det kommer att finnas en fångst av motståndarens pjäs, som gjorde det sista draget. Eftersom nästan alla drag under uppräkningen är dumma och inte särskilt rimliga, kommer en sådan idé att begränsa sökfönstret avsevärt i början och därmed skära bort många onödiga drag.

Även känd historia heuristik eller bästa flytttjänsten. Under uppräkningen sparas de bästa dragen på en given nivå av trädet, och när du överväger en position kan du först försöka göra ett sådant drag för ett givet djup (baserat på tanken att på lika djup i trädet, samma bästa drag görs mycket ofta).
Det är känt att en sådan typ av cachning av rörelser förbättrade prestandan för det sovjetiska programmet Caissa med 10 gånger.

Det finns också några idéer om genereringen av rörelser. Först övervägs vinnande fångar, det vill säga sådana fångar när en pjäs med lägre poäng slår en pjäs med högre poäng. Sedan övervägs befordringar (när bonden i andra änden av brädet kan ersättas av en starkare pjäs), sedan lika fångar, och sedan flyttar från historiens heuristiska cache. Resten av dragen kan sorteras efter styrelsekontroll eller något annat kriterium.

Allt skulle vara bra om alfa-beta-beskärning garanterat gav det bästa svaret. Även med tanke på den långa tiden det tar att gå av. Men det fanns inte där. Problemet är att efter uppräkningen med ett fast värde, utvärderas positionen och det är det, men, som det visade sig, i vissa spelpositioner är det omöjligt att stoppa uppräkningen. Efter många försök visade det sig att uppräkningen endast kan stoppas i lugna positioner. I huvuduppräkningen lades därför till en ytterligare uppräkning, där endast fångar, kampanjer och checkar beaktas (kallas påtvingad uppräkning). Vi märkte också att vissa positioner med ett utbyte i mitten också måste övervägas djupare. Så det fanns idéer om förlängningar і minskningar, det vill säga urtag och förkortningar av uppräkningsträdet. För fördjupning är de mest lämpliga positionerna som slutspel med bönder, att undvika check, byta en pjäs mitt i en byst, etc. För förkortning är "absolut lugna" positioner lämpliga. I det sovjetiska Caissa-programmet var påtvingad uppräkning lite speciellt - där, efter ett fångst under uppräkningen, började tvångsuppräkningen omedelbart och dess djup var inte begränsat (eftersom den kommer att uttömma sig själv i en lugn position efter en tid).

Som Anthony Hoare sa: För tidig optimering är roten till allt ont i programmering." (obs: för de som tror att detta citat är från Knuth finns det intressanta diskussioner

1997, New York. Världsmästaren i schack Garry Kasparov förlorar mot IBM Deep Blue-datorn, och denna kamp blir det största schackspelet genom tiderna. Det här spelet kommer att kallas "det mänskliga sinnets sista strid", många kommer att jämföra det med bröderna Wrights första flygning och astronauternas landning på månen.

20 juli – Internationella schackdagen – vi berättar om vad som hände sedan. Och även om vad artificiell intelligens är sämre än människan, och var Alan Turing har med det att göra. Ett ord till Garry Kasparov, världsmästare i schack och författare till boken.

Paradoxalt nog, under en samtidig session med de bästa professionella schackspelarna, skulle roboten ha svårast att förflytta sig mellan borden och arrangera om schackpjäser, snarare än att beräkna drag. Även om science fiction-författare har uppfunnit automater som ser ut och rör sig som människor i århundraden, och robotar idag framgångsrikt utför manuellt arbete, måste det erkännas att våra maskiner återger mänskligt tänkande mycket bättre än mänskliga rörelser.

Inom schack, liksom inom många andra verksamhetsområden, är maskiner starka i vad människor är svaga och vice versa.

Denna välkända princip inom området artificiell intelligens och robotik formulerades under året av Hans Moravek, som noterade att "det är relativt lätt att få datorer att utföra ett intelligenstest eller spela pjäs på vuxens nivå, men det är svårt eller omöjligt att ingjuta ett ettårigt barns färdigheter när det gäller uppfattning eller rörlighet.

Vid den tiden var jag inte medveten om dessa teorier; dessutom talade Moravec om pjäs, inte schack, men tio år senare blev det uppenbart att denna princip gäller även för mitt verksamhetsområde. Stormästare utmärkte sig vid positionsbedömning och strategisk planering, svaga punkter hos schackdatorer, men de kunde beräkna taktiska konsekvenser på några sekunder, vilket skulle ta även de bästa mänskliga sinnen många dagar att slutföra.

Detta gav mig en idé. Efter att mina matcher med Deep Blue fått så mycket uppmärksamhet ville jag fortsätta experimentera med schack trots att IBM hade övergett det.

Min plan, enkelt uttryckt, var denna: om du inte kan slå dem, gå med dem.

Jag tänkte: tänk om människan och maskinen inte är motståndare, utan partners? Idén förkroppsligades under året i spanska Leon, där den första matchen i avancerad schack (avancerat schack) ägde rum. Båda partnerna hade en persondator till hands och kunde använda valfritt program under spelet. Målet var att nå en ny, högsta nivå i spelet - tack vare syntesen av de starkaste sidorna av mänsklig och maskinell intelligens. Även om, som vi ska se senare, inte allt gick som planerat, övertygade de häpnadsväckande resultaten av dessa "kamper om kentaurerna" mig att schack fortfarande har mycket att erbjuda inom området för interaktion mellan det mänskliga sinnet och artificiell intelligens.

Jag var inte den första att komma till denna övertygelse. Schackmaskiner var den heliga gralen långt innan folk kunde bygga dem. Och nu fick vetenskapen äntligen tillgång till den här skålen - och jag visade sig vara personen som håller den i mina händer. Jag hade ett val: avvisa samtalet eller acceptera det. Hur kunde jag motstå? Det var en chans att ytterligare höja schackets popularitet och utöka publiken det hade vunnit efter den berömda matchen mellan Bobby Fischer och Boris Spassky under det kalla kriget och efter mina kamper om världskronan med Anatoly Karpov. Detta skulle locka en armé av generösa sponsorer till schackvärlden, särskilt från högteknologiska företag. Till exempel, i mitten av 1990-talet, sponsrade Intel en hel serie snabba och klassiska schackturneringar och hela världsmästerskapets cykel, inklusive min titelmatch med Viswanathan Anand, som ägde rum på översta våningen i World Trade Center. Dessutom drevs jag av en oemotståndlig nyfikenhet. Kan maskiner verkligen lära sig att spela schack lika bra som en världsmästare? Är de verkligen kapabla att tänka?

Det är intressant det där
Det första schackprogrammet dök upp före den första datorn.

Den utvecklades av den briljante brittiske matematikern Alan Turing, som knäckte koden för den nazistiska Enigma-chiffermaskinen. 1952 skrev han på papper en algoritm med vilken en maskin kunde spela schack, endast matematikern själv fungerade som central processor. Turings pappersmaskin visade sig vara en ganska kompetent spelare. Anledningen till dess konstruktion gick utöver Turings personliga intresse för schack. Förmågan att spela schack har länge ansetts vara en del av mänsklig intelligens, och skapandet av en enhet som kan besegra en person i detta spel borde ha markerat framväxten av en verkligt intelligent maskin.

Namnet Alan Turing är också för alltid förknippat med namnet på det tankeexperiment han föreslog, senare utfört i verkligheten och kallat "Turing-testet". Dess kärna är att avgöra om datorn kan lura en person på ett sådant sätt att han tror att han har att göra med en person, och om han kan anses testet vara godkänt. Redan innan min första match med Deep Blue hade datorer börjat klara vad man kan kalla Turing Chess Test. De spelade fortfarande ganska dåligt och gjorde ofta uppenbart omänskliga drag, men ibland lyckades de spela spel som skulle se ganska passande ut i en anständig mänsklig turnering. Varje år blev maskinerna starkare och starkare, men under deras utveckling lärde vi oss mer om schack i sig än om artificiell intelligens (AI).

Det går inte att hävda att kulmen på 45 års forskning, som har blivit en händelse i en världsomfattande skala, blev en besvikelse, men den visade tydligt att att konstruera en schacksuperdator inte alls är detsamma som att skapa en artificiell intelligens som kan jämför med det mänskliga sinnet, som man drömde om. Turing och andra.

Faktum är att "sinnet" hos Deep Blue inte skilde sig från "sinnet" hos en programmerbar väckarklocka.

Tanken på detta förvärrade bara nederlagets bitterhet för mig – att förlora mot en programmerbar väckarklocka, även om det kostar 10 miljoner dollar?!

Det så kallade AI-communityt gladde sig verkligen över resultatet och uppmärksamheten det väckte, men samtidigt var forskarna tydligt avskräckta av att Deep Blue inte alls liknade den artificiella intelligens som deras föregångare drömde om. Istället för att spela schack som en man, visa mänsklig intuition och kreativt tänkande utanför ramarna, spelar han schack som en maskin: han uppskattar upp till 200 miljoner möjliga drag per sekund och vinner tack vare brutal beräkningskraft. Detta förtar naturligtvis inte själva prestationen. När allt kommer omkring är Deep Blue en skapelse av det mänskliga sinnet, och förlusten av en person till maskinen han skapade samtidigt betyder hans seger.

Efter den otroliga spänningen i den matchen, förvärrad av IBM:s misstänksamma beteende och min tendens att tvivla, var jag inte redo att erkänna nederlag lätt. Om jag ska vara ärlig så har jag aldrig varit bra på att förlora. Jag tror att en person som lätt accepterar nederlag aldrig kommer att bli en riktig mästare, och denna princip är naturligtvis sann i mitt fall. Men jag tror på en rättvis kamp. Då trodde jag att IBM hade lurat mig – liksom hela världen, som noga följde vår match.

Jag måste erkänna att det inte var lätt att analysera varje aspekt av den där ökända duellen med Deep Blue.

Under årens lopp har jag medvetet undvikit all diskussion om detta ämne, och bara berört det som redan var känt för allmänheten.

Det finns många publikationer om Deep Blue, men den här boken är den första och enda där all fakta är samlad och hela historien berättas som jag ser den. Trots minnets smärta var det en upplysande och givande upplevelse. Min store lärare Mikhail Botvinnik, den sjätte världsmästaren i schack, lärde mig att leta efter sanningen i varje position. Och jag försökte uppfylla hans testamente och leta efter sanningen i själva essensen av Deep Blue.

Illustration: Shutterstock