minimax algprithmus

[don_house]

ich wünsche einen schönen spät-nachmittag!

ich habe ein kleines problem! ich will eine künstliche intelligenz für 5-wins schreiben. (man spielt auf einem feld, 2 spieler, ca 10*10, und muss 5 steine horizontal oder diagonal in eine reihe kriegen, dabei fallen die steine nicht nach unten wie bei 4 gewinnt.)

ich habe 3 klassen: spielfeld, feldbewertung und KI. doch bei der KI komme ich nicht ganz weiter.

kann mir das jemand erklären? hier mein code:
Das Feld:

import java.util.ArrayList;


public class feld {
	
	
	
	public ArrayList <Integer> feld;
	
	
	
	feld()
	{
		
		feld=new ArrayList<Integer>();
		for(int i=0;i<64;i++)
		{
			feld.add(0);    // 64 spielfelder, leer. 
		}
	}
	
	
	public void setZug(int pos, int color) //0=leer, 1=weiß, 2=schwarz
	{
		feld.set(pos, color);  
	}
	
	

}

Die Bewertungsfunktion (Testversion):

public class feldwert {
	
	
	feld F; 
	int value; // der zugwert: 0=draw, 1=sieg, -1=niederlage
	
	
	feldwert(feld F)
	{
		this.F=F;
		
		
	}
	
	public int getFeldwert(feld F, int color)
	{
		value=0;
		for(int i=0; i<62; i++)  // 62, weil 64+2 => out of bounds 
		{
			if(F.feld.get(i)==color && F.feld.get(i+1)==color && F.feld.get(i+2)==color)
				// bis jetzt gewinnt man nur mit 3 in einer reihe
			{
				value=1;
			}
		}
		
		
		return value;
	}
	
	
	


}

die "KI" (das problem!) :

public class KI {
	
	
	
	
	int besterzugwert=-999; // der beste ermittelte zug
	int besterzug;
	int zugwert;
	int farbe; // farbe wechseln von 1>2 oder 2>1 
	feldwert FW;
	
	KI()
	{
		
	}
	
	
	public int getKizug(feld F, int color, int suchtiefe )
	{
		FW= new feldwert(F);
		for(int z=0; z<64; z++)
		{
			
			if(F.feld.get(z)==0 && suchtiefe>0) // wenn das feld noch frei ist und die angegebene suchtiefe noch nicht erreicht ist
			{
				F.setZug(z, color);
				zugwert=FW.getFeldwert(F, color);
				if(zugwert>besterzugwert)
				{
					besterzug=z; // das passt noch nicht ganz, weil er ja den zug aus suchtiefe 1 ausgeben muss!?
				}
				
			}
			if(color==1){ farbe=2;} if(color==2){farbe=1;} // anderer spieler ist dran
			
			getKizug(F, farbe, suchtiefe-1);
		}
		
		return besterzug;
	}

}

wo ist mein denkfehler? was fehlt mir? könnt ihr mir helfen und mir sagen, was ich tun muss?

mit freundlichen grüßen
don house

 

[SlaterB]

zuerst mal musst du sagen
1.)
was passieren soll und
2.)
was stattdessen passiert






--------------

// das passt noch nicht ganz, weil er ja den zug aus suchtiefe 1 ausgeben muss!?

das mag sein, müsstest du irgendwo zwischenspeichern, z.B. als Parameter rekursiv mitschleppen

----------

du bewertest den Zug abwchseln für Spieler 1 und für Spieler 2,
das kann doch keinen Sinn machen, Spieler 1 will doch keinen Zug machen,
der zu einer hohen Bewertung von Spieler 2 im nächsten Zug führt

falls das mal repariert ist, kommen die höchsten Bewertungen vielleicht dann zustande,
wenn Spieler 2 unsinnige Züge macht (du probierst ja alle Möglichkeiten durch),

davon ist aber nicht auszugehen, das ist eine dumme/ gefährliche Strategie


---------

wenn du mit einem Rekursionsschritt fertig bist,
dann musst du diesen zurücknehmen bevor du einen anderen versuchst!


----------

wozu ist farbe eine Exemplarvariable?
wird nur in einer Operation benutzt, dann rekursiv übergeben und ist dann color..,
sehr verwirrend,
verwende doch nur lokale Variablen in der rekursiven Operation

 

[don_house]

er soll nach dem gewinn suchen und den zug ausgeben, der zum gewinn führt und noch viel wichtiger: ausschließen, dass der andere spieler gewinnt.

was passiert: er gibt mir als zugwert 63 zurück, was mir sehr nach fehler aussieht.

lokalvariable geht nich, weil das nich alles in einer funktion ist.

habe eben stack overflow gehabt, habe die rekursion nich mit in die if funktion getan. habe das jetzt korrigiert.
wenn ich jetzt das ausprobier, geht er irgendwie in eine endlosschleife. wieso?

public class KI {
	
	
	
	
	int besterzugwert=-999; // der beste ermittelte zug
	int besterzug;
	int zugwert;
	int farbe; // farbe wechseln von 1>2 oder 2>1 
	feld F2;
	feldwert FW;
	
	KI()
	{
		
	}
	
	
	public int getKizug(feld F, int color, int suchtiefe ) // die position, die in erster ebene am ende dann besten wert hat
	{
		FW= new feldwert(F2);
		for(int z=0; z<64; z++)
		{
			
			this.F2=F; // um ausprobierten zug zurück zu nehmen
			if(F2.feld.get(z)==0 && suchtiefe>0) // wenn das feld noch frei ist und die angegebene suchtiefe noch nicht erreicht ist
			{
				F2.setZug(z, color);
				System.out.println("Test! Zug: "+z+" Suchtiefe.: "+suchtiefe+" Color: "+color+" Zugwert: "+FW.getFeldwert(F2, color));
				zugwert=FW.getFeldwert(F2, color);
				if(zugwert>besterzugwert)
				{
					besterzug=z; // das passt noch nicht ganz, weil er ja den zug aus suchtiefe 1 ausgeben muss!?
				}
				
				getKizug(F2, farbe, suchtiefe-1);
			}
			if(color==1){ farbe=2;} if(color==2){farbe=1;} // anderer spieler ist dran
			
			
		}
		
		return besterzug;
	}

}

er müsste doch bei suchtiefe=1 aufhören dann?
also wenn ich am anfang mit 5 starte, zählt er runter und bei 1 müsste schluss sein. aber er hört nicht auf?

und wie kann ich den zug auf erster ebene dann rekursiv mitschleppen? der würde doch immer überschrieben werden, mir fällt keine möglichkeit ein.

 

[SlaterB]

beginnst du mit einem leeren Feld?
weißt du wieviele Möglichkeiten es gibt? 64^5?
falls dein Code richtig funktioniert mit zurücklegen usw, dann dauert das schon eine Weile..

allein bei Suchtiefe 2 sind es 4000 Kombinationen


lasse die Ausgabe pro Runde weg, dann gehts um ein vielfaches schneller,
aber kann trotzdem noch sehr lange dauern,
vielleicht versuchst du es erstmal mit einem kleinen Feld von 3x3 oder so..
----------

> er soll nach dem gewinn suchen und den zug ausgeben,
> der zum gewinn führt und noch viel wichtiger: ausschließen,
> dass der andere spieler gewinnt.

das ist keine Problembeschreibung, sondern eine Aufgabe für Wochen/ Monate



-----------

ich hab noch mal dein Programm etwas vereinfacht und umstrukturiert,
vielleicht magst du damit weiterarbeiten,

startzug sollte mit drin sein (als Exemplarvariable, nicht als Rekursionsparameter),
außerdem wird mit nur einem Feld gearbeitet,
auf dem Züge wieder zurückgenommen werden können

kann nicht 100% sagen ob es das gleiche macht wie vorher,
aber auf jeden Fall schicker

public class Feld {

	private int[] feld;

	public Feld() {

		feld = new int[64];
	}

	public int get(int pos) {
		return feld[pos];
	}
	//0=leer, 1=weiß, 2=schwarz
	public void setZug(int pos, int color) {
		feld[pos] = color;
	}
	public void unset(int pos) {
		feld[pos] = 0;
	}
	public int getFeldwert(int color) {
		int value = 0;
		// 62, weil 64+2 => out of bounds
		for (int i = 0; i < 62; i++) {

			// bis jetzt gewinnt man nur mit 3 in einer reihe			
			if (feld[i] == color
				&& feld[i + 1] == color
				&& feld[i + 2] == color) {

				value = 1;
			}
		}

		return value;
	}

}


-----------------------------

public class KI {

	int besterzugwert = -999; // der beste ermittelte zug
	int besterzug;
	int zugwert;
	Feld feld;
	int startzug = -1;
	long count = 0; // Anzahl Arbeitsschritt zählen


	public KI() {
		feld = new Feld();
		getKizug(1, 1);
		System.out.println("bester Zug: "+besterzug+" count: "+count);
	}

	public void getKizug(int color, int suchtiefe) {
		count++;
		int nextColor = 3 - color;

		if (suchtiefe == 0) {
		  return;
		}

		for (int z = 0; z < 64; z++) {
			// wenn das feld noch frei ist  
			if (feld.get(z) == 0) {
				boolean startzugSet = false;
				if (startzug == -1) {
					startzugSet = true;
					startzug = z;
				}
				feld.setZug(z, color);
				System.out.println(
					"Test! Startzug: "	+ startzug	+ " Zug: "	+ z	+ " Suchtiefe.: "
						+ suchtiefe	+ " Color: "+ color	+ " Zugwert: "	+ feld.getFeldwert(color));
				zugwert = feld.getFeldwert(color);
				if (zugwert > besterzugwert) {
					besterzug = startzug;
				}

				getKizug(nextColor, suchtiefe - 1);
				if (startzugSet) {
					startzug = -1;
				}
				feld.unset(z);
			}

		}
		
	}
	public static void main(String[] args) throws Exception {
		new KI();
	}
}

 

[don_house]

ja also keine ahnung! ich würd sagen, das macht noch weniger als meine alte version! der returnt ja gar nichts ^^
bin mir jetzt nicht so sicher, ob ich das nicht verstehe oder wir aneinander vorbeireden ....

 

[SlaterB]

der beste Zug wird doch in der Exemplarvariablen besterzug gespeichert,
was nützt es, wenn die Rekursion am Ende diese Exemplarvariable liest und zurückgibt,
genausogut kann doch der Aufrufer direkt diese Variable lesen,

spart 1000fache (!) unnötige Rückgaben während der einzelnen Rekursionsschritte