alfabeta -reducering

Alfabeta -reducering är en optimering av minmax sökalgoritm. Säg att vi hittat ett drag som garanterar oss en viss poäng i ett tidigare delträd. Om vi senare i sökningen kommer till en situation i ett annat delträd där vi kan vara säkra på att vi kommer få samma eller mindre poäng - då kan vi avbryta sökningen i det delträdet (och spara tid). Det är denna grej detta handlar om. Skippa onödig sökning.

skippar onödig sökning

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.

För att förstå alfabeta -reducering är det hög tid begripa att minmax är av typen djupet-först. Sökalgoritmen söker alltså igenom trädet i nedan ordning.

Låt oss ta det från början. Vi listar alla drag vi kan göra, det verkar vara 2 stycken. Vi börjar med att undersöka det första. Vi listar alla motdrag till detta drag, det verkar vara 2 stycken. Vi upptäcker att motspelaren kan göra ett drag som ger oss en situation på 11 poäng. Vi testar nästan motdrag. Det verkar vara bättre (för motspelaren) eftersom det sänker vår poäng till 6 poäng för ställningen. Inga mer motdrag att undersöka, så algoritmen backtrackar. Vi testar vårt nästa möjliga drag. Det verkar finnas 2 motdrag på vårt drag (4). Vi börjar med att undersöka första motdraget. Detta leder till en position där vi får 1 poäng (se nedan). Nu till en intressant fråga: Motspelaren kan minimera denna gren till 1 poäng. 1 poäng är lägre än 6 poäng som vi fick i vårt tidigare drag. Kan den här 1 poängen magiskt bli större än 6 poäng? Nej, det kan den inte. Den kan däremot bli ännu lägre än 1 poäng. Men det spelar ingen roll. Vi vet redan att det enda detta delträd har att erbjuda är ett sämre alternativ än första draget som gav oss garanterade 6 poäng. Eller hur?

Vi kan alltså avbryta sökningen i detta delträd och spara en massa tid. Så, vi kan avbryta om vi stöter på något som best-case är sämre än det vi redan har. Med samma resonamang fast omvänt ur motspelarens perspektiv, kan vi avbryta om motspelaren stöter på något bättre än det vi behöver acceptera.

Vi kör ett exempel till. Vi dyker ner i vårt träd och finner 1 poäng. Vi söker vidare och upptäcker att vi kan sänka motspelaren till få 5 poäng här. Vi memorerar denna siffra 5 poäng. Alfa = 5. När vi nu fortsätter söka på minimera -nivån, så vet vi att vi kan minimera till 5 poäng. Dvs om maximeranivån under oss överstiger detta värde på 5, då kan vi direkt avbryta. Vi testar vidare och finner att även nästa delträd överstiger 5, vi avbryter där också. Vi testar sista draget i detta delträd och hittar 8 poäng, vilket är högre än 5 så vi avbryter där också. Nu när vi går över till höger delträd, så vet vi redan att vi är garanterade ett drag som ger 5 poäng. Det betyder att när vi upptäcker att motspelaren kan minimera detta delträd till 2, så kan vi skippa resten av sökningen på detta delträd. Det kanske är ännu sämre än 2 poäng - oavsett är det sämre än 5 poäng och vi behöver inte ödsla vår tid.

alfa och beta

alfa

Alfa är 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. Alfa representerar den minsta poäng som den maximerande ("vi") spelaren är garanterad.

beta

Beta är det högsta värde som vi efter en sökning kan uppnå. Beta är den högsta poäng som den minimerade spelaren (motspelaren) är garanterad.

negamax med alfabeta -reducering

För att skriva om negamax så att den arbetar med alfabeta -reducering behöver vi dels skicka med alfa och beta som parametrar. Dessutom lägga till två if -statser, den ena gör ett beta -klipp, den andra lagrar undan alfa -värdet. Vi byter plats på, dvs vänder på, logiken varannan nivå i trädet.

def NegaMaxAlfaBeta(djup, alfa, beta):
	if (djup == 0):
		return Eval()
	drag = dragGenerator
	while (drag kvar):
		Gör ett drag i listan
		val = -NegaMaxAlfaBeta(djup-1, -beta, -alfa)
		Ta tillbaka draget
		if (val >= beta):
			return beta
		if (val > alfa):
			alfa = val
	return alfa

För att testa om ovan pseudokod verkligen fungerar, så kan vi åter ta fram vårt lilla träd och köra negamax -algoritmen på det. Ändra värden i trädet och studera resultatet!

Negamax alfabeta

Som du ser ovan när du kör koden, så skippar den ganska många delträd men kommer fram till samma resultat. Prova köra med och utan alfabeta. Det står None på värdet, där negamax skippat delträd. Jämför utan alfabeta.

egenskaper

Ju större sökträd desto mer kan sparas med alfabeta -reducering. Ju tidigare vi upptäcker att vi kan klippa i trädet, desto mer kan vi klippa bort. Pga detta spelar dragsortering en stor roll, dvs att vi sorterar dragen så att beta -klippet kommer så tidigt som möjligt. Vi kan göra detta genom att i schack som exempel lägga drag som slår ut andra pjäser först i draglistan. Det är en enkel sortering som ger väldigt stor effekt på hur mycket som kan klippas bort i sökträdet.

I ovan experiment -träd så klipps ungefär 50% bort när vi kör alfabeta -reducering jämfört med vanilla negamax. Men i verkligen, om förgreningsfaktorn är stor, så blir besparingen typiskt mycket större. 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. Om man söker 2 ply fram och förgreningsfaktorn är 30, så med minimax genomsöks då 30*30 noder = 900 noder. Med alfabeta -reducering så genomsöks under optimala omständigheter, dvs perfekt dragsortering, 301+301-1 = 59 noder. Det är stor skillnad mellan 59 noder och 900 noder. Då är detta ett litet exempel. Det sticker iväg mot 99% vid lite större exempel. Det är alltså dumt att inte använda alfabeta -reducering. Men det förutsätter att du använder dragsortering, vilket lyckligtvis är ganska okomplicerat.