das Spiel Isola Teil 3: der Alpha-Beta Ansatz zur Zugsuche - ein Zwischenstand
Von: Delastelle
Datum: Fr. 17. Februar 2023 22:38:47
Thema: Spiele+Rätsel
| 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. 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)
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)
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
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
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
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
|
|
