Latex-Bibliographie in HTML umwandeln

Mathematik: das Spiel Isola Teil 3: der Alpha-Beta Ansatz zur Zugsuche - ein Zwischenstand Released by matroid on Fr. 17. Februar 2023 22:38:47 [Statistics] [Comments] Written by Delastelle - 149 x read [Outline] Printer-friendly version -  Choose languageDE EN   \(\begingroup\) Dies ist mein 3.Artikel zum Spiel Isola. Im 1.Teil habe ich versucht, Isola für kleine Bretter zu lösen. (eher nicht so erfolgreich?) Im 2.Teil habe ich für das normale 8x6 Isola mehrere Strategien mit Suchtiefe 1 getestet. Jetzt habe ich für das 8x6 Brett mit Suchtiefe 1,3,5 und für das kleinere 5x5 Brett mit Suchtiefe 1,3,5 gearbeitet. Möglich wurde dies durch den Einsatz des Alpha-Beta-Algorithmus, den man z.B. aus der Computerschachprogrammierung in ähnlicher Form kennt. [Edit] [To the bottom] Problembeschreibung Aus der Spielanleitung zum Brettspiel Isola (aus dem Jahr 1980) Das Spielbrett umfasst 6x8 = 48 Felder, von denen die 2 Startfelder nicht gedrückt werden können. Die restlichen 46 Felder werden mit gelben drückbaren Plättchen belegt. Spielverlauf "Wenn ein Spieler an der Reihe ist, zieht er zunächst seine Figur ein Feld weiter auf ein benachbartes Feld, und zwar in jede beliebige Richtung. Danach entfernt er noch einen Spielstein seiner Wahl vom Plan. Dies geschieht indem man den Spielstein durch das Gitter hindurchdrückt. Ziel des Spieles ist es, durch Entfernen der Spielsteine den Gegner so zu behindern, daß dieser auf einem Feld isoliert wird und nicht mehr ziehen kann. Derjenige, dem es zuerst gelingt, seinen Gegenspieler zu isolieren, gewinnt das Spiel. Auf einem Feld darf nur eine Figur stehen. Als Feld gelten die gelben Spielsteine und auch die beiden Ausgangsfelder. Beide Spieler können die Ausgangsfelder (auch das des Gegenspielers) beliebig oft besetzen." Ich habe als Startfeld für Rot immer das Mittlere Feld links (Zeilenzahl ungerade) oder das Feld 1 über der Mitte (Zeilenzahl gerade) gewählt. Das Startfeld von Blau ist gespiegelt. Hinweis: in meinen aktuellen Programm sind alle Felder drückbar. Falls die Startfelder nicht drückbar sein sollen - wie im Originalspiel - so muss man das Programm leicht anpassen. Damit ist für einen Spieler der ziehen kann immer ein Feld drückbar - nämlich mindestens das Feld wo er gerade stand. (Bild 2: Originalspiel - Rot kann zwar ziehen, aber keinen Stein mehr drücken) (Bild 3: Originalspiel - Blau kann zwar ziehen, aber keinen Stein mehr drücken) [Edit] Bewertung einer Stellung Eine recht einfache Bewertung einer Stellung (siehe u.a. Internet Kory Becker). Strategien: (1) Zufall, bei mir bewert = 0 für jeden Zug (2) bewert = 2*rotzüge - blauzüge, rotzüge = Anzahl der Felder die rot betreten kann, blauzüge = Anzahl der Felder die blau betreten kann (Bild 4: Bewertung bei Strategie Nr.3 bewert = 20 + rotzüge - 2*blauzüge = 20+7-2*6 = 15) (3) bewert = rotzüge - 2*blauzüge (4) für zugzahl < 22 Strategie (2), sonst Strategie (3) Idee: spiele bei vollerem Brett (Eröffnung) eine andere Strategie als bei leererem Brett (Endspiel) (5) für zugzahl < 22 Strategie (3), sonst Strategie (2) Bei mir wurde zu bewert noch 20 addiert, um bewertungen > 0 zu erhalten falls blauzüge = 0, so gilt bewert = 1000 (Matt von blau) [Edit] der Alpha Beta Code \sourceon integer procedure alphabetamax(position J, integer alpha,beta); begin integer j, w, value; . determine successor posions J.1, ..., J.w; . if w = 0 then return f(J) // Blattbewertung . value = alpha . for j = 1 to w do begin . value = max(value, alphabetamin(J.j, value, beta); . if (value >= beta) then return value // beta-Schnitt . end; . return value end; integer procedure alphabetamin(position J, integer alpha,beta); begin integer j, w, value; . determine successor posions J.1, ..., J.w; . if w = 0 then return f(J) // Blattbewertung . value = beta . for j = 1 to w do begin . value = max(value, alphabetamax(J.j, alpha, value); . if (value <= alpha) then return value // alpha-Schnitt . end; . return value end; \sourceoff siehe Literaturliste am Ende [Edit] Ein paar Ergebnisse und Beispielläufe für das 8x6 und das 5x5 Brett Ergebnisse für 20 Läufe für das 8x6 Brett (Strategie und Suchtiefe) ! Rot 2 / T 3 // Blau 2 / T 3 -> Rot 8 von 20 gewonnen / 38,4 Sekunden ! Rot 2 / T 5 // Blau 2 / T 3 -> Rot 20 von 20 gewonnen / 46447,9 Sekunden ! Rot 2 / T 3 // Blau 2 / T 5 -> Rot 1 von 20 gewonnen / 35397,1 Sekunden ! Rot 2 / T 5 // Blau 2 / T 5 -> Rot 10 von 20 gewonnen / 105501,8 Sekunden ! ! Rot 3 / T 3 // Blau 3 / T 3 -> Rot 11 von 20 gewonnen / 36,7 Sekunden ! Rot 3 / T 5 // Blau 3 / T 3 -> Rot 14 von 20 gewonnen / 18035,1 Sekunden ! Rot 3 / T 3 // Blau 3 / T 5 -> Rot 2 von 20 gewonnen / 16782,2 Sekunden ! Rot 3 / T 5 // Blau 3 / T 5 -> Rot 11 von 20 gewonnen / 44948,5 Sekunden Ergebnisse für 20 Läufe für das 5x5 Brett (Strategie und Suchtiefe) ! Rot 2 / T 3 // Blau 2 / T 3 -> Rot 10 von 20 gewonnen / 5,4 Sekunden ! Rot 2 / T 5 // Blau 2 / T 3 -> Rot 18 von 20 gewonnen / 1018,4 Sekunden ! Rot 2 / T 3 // Blau 2 / T 5 -> Rot 5 von 20 gewonnen / 1427,3 Sekunden ! Rot 2 / T 5 // Blau 2 / T 5 -> Rot 14 von 20 gewonnen / 1537,6 Sekunden ! ! Rot 3 / T 3 // Blau 3 / T 3 -> Rot 20 von 20 gewonnen / 2,3 Sekunden ! Rot 3 / T 5 // Blau 3 / T 3 -> Rot 19 von 20 gewonnen / 456,6 Sekunden ! Rot 3 / T 3 // Blau 3 / T 5 -> Rot 17 von 20 gewonnen / 335,5 Sekunden ! Rot 3 / T 5 // Blau 3 / T 5 -> Rot 19 von 20 gewonnen / 686,6 Sekunden Ein Beispiellauf für das 5x5 Feld. \showon \sourceon rotstrategie 3 suchtieferot 3 blaustrategie 3 suchtiefeblau 3 Zug Spieler 1 (rot) zugnr 1 Brett ------------ x x x x x x x x x x x R x . B x x x x x x x x x x ------------ Zeit = 3.120020E-02 Zug Spieler 2 (blau) zugnr 2 Brett ------------ x x x x x . x x x x x R x . x x x x B x x x x x x ------------ Zeit = 7.800050E-02 Zug Spieler 1 (rot) zugnr 3 Brett ------------ x x x x x . x x x x x x R . x x x . B x x x x x x ------------ Zeit = 9.360060E-02 Zug Spieler 2 (blau) zugnr 4 Brett ------------ x x x x x . x x x x x . R . x x x . x x x x B x x ------------ Zeit = 0.109201 Zug Spieler 1 (rot) zugnr 5 Brett ------------ x x x x x . x x x x x . x . x x . . R x x x B x x ------------ Zeit = 0.109201 Zug Spieler 2 (blau) zugnr 6 Brett ------------ x x x x . . x x x x x . x . x x . . R x x x x B x ------------ Zeit = 0.124801 Zug Spieler 1 (rot) zugnr 7 Brett ------------ x x x x . . x x x x x . x . x x . . . R x x x B x ------------ Zeit = 0.124801 Zug Spieler 2 (blau) zugnr 8 Brett ------------ x x x x . . x x x x x . x . x x . . . R x x B x . ------------ Zeit = 0.124801 Zug Spieler 1 (rot) zugnr 9 Brett ------------ x x x x . . x x x x x . x . x x . . . x x . B R . ------------ Zeit = 0.124801 rotgewinn 1 blaugewinn 0 von 1 feldmax 1 147 Zeit = 0.124801 \sourceoff \showoff Ein Beispiellauf für das 8x6 Brett. \showon \sourceon rotstrategie 3 suchtieferot 3 blaustrategie 3 suchtiefeblau 3 Zug Spieler 1 (rot) zugnr 1 Brett ------------ x x x x x x x x x x x x x x x x x R x x x x x x x x x x x . x B x x x x x x x x x x x x x x x x ------------ Zeit = 0.109201 Zug Spieler 2 (blau) zugnr 2 Brett ------------ x x x x x x x x x x x x x x x x x R . x x x x B x x x x x . x x x x x x x x x x x x x x x x x x ------------ Zeit = 0.187201 Zug Spieler 1 (rot) zugnr 3 Brett ------------ x x x x x x x x x x x x x x x x x x . x x . x B R x x x x . x x x x x x x x x x x x x x x x x x ------------ Zeit = 0.312002 Zug Spieler 2 (blau) zugnr 4 Brett ------------ x x x x x x x x x x x x x x x x x x . x x . x x R x x x x . x B x x x x x x x x x x . x x x x x ------------ Zeit = 0.374402 Zug Spieler 1 (rot) zugnr 5 Brett ------------ x x x x x x x x x x x x x x x x x R . x x . x x x x x x x . . B x x x x x x x x x x . x x x x x ------------ Zeit = 0.468003 Zug Spieler 2 (blau) zugnr 6 Brett ------------ x x x x x x x x x x x x x x x x x R . x x . B x x x x x x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 0.592804 Zug Spieler 1 (rot) zugnr 7 Brett ------------ x x x x x . x x x x R x x x x x x x . x x . B x x x x x x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 0.624004 Zug Spieler 2 (blau) zugnr 8 Brett ------------ x x x x x . x x x x R x x B x x . x . x x . x x x x x x x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 0.670804 Zug Spieler 1 (rot) zugnr 9 Brett ------------ x x x x x . x x x x x x x B x x . R . x x . x . x x x x x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 1.20121 Zug Spieler 2 (blau) zugnr 10 Brett ------------ x x x x x . x x x x x x x x x x . R . . B . x . x x x x x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 1.24801 Zug Spieler 1 (rot) zugnr 11 Brett ------------ x x x x x . x x x x x x . x x x . x . . B . x . x R x x x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 1.29481 Zug Spieler 2 (blau) zugnr 12 Brett ------------ x x x x x . x x x x x x . x x x . x . . x . x . x R . B x . . x x x x x x x x . x x . x x x x x ------------ Zeit = 1.31041 Zug Spieler 1 (rot) zugnr 13 Brett ------------ x x x x x . x x x x x x . x x x . x . . x . x . x x . B x . . x x x R x . x x . x x . x x x x x ------------ Zeit = 1.60681 Zug Spieler 2 (blau) zugnr 14 Brett ------------ x x x x x . x x x x x x . x x x . x . . x . x . x x . x x . . x x . R B . x x . x x . x x x x x ------------ Zeit = 1.68481 Zug Spieler 1 (rot) zugnr 15 Brett ------------ x x x x x . x x x x x x . x x x . x . . x . x . x x . R x . . x x . x B . x x . x . . x x x x x ------------ Zeit = 1.77841 Zug Spieler 2 (blau) zugnr 16 Brett ------------ x x x x x . x x x x x x . x x x . x . . x . x . x x . R B . . x x . x x . x x . x . . . x x x x ------------ Zeit = 1.79401 Zug Spieler 1 (rot) zugnr 17 Brett ------------ x x x x x . x x x x x x . x x x . x . . R . x . x x . x B . . x x . x x . x x . x . . . . x x x ------------ Zeit = 1.80961 Zug Spieler 2 (blau) zugnr 18 Brett ------------ x x x x . . x x x x x x . x x x . x . . R . x . x x . B x . . x x . x x . x x . x . . . . x x x ------------ Zeit = 1.84081 Zug Spieler 1 (rot) zugnr 19 Brett ------------ x x x x . . x x x x x x . . x x . x . . x . x . x x . B R . . x x . x x . x x . x . . . . x x x ------------ Zeit = 1.84081 Zug Spieler 2 (blau) zugnr 20 Brett ------------ x x x x . . x x x x x x . . x x . . . . B . x . x x . x R . . x x . x x . x x . x . . . . x x x ------------ Zeit = 1.85641 Zug Spieler 1 (rot) zugnr 21 Brett ------------ x x x x . . x x x x . x . . x x . . . . B . x . x x . R x . . x x . x x . x x . x . . . . x x x ------------ Zeit = 1.87201 Zug Spieler 2 (blau) zugnr 22 Brett ------------ x x x x . . x x x x . x . . x x . . . . x . x . x . . R B . . x x . x x . x x . x . . . . x x x ------------ Zeit = 1.87201 Zug Spieler 1 (rot) zugnr 23 Brett ------------ x x x x . . x x x x . x . . . x . . . . x . x . x . . x B . . x x . x R . x x . x . . . . x x x ------------ Zeit = 1.88761 Zug Spieler 2 (blau) zugnr 24 Brett ------------ x x x x . . x x x x . x . . . x . . . . x . x . x . . B . . . x x . x R . x x . x . . . . x x x ------------ Zeit = 1.88761 Zug Spieler 1 (rot) zugnr 25 Brett ------------ x x x x . . . x x x . x . . . x . . . . x . x . x . . B . . . x x . R x . x x . x . . . . x x x ------------ Zeit = 1.88761 Zug Spieler 2 (blau) zugnr 26 Brett ------------ x x x x . . . x x x . x . . . x . . . . x . x . x . . . . . . x x . R B . x x . x . . . . x x x ------------ Zeit = 1.88761 rotgewinn 0 blaugewinn 1 von 1 feldmax 1 308 Zeit = 1.88761 \sourceoff \showoff [Edit] Quelltext in Fortran 90 für 8x6 und 5x5 Brett Kurzbeschreibung des Algorithmus: - Hauptprogramm // hier findet das Spiel rot gegen blau statt - init // belege das Brett, stelle rot und blau auf Startposition - augabebrett // Ausgabe des Spielbrettes auf den Bildschirm falls gewünscht - rotmatt // ist Spieler rot Matt (kann nicht ziehen?) - blaumatt // ist Spieler blau Matt (kann nicht ziehen?) - rotbewegtfelder // bestimme Anzahl der Felder auf die rot ziehen kann - blaubewegtfelder // bestimme Anzahl der Felder auf die blau ziehen kann - sortiere // eine Sortierfunktion für Züge in Variable "feld" -> wird aktuell nicht verwendet - mische // mische Züge aus Variable "feld" - rotzugTiefe1 // ermittle einen Zug von rot für Tiefe 1 - bewertestellung // bewerte die Stellung auf dem Brett im Sinne von rot - AlphaBetaMax // Teil 1 von Alpha-Beta-Suche - AlphaBetaMin // Teil 2 von Alpha-Beta-Suche - AlphaBetaHauptprogramm // das Rahmenprogramm von Alpha-Beta-Suche - IsolaSuche // rufe die Zugsuche für Tiefe 3 oder 5 auf Code für das 8x6 Brett \showon \sourceon Fortran 90 program Isola2023AlphaBetaV14 implicit none ! Isola 2023 mit Tiefe 1, 3, 5 (AlphaBeta-Algorithmus) ! ! de.wikipedia.org/wiki/Minimax-Algorithmus ! de.wikipedia.org/wiki/Alpha-Beta-Suche ! Der Alpha-Wert ist das Ergebnis, das Spieler A mindestens erreichen wird, ! der Beta-Wert ist das Ergebnis, das Spieler B höchstens erreichen wird. ! ! mit Alpha-Beta: Isola2023AlphaBetaV14 ! 8x6 Brett (im Computer 80 Felder mit Rand) ! ! Rot 2 / T 3 // Blau 2 / T 3 -> Rot 8 von 20 gewonnen / 38,4 Sekunden ! Rot 2 / T 5 // Blau 2 / T 3 -> Rot 20 von 20 gewonnen / 46447,9 Sekunden ! Rot 2 / T 3 // Blau 2 / T 5 -> Rot 1 von 20 gewonnen / 35397,1 Sekunden ! Rot 2 / T 5 // Blau 2 / T 5 -> Rot 10 von 20 gewonnen / 105501,8 Sekunden ! ! Rot 3 / T 3 // Blau 3 / T 3 -> Rot 11 von 20 gewonnen / 36,7 Sekunden ! Rot 3 / T 5 // Blau 3 / T 3 -> Rot 14 von 20 gewonnen / 18035,1 Sekunden ! Rot 3 / T 3 // Blau 3 / T 5 -> Rot 2 von 20 gewonnen / 16782,2 Sekunden ! Rot 3 / T 5 // Blau 3 / T 5 -> Rot 11 von 20 gewonnen / 44948,5 Sekunden ! integer brett(80),brett2(80),zug8(8),zug(2) integer i,j,laeufe,rot,blau,roterg,blauerg,rotstrategie,blaustrategie integer rot2,blau2,zugnr,azspiele,rotgewinn,blaugewinn integer ende,ausgabe,suchtieferot,suchtiefeblau integer max1,strategie,suchtiefe,testen real t0,t1 common /isola1/ max1 common /isola4/ strategie common /isola5/ suchtiefe !common /isola6/ zugnr call cpu_time(t0) call random_seed() laeufe = 1 rotstrategie = 3 suchtieferot = 3 blaustrategie = 3 suchtiefeblau = 3 ausgabe = 0 !testen = 0 print *,'rotstrategie ',rotstrategie print *,'suchtieferot ',suchtieferot print *,'blaustrategie ',blaustrategie print *,'suchtiefeblau ',suchtiefeblau print *,' ' rotgewinn = 0 blaugewinn = 0 azspiele = 0 max1 = 0 DO i = 1,laeufe call init(brett,zug8,rot,blau,zugnr) ende = 0 ! call ausgabebrett(brett,rot,blau) do while (ende == 0) ! while (ende == 0) do call rotmatt(brett,zug8,rot,blau,roterg) if (roterg == 0) then !call ausgabebrett(brett,rot,blau) !stop if (suchtieferot == 1) then call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,rotstrategie) !print *,zug rot = zug(1) brett(zug(2)) = 0 zugnr = zugnr + 1 else strategie = rotstrategie suchtiefe = suchtieferot call IsolaSuche(brett,zug8,rot,blau,zug,zugnr) !print *,'nach Alpha Beta: rot(zug) ',zug !rot = zug(1) !brett(zug(2)) = 0 endif !print *,zug ! print *,zug,rot,blau if (ausgabe == 1) then ! print *,'rotzug ',zug print *,' ' print *,'Zug Spieler 1 (rot) zugnr ',zugnr call ausgabebrett(brett,rot,blau) call cpu_time(t1) print *,'Zeit = ',t1 endif else blaugewinn = blaugewinn + 1 azspiele = azspiele + 1 ende = 1 endif !print *,roterg if (roterg == 0) then ! spiegele Brett do j = 1,80 brett2(j) = brett(81-j) end do rot2 = 81-blau blau2 = 81-rot ! call blaumatt(brett,zug8,rot,blau,blauerg) call rotmatt(brett2,zug8,rot2,blau2,blauerg) if (blauerg == 0) then ! call blauzug(brett,zug8,rot,blau,zug,zugnr,blaustrategie,suchtiefeblau) !print *,suchtiefeblau if (suchtiefeblau == 1) then call rotzugTiefe1(brett2,zug8,rot2,blau2,zug,zugnr,blaustrategie) rot2 = zug(1) brett2(zug(2)) = 0 zugnr = zugnr + 1 else strategie = blaustrategie suchtiefe = suchtiefeblau call IsolaSuche(brett2,zug8,rot2,blau2,zug,zugnr) !print *,'nach Alpha Beta blau(Zug) ',zug !rot2 = zug(1) !brett2(zug(2)) = 0 ! print *,'blau(Zug) ',zug endif ! spiegele Brett do j = 1,80 brett(j) = brett2(81-j) end do rot = 81-blau2 blau = 81-rot2 if (ausgabe == 1) then ! print *,'blauzug ',zug print *,' ' print *,'Zug Spieler 2 (blau) zugnr ',zugnr call ausgabebrett(brett,rot,blau) call cpu_time(t1) print *,'Zeit = ',t1 endif else rotgewinn = rotgewinn + 1 azspiele = azspiele + 1 ende = 1 endif endif end do ! print *,brett end do print *,'rotgewinn ',rotgewinn print *,'blaugewinn ',blaugewinn print *,'von ',azspiele print *,' ' print *,'feldmax 1 ',max1 call cpu_time(t1) print *,'Zeit = ',t1 end ! ********** ! Initialiserung ! brett(1..80) = 1 (Plaetchen) oder 100 (Rand) ! rot = 32 // Startfeld ! blau = 49 // Startfeld ! spielzuege // 42x (von,nach,plaetchen gedrueckt aktuell) ! ********** subroutine init(Grundstellung,zug8,rot,blau,zugnr) implicit none integer Grundstellung(80),zug8(8) integer i,rot,blau,zugnr DO i = 1,80 GrundStellung(i) = 1 ! Plaettchen END DO Grundstellung(1) = 100 Grundstellung(2) = 100 Grundstellung(3) = 100 Grundstellung(4) = 100 Grundstellung(5) = 100 Grundstellung(6) = 100 Grundstellung(7) = 100 Grundstellung(8) = 100 Grundstellung(9) = 100 Grundstellung(10) = 100 Grundstellung(11) = 100 Grundstellung(20) = 100 Grundstellung(21) = 100 Grundstellung(30) = 100 Grundstellung(31) = 100 Grundstellung(40) = 100 Grundstellung(41) = 100 Grundstellung(50) = 100 Grundstellung(51) = 100 Grundstellung(60) = 100 Grundstellung(61) = 100 Grundstellung(70) = 100 Grundstellung(71) = 100 Grundstellung(72) = 100 Grundstellung(73) = 100 Grundstellung(74) = 100 Grundstellung(75) = 100 Grundstellung(76) = 100 Grundstellung(77) = 100 Grundstellung(78) = 100 Grundstellung(79) = 100 Grundstellung(80) = 100 ! spaeter vielleicht mit 2 fixen Feldern (Isola Original) !Grundstellung(31) = 50 !Grundstellung(49) = 50 rot = 32 blau = 49 zug8(1) = -11 zug8(2) = -10 zug8(3) = -9 zug8(4) = -1 zug8(5) = 1 zug8(6) = +9 zug8(7) = +10 zug8(8) = +11 zugnr = 0 end ! ***************************************************************** ! drucken des Bretts auf Bildschirm (Isola) ! ***************************************************************** subroutine ausgabebrett(brett,rot,blau) implicit none integer brett(80) integer rot,blau,i,j,nr character(len=30) merk print *,'Brett' print *,'------------' !print *,rot,blau !print *,brett nr = 0 do i = 1,8 merk = " " do j = 1,10 nr = nr + 1 if (rot == nr) then merk((j-2)*3+2:(j-2)*3+2) = "R" else if (blau == nr) then merk((j-2)*3+2:(j-2)*3+2) = "B" else if (brett(nr) == 0) then merk((j-2)*3+2:(j-2)*3+2) = "." else if (brett(nr) == 1) then merk((j-2)*3+2:(j-2)*3+2) = "x" endif endif endif endif end do print *,merk end do print *,'------------' ! print *,'rot blau ',rot,blau end !*********** ! rotmatt // ist rot Matt? ! erg = 0 // rot nicht Matt ! erg = 1 // rot ist Matt !*********** subroutine rotmatt(brett,zug8,rot,blau,roterg) implicit none integer brett(80),zug8(8) integer rot,blau,roterg,i,lala roterg = 1 do i = 1,8 lala = rot+zug8(i) if (brett(lala) == 1.and.lala.ne.blau) then roterg = 0 exit endif end do end !*********** ! blaumatt // ist blau Matt? ! erg = 0 // blau nicht Matt ! erg = 1 // blau ist Matt !*********** subroutine blaumatt(brett,zug8,rot,blau,blauerg) implicit none integer brett(80),zug8(8) integer rot,blau,blauerg,i,lala blauerg = 1 do i = 1,8 lala = blau+zug8(i) if (brett(lala) == 1.and.lala.ne.rot) then blauerg = 0 exit endif end do end ! ********** ! berechne Anzahl der Rotfelder (Felder auf die Rot ziehen kann) ! ********** subroutine rotbewegtfelder(brett,zug8,rot,blau,rotfelder) implicit none integer brett(80),zug8(8) integer rot,blau,rotfelder,i,lala rotfelder = 0 do i = 1,8 lala = rot+zug8(i) if (brett(lala) == 1.and.lala.ne.blau) then rotfelder = rotfelder + 1 endif end do end ! ********** ! berechne Anzahl der Blaufelder (Felder auf die Blau ziehen kann) ! ********** subroutine blaubewegtfelder(brett,zug8,rot,blau,blaufelder) implicit none integer brett(80),zug8(8) integer rot,blau,blaufelder,i,lala blaufelder = 0 do i = 1,8 lala = blau+zug8(i) if (brett(lala) == 1.and.lala.ne.rot) then blaufelder = blaufelder + 1 endif end do end ! ********** ! sortiere Zuege aus feld(azzuege) ! feld(i,1) = rotneu ! feld(i,2) = gedrueckt ! feld(i,3) = Bewertung (hoch am besten) ! ********** subroutine sortiere(feld,azzuege) implicit none integer feld(352,3) !,feld2(121088,4) integer i,j,azzuege,merk,merk2 integer lala,lala2,lala3 ! sortiere gesamtes Feld do i = 1,azzuege-1 do j = i+1,azzuege merk = feld(i,3) merk2 = feld(j,3) if (merk < merk2) then ! tausche lala = feld(i,1) lala2 = feld(i,2) lala3 = feld(i,3) !lala4 = feld(i,4) feld(i,1) = feld(j,1) feld(i,2) = feld(j,2) feld(i,3) = feld(j,3) !feld(i,4) = feld(j,4) feld(j,1) = lala feld(j,2) = lala2 feld(j,3) = lala3 !feld(j,4) = lala4 endif end do end do !print *,feld(:,3) !stop end ! ********** ! mische Zuege aus feld(azzuege) ! ********** subroutine mischen(feld,azzuege) implicit none integer feld(352,3) integer i,j,azzuege integer lala,lala2,lala3 real zwi ! mische gesamtes Feld do i = azzuege,1,-1 call random_number(zwi) j = floor(zwi*azzuege)+1 !print *,j,azzuege ! tausche lala = feld(i,1) lala2 = feld(i,2) lala3 = feld(i,3) feld(i,1) = feld(j,1) feld(i,2) = feld(j,2) feld(i,3) = feld(j,3) feld(j,1) = lala feld(j,2) = lala2 feld(j,3) = lala3 end do !do i = 1,azzuege ! print *,i,feld(i,:) !end do !stop end ! ********** ! Zug von Rot ! Strategie 1: Zufall ! Strategie 2: Defensiv ! Strategie 3: Offensiv ! Strategie 4: variabel ! Strategie 5: variabel2 ! Baum Tiefe 1 in feld ! feld(:,1) = rotneu ! feld(:,2) = gedrueckt ! feld(:,3) = Bewertung des Zuges ! ********** subroutine rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,rotstrategie) implicit none integer feld(352,3) ! feld2(352*8*43) integer brett(80),zug8(8),zug(2),zug1(2),feld99(352) integer rot,blau,rotneu,zugnr,rotstrategie,rotmax integer i,j,merk,r integer azzuege,azzuege99,gedrueckt integer max1,bewert real zwi common /isola1/ max1 ! (1) berechne und bewerte Zuege azzuege = 0 !do i = 1,352 ! feld(i,1) = 0 ! feld(i,2) = 0 ! feld(i,3) = 0 !end do do i = 1,8 !print *,'i ',i rotneu = rot+zug8(i) if (brett(rotneu) == 1.and.rotneu.ne.blau) then do j = 12,69 !print *,'j ',j gedrueckt = j if (brett(gedrueckt) == 1.and.rotneu.ne.gedrueckt.and.blau.ne.gedrueckt) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = rotneu feld(azzuege,2) = gedrueckt brett(gedrueckt) = 0 call bewertestellung(brett,zug8,rotstrategie,zugnr,rotneu,blau,bewert) feld(azzuege,3) = bewert ! mache Zug rueckgaengig brett(gedrueckt) = 1 endif end do endif end do if (azzuege > 0) then if (azzuege > max1) then max1 = azzuege endif endif ! (2) jetzt suche besten Zug aus feld von eben rotmax = -1000 azzuege99 = 0 ! finde besten Zug do i = 1,azzuege if (feld(i,3) >= rotmax) then rotmax = feld(i,3) endif end do ! erstelle Liste mit allen besten Zuegen do i = 1,azzuege ! print *,'i feld(i,3) ',i,feld(i,3) if (feld(i,3) == rotmax) then azzuege99 = azzuege99 + 1 feld99(azzuege99) = i ! print *,'rotmax azzuege2 i ',rotmax,azzuege2,i endif end do ! waehle Zug aus if (azzuege99 == 1) then merk = feld99(azzuege99) else call random_number(zwi) r = floor(zwi*azzuege99)+1 merk = feld99(r) endif zug1(1) = feld(merk,1) zug1(2) = feld(merk,2) zug(1) = zug1(1) zug(2) = zug1(2) !rot = zug(1) !brett(zug(2)) = 0 !zugnr = zugnr + 1 !print *,'zugnr ',zugnr end ! ********** ! bewerte die Stellung auf dem Brett bei Strategie 1 bis 5 ! ********** subroutine bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) implicit none integer brett(80),zug8(8) integer rot,blau,rotfelder,blaufelder,rotstrategie,bewert,zugnr,tiefe common /isola7/ tiefe !print *,rot,blau !print *,brett call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) call blaubewegtfelder(brett,zug8,rot,blau,blaufelder) !print *,rotfelder,blaufelder !print *,'rs ',rotstrategie select case (rotstrategie) case (1) bewert = 0 case (2) bewert = 2*rotfelder-blaufelder case (3) bewert = rotfelder-2*blaufelder case (4) if (zugnr < 22) then bewert = 2*rotfelder-blaufelder else bewert = rotfelder-2*blaufelder endif case (5) if (zugnr < 22) then bewert = rotfelder-2*blaufelder else bewert = 2*rotfelder-blaufelder endif !case (6) ! bewert = 3*rotfelder-blaufelder end select bewert = bewert + 20 if (blaufelder == 0) then bewert = 1000 !if (tiefe == 2) then ! bewert = 2000 !endif !if (tiefe == 4) then ! bewert = 3000 !endif !if (tiefe >= 6) then ! bewert = 4000 !endif endif ! endif end ! *********** ! 111 ! Zug von Spieler 1 rot ! *********** subroutine AlphaBetaMax(brett,zug8,zugnr,rot,blau,h,alpha,beta,erg) implicit none integer feld(352,3) integer brett(80),brett2(80),zug8(8),zug99(2) integer value,value2 integer azzuege,erg,zugnr,h integer i,j,rot,blau,rotneu,gedrueckt integer rotfelder integer alpha,beta,strategie,suchtiefe common /isola4/ strategie common /isola5/ suchtiefe common /isola6/ zug99 !common /isola6/ zugnr !maxValue = -9999 !minValue = 9999 !CIRCLE = 1 !CROSS = -1 !print *,'vor bewert h suchtiefe',h,suchtiefe !print *,brett !print *,rot,blau !print *,rotstrategie,rot,blau !print *,h !if (spieler == 1) then ! Spieler 2 call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) if (rotfelder == 0) then erg = -1000 !print *,'Min bewert ',bewert return endif !print *,'nach rotbewegtfelder' ! call blaubewegtfelder(brett,zug8,rot,blau,blaufelder) !print *,'h spieler blaufelder ',h,spieler,blaufelder !call ausgabebrett(brett,rot,blau) ! if (blaufelder == 0) then ! erg = 1000 ! if ((suchtiefe-h) == 2) then ! erg = 2000 ! endif ! if ((suchtiefe-h) == 4) then ! erg = 3000 ! endif ! if ((suchtiefe-h) >= 6) then ! erg = 4000 ! endif !if (h == suchtiefe) then ! return !endif ! endif !else ! geloescht !endif !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) !print *,'nach bewert' !if ((h == (suchtiefe+1))) then ! call bewertestellung(brett,zug8,strategie,zugnr,rot,blau,bewert) ! erg = bewert !print *,'Max bewert ',bewert ! return !endif ! (1) Zuege ermitteln azzuege = 0 !if (spieler == 1) then do i = 1,8 !print *,'i ',i rotneu = rot+zug8(i) if ((brett(rotneu) == 1).and.(rotneu.ne.blau)) then do j = 12,69 !print *,'j ',j gedrueckt = j if ((brett(gedrueckt) == 1).and.(rotneu.ne.gedrueckt).and.(blau.ne.gedrueckt)) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = rotneu feld(azzuege,2) = gedrueckt ! brett(gedrueckt) = 0 !call bewertestellung(brett,zug8,rotstrategie,zugnr,rotneu,blau,bewert) !feld(azzuege,3) = bewert ! mache Zug rueckgaengig !brett(gedrueckt) = 1 endif end do endif end do !else ! geleert !print *,'Zuege ermittelt' !if (spieler == 1) then do i = 1,azzuege feld(i,3) = i end do if (h == 1) then call mischen(feld,azzuege) endif value = alpha !erg = beta do i = 1,azzuege do j = 1,80 brett2(j) = brett(j) end do rotneu = feld(i,1) brett2(feld(i,2)) = 0 zugnr = zugnr + 1 !call Minimax_Value(brett2,h+1,dran,value) !print *,rot,blauneu call AlphaBetaMin(brett2,zug8,zugnr,rotneu,blau,h+1,value,beta,value2) ! value = max(value,value2) !print *,h if (h == 1) then feld(i,3) = value2 !print *,'Max Tiefe 0: i feld ',i,feld(i,1:3) !print *,'alpha beta ',alpha,beta !if (value2 > value) then ! azzuege99 = 1 ! feld99(1,1) = rotneu ! feld99(1,2) = feld(i,2) !else ! azzuege = azzuege + 1 ! feld99(azzuege,1) = rotneu ! feld99(azzuege,2) = feld(i,2) !endif endif zugnr = zugnr - 1 if (value2 > value) then value = value2 if (h == 1) then zug99(1) = rotneu zug99(2) = feld(i,2) endif endif !brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 !if (h > 1) then if (value >= beta) then erg = value !print *,'in Max ',value,i,zugnr brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 return !zug(1) = zug2(1) !zug(2) = zug2(2) endif !endif brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 end do !zugnr = zugnr + 1 erg = value end ! *********** ! 222 ! Zug von Spieler 2 blau ! *********** subroutine AlphaBetaMin(brett,zug8,zugnr,rot,blau,h,alpha,beta,erg) implicit none integer feld(352,2) integer brett(80),brett2(80),zug8(8) integer value,value2 integer azzuege,erg,zugnr,h integer i,j,rot,blau,blauneu,gedrueckt integer bewert,blaufelder integer alpha,beta,strategie,suchtiefe,tiefe common /isola4/ strategie common /isola5/ suchtiefe common /isola7/ tiefe !common /isola6/ zugnr !print *,'(Min) vor bewert: h suchtiefe',h,suchtiefe call blaubewegtfelder(brett,zug8,rot,blau,blaufelder) !print *,'h spieler blaufelder ',h,spieler,blaufelder !call ausgabebrett(brett,rot,blau) if (blaufelder == 0) then erg = 1000 !print *,'st h st-h ',suchtiefe,h,suchtiefe-h !if ((h-suchtiefe) >= 1) then ! erg = 3000 !endif !if ((h-suchtiefe) >= 3) then ! erg = 2000 !endif !if ((h-suchtiefe) >= 5) then ! erg = 1000 !endif !if (h == suchtiefe) then return !endif endif !call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) !if (rotfelder == 0) then ! erg = -1000 !print *,'Min bewert ',bewert ! return !endif !call blaubewegtfelder(brett2,zug8,rot2,blau2,blaufelder) !if (blaufelder == 0) then ! erg = -1000 ! !print *,'Min bewert ',bewert ! return !endif !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) !print *,'nach bewert' if ((h == (suchtiefe+1))) then tiefe = suchtiefe-h call bewertestellung(brett,zug8,strategie,zugnr,rot,blau,bewert) erg = bewert !print *,'Min bewert ',bewert return endif ! (1) Zuege ermitteln azzuege = 0 ! if (spieler == 1) then ! geleert !else do i = 1,8 !print *,'i ',i blauneu = blau+zug8(i) if ((brett(blauneu) == 1).and.(blauneu.ne.rot)) then do j = 12,69 !print *,'j ',j gedrueckt = j if ((brett(gedrueckt) == 1).and.(blauneu.ne.gedrueckt).and.(rot.ne.gedrueckt)) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = blauneu feld(azzuege,2) = gedrueckt !brett(gedrueckt) = 0 !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blauneu,bewert) !feld(azzuege,3) = bewert ! mache Zug rueckgaengig !brett(gedrueckt) = 1 endif end do endif end do !endif !print *,'Zuege ermittelt' !if (spieler == 1) then ! geleert value = beta !erg = alpha do i = 1,azzuege do j = 1,80 brett2(j) = brett(j) end do blauneu = feld(i,1) brett2(feld(i,2)) = 0 zugnr = zugnr + 1 ! call Minimax_Value(brett2,h+1,dran,value) !print *,rotneu,blau call AlphaBetaMax(brett2,zug8,zugnr,rot,blauneu,h+1,alpha,value,value2) value = min(value,value2) !value = max(value,value2) !brett2(feld(i,2)) = 1 zugnr = zugnr - 1 !print *,'Hurz min ',value,value2 !if (h > 2) then if (value <= alpha) then !if (value >= alpha) then erg = value !print *,'in Min ',value,i,zugnr brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 return !zug(1) = zug2(1) !zug(2) = zug2(2) endif !endif brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 end do erg = value !endif end ! *********** ! ! *********** subroutine AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) implicit none integer brett(80),zug8(8),zug(2),zug99(2) integer value integer alpha,beta integer zugnr integer rot,blau common /isola6/ zug99 alpha = -99999 beta = 99999 call AlphaBetaMax(brett,zug8,zugnr,rot,blau,1,alpha,beta,value) zug(1) = zug99(1) zug(2) = zug99(2) !zugnr = zugnr + 1 end ! *********** ! Suche für Tiefe 3 und 5 ! erst Tiefe 1, dann 3, dann ev. 5 ! *********** subroutine IsolaSuche(brett,zug8,rot,blau,zug,zugnr) implicit none integer brett(80),zug8(8),zug(2) integer zugnr,rot,blau,rotalt integer strategie,suchtiefe,merk integer blauerg,blauerg2 common /isola4/ strategie common /isola5/ suchtiefe blauerg = 0 merk = suchtiefe if (merk == 3) then ! Suchtiefe 3 call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,strategie) !print *,'T1: ',zug rotalt = rot rot = zug(1) brett(zug(2)) = 0 call blaumatt(brett,zug8,rot,blau,blauerg) if (blauerg == 0) then brett(zug(2)) = 1 rot = rotalt call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3 ',zug rot = zug(1) brett(zug(2)) = 0 endif zugnr = zugnr + 1 else ! Suchtiefe == 5 call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,strategie) !print *,'T1: ',zug rotalt = rot rot = zug(1) brett(zug(2)) = 0 call blaumatt(brett,zug8,rot,blau,blauerg) if (blauerg == 0) then brett(zug(2)) = 1 rot = rotalt suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3: ',zug suchtiefe = 5 rotalt = rot rot = zug(1) brett(zug(2)) = 0 endif call blaumatt(brett,zug8,rot,blau,blauerg2) if (blauerg2 == 0) then brett(zug(2)) = 1 rot = rotalt call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T5: ',zug rot = zug(1) brett(zug(2)) = 0 endif zugnr = zugnr + 1 endif end \sourceoff \showoff Code für das 5x5 Brett \showon \sourceon Fortran 90 program Isola2023AlphaBetaV15_25 implicit none ! Isola 2023 mit Tiefe 1, 3, 5 (AlphaBeta-Algorithmus) ! ! de.wikipedia.org/wiki/Minimax-Algorithmus ! de.wikipedia.org/wiki/Alpha-Beta-Suche ! Der Alpha-Wert ist das Ergebnis, das Spieler A mindestens erreichen wird, ! der Beta-Wert ist das Ergebnis, das Spieler B höchstens erreichen wird. ! ! mit Alpha-Beta: Isola2023AlphaBetaV15_25 ! 5x5 Brett (im Computer 49 Felder mit Rand) ! ! Rot 2 / T 3 // Blau 2 / T 3 -> Rot 10 von 20 gewonnen / 5,4 Sekunden ! Rot 2 / T 5 // Blau 2 / T 3 -> Rot 18 von 20 gewonnen / 1018,4 Sekunden ! Rot 2 / T 3 // Blau 2 / T 5 -> Rot 5 von 20 gewonnen / 1427,3 Sekunden ! Rot 2 / T 5 // Blau 2 / T 5 -> Rot 14 von 20 gewonnen / 1537,6 Sekunden ! ! Rot 3 / T 3 // Blau 3 / T 3 -> Rot 20 von 20 gewonnen / 2,3 Sekunden ! Rot 3 / T 5 // Blau 3 / T 3 -> Rot 19 von 20 gewonnen / 456,6 Sekunden ! Rot 3 / T 3 // Blau 3 / T 5 -> Rot 17 von 20 gewonnen / 335,5 Sekunden ! Rot 3 / T 5 // Blau 3 / T 5 -> Rot 19 von 20 gewonnen / 686,6 Sekunden ! integer brett(49),brett2(49),zug8(8),zug(2) integer i,j,laeufe,rot,blau,roterg,blauerg,rotstrategie,blaustrategie integer rot2,blau2,zugnr,azspiele,rotgewinn,blaugewinn integer ende,ausgabe,suchtieferot,suchtiefeblau integer max1,strategie,suchtiefe,testen real t0,t1 common /isola1/ max1 common /isola4/ strategie common /isola5/ suchtiefe !common /isola6/ zugnr call cpu_time(t0) call random_seed() laeufe = 1 rotstrategie = 3 suchtieferot = 3 blaustrategie = 3 suchtiefeblau = 3 ausgabe = 1 testen = 0 print *,'rotstrategie ',rotstrategie print *,'suchtieferot ',suchtieferot print *,'blaustrategie ',blaustrategie print *,'suchtiefeblau ',suchtiefeblau print *,' ' rotgewinn = 0 blaugewinn = 0 azspiele = 0 max1 = 0 if (testen > 0) then ! Test 1 call test1(brett,zug8,rot,blau,zugnr) call ausgabebrett(brett,rot,blau) strategie = 3 suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) ! Test 2 call test2(brett,zug8,rot,blau,zugnr) call ausgabebrett(brett,rot,blau) strategie = 3 suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) stop endif DO i = 1,laeufe call init(brett,zug8,rot,blau,zugnr) ende = 0 ! call ausgabebrett(brett,rot,blau) do while (ende == 0) ! while (ende == 0) do call rotmatt(brett,zug8,rot,blau,roterg) if (roterg == 0) then !call ausgabebrett(brett,rot,blau) !stop if (suchtieferot == 1) then call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,rotstrategie) !print *,zug rot = zug(1) brett(zug(2)) = 0 zugnr = zugnr + 1 else strategie = rotstrategie suchtiefe = suchtieferot call IsolaSuche(brett,zug8,rot,blau,zug,zugnr) !print *,'nach Alpha Beta: rot(zug) ',zug !rot = zug(1) !brett(zug(2)) = 0 endif !print *,zug ! print *,zug,rot,blau if (ausgabe == 1) then ! print *,'rotzug ',zug print *,' ' print *,'Zug Spieler 1 (rot) zugnr ',zugnr call ausgabebrett(brett,rot,blau) call cpu_time(t1) print *,'Zeit = ',t1 endif else blaugewinn = blaugewinn + 1 azspiele = azspiele + 1 ende = 1 endif !print *,roterg if (roterg == 0) then ! spiegele Brett do j = 1,49 brett2(j) = brett(50-j) end do rot2 = 50-blau blau2 = 50-rot ! call blaumatt(brett,zug8,rot,blau,blauerg) call rotmatt(brett2,zug8,rot2,blau2,blauerg) if (blauerg == 0) then ! call blauzug(brett,zug8,rot,blau,zug,zugnr,blaustrategie,suchtiefeblau) !print *,suchtiefeblau if (suchtiefeblau == 1) then call rotzugTiefe1(brett2,zug8,rot2,blau2,zug,zugnr,blaustrategie) rot2 = zug(1) brett2(zug(2)) = 0 zugnr = zugnr + 1 else strategie = blaustrategie suchtiefe = suchtiefeblau call IsolaSuche(brett2,zug8,rot2,blau2,zug,zugnr) !print *,'nach Alpha Beta blau(Zug) ',zug !rot2 = zug(1) !brett2(zug(2)) = 0 ! print *,'blau(Zug) ',zug endif ! spiegele Brett do j = 1,49 brett(j) = brett2(50-j) end do rot = 50-blau2 blau = 50-rot2 if (ausgabe == 1) then ! print *,'blauzug ',zug print *,' ' print *,'Zug Spieler 2 (blau) zugnr ',zugnr call ausgabebrett(brett,rot,blau) call cpu_time(t1) print *,'Zeit = ',t1 endif else rotgewinn = rotgewinn + 1 azspiele = azspiele + 1 ende = 1 endif endif end do ! print *,brett end do print *,'rotgewinn ',rotgewinn print *,'blaugewinn ',blaugewinn print *,'von ',azspiele print *,' ' print *,'feldmax 1 ',max1 call cpu_time(t1) print *,'Zeit = ',t1 end ! ********* ! Test 1: Rot am Zug ! ********* subroutine Test1(brett,zug8,rot,blau,zugnr) implicit none integer brett(49),zug8(8) integer i,rot,blau,zugnr DO i = 1,49 brett(i) = 0 ! Plaettchen END DO do i = 1,8 brett(i) = 100 end do do i = 42,49 brett(i) = 100 end do brett(14) = 100 brett(15) = 100 brett(21) = 100 brett(22) = 100 brett(28) = 100 brett(29) = 100 brett(35) = 100 brett(36) = 100 rot = 10 blau = 16 brett(9) = 1 brett(17) = 1 brett(26) = 1 brett(27) = 1 brett(10) = 1 brett(16) = 1 zug8(1) = -8 zug8(2) = -7 zug8(3) = -6 zug8(4) = -1 zug8(5) = 1 zug8(6) = +6 zug8(7) = +7 zug8(8) = +8 zugnr = 0 end ! ********* ! Test 2: Rot am Zug ! x x x x x ! . x . x x ! x . x . . ! x . . . B ! x x R x x ! ********* subroutine Test2(brett,zug8,rot,blau,zugnr) implicit none integer brett(49),zug8(8) integer i,rot,blau,zugnr DO i = 1,49 brett(i) = 0 ! Plaettchen END DO do i = 1,8 brett(i) = 100 end do do i = 42,49 brett(i) = 100 end do brett(14) = 100 brett(15) = 100 brett(21) = 100 brett(22) = 100 brett(28) = 100 brett(29) = 100 brett(35) = 100 brett(36) = 100 rot = 39 blau = 34 brett(34) = 1 brett(37) = 1 brett(38) = 1 brett(39) = 1 brett(40) = 1 brett(41) = 1 zug8(1) = -8 zug8(2) = -7 zug8(3) = -6 zug8(4) = -1 zug8(5) = 1 zug8(6) = +6 zug8(7) = +7 zug8(8) = +8 zugnr = 0 end ! ********** ! Initialiserung ! brett(1..49) = 1 (Plaetchen) oder 100 (Rand) ! rot = 31 // Startfeld ! blau = 49 // Startfeld ! spielzuege // 42x (von,nach,plaetchen gedrueckt aktuell) ! ********** subroutine init(Grundstellung,zug8,rot,blau,zugnr) implicit none integer Grundstellung(49),zug8(8) integer i,rot,blau,zugnr DO i = 1,49 GrundStellung(i) = 1 ! Plaettchen END DO Grundstellung(1) = 100 Grundstellung(2) = 100 Grundstellung(3) = 100 Grundstellung(4) = 100 Grundstellung(5) = 100 Grundstellung(6) = 100 Grundstellung(7) = 100 Grundstellung(8) = 100 Grundstellung(14) = 100 Grundstellung(15) = 100 Grundstellung(21) = 100 Grundstellung(22) = 100 Grundstellung(28) = 100 Grundstellung(29) = 100 Grundstellung(35) = 100 Grundstellung(36) = 100 Grundstellung(42) = 100 Grundstellung(43) = 100 Grundstellung(44) = 100 Grundstellung(45) = 100 Grundstellung(46) = 100 Grundstellung(47) = 100 Grundstellung(48) = 100 Grundstellung(49) = 100 ! spaeter vielleicht mit 2 fixen Feldern (Isola Original) !Grundstellung(31) = 50 !Grundstellung(49) = 50 rot = 23 blau = 27 zug8(1) = -8 zug8(2) = -7 zug8(3) = -6 zug8(4) = -1 zug8(5) = 1 zug8(6) = +6 zug8(7) = +7 zug8(8) = +8 zugnr = 0 end ! ***************************************************************** ! drucken des Bretts auf Bildschirm (Isola) ! ***************************************************************** subroutine ausgabebrett(brett,rot,blau) implicit none integer brett(49) integer rot,blau,i,j,nr character(len=30) merk print *,'Brett' print *,'------------' !print *,rot,blau !print *,brett nr = 0 do i = 1,7 merk = " " do j = 1,7 nr = nr + 1 if (rot == nr) then merk((j-2)*3+2:(j-2)*3+2) = "R" else if (blau == nr) then merk((j-2)*3+2:(j-2)*3+2) = "B" else if (brett(nr) == 0) then merk((j-2)*3+2:(j-2)*3+2) = "." else if (brett(nr) == 1) then merk((j-2)*3+2:(j-2)*3+2) = "x" endif endif endif endif end do print *,merk end do print *,'------------' ! print *,'rot blau ',rot,blau end !*********** ! rotmatt // ist rot Matt? ! erg = 0 // rot nicht Matt ! erg = 1 // rot ist Matt !*********** subroutine rotmatt(brett,zug8,rot,blau,roterg) implicit none integer brett(49),zug8(8) integer rot,blau,roterg,i,lala roterg = 1 do i = 1,8 lala = rot+zug8(i) if (brett(lala) == 1.and.lala.ne.blau) then roterg = 0 exit endif end do end !*********** ! blaumatt // ist blau Matt? ! erg = 0 // blau nicht Matt ! erg = 1 // blau ist Matt !*********** subroutine blaumatt(brett,zug8,rot,blau,blauerg) implicit none integer brett(49),zug8(8) integer rot,blau,blauerg,i,lala blauerg = 1 do i = 1,8 lala = blau+zug8(i) if (brett(lala) == 1.and.lala.ne.rot) then blauerg = 0 exit endif end do end ! ********** ! berechne Anzahl der Rotfelder (Felder auf die Rot ziehen kann) ! ********** subroutine rotbewegtfelder(brett,zug8,rot,blau,rotfelder) implicit none integer brett(49),zug8(8) integer rot,blau,rotfelder,i,lala rotfelder = 0 do i = 1,8 lala = rot+zug8(i) if (brett(lala) == 1.and.lala.ne.blau) then rotfelder = rotfelder + 1 endif end do end ! ********** ! berechne Anzahl der Blaufelder (Felder auf die Blau ziehen kann) ! ********** subroutine blaubewegtfelder(brett,zug8,rot,blau,blaufelder) implicit none integer brett(49),zug8(8) integer rot,blau,blaufelder,i,lala blaufelder = 0 do i = 1,8 lala = blau+zug8(i) if (brett(lala) == 1.and.lala.ne.rot) then blaufelder = blaufelder + 1 endif end do end ! ********** ! sortiere Zuege aus feld(azzuege) ! feld(i,1) = rotneu ! feld(i,2) = gedrueckt ! feld(i,3) = Bewertung (hoch am besten) ! ********** subroutine sortiere(feld,azzuege) implicit none integer feld(352,3) !,feld2(121088,4) integer i,j,azzuege,merk,merk2 integer lala,lala2,lala3 ! sortiere gesamtes Feld do i = 1,azzuege-1 do j = i+1,azzuege merk = feld(i,3) merk2 = feld(j,3) if (merk < merk2) then ! tausche lala = feld(i,1) lala2 = feld(i,2) lala3 = feld(i,3) !lala4 = feld(i,4) feld(i,1) = feld(j,1) feld(i,2) = feld(j,2) feld(i,3) = feld(j,3) !feld(i,4) = feld(j,4) feld(j,1) = lala feld(j,2) = lala2 feld(j,3) = lala3 !feld(j,4) = lala4 endif end do end do !print *,feld(:,3) !stop end ! ********** ! mische Zuege aus feld(azzuege) ! ********** subroutine mischen(feld,azzuege) implicit none integer feld(352,3) integer i,j,azzuege integer lala,lala2,lala3 real zwi ! mische gesamtes Feld do i = azzuege,1,-1 call random_number(zwi) j = floor(zwi*azzuege)+1 !print *,j,azzuege ! tausche lala = feld(i,1) lala2 = feld(i,2) lala3 = feld(i,3) feld(i,1) = feld(j,1) feld(i,2) = feld(j,2) feld(i,3) = feld(j,3) feld(j,1) = lala feld(j,2) = lala2 feld(j,3) = lala3 end do !do i = 1,azzuege ! print *,i,feld(i,:) !end do !stop end ! ********** ! Zug von Rot ! Strategie 1: Zufall ! Strategie 2: Defensiv ! Strategie 3: Offensiv ! Strategie 4: variabel ! Strategie 5: variabel2 ! Baum Tiefe 1 in feld ! feld(:,1) = rotneu ! feld(:,2) = gedrueckt ! feld(:,3) = Bewertung des Zuges ! ********** subroutine rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,rotstrategie) implicit none integer feld(352,3) ! feld2(352*8*43) integer brett(49),zug8(8),zug(2),zug1(2),feld99(352) integer rot,blau,rotneu,zugnr,rotstrategie,rotmax integer i,j,merk,r integer azzuege,azzuege99,gedrueckt integer max1,bewert real zwi common /isola1/ max1 ! (1) berechne und bewerte Zuege azzuege = 0 !do i = 1,352 ! feld(i,1) = 0 ! feld(i,2) = 0 ! feld(i,3) = 0 !end do do i = 1,8 !print *,'i ',i rotneu = rot+zug8(i) if (brett(rotneu) == 1.and.rotneu.ne.blau) then do j = 9,41 !print *,'j ',j gedrueckt = j if (brett(gedrueckt) == 1.and.rotneu.ne.gedrueckt.and.blau.ne.gedrueckt) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = rotneu feld(azzuege,2) = gedrueckt brett(gedrueckt) = 0 call bewertestellung(brett,zug8,rotstrategie,zugnr,rotneu,blau,bewert) feld(azzuege,3) = bewert ! mache Zug rueckgaengig brett(gedrueckt) = 1 endif end do endif end do if (azzuege > 0) then if (azzuege > max1) then max1 = azzuege endif endif ! (2) jetzt suche besten Zug aus feld von eben rotmax = -1000 azzuege99 = 0 ! finde besten Zug do i = 1,azzuege if (feld(i,3) >= rotmax) then rotmax = feld(i,3) endif end do ! erstelle Liste mit allen besten Zuegen do i = 1,azzuege ! print *,'i feld(i,3) ',i,feld(i,3) if (feld(i,3) == rotmax) then azzuege99 = azzuege99 + 1 feld99(azzuege99) = i ! print *,'rotmax azzuege2 i ',rotmax,azzuege2,i endif end do ! waehle Zug aus if (azzuege99 == 1) then merk = feld99(azzuege99) else call random_number(zwi) r = floor(zwi*azzuege99)+1 merk = feld99(r) endif zug1(1) = feld(merk,1) zug1(2) = feld(merk,2) zug(1) = zug1(1) zug(2) = zug1(2) !rot = zug(1) !brett(zug(2)) = 0 !zugnr = zugnr + 1 !print *,'zugnr ',zugnr end ! ********** ! bewerte die Stellung auf dem Brett bei Strategie 1 bis 5 ! ********** subroutine bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) implicit none integer brett(49),zug8(8) integer rot,blau,rotfelder,blaufelder,rotstrategie,bewert,zugnr,tiefe common /isola7/ tiefe !print *,rot,blau !print *,brett call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) call blaubewegtfelder(brett,zug8,rot,blau,blaufelder) !print *,rotfelder,blaufelder !print *,'rs ',rotstrategie select case (rotstrategie) case (1) bewert = 0 case (2) bewert = 2*rotfelder-blaufelder case (3) bewert = rotfelder-2*blaufelder case (4) if (zugnr < 12) then bewert = 2*rotfelder-blaufelder else bewert = rotfelder-2*blaufelder endif case (5) if (zugnr < 12) then bewert = rotfelder-2*blaufelder else bewert = 2*rotfelder-blaufelder endif !case (6) ! bewert = 3*rotfelder-blaufelder end select bewert = bewert + 20 if (blaufelder == 0) then bewert = 1000 !if (tiefe == 2) then ! bewert = 2000 !endif !if (tiefe == 4) then ! bewert = 3000 !endif !if (tiefe >= 6) then ! bewert = 4000 !endif endif ! endif end ! *********** ! 111 ! Zug von Spieler 1 rot ! *********** subroutine AlphaBetaMax(brett,zug8,zugnr,rot,blau,h,alpha,beta,erg) implicit none integer feld(352,3) integer brett(49),brett2(49),zug8(8),zug99(2) integer value,value2 integer azzuege,erg,zugnr,h integer i,j,rot,blau,rotneu,gedrueckt integer rotfelder integer alpha,beta,strategie,suchtiefe common /isola4/ strategie common /isola5/ suchtiefe common /isola6/ zug99 !common /isola6/ zugnr !maxValue = -9999 !minValue = 9999 !CIRCLE = 1 !CROSS = -1 !print *,'vor bewert h suchtiefe',h,suchtiefe !print *,brett !print *,rot,blau !print *,rotstrategie,rot,blau !print *,h !if (spieler == 1) then ! Spieler 2 call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) if (rotfelder == 0) then erg = -1000 !print *,'Min bewert ',bewert return endif !print *,'nach rotbewegtfelder' ! call blaubewegtfelder(brett,zug8,rot,blau,blaufelder) !print *,'h spieler blaufelder ',h,spieler,blaufelder !call ausgabebrett(brett,rot,blau) ! if (blaufelder == 0) then ! erg = 1000 ! if ((suchtiefe-h) == 2) then ! erg = 2000 ! endif ! if ((suchtiefe-h) == 4) then ! erg = 3000 ! endif ! if ((suchtiefe-h) >= 6) then ! erg = 4000 ! endif !if (h == suchtiefe) then ! return !endif ! endif !else ! geloescht !endif !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) !print *,'nach bewert' !if ((h == (suchtiefe+1))) then ! call bewertestellung(brett,zug8,strategie,zugnr,rot,blau,bewert) ! erg = bewert !print *,'Max bewert ',bewert ! return !endif ! (1) Zuege ermitteln azzuege = 0 !if (spieler == 1) then do i = 1,8 !print *,'i ',i rotneu = rot+zug8(i) if ((brett(rotneu) == 1).and.(rotneu.ne.blau)) then do j = 9,41 !print *,'j ',j gedrueckt = j if ((brett(gedrueckt) == 1).and.(rotneu.ne.gedrueckt).and.(blau.ne.gedrueckt)) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = rotneu feld(azzuege,2) = gedrueckt ! brett(gedrueckt) = 0 !call bewertestellung(brett,zug8,rotstrategie,zugnr,rotneu,blau,bewert) !feld(azzuege,3) = bewert ! mache Zug rueckgaengig !brett(gedrueckt) = 1 endif end do endif end do !else ! geleert !print *,'Zuege ermittelt' !if (spieler == 1) then do i = 1,azzuege feld(i,3) = i end do if (h == 1) then call mischen(feld,azzuege) endif value = alpha !erg = beta do i = 1,azzuege do j = 1,49 brett2(j) = brett(j) end do rotneu = feld(i,1) brett2(feld(i,2)) = 0 zugnr = zugnr + 1 !call Minimax_Value(brett2,h+1,dran,value) !print *,rot,blauneu call AlphaBetaMin(brett2,zug8,zugnr,rotneu,blau,h+1,value,beta,value2) ! value = max(value,value2) !print *,h if (h == 1) then feld(i,3) = value2 !print *,'Max Tiefe 0: i feld ',i,feld(i,1:3) !print *,'alpha beta ',alpha,beta !if (value2 > value) then ! azzuege99 = 1 ! feld99(1,1) = rotneu ! feld99(1,2) = feld(i,2) !else ! azzuege = azzuege + 1 ! feld99(azzuege,1) = rotneu ! feld99(azzuege,2) = feld(i,2) !endif endif zugnr = zugnr - 1 if (value2 > value) then value = value2 if (h == 1) then zug99(1) = rotneu zug99(2) = feld(i,2) endif endif !brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 !if (h > 1) then if (value >= beta) then erg = value !print *,'in Max ',value,i,zugnr brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 return !zug(1) = zug2(1) !zug(2) = zug2(2) endif !endif brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 end do !zugnr = zugnr + 1 erg = value end ! *********** ! 222 ! Zug von Spieler 2 blau ! *********** subroutine AlphaBetaMin(brett,zug8,zugnr,rot,blau,h,alpha,beta,erg) implicit none integer feld(352,2) integer brett(49),brett2(49),zug8(8) integer value,value2 integer azzuege,erg,zugnr,h integer i,j,rot,blau,blauneu,gedrueckt integer bewert,blaufelder integer alpha,beta,strategie,suchtiefe,tiefe common /isola4/ strategie common /isola5/ suchtiefe common /isola7/ tiefe !common /isola6/ zugnr !print *,'(Min) vor bewert: h suchtiefe',h,suchtiefe call blaubewegtfelder(brett,zug8,rot,blau,blaufelder) !print *,'h spieler blaufelder ',h,spieler,blaufelder !call ausgabebrett(brett,rot,blau) if (blaufelder == 0) then erg = 1000 !print *,'st h st-h ',suchtiefe,h,suchtiefe-h !if ((h-suchtiefe) >= 1) then ! erg = 3000 !endif !if ((h-suchtiefe) >= 3) then ! erg = 2000 !endif !if ((h-suchtiefe) >= 5) then ! erg = 1000 !endif !if (h == suchtiefe) then return !endif endif !call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) !if (rotfelder == 0) then ! erg = -1000 !print *,'Min bewert ',bewert ! return !endif !call blaubewegtfelder(brett2,zug8,rot2,blau2,blaufelder) !if (blaufelder == 0) then ! erg = -1000 ! !print *,'Min bewert ',bewert ! return !endif !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) !print *,'nach bewert' if ((h == (suchtiefe+1))) then tiefe = suchtiefe-h call bewertestellung(brett,zug8,strategie,zugnr,rot,blau,bewert) erg = bewert !print *,'Min bewert ',bewert return endif ! (1) Zuege ermitteln azzuege = 0 ! if (spieler == 1) then ! geleert !else do i = 1,8 !print *,'i ',i blauneu = blau+zug8(i) if ((brett(blauneu) == 1).and.(blauneu.ne.rot)) then do j = 9,41 !print *,'j ',j gedrueckt = j if ((brett(gedrueckt) == 1).and.(blauneu.ne.gedrueckt).and.(rot.ne.gedrueckt)) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = blauneu feld(azzuege,2) = gedrueckt !brett(gedrueckt) = 0 !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blauneu,bewert) !feld(azzuege,3) = bewert ! mache Zug rueckgaengig !brett(gedrueckt) = 1 endif end do endif end do !endif !print *,'Zuege ermittelt' !if (spieler == 1) then ! geleert value = beta !erg = alpha do i = 1,azzuege do j = 1,49 brett2(j) = brett(j) end do blauneu = feld(i,1) brett2(feld(i,2)) = 0 zugnr = zugnr + 1 ! call Minimax_Value(brett2,h+1,dran,value) !print *,rotneu,blau call AlphaBetaMax(brett2,zug8,zugnr,rot,blauneu,h+1,alpha,value,value2) value = min(value,value2) !value = max(value,value2) !brett2(feld(i,2)) = 1 zugnr = zugnr - 1 !print *,'Hurz min ',value,value2 !if (h > 2) then if (value <= alpha) then !if (value >= alpha) then erg = value !print *,'in Min ',value,i,zugnr brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 return !zug(1) = zug2(1) !zug(2) = zug2(2) endif !endif brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 end do erg = value !endif end ! *********** ! ! *********** subroutine AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) implicit none integer brett(49),zug8(8),zug(2),zug99(2) integer value integer alpha,beta integer zugnr integer rot,blau common /isola6/ zug99 alpha = -99999 beta = 99999 call AlphaBetaMax(brett,zug8,zugnr,rot,blau,1,alpha,beta,value) zug(1) = zug99(1) zug(2) = zug99(2) !zugnr = zugnr + 1 end ! *********** ! Suche für Tiefe 3 und 5 ! erst Tiefe 1, dann 3, dann ev. 5 ! *********** subroutine IsolaSuche(brett,zug8,rot,blau,zug,zugnr) implicit none integer brett(49),zug8(8),zug(2) integer zugnr,rot,blau,rotalt integer strategie,suchtiefe,merk integer blauerg,blauerg2 common /isola4/ strategie common /isola5/ suchtiefe blauerg = 0 merk = suchtiefe if (merk == 3) then ! Suchtiefe 3 call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,strategie) !print *,'T1: ',zug rotalt = rot rot = zug(1) brett(zug(2)) = 0 call blaumatt(brett,zug8,rot,blau,blauerg) if (blauerg == 0) then brett(zug(2)) = 1 rot = rotalt call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3 ',zug rot = zug(1) brett(zug(2)) = 0 endif zugnr = zugnr + 1 else ! Suchtiefe == 5 call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,strategie) !print *,'T1: ',zug rotalt = rot rot = zug(1) brett(zug(2)) = 0 call blaumatt(brett,zug8,rot,blau,blauerg) if (blauerg == 0) then brett(zug(2)) = 1 rot = rotalt suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3: ',zug suchtiefe = 5 rotalt = rot rot = zug(1) brett(zug(2)) = 0 endif call blaumatt(brett,zug8,rot,blau,blauerg2) if (blauerg2 == 0) then brett(zug(2)) = 1 rot = rotalt call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T5: ',zug rot = zug(1) brett(zug(2)) = 0 endif zugnr = zugnr + 1 endif end \sourceoff \showoff [Edit] Literatur und Ausblick Literatur: - Steinwender/Friedel // "Schach am PC" // Markt und Technik // 1995 darin Informationen zu Alpha-Beta-Suche und viele Ideen für Schach und Spiele. - Reinefeld // "Spielbaum Suchverfahren" // Springer // 1989 darin der von mir verwendete Alpha-Beta-Algortihmus - Henrique de Figueiredo // "Lua Programming Gems" // Lua.org // 2008 darin ein von mir auch verwendeter Minimax-Algorithmus - Brainerd/Goldberg/Adams // "Fortran 90" // Oldenbourg // 1994 Ausblick: (a) Für Suchtiefe 5 verwende ich bisher: - berechne Züge für Tiefe 1, falls kein Matt, berechne Züge für Tiefe 3, falls kein Matt, berechne Züge für Tiefe 5 Dabei wird aber die Information geringerer Tiefen bisher nicht für höhere Tiefen verwendet. (Bild 5: aus Wikipedia - Minimax, Alpha Beta und Verbesserungen bei einer Schach-Stellung, bei Isola bin ich momentan in der mittleren Zeile) (b) Alpha Beta sollte sich noch beschleunigen lassen durch eine geschickte Sortierung der Züge bei der Berechnung. (c) die Bewertung könnte noch verbessert werden. (d) bisher habe ich keine Zugliste mit gleich guten Zügen z.B. in Tiefe 5. Um eine zufällige Auswahl von z.B 3 gleichguten Zügen mit z.B. bewert = 20 zu finden, wird die Auswahl der Züge in Tiefe 1 vor der Berechnung zufällig durchgeführt. (e) es ist mein erster Versuch mit MiniMax-Suche und Alpha-Beta-Suche. Da fehlt mir noch die Erfahrung. Danke fürs Lesen sagt Ronald [Edit] \(\endgroup\) [Show outline only] Get link to this article   Printer-friendly version -  Choose languageDE EN     Comments   Für diesen Artikel gibt es keine pdf-Datei Write a comment Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen. [Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

Re: das Spiel Isola Teil 3: der Alpha-Beta Ansatz zur Zugsuche - ein Zwischenstand von: Delastelle am: Mi. 22. Februar 2023 14:55:28

\(\begingroup\)Hallo, zur Beschleunigung der Programme. Benutze jetzt für Tiefe 5 die Information der Tiefe 3. Laufzeit 8x6 Brett: (a) 3(5) vs 3(3) -> 20x = 18035,1 Sekunden (100 % Rechnenzeit) (b) mit Hauptvariante. Dazu berechne in Tiefe 3 3x und speichere die 3 Züge dann Tiefe 5: in Tiefe 1 bewege die 3 gespeicherten Züge auf Position 1 bis 3 bei den Zügen vor der Berechnung 3(5) vs 3(3) mit hv 3x -> 20x = 13197,1 Sekunden (73,1 % Rechenzeit) (c) setzte bewert = bewert + 20 in Kommentare (auch ohne diese Verschiebung geht Programm -> "schnell") 2. compiliere mit optimise ftn95 -optimise -link Programm Programm.f90 3(5) vs 3(3) mit hv 3x schnell optim -> 20x = 5522,4 Sekunden (30,6 % Rechenzeit) Dazu muss der Code nur in 2 Routinen geändert werden: \showon \sourceon Fortran 90 ! *********** ! 111 ! Zug von Spieler 1 rot ! *********** subroutine AlphaBetaMax(brett,zug8,zugnr,rot,blau,h,alpha,beta,erg) implicit none integer feld(352,3) integer brett(80),brett2(80),zug8(8),zug99(2) integer hauptvariante(2),hauptvariante2(2),hauptvariante3(2) integer value,value2 integer azzuege,erg,zugnr,h integer i,j,rot,blau,rotneu,gedrueckt integer rotfelder,lala1,lala2 integer alpha,beta,strategie,suchtiefe common /isola4/ strategie common /isola5/ suchtiefe common /isola6/ zug99 common /isola8/ hauptvariante common /isola9/ hauptvariante2 common /isola10/ hauptvariante3 !common /isola6/ zugnr !maxValue = -9999 !minValue = 9999 !CIRCLE = 1 !CROSS = -1 !print *,'vor bewert h suchtiefe',h,suchtiefe !print *,brett !print *,rot,blau !print *,rotstrategie,rot,blau !print *,h !if (spieler == 1) then ! Spieler 2 call rotbewegtfelder(brett,zug8,rot,blau,rotfelder) if (rotfelder == 0) then erg = -1000 !print *,'Min bewert ',bewert return endif !print *,'nach rotbewegtfelder' !else ! geloescht !endif !call bewertestellung(brett,zug8,rotstrategie,zugnr,rot,blau,bewert) !print *,'nach bewert' !if ((h == (suchtiefe+1))) then ! call bewertestellung(brett,zug8,strategie,zugnr,rot,blau,bewert) ! erg = bewert !print *,'Max bewert ',bewert ! return !endif ! (1) Zuege ermitteln azzuege = 0 !if (spieler == 1) then do i = 1,8 !print *,'i ',i rotneu = rot+zug8(i) if ((brett(rotneu) == 1).and.(rotneu.ne.blau)) then do j = 12,69 !print *,'j ',j gedrueckt = j if ((brett(gedrueckt) == 1).and.(rotneu.ne.gedrueckt).and.(blau.ne.gedrueckt)) then ! zug zulaessig azzuege = azzuege + 1 feld(azzuege,1) = rotneu feld(azzuege,2) = gedrueckt ! brett(gedrueckt) = 0 !call bewertestellung(brett,zug8,rotstrategie,zugnr,rotneu,blau,bewert) !feld(azzuege,3) = bewert ! mache Zug rueckgaengig !brett(gedrueckt) = 1 endif end do endif end do !else ! geleert !print *,'Zuege ermittelt' !if (spieler == 1) then do i = 1,azzuege feld(i,3) = i end do if (h == 1) then call mischen(feld,azzuege) if (suchtiefe == 5) then do i = 2,azzuege if ((feld(i,1) == hauptvariante(1)).and.(feld(i,2) == hauptvariante(2))) then ! tausche nach vorne lala1 = feld(1,1) lala2 = feld(1,2) feld(1,1) = hauptvariante(1) feld(1,2) = hauptvariante(2) feld(i,1) = lala1 feld(i,2) = lala2 endif end do do i = 3,azzuege if ((feld(i,1) == hauptvariante2(1)).and.(feld(i,2) == hauptvariante2(2))) then ! tausche nach vorne lala1 = feld(2,1) lala2 = feld(2,2) feld(2,1) = hauptvariante2(1) feld(2,2) = hauptvariante2(2) feld(i,1) = lala1 feld(i,2) = lala2 endif end do do i = 4,azzuege if ((feld(i,1) == hauptvariante3(1)).and.(feld(i,2) == hauptvariante3(2))) then ! tausche nach vorne lala1 = feld(3,1) lala2 = feld(3,2) feld(3,1) = hauptvariante3(1) feld(3,2) = hauptvariante3(2) feld(i,1) = lala1 feld(i,2) = lala2 endif end do endif endif value = alpha !erg = beta do i = 1,azzuege do j = 1,80 brett2(j) = brett(j) end do rotneu = feld(i,1) brett2(feld(i,2)) = 0 zugnr = zugnr + 1 !call Minimax_Value(brett2,h+1,dran,value) !print *,rot,blauneu call AlphaBetaMin(brett2,zug8,zugnr,rotneu,blau,h+1,value,beta,value2) ! value = max(value,value2) !print *,h if (h == 1) then feld(i,3) = value2 !print *,'Max Tiefe 0: i feld ',i,feld(i,1:3) !print *,'alpha beta ',alpha,beta !if (value2 > value) then ! azzuege99 = 1 ! feld99(1,1) = rotneu ! feld99(1,2) = feld(i,2) !else ! azzuege = azzuege + 1 ! feld99(azzuege,1) = rotneu ! feld99(azzuege,2) = feld(i,2) !endif endif zugnr = zugnr - 1 if (value2 > value) then value = value2 if (h == 1) then zug99(1) = rotneu zug99(2) = feld(i,2) endif endif !brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 !if (h > 1) then if (value >= beta) then erg = value !print *,'in Max ',value,i,zugnr brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 return !zug(1) = zug2(1) !zug(2) = zug2(2) endif !endif brett2(feld(i,2)) = 1 !zugnr = zugnr - 1 end do !zugnr = zugnr + 1 erg = value end \sourceoff und \sourceon Fortran 90 ! *********** ! Suche für Tiefe 3 und 5 ! erst Tiefe 1, dann 3, dann ev. 5 ! *********** subroutine IsolaSuche(brett,zug8,rot,blau,zug,zugnr) implicit none integer brett(80),zug8(8),zug(2),hauptvariante(2),hauptvariante2(2),hauptvariante3(2) integer zugnr,rot,blau,rotalt integer strategie,suchtiefe,merk integer blauerg,blauerg2 common /isola4/ strategie common /isola5/ suchtiefe common /isola8/ hauptvariante common /isola9/ hauptvariante2 common /isola10/ hauptvariante3 blauerg = 0 merk = suchtiefe if (merk == 3) then ! Suchtiefe 3 call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,strategie) !print *,'T1: ',zug rotalt = rot rot = zug(1) brett(zug(2)) = 0 call blaumatt(brett,zug8,rot,blau,blauerg) if (blauerg == 0) then brett(zug(2)) = 1 rot = rotalt call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3 ',zug rot = zug(1) brett(zug(2)) = 0 endif zugnr = zugnr + 1 else ! Suchtiefe == 5 call rotzugTiefe1(brett,zug8,rot,blau,zug,zugnr,strategie) !print *,'T1: ',zug rotalt = rot rot = zug(1) brett(zug(2)) = 0 call blaumatt(brett,zug8,rot,blau,blauerg) if (blauerg == 0) then brett(zug(2)) = 1 rot = rotalt suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3: ',zug suchtiefe = 5 rotalt = rot rot = zug(1) brett(zug(2)) = 0 hauptvariante(1) = rot hauptvariante(2) = zug(2) brett(zug(2)) = 1 rot = rotalt suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3: ',zug suchtiefe = 5 rotalt = rot rot = zug(1) brett(zug(2)) = 0 hauptvariante2(1) = rot hauptvariante2(2) = zug(2) brett(zug(2)) = 1 rot = rotalt suchtiefe = 3 call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T3: ',zug suchtiefe = 5 rotalt = rot rot = zug(1) brett(zug(2)) = 0 hauptvariante3(1) = rot hauptvariante3(2) = zug(2) endif call blaumatt(brett,zug8,rot,blau,blauerg2) if (blauerg2 == 0) then brett(zug(2)) = 1 rot = rotalt call AlphaBetaHauptprogramm(brett,zug8,rot,blau,zug,zugnr) !print *,'T5: ',zug rot = zug(1) brett(zug(2)) = 0 endif zugnr = zugnr + 1 endif end \sourceoff \showoff Viele Grüße Ronald \(\endgroup\)