{***************************************************************************} {* Die Suche nach dem besten Zug - Alpha-Beta-MaxiMin *} {***************************************************************************} PROCEDURE Suche(VAR BestZug: Zug; p: ZugListe; S: SpielFeld); LABEL Gefunden; VAR i : byte; SF : SpielFeld; W, Count, tWert: integer; tLevel : 0..maxZugTiefe; FUNCTION MAX(x,y:integer):integer; BEGIN IF x>y THEN MAX:=x ELSE MAX:=y END; FUNCTION MIN(x,y:integer):integer; BEGIN IF xleer THEN Steine[b]:=Steine[b]+3*z; IF a<>leer THEN IF b=leer THEN Steine[c]:=Steine[c]+z; END; {KritWert} BEGIN {Wert} Count:=succ(Count); fillchar(Steine,SizeOf(Steine),0); FOR i:=1 TO Groesse DO FOR j:=1 TO Groesse DO BEGIN b:=SF[i,j]; Steine[b]:=succ(Steine[b]) END; Ende:=(Steine[leer]=0) OR (KannNicht[Mensch] AND KannNicht[Computer]) OR (Steine[Mensch]=0) OR (Steine[Computer]=0); IF Ende THEN IF Steine[Computer]>Steine[Mensch] THEN Wert:=+256 ELSE IF Steine[Mensch]>Steine[Computer] THEN Wert:=-256 ELSE Wert:=0 ELSE BEGIN KritWert(2,2,1,1); KritWert(2,Groesse-1,1,Groesse); KritWert(Groesse-1,2,Groesse,1); KritWert(Groesse-1,Groesse-1,Groesse,Groesse); Wert:=Steine[Computer]-Steine[Mensch]; END END; {Wert} {$A-} FUNCTION WertVon(AmZug:Spieler; SF:SpielFeld; Tiefe:byte; alphaO,betaO:integer):integer; VAR i : byte; cut : boolean; alpha, beta: integer; tSF : SpielFeld; ZL : ZugListe; BEGIN IF Tiefe=0 THEN WertVon:=Wert(SF) ELSE BEGIN GenZugliste(SF,AmZug,ZL); i:=1; IF AmZug=computer THEN alpha:=-256 ELSE beta:=+256; WITH ZL DO REPEAT tSF:=SF; IF Anzahl>0 THEN SpielFeldNeu(tSF,AmZug,Zuege[i]); IF AmZug=computer THEN BEGIN alpha:=MAX(WertVon(mensch,tSF,Tiefe-1,alpha,betaO),alpha); cut:=alpha>betaO END ELSE BEGIN beta:=MIN(WertVon(computer,tSF,Tiefe-1,alphaO,beta),beta); cut:=betaAnzahl); IF AmZug=computer THEN WertVon:=alpha ELSE WertVon:=beta END END; {WertVon} {$A+} BEGIN {Suche} normvideo; gotoxy(70,22); ClrEol; gotoxy(50,12); ClrEol; gotoxy(50,13); ClrEol; IF p.Anzahl=1 THEN BEGIN BestZug:=p.Zuege[1]; GOTO Gefunden END; IF ZugNummer=0 THEN BEGIN BestZug:=p.Zuege[Random(4)+1]; GOTO Gefunden END; IF ZugNummer+42*Groesse*Groesse DIV 3 THEN tLevel:=LEVEL+1 ELSE tLevel:=LEVEL; gotoxy(50,15); write('Zugtiefe: ',tLevel); W:=-maxint; Count:=0; WITH p DO FOR i:=1 TO Anzahl DO BEGIN gotoxy(50,13); write(chr(Zuege[i].Spalte+64),Zuege[i].Zeile:2); SF:=S; SpielFeldNeu(SF,Computer,Zuege[i]); tWert:=WertVon(Mensch,SF,tLevel,W,maxint); gotoxy(70,22); write(count:7); IF (tWert>W) OR ((tWert=W) AND (random(4)=0)) THEN BEGIN W:=tWert; BestZug:=Zuege[i]; gotoxy(50,12); write(chr(BestZug.Spalte+64), Bestzug.Zeile:2,W:8); IF W=256 THEN GOTO Gefunden END END; Gefunden: END;