Spela schack | Om dataschack | Koda spelbräda | Öppningsspel | Evalueringsfunktion | Draggenerator | Minimax & Alfabeta-reducering | Dragsortering | Slutspel | Schackregler | Javascript | Länkar/referenser

Minmax och negamax beskrivs bättre på python-rummet numera. Jag skriver om koden i python och det kommer gå att labba och lära sig bättre än på denna gamla sida. Detsamma gäller även optimeringen av minmax med alfabeta -reducering.

Dessa algoritmer, som egentligen är samma fast den senare är en optimerad variant av den förra, är det nav kring vilket de flesta schackprogram är byggda kring. Om dessa algoritmer inte fanns och man skulle sätta sig med ett blankt papper och fundera över hur ett schackprogram skulle konstrueras så skulle man sannolikt uppfinna dessa algoritmer. Vad det handlar om är en logisk slutsats utifrån spelets natur.

Givet alla tänkbara drag väljer du det bästa, motspelaren resonerar självfallet på samma sätt. Frågan är alltså konkret: Hur bra drag går det att spela givet att motspelaren saboterar maximalt?

Schack är ett symetriskt spel där 2 spelare med samma spelregler och pjäser turas om att flytta sina pjäser. Studera grafen här nedan. Säg att du är ljusgrå och datorn är mörkgrå. Tänk vidare att du funderar över ditt nästa drag. Detta är den översta ljusgrå cirkeln. Om du gör detta drag kan datorn göra 4 motdrag (mörkgrå cirklar). För varje dessa motdrag datorn kan göra kan du göra ytterligare motdrag.


Denna graf/träd representerar alltså olika tänkbara scenarion. I denna graf förgrenar sig motdragen som 4 stycken givet ett drag. Detta är enbart för att illustrera något överskådligt. I verkligheten är förgreningsfaktorn i schack ca 35. Trädet växer mycket snabbt för varje ytterligare nivå (djup). Man brukar kalla detta för den kombinatoriska explosionen. Antalet noder att söka igenom växer till mer än antalet atomer i universum. Man måste därför begränsa djupet. Problemet med att begränsa djupet i denna graf är att du missar information i analysen. Du kanske klipper trädet precis så att du missar draget som skulle ge schackmatt. Detta brukar kallas horisonteffekten. Du ser inte mer än det du studerar i grafen. Vad som finns på nästa nivå är okänt. Det finns olika ideer om lösningar för att hantera horisonteffekten. Om det längre fram.

Vi tänker oss vidare att vi har en evalueringsfunktion som ger en poäng för hur bra eller dåligt vår spelposition är.

Samma träd fast med poäng kan då se ut som nedan.


Vilket av dragen A, B, C eller D skall datorn göra? Datorn skall naturligtvis maximera sin poäng. Man får ju vidare anta att motståndaren (människan) kommer "förstöra" så mycket som möjligt.

Vi formulerar oss så här: Vilket drag ger datorn mest poäng givet att motspelaren, när det är dennes drag, försätter datorn i så dålig position som möjligt - alltså själv försöker maximera poängen ur sitt perspektiv?

Givet detta synsätt förefaller C vara den som ger mest poäng därför att då får vi minst 4 poäng. Eller hur? Vi måste ju utgå ifrån att motståndaren försöker sabotera maximalt. Men även om motståndaren saboterar maximalt får vi minst 4 poäng, vilket är bättre än 2 poäng eller 3 poäng.


Vi kan konkretisera denna taktik och på följande sätt.


Vi kallar algoritmen minimax eftersom vi varannan ply väljer max och varannan min.

Nedan har vi lite kod som implementerar denna minimax -strategi. Notera hur Max loopar över alla noders poäng och memorerar det bästa och att Min gör tvärtom.

function Max(var depth)
{
	var best = -99999999;
	if (depth <= 0)
	{
		return Eval();
	}
	Skapa draglista
	while (drag kvar att göra) 
	{
		Gör ett drag i listan
		val = Min(depth - 1);
		Ta tillbaka detta drag
		if (val > best)
		{
			best = val;
		}
	}
	return best;
}

 

function Min(int depth)
{

    int best = 99999999
	if (depth <= 0)
	{
		return Eval();
	}
	Skapa draglista
	while (drag kvar att göra) 
	{
		Gör ett drag i listan
		val = Max(depth - 1);
		Ta tillbaka detta drag
		if (val < best)
		{
			best = val;
		}
	}
	return best;
}

Dessa två funktioner är ömsesidigt rekursiva. De anropar varandra ömsesidigt tills de når maxdjupet i grafen där de istället returnerar evalueringsfunktionens värde.

Om man funderar lite över dessa två symetriska funktioner och hur evalueringsfunktionen räknar ut sitt värde kommer man snart fram till att dessa två funktioner kan skrivas på ett enklare sätt.

Schack är ett helt symetriskt nollsummespel. Den enes övertag enligt evalueringsfunktionen är den andras underläge enligt samma. Om vit ligger över med E poäng så det samma sak som att svart ligger under med E poäng.

Vi utnyttjar detta genom att helt enkelt skriva om ovanstående till följande kod, som kallas negamax:

function NegaMax(var depth)
{
	if (depth == 0)
	{
		return Eval();
	}
	Skapa en lista av alla drag
	best = -99999999;
	while (drag kvar att göra)
	{
		Gör ett drag i listan
		temp=-Negamax(depth-1)	
		Ta tillbaka draget
		if (temp>best)
		{
			best=temp;
		}
	}
	return best;
}

För att förstå alfabeta -reducering måste man ha klart för sig i vilken ordning sökningen sker. Ovanstående sökalgoritmer sorterar under kategorin djupet-först vilket gör att man skall tolka grafen enligt nedan.


Om man tar ett större exempel på minimax ...



Alfabeta -reducering är en optimering av minimax som bygger på en enkel observation. Om det finns ett bra drag och du har hamnat i delträd som i bästa fall ger ett sämre drag - sluta sök i den grenen och gå istället vidare. Om man applicerar alfabeta -reducering på ovanstående exempel får man nedanstående exempel som ger precis samma resultat fast med mycket mindre sökning. De icke ifyllda noderna är sådana noder som ej behövs undersökas.
För att återknyta till något som går att ta på. Om du i din sökning hittar ett drag där motståndaren kan ta din drottning - trots att det finns ett drag där du istället kan ta motståndarens torn - sök då istället vidare kring denna senare väg och skippa den förra.

Alfa är definitionsmässigt det minsta värde som vi efter en sökning är garanterade. Det kan bli högre om motspelaren gör dåligt ifrån sig. Men det kommer minst bli detta alfa-värde. Det betyder också att vi kan dra slutsatser utifrån detta alfavärde. Om alfavärdet är lika med eller större än det matriella värdet av en drottning, då lyckas vi minst plocka en drottning av motspelaren.

Beta är det högsta värde som vi efter en sökning kan uppnå.

När ett betaklipp i sökträdet sker då är det högsta värdet man kan uppnå väldigt dåligt. Säg att vi har en drottning som kan bli utslagen ifall vi inte flyttar den. Om vi låter den stå kvar då är det bästa vi kan uppnå; att förlora vår drottning. Det kan gå ännu värre. Men vi kommer minst bli av med drottningen.

Studera trädet ovan där det står a=7. När vi kommit dit vet vi att 7 > 5 (noden ovan). Vi behöver alltså inte forska vidare just där eftersom detta delträd ändå inte kommer påverka något.

Studera trädet där det står b=2. Där vet vi att vi aldrig kommer få mer poäng än 2 och eftersom 2 < 5 kan vi avsluta sökningen där helt.

function NegaMaxAlfaBeta(var depth, var alfa, var beta)
{
	if (depth == 0)
	{
		return Eval();
	}
	Skapa en lista av alla drag
	while (drag kvar att göra)
	{
		Gör ett drag i listan
		val = -NegaMaxAlfaBeta(depth - 1, -beta, -alfa);
		Ta tillbaka draget
		if (val >= beta)
		{
			return beta;
		}	
		if (val > alfa)
		{	
			alfa = val;
		}
	}
	return alfa;
}

val = NegaMaxAlfaBeta(4, -99999999, 99999999);

Alfa representerar den minsta poäng som den maximerande spelaren är garanterad och beta är den högsta poäng som den minimerade spelaren är garanterad. Från start sätts alfa till ett stort negativt tal och beta till ett stort positivt tal.

Värt att notera är att alfabeta -reduceringen blir större desto tidigare algoritmen upptäcker att den kan klippa i sökträdet. Man förstår därför att det är värt att fundera över om det är möjligt att sortera dragen på något sätt i draggeneratorn. Detta är svåra saker men viktigt att lägga på minnet. Går det att påverka dragordningen man matar sökalgoritmen med finns mycket att vinna. Läs mer om detta under dragsortering.

Vi vill testa kanske 30 tänkbara drag. För varje drag finns kanske 30 motdrag. osv. Vi har att göra med en funktion som ökar exponentiellt. Man pratar allmänt om tidskomplexiteter för olika algoritmer, den är alltså O(B^D) för minimax. Det betyder att när vi ökar djupet i sökningen kommer antalet noder öka extremt kraftigt och tidsåtgången ökar från sekunder till hundratusenstals år, alltså något som inte går att räkna på.
Det kommer sålunda bli ett krig mot detta matematiska faktum. Vi kan helt enkelt inte söka hur mycket som helst. Vi måste hitta metoder att klippa i trädet eller söka smalare och vassare. Många tekniker vid sidan om minimax och alfabeta -reducering är metoder som just försöker hantera detta.

Optimalt reduceras trädet med alfabeta till B^[D/2] + B^[D/2] - 1 (Knuth & Moore, 1975), där D är djupet och B är förgreningsfaktorn. En matematisk konsekvens är här att man optimalt teoretiskt kan söka dubbelt så djupt med samma tidsåtgång. Ett annat sätt att se på det är att förgreningsfaktorn minskar från ca 35 till ca 6.

Exempel. Ponera att man söker 2 ply fram och förgreningsfaktorn är 30. Med minimax genomsöks då 30*30 noder = 900 noder. Kopplar man in alfabeta -reducering så genomsöks under optimala omständigheter, dvs perfekt dragsortering, 30¹+30¹-1 = 59 noder. Det är stor skillnad mellan 59 noder och 900 noder. Reduceringen blir större desto djupare du söker men man skall samtidigt komma ihåg att det är osannolikt att man uppnår ideala förhållanden, dvs perfekt dragsortering, så detta är bara teori. Oftast finns ingen dragsortering alls och då blir förbättringen mycket mindre. Men det blir alltid en förbättring med alfabeta.

Ett problem i schack är det s.k. horisontproblemet. Man måste ju avbryta sökningen vid något djup annars kommer den kombinatoriska explosionen att ta överhanden och man får ett program som tänker i all oändlighet.

Men ponera att det som händer vid horisonten är att vi tar någon pjäs från motståndaren. Vi är naturligtvis väldigt nyfikna på om motståndaren kan göra ett motdrag.

Det som ser ut som ett bra drag kanske är helt värdelöst. Eller tvärtom, det som ser ut som ett dåligt drag kanske är ett genialt.

Det finns många taktiska situationer i schack som bara handlar om att utbyta pjäser. I dessa sitationer ger ofta ren minimax -sökning opålitliga svar p.g.a. av att algoritmen klipper vid ett fixt djup innan analysen av pjäsutbytet är färdigt. I dessa speciella strider är den kombinatoriska explosionen ganska begränsad samtidigt som resultatet av striden känns mer intressant än genomsnittet av olika analys-situationer. Vi skulle kunna tänka oss att göra ett undantag och låta undersöka dessa slag vid horisonten om de uppstår.

Denna metod förekommer ofta i schackprogram och brukar kallas quiescent search. Istället för att anropa evalueringsfunktionen från negamax anropar vi en quiescent -sökning som i sin tur evaluerar eventuellt pjäsutbyte och returnerar facit.

Exempel på pjäsutbyte ser du här till höger. Svart torn börjar med att slå F4-F8. Det finns olika utgångar på denna strid men det ser ut som svart minst kommer avancera 100 poäng i matrial. Det mest sannolika är en vinst på 300 poäng i matrial, dvs att vit flyr direkt. Om vit till varje pris skall hämnas varje utslagen pjäs kommer detta ge svart 600 poäng plus i matrial vilket involverar att vit drottning bli utslagen. Det är naturligtvis inte sannolikt. Men svart tjänar minst 100 poäng på detta drag. Det är också detta svar algoritmen ger.

Denna typ av analys söker utan djupbegränsning. Det betyder, i terorin, att den kan söka hur djupt som helst. Detta är möjligt eftersom dessa strider ofta har en låg förgreningsfaktor. Men ofta är ju inte samma sak som alltid. Det kan uppstå situationer när quies search tar extra lång tid på sig. Denna risk och den tidsåtgång generellt som analysen kräver skall ställas mot den ökade spelstyrkan. Man kan ju också rent allmänt ställa sig frågan: Om man skapar en funktion för att komma över ett horisontproblem skall man introducera ett nytt horisontproblem i denna funktion? Studera grafen till vänster som visar slaget ovan till höger. Det finns 2 grenar i grafen beroende på vilket motdrag vit väljer.

Nedan ser du kod jag gjort för quiescent search, QSearch, samt hur den anropas från NegaMaxAlfaBeta. Den största skillnaden mellan qsearch och negamax är att quiescent search anropar en draggenerator som enbart returnerar drag som slår ut andra pjäser. Observera att det är en separat draggenerator. Jag skulle naturligtvis kunna fixa så att den vanliga draggeneratorn kunde ställas om med något argument så att den producerar dessa drag men jag har här prioriterat hastighet framför kompakt kod. Det blir alltså lite mer kod (2 draggeneratorer, generateMovelist samt generateKillMovelist) men jag får då en snabb quiescent search.

function QSearch(depth, alfa, beta, tp, mdepth)
{
   var E, nrMoves, nrMovesMem, local_sp, es=(tp)%2;   
   E = es?-Evalue:Evalue;

   if (E >= beta)
   {
      return beta;
   }   
   if (E > alfa)
   {
      alfa = E;
   }

   nrMoves=nrMovesMem=generateKillMovelist(tp,depth);
   local_sp=m_sp-nrMoves-1;

   while (nrMoves--)
   {
      local_sp++;

      doMove(m_stFr[local_sp],m_stTo[local_sp],tp,depth);
      E = -QSearch(depth - 1, -beta, -alfa, 1-tp, mdepth);
      undoMove(0);

      if (E >= beta)
      {
         m_sp-=nrMovesMem;
         return beta;
      }   
      if (E > alfa)
      {
         alfa = E;
      }
   }

   m_sp-=nrMovesMem;
   return alfa;
}

function NegaMaxAlfaBeta(depth, alfa, beta, tp, mdepth)
{
   var E, nrMoves, nrMovesMem, local_sp, es=(tp)%2;

   nrMoves=nrMovesMem=generateMovelist(tp,depth);
   local_sp=m_sp-nrMoves-1;
   
   while (nrMoves--)
   {
      local_sp++;

      doMove(m_stFr[local_sp],m_stTo[local_sp],tp,mdepth-depth);

      if (depth==1)
      {
         E = es?-Evalue:Evalue;
         if (E > alfa)
         {
            E = -QSearch(depth - 1, -beta, -alfa, 1-tp, mdepth);
         }
         else
         {
            E = alfa;
         }
      }
      else
      {
         E = -NegaMaxAlfaBeta(depth - 1, -beta, -alfa, 1-tp, mdepth);
      }

      undoMove(0);

      if (E >= beta)
      {
         m_sp-=nrMovesMem;
         return beta;
      }   
      if (E > alfa)
      {
         pvlFr[mdepth-depth]=m_stFr[local_sp];
         pvlTo[mdepth-depth]=m_stTo[local_sp];
         pvlAlfa[mdepth-depth]=E;

         alfa = E;
      }
   }

   m_sp-=nrMovesMem;
   return alfa;
}

Iterativ fördjupning handlar om att sakta öka djupet till önskvärt djup vid sökningen. Om vi vill titta 4 ply fram så söker först på 1 ply. Därefter börjar vi om och söker på 2 ply. Därefter börjar vi om och söker på 3 ply. Därefter börjar vi om och söker på 4 ply.

Vad vinner vi på detta då? Vi kan få ut en del information allt eftersom vi sakta ökar djupet som gör att den extra tiden det går åt att ständigt börja om återvinns med marginal. Samtidigt får vi en möjlighet att få kontroll över tidsåtgången. Vi kan alltså mäta tiden det tar för programmet att göra en sökning och ifall denna tid är överskriden kan vi avbryta.

Vad vi gör är att vi låter sökalgoritmen komma ihåg den bästa linjen, som gav det bästa alfa-värdet. När vi återstartar sökningen med ett större djup så är sannolikheten hög att vi inte behöver göra om någonting tidigare gjort om dragsortering lägger draget i bästa linjen först. Nu finns det situationer när den bästa linjen tycks förändras då djupet ökar och då är effektiviteten lägre. Men man skall samtidigt komma ihåg att för varje ytterigare djup ökar antalet noder väldigt stort. Även om vi skulle söka om alla tidigare nivåer utan att ta hänsyn till bästa linjen så ökar antalet genomsökta noder bara med ca 4%. Det är alltså värt allt bekymmer att köra iterativ fördjupning.

function IDNegaMaxAlfaBeta(maxdepth,maxtime)
{
	timestart=timer();
	for (depth=1;depth<=maxdepth;depth++)
	{
		NegaMaxAlphaBeta(depth, -999999, 999999);
		timenow=timer();
		if (avbryt || ((timenow-timestart)>maxtime))
			break;
	}
}

Oavn ser du hur koden kan se ut för iterativ fördjupning, något förenklat.




Saker och ting är inte färdiga här, så du kommer nog inte få ut något av att exprimentera ännu. När det är klart kan du testa olika uppställningar med olika sökmöjligheter.