Veränderung eines MiniMax- Algorithmus zur Alpha-Beta-Suche

Status
Nicht offen für weitere Antworten.
T

Tequila82

Gast
Hi,

ich habe einen Minimax algorithmus implementiert nach Wikipedia Pseudocode. Jetzt will ich den bestehenden code in eine Alpha-Beta-Suche (Alpha-Beta-Pruning) umwandeln.


Hier der original Minimax:

Code:
/**
	 * Die Method (max) search for the best next step with the MiniMax-Algorithmus
	 * @param board - Das Spielfeld
	 * @param restTiefe - die restliche Tiefe
	 * @param suchTiefe - die gewünschte Suchtiefe
	 * @return - der ermittelte Zugwert
	 */
	private int maxWert(int restTiefe, int alpha, int beta) {
		int ermittelt = 0;
		int zugWert = 0;
		int counter = 0;
		
		if(id==1) {
			int oppId = 4;
		} else {
			int oppID = 1;
		}	
		
		ermittelt= Integer.MIN_VALUE;
		
		for(int i=0; i<cols; i++) {
			counter = 0;
			if(board.isValidMove(i)) {
				
				board.move(i,id);		
				
				if(restTiefe<=1 || board.isFull()) { 
					for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
						if(board.isOccupied(ii,i)) {									
							counter++;
						} else {
							zugWert = countPoints(i, counter, id);
							break;
						}
						
					}
				}
				else {
					zugWert = minWert(restTiefe-1,alpha,beta);
					
				}
					
				board.unmove(i,id);
				
				if(zugWert>ermittelt) {
					ermittelt = zugWert;
					
					if(restTiefe == suchTiefe) {
						
						if(board.isValidMove(i)) {
							nextMove = i;
						}
					}
				}
			}
		}
		return ermittelt;
	}
	
	
	/**
	 * Die Method for the best result --> (min) of the MiniMax-Algorithmus
	 * @param board - Das Spielfeld
	 * @param restTiefe - die restliche Tiefe
	 * @param suchTiefe - die gewünschte Suchtiefe
	 * @return - der ermittelte Zugwert
	 */
	private int minWert(int restTiefe, int alpha, int beta) {
		int ermittelt = 0; 
		int zugWert = 0;
		int counter = 0;
		
		ermittelt = Integer.MAX_VALUE;
		
		//cols
		for(int i=0; i<cols; i++){
			counter=0;
			if(board.isValidMove(i)) {	
				
				board.move(i,oppId);
				    
				if(restTiefe<=1 || board.isFull()) { 
					for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
						if(board.isOccupied(ii,i)) {
							counter++;
						} else {
							zugWert = -countPoints(i, counter, oppId);
							break;
						}						
					}
				}
				else {
					zugWert = maxWert(restTiefe-1,alpha,beta);
				}
								
				board.unmove(i,oppId);
				
				if(zugWert<ermittelt) {
					ermittelt = zugWert;
				}
			}
		}
		return ermittelt;
	}




Und hier mein Versuch, ihn umzuwandeln:

Code:
         /**
	 * Die Method (max) search for the best next step with the MiniMax-Algorithmus
	 * @param board - Das Spielfeld
	 * @param restTiefe - die restliche Tiefe
	 * @param suchTiefe - die gewünschte Suchtiefe
	 * @return - der ermittelte Zugwert
	 */
	private int maxWert(int restTiefe, int alpha, int beta) {
		int ermittelt = 0;
		int zugWert = 0;
		int counter = 0;
		
		if(id==1) {
			int oppId = 4;
		} else {
			int oppID = 1;
		}	
		
		ermittelt= Integer.MIN_VALUE;
		
		for(int i=0; i<cols; i++) {
			counter = 0;
			if(board.isValidMove(i)) {
				
				board.move(i,id);		
				
				if(restTiefe<=1 || board.isFull()) { 
					for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
						if(board.isOccupied(ii,i)) {									
							counter++;
						} else {
							zugWert = countPoints(i, counter, id);
							break;
						}
						
					}
				}
				else {
					zugWert = minWert(restTiefe-1,alpha,beta);
					
				}
					
				board.unmove(i,id);
				


                                //WURDE HINZUGEFÜGT
				if (zugWert >= beta)
		                    return beta;
				
				if(zugWert>ermittelt) {
					ermittelt = zugWert;
					
					if(restTiefe == suchTiefe) {
						
						if(board.isValidMove(i)) {
							nextMove = i;
						}
					}
				}
			}
		}
		return ermittelt;
	}
	
	
	/**
	 * Die Method for the best result --> (min) of the MiniMax-Algorithmus
	 * @param board - Das Spielfeld
	 * @param restTiefe - die restliche Tiefe
	 * @param suchTiefe - die gewünschte Suchtiefe
	 * @return - der ermittelte Zugwert
	 */
	private int minWert(int restTiefe, int alpha, int beta) {
		int ermittelt = 0; 
		int zugWert = 0;
		int counter = 0;
		
		ermittelt = Integer.MAX_VALUE;
		
		//cols
		for(int i=0; i<cols; i++){
			counter=0;
			if(board.isValidMove(i)) {	
				
				board.move(i,oppId);
				    
				if(restTiefe<=1 || board.isFull()) { 
					for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
						if(board.isOccupied(ii,i)) {
							counter++;
						} else {
							zugWert = -countPoints(i, counter, oppId);
							break;
						}						
					}
				}
				else {
					zugWert = maxWert(restTiefe-1,alpha,beta);
				}
								
				board.unmove(i,oppId);
				

                                //WURDE HINZUGEFÜGT
				if (zugWert <= alpha)
		                    return alpha;
                                
				
				if(zugWert<ermittelt) {
					ermittelt = zugWert;
				}
			}
		}
		return ermittelt;
	}


Das Problem dabei ist nun, dass nicht dasselbe ergebnis rauskommt wie wenn der Minimax läuft. Es sollte aber das gleiche sein.
Der Spieler (für ein 4 Gewinnt Spiel) setzt normal seine Steine erst in der Mitte (also mit dem Minimax), und mit der Optimierung zur Alpha-Beta-Suche setzt er den Stein nur ganz links in der Spalte.

Weiss jemand, woran das liegen könnte?
Bin für jeden Tip dankbar :)
Vielen Dank im Voraus.

Gruß Tequila82
 
Hallo Tequila82
Ich schlage mich auch grade mit dem alphabeta Algorithmus rum, habe allerdings eine etwas anderen Vorlage Algorithmus www-il.informatik.rwth-aachen.de/~algorithmus/algo19.php.
Ohne Komentare finde ich es ziemlich schwer deinen Code zu durchschauen. Meiner Ansicht nach muss dein hinzugefügter Code in die else -Anweisung hinein, also statt:
Code:
else { 
               zugWert = minWert(restTiefe-1,alpha,beta); 
                
            } 
                
            board.unmove(i,id); 
             


                                //WURDE HINZUGEFÜGT 
            if (zugWert >= beta) 
                          return beta;



Code:
else { 
               zugWert = minWert(restTiefe-1,alpha,beta); 
                
                           
            board.unmove(i,id); 
             


                                //WURDE HINZUGEFÜGT 
            if (zugWert >= beta) 
                          return beta; 
        }

Und bei der zweiten Einfügung analog.
Ich kann dir nichts garantieren, aber vieleicht war's das.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
H Veränderung eines Objekts ermitteln Java Basics - Anfänger-Themen 6
M Objekt einer Klasse speichert die Veränderung nicht Java Basics - Anfänger-Themen 1
K Veränderung einer Variable von einer anderen Klasse aus Java Basics - Anfänger-Themen 12
E JLabel deaktivieren ohne Veränderung der Darstellung Java Basics - Anfänger-Themen 2
R JTable Column Breite bei Veränderung registrieren Java Basics - Anfänger-Themen 2
S Veränderung von Protected Daten durch Übergabe? Java Basics - Anfänger-Themen 3
S Veränderung anzeigen Java Basics - Anfänger-Themen 4
M Länge eines Arrays als Variable speichern möglich? Java Basics - Anfänger-Themen 14
P Objekt einer Methode eines anderen Objektes übergeben Java Basics - Anfänger-Themen 5
P Wie kann ich beispielsweise Speicherstände eines Spiels DAUERHAFT in meinem Programm speichern? Java Basics - Anfänger-Themen 3
laxla123 Eigenschaften eines Algorithmus (determiniert vs.. deterministisch) Java Basics - Anfänger-Themen 2
monsterherz Ablauf der Erstellung eines Java Programmes Java Basics - Anfänger-Themen 17
monsterherz Fehler Semikolon fehlt - ich weiss aber nicht wo da noch eines hin sollte... Java Basics - Anfänger-Themen 21
J Farbe des Striches eines TitledBorders ändern Java Basics - Anfänger-Themen 2
pc pc pc pc pc letztes Element eines Arrays n Java Basics - Anfänger-Themen 3
walid Öffnungszeiten eines Geschäftes Java Basics - Anfänger-Themen 3
paulen1 Best Practice "Unchecked Assignment" Warnung beim erstellen eines 2D Arrays of Arraylists Java Basics - Anfänger-Themen 2
T Probleme beim Import eines Git-Repos Java Basics - Anfänger-Themen 2
U Eigenschaft eines JTextfiels per ActionListener ändern... Java Basics - Anfänger-Themen 2
B Synchronisation eines kleinen Museums Java Basics - Anfänger-Themen 47
krgewb Breite und Höhe eines Bildes in base64 auslesen Java Basics - Anfänger-Themen 3
Sachinbhatt Was ist die Notwendigkeit eines Sammlungsframeworks in Java? Java Basics - Anfänger-Themen 2
N Textdatei aus Resourcen-Ordner eines Projekts/ jar-file lesen Java Basics - Anfänger-Themen 4
B Produkt eines double - streams Java Basics - Anfänger-Themen 3
B Attribute eines Objekts einer Klasse durch statische Methode einer 2. Klasse ändern? Java Basics - Anfänger-Themen 32
S Variablen Letzte Zeile eines Strings entfernen Java Basics - Anfänger-Themen 1
D Inhalt eines Arrays ausgeben Java Basics - Anfänger-Themen 7
A Jedes zweite Element eines Arrays entfernen Java Basics - Anfänger-Themen 30
sserio Java Fx, wie erstellt man einen EventHandler, der durch das Drücken eines Button Texte in eine Table view einfügt Java Basics - Anfänger-Themen 17
J Größe eines Strings in Pixel Java Basics - Anfänger-Themen 18
M Parse-Tree eines statements darstellen Java Basics - Anfänger-Themen 0
H Java verkettete Liste, Wert eines Index zurückgeben Java Basics - Anfänger-Themen 1
bluetrix Programmieren eines Bots für Zahlen-Brettspiel Java Basics - Anfänger-Themen 9
J Hinzufügen eines Objektes in ein Objekt-Array Java Basics - Anfänger-Themen 62
M Wie kann die Implementation einer Methode den Wert eines Attributs vermindern? Java Basics - Anfänger-Themen 3
A Rekursive Implementation eines Codes Java Basics - Anfänger-Themen 4
H String Repräsentation eines Rechtecks mit Instanz-Methode Java Basics - Anfänger-Themen 8
M Konstruktor ohne Übergabe eines Wertes Java Basics - Anfänger-Themen 7
M Wie kann ich in einem Konstruktor die Methode eines anderen Interfaces mit den jeweiligen Parametern aufrufen? Java Basics - Anfänger-Themen 8
M Wie erreiche ich das Vorwärtsgehen eines Roboters? Java Basics - Anfänger-Themen 2
M Wie erreiche ich es das Vorwärtsgehen eines Roboters? Java Basics - Anfänger-Themen 0
R While-Loop der die Einträge eines Arrays in umgekehrter Reihenfolge anzeigt Java Basics - Anfänger-Themen 3
A Optimierung eines Programms: Mergen der Dateien Java Basics - Anfänger-Themen 23
melisax Alle Möglichkeiten eines Wortes angeben Java Basics - Anfänger-Themen 3
A Java, verarbeitung eines xml-files Java Basics - Anfänger-Themen 2
C Fehler beim erstellen eines Objektes Java Basics - Anfänger-Themen 3
B Konkatenieren eines Strings und inkremtierenden Zahl zu einer INT Variablen Java Basics - Anfänger-Themen 7
F Initialisieren eines Web-Mp3 Players in Tabs durch "booleans" erst wenn Tab geöffnet wird ...? Java Basics - Anfänger-Themen 1
P Drei Zahlen eines Würfelspiels auswerten Java Basics - Anfänger-Themen 7
C Brauche Hilfe beim Schreiben eines Programmes :/ Java Basics - Anfänger-Themen 1
C initialisieren eines arrays richtiger Größe und mit geeignetem Datentyp Java Basics - Anfänger-Themen 26
C Überprüfen eines Programms auf Syntaxfehler Java Basics - Anfänger-Themen 3
S Wie kann ich den Bereich eines Integers begrenzen? Java Basics - Anfänger-Themen 2
nonickatall Grundsätzliches Verständnisproblem des Aufbaus eines Programms Java Basics - Anfänger-Themen 19
B Downgrade eines bestehenden Projektes Java Basics - Anfänger-Themen 5
amelie123456 Geschwindigkeit der Methode bewegeDich eines Objekts ändern Java Basics - Anfänger-Themen 2
D Hilfe beim Erzeugen eines Arrays NullPointerException wird ausgelöst Java Basics - Anfänger-Themen 11
J maximaler Wert eines Integers Java Basics - Anfänger-Themen 14
TimoN11 IntelliJ , Ausgabe von einem Quellcode in Eingabe eines Quellcodes Java Basics - Anfänger-Themen 1
Z Rückgabe eines Values in umgekehrte richtung Java Basics - Anfänger-Themen 5
L Methode zum invertieren eines Arrays Java Basics - Anfänger-Themen 7
B fragen zu Aufbau eines UML-Klassendiagramm Java Basics - Anfänger-Themen 1
eleonori Durchschnitt aller Werte eines Baums berechnen Java Basics - Anfänger-Themen 5
M Benutzereingabe eines Codes verbessern Java Basics - Anfänger-Themen 3
B Modulo-Operator anhand eines Beispieles erklären Java Basics - Anfänger-Themen 7
J Verschieben von Buchstaben in einem String um vorgegebene Anzahl von Zeichen innerhalb eines weiteren String Java Basics - Anfänger-Themen 12
F Auf Variablen eines Konstruktors zugreifen Java Basics - Anfänger-Themen 4
Kawastori Größe eines Arrays bestimmen Java Basics - Anfänger-Themen 13
Lena_2611 Vergleich von Array1 Index mit Array2 Wert und erzeugen eines neues Arrays Java Basics - Anfänger-Themen 8
A Teilarrays eines 2D-Arrays sortieren Java Basics - Anfänger-Themen 4
marcooooo Separator zwischen allen Zeichen eines Strings einfügen Java Basics - Anfänger-Themen 29
C Wie kann ich Versionen eines Projektes in Eclipse erstellen? Java Basics - Anfänger-Themen 3
yoskaem Text Color durch Klicken eines Buttons in anderer Activity ändern Java Basics - Anfänger-Themen 2
A Teilen eines Arrays Java Basics - Anfänger-Themen 5
DorFey Sortieren eines mehrdimensionalen Arrays Java Basics - Anfänger-Themen 8
P Klasse hat keinen Zugriff auf getter/setter-Methoden eines Objektes Java Basics - Anfänger-Themen 9
R Löschen und ausgeben eines Teilbaums Java Basics - Anfänger-Themen 3
J Alle Werte eines Strings zusammen addieren Java Basics - Anfänger-Themen 15
M Hilfe bei Strukturierung eines Buchungssystems Java Basics - Anfänger-Themen 3
M Erstellen eines insets Objekts, GridBagLayout Java Basics - Anfänger-Themen 13
M Rückgabe eines Arrays Java Basics - Anfänger-Themen 10
Z Erste Schritte Indexe innerhalb eines Arrays zusammensählen Java Basics - Anfänger-Themen 14
W Random Zahl unter Berücksichtung eines Durchschnitts Java Basics - Anfänger-Themen 7
N Länge eines Arrays in einem Objekt testen Java Basics - Anfänger-Themen 51
A Freie Stelle eines Arrays Java Basics - Anfänger-Themen 17
C Erstellen eines Widerstandsnetzwerks Java Basics - Anfänger-Themen 10
C Methode Seiten tauschen eines erstellten Rechtecks mit Seite A und B Java Basics - Anfänger-Themen 9
R Zugriff auf den Index eines Arrays, welches ein Objekt ist. Java Basics - Anfänger-Themen 4
J Problem bei der Programmierung eines Tannenbaums Java Basics - Anfänger-Themen 9
F Berechnung der Rektaszension und Deklination eines Sterns Java Basics - Anfänger-Themen 7
1 Erste Schritte Was denkt ihr über eines meiner ersten Javaprogramme? Java Basics - Anfänger-Themen 2
A Problem bei returnen eines Wertes Java Basics - Anfänger-Themen 6
D Input/Output Problem bei der Benutzereingabe eines Befehls Java Basics - Anfänger-Themen 14
H Größte Duplikat (Größte Doppelte Wert) eines Arrays ausgeben Java Basics - Anfänger-Themen 9
M Hinzufügen eines Objekts auf ein Map Java Basics - Anfänger-Themen 4
M Auf einen Array innerhalb eines Objekts zugreifen Java Basics - Anfänger-Themen 5
S Elemente eines Arrays bei Ausgabe auslassen Java Basics - Anfänger-Themen 2
S Ersetzen eines Asterix in einem String Java Basics - Anfänger-Themen 8
M Struktur eines Fotobuches Java Basics - Anfänger-Themen 6
J Implementierung eines Zustandsdiagramms Java Basics - Anfänger-Themen 19

Ähnliche Java Themen

Neue Themen


Oben