Go

C

CEric

Aktives Mitglied
Hi!
Wir programmieren gerade das Spiel Go (chinesisches Brettspiel).Wir haben bereits unser Spielfeld Zustand[][] spielbrett = new Zustand[10][10];
mit den Zuständen LEER ( . ), SCHWARZ (X) und WEISS (O).
Nun sollen wir in der Methode public int entferneEingeschlosseneSteine(Zustand farbe), alle vollständig eingeschlossenen Ketten der Farbe farbe vom Spielbrett
nehmen und die Anzahl der entnommenen Steine als Resultat zurückgegeben. Dazu sollen wir zunächst alle Steine der Farbe farbe markieren die nicht zu vollständig eingeschlossenen Ketten gehören.
Dazu haben wir folgendes array, boolean [10][10]markierung, in dem alle Felder auf false gesetz sind, wird ein Feld true, dann ist der entsprechende Stein markiert!
Nun soll man für alle Felder testen, ob dort ein noch nicht markierter Stein der Farbe farbe liegt, welcher markiert werden kann.
Was der Fall ist, wenn er direkter Nachbar eines leeren Feldes ist, oder falls er neben einem bereits markierten Stein liegt.
Falls er markiert werden kann, sollen wir ihn markieren.
Nach der letzten Iteration sollten dann alle Steine der Farbe farbe markiert sein, die nicht zu vollständig eingeschlossenen Ketten gehören.
Die Steine der Farbe farbe die also nicht markiert sind, gehören dann zu eingeschlossenen Ketten.
Also sollte man wohl testen welche Steine von farbe nicht markiert sind und diese dann entefernen und zählen.

Java: 
public int entferneEingeschlosseneSteine(Zustand farbe) {

		if (farbe != Zustand.WEISS || farbe != Zustand.SCHWARZ) {
			throw new IllegalArgumentException(
					"Farbe ist nicht WEISS und nicht SCHWARZ!");
		}
		boolean[][] markierung = new boolean[10][10]; // neues boolean-array
		for (int x = 0; x < 10; x++) {
			for (int y = 0; y < 10; y++) {
				markierung[x][y] = false; // alle Felder false
			}
		}

		for (int x = 0; x < 10; x++) {
			for (int y = 0; y < 10; y++) {
				if (markierung[x][y] = false & farbe == Zustand.WEISS){

				}
			}
		}

	}
Das ist mein bisheriger Code; ich habe aber keine Idee wie das ganze funktionieren soll, insbesondere wie ich die anzahl der Steine die ich irgendwie entferne bekomme usw.
 
C

Christi

Mitglied
Also, wenn ich mir deinen Code so ansehe, fällt mir sofort auf:
* Die erste For-Schleife ist umsonst, weil du ja in der zweiten das ganze nocheinmal durchgehst
* In der zweiten Forschleife machst du ein if auf markierung[x][y] = false; Ich denke mal du willst die beiden vergleiche, aber das geht mit ==
Außerdem ist das sowieso immer true, weil du es zuvor ja auf fals gesetzt hast.

Wenn ich das richtig verstanden habe, brauchst du nur eine For-Schleife:
Java: 
 for (int x = 0; x < 10; x++) {
            for (int y = 0; y < 10; y++) {
                markierung[x][y] = false;
                if (farbe == spielbrett[x][y]){
                           markierung[x][y] = true;
                }
            }
        }

Die Markierung kannst du im gleichen Schritt false setzten und nur wenn am Spielfeld ein der Zustand der Farbe entspricht wird die Markierung true. Habe ich das richtig verstanden?
 
C

CEric

Aktives Mitglied
Genau, ein Zustand entspricht der Farbe farbe und wird true!
Jedes Feld soll überprüft werden und wenn dort ein Stein der Farbe farbe ist der noch nicht markiert ist, wenn er direkter Nachbar eines leeren feldes ist, oder falls er neben einem markierten Stein liegt soll er markiert werden!
Am ende sollen dann alle Steine der Farbe farbe markiert sein, die nicht zu vollständig eingeschlossenen Ketten gehören, die Steine der farbe die nicht markiert sind sind also eingeschlossene Ketten und sollen entfernt werden, die Zahl der entfernten Steine soll zurückgegeben werden!

Das mit der for-Schleife ist mir schon klar, allerdings weis ich nicht genau wie das ganze mit der markierung und dem entfernen ablaufen soll!

MfG
 
C

Christi

Mitglied
So, jetzt hab ich mir mal auf Wikipedia reigezogen, wie das Spiel funktioniert.

Du gehst alle felder in einer Schleife durch. Untersuche jeden nachbarn des feldes. Wenn ein nachbar leer ist kannst du ihn markieren und das nächste Feld am Spielbrett bearbeiten. Ist der nachbar von der gleichen farbe, kannst du ihn zu einer Liste (Kette) hinzufügen).

Wenn das feld keine leeren nachbarn hat, kannst du dir alle objekte der kette ansehen. Wenn diese gleichfarbigen nachbarn wiederum einen leeren nachbaren haben, kann die ganze kette markiert werden. Haben Sie einen gleichfärbigen Nachbarn haben fügst du ihn zur kette hinzu. So wird die kette immer größer.

Das Entfernen und die Rückgabe der entfernten steine ist wahrscheinlich einfach im vergleich zu dem.

Ich denke das ganze ist rekursiv zu lösen. Wahrscheinlich mit einer methode, die sich selbst aufruft. Aber iterativ gehts sicher auch, ohne dementsprechende Resourcen zu beanspruchen.
 
bERt0r

bERt0r

Top Contributor
Also ich denke mal dass ihr keine KI für go schreiben sollt, ich spiel das Spiel nämlich und weiß dass Go eine der größten Herausforderungen für KI Entwickler ist (im gegensatz zum Schach wo der Computer den Menschen schlägt).
Wenn du ein 19x19 Array hast und dir schon eine Enum "Zustand" gemacht hast, wäre es dann nicht sinnvoll mal festzustellen: Der Zustand eines Feldes im Array kann entweder leer, weiß oder schwarz sein.

Das fangen von Steinen ließe sich wohl am besten rekursiv lösen.
 
C

CEric

Aktives Mitglied
Hi ich habe jetzt folgenden Code geschrieben!
Java: 
public int entferneEingeschlosseneSteine(Zustand farbe) {
		spielbrett[9][8] = Zustand.WEISS;
		spielbrett[9][9] = Zustand.WEISS;
		spielbrett[8][8] = Zustand.WEISS;
		spielbrett[9][7] = Zustand.SCHWARZ;
		spielbrett[8][7] = Zustand.SCHWARZ;
		spielbrett[7][8] = Zustand.SCHWARZ;
		spielbrett[8][9] = Zustand.SCHWARZ;
		spielbrett[2][6] = Zustand.SCHWARZ;
		spielbrett[1][6] = Zustand.WEISS;
	
		// Farbe verschieden von Zustand WEISS und SCHWARZ, also
		// IllegalArgumentException
		if (farbe == Zustand.LEER) {
			throw new IllegalArgumentException("Farbe ist nicht WEISS und nicht SCHWARZ!");
		}

		boolean[][] markierung = new boolean[10][10];
		int entfernteSteine = 0;

		for (int x = 1; x < 9; x++) {
			for (int y = 1; y < 9; y++) {
				markierung[x][y] = false;
				
				// spielbrett[x][y] ist Nachbar eines LEEREN Feldes, kann markiert werden
				if (spielbrett[x][y]==farbe & markierung[x][y]==false & spielbrett[x+1][y] == Zustand.LEER|| spielbrett[x-1][y] == Zustand.LEER || spielbrett[x][y+1] == Zustand.LEER || spielbrett[x][y-1] == Zustand.LEER) {
					// Stein wird markiert
					markierung[x][y] = true;
				}
				// ein Nachbarstein ist bereits markiert, kann ebenfalls markiert werden
				else if (markierung[x+1][y] == true|| markierung[x-1][y] == true|| markierung[x][y+1] == true|| markierung[x][y-1] == true) {
					// Stein wird markiert
					markierung[x][y] = true;
				}
				//sonst keine Markierung
			
				
				//Nach der letzten Iteration sind alle Steine der Farbe farbe markiert, die nicht zu vollstaendig eingeschlossenen Ketten gehoeren
				//Steine der Farbe farbe die nicht markiert wurden sind vollstaendig eingeschlossen
				//also alle Steine die false sind und zur Farbe farbe gehoeren, sind vollstaendig eingeschlossen
				// vollstaendig eingeschlossener Stein, also entfernen
				if ( spielbrett[x][y] == farbe & markierung[x][y] == false ) {
					spielbrett[x][y] = Zustand.LEER;
				//fuer jeden entfernten Stein den Zaehler hochzaehlen	
					entfernteSteine++;
				}	
				else markierung[x][y] = false;
				
				
			}// Ende innere for-Schleife
		}// Ende aeussere for-Schleife
		return entfernteSteine;

	}// Ende Methode entferne

	public static void main(String[] args) {

		Spielbrett spiel = new Spielbrett();
		System.out.println(spiel.entferneEingeschlosseneSteine(Zustand.WEISS));

	}

Das ganze zu folgendem Bild/Spielbrett;
y\x 0 1 2 3 4 5 6 7 8 9
0 . . . . . . . . . .
1 . . . . . . . . . .
2 . . . . . . . . . .
3 . . . . . . . . . .
4 . . . . . . . . . .
5 . . . . . . . . . .
6 . O X . . . . . . .
7 . . . . . . . . X X
8 . . . . . . . X O O
9 . . . . . . . . X O
X steht für SCHWARZ und O für WEISS;
wird also farbe=Zustand.WEISS aufgerufen, erhält nur der weiße Stein auf (1,6) eine Markierung, da er der einzige weiße Stein ist, der nicht zu einer vollständig eingeschlossenen Kette gehört. Daraufhin werden die Steine auf den Feldern (8,8), (9,8) und (9,9) entfernt.
Habe irgendwo einen Fehler, da mir meine Methode gerade den Wert 1 zurück liefert!

Und wahrscheinlich muss ich noch i-wie an die eckpunkte dran!
 
Zuletzt bearbeitet:
bERt0r

bERt0r

Top Contributor
Ich würde einen anderen Ansatz verfolgen: Anstatt das ganze Spielbrett zu überprüfen reicht es doch, wenn man einen Stein setzt nur die Steine zu überprüfen, welche angrenzen und die andere Farbe haben.
Im Go spricht man von Freiheiten, das sind einfach leere Felder neben einer zusammenhängenden Gruppe von Steinen. Hat eine Gruppe keine Freiheiten mehr, ist sie umzingelt und gefangen.
z.B
Java: 
boolean isEnclosed(Point p,Set<Point> points,Zustand farbe)
{
 if(points.contains(p))  //Wenn der Punkt bereits untersucht wurde, kann er keine Freiheit haben.
 {
  return true;
 }
 else
 {
  points.add(p);

  Point punktOben=new Point(p.x,p.y-1);
  Zustand zustandOben=spielfeld.getZustandAt(punktOben;
  boolean enclosedOben;
  if(zustandOben==farbe)
  {
    enclosedOben=isEnclosed(punktOben,points,farbe);
  }
  else if(zustandOben==Zustand.LEER)
  {
    enclosedOben=false;
  }
  else
  {
    enclosedOben=true;
  }
  if(!enclosedOben)
  {
    return false;            //Bei einem gefundenen freien Feld kann man die ganze Berechnung abbrechen
  }

  //Das selbe jetzt für links, rechts und unten
  if(enclosedTop && enclosedLeft && enclosedRight && enclosedBot)
  {
     return true;
  }
  return false;
 }
}
 
Zuletzt bearbeitet:
C

CEric

Aktives Mitglied
Hm deine Loesung klingt auf jeden Fall einfacher, allerdings dürfen wir diese glaube ich nicht verwenden.
Mein Problem liegt denke ich nur noch in den if-abfragen, da mir die Methode wie gesagt den Wert 1 zurueckliefert, ich denke mal das ist der Punkt [1][6], eigentlich sollte der Wert aber 3 betragen, also die eingeschlossene Kette rechts unten!
 
bERt0r

bERt0r

Top Contributor
Bekommst du eigentlich eine IndexOutOfBounds Exception?
Ausserdem hast du noch das Problem dass du nur in eine Richtung überprüfst, bei sowas:go.png wird nur ein schwarzer Stein (der ganz rechts) markiert.
edit: Beziehungsweise nicht markiert, du ziehst das ja anders auf.
 
Zuletzt bearbeitet:
C

CEric

Aktives Mitglied
Habe jetzt folgenden Code für das Feld geschrieben.
Das ganze passt auch, heißt ich bekomme den Wert 3 zurück!
Setze ich jetzt aber das Feld [9][7] auf leer, sollte ich 0 zurück kriegen, die Methode gibt mir aber 2 d.h. sie entfernt mir immer noch die Steine auf [8][8] und [9][9]!
Das ganze muss ich i-wie mit der while-Schleife lösen, aber ich weis nicht wie!

Java: 
public int entferneEingeschlosseneSteine(Zustand farbe) {
		spielbrett[9][8] = Zustand.WEISS;
		spielbrett[9][9] = Zustand.WEISS;
		spielbrett[8][8] = Zustand.WEISS;
		spielbrett[9][7] = Zustand.SCHWARZ;
		spielbrett[8][7] = Zustand.SCHWARZ;
		spielbrett[7][8] = Zustand.SCHWARZ;
		spielbrett[8][9] = Zustand.SCHWARZ;
		spielbrett[2][6] = Zustand.SCHWARZ;
		spielbrett[1][6] = Zustand.WEISS;
		farbe = Zustand.WEISS;

		// Farbe verschieden von Zustand WEISS und SCHWARZ, also
		// IllegalArgumentException
		if (farbe != Zustand.WEISS && farbe != Zustand.SCHWARZ) {
			throw new IllegalArgumentException(
					"Farbe ist nicht WEISS und nicht SCHWARZ!");
		}

		boolean[][] markierung = new boolean[10][10];
		int entfernteSteine = 0;
		// alle Felder auf false setzen
		for (int x = 0; x < 10; x++) {
			for (int y = 0; y < 10; y++) {
				markierung[x][y] = false;
			}
		}
		boolean aenderung = true;
		while(aenderung==true){
		  aenderung = false;
		for (int x = 1; x < 9; x++) {
			for (int y = 1; y < 9; y++) {
				// spielbrett[x][y] ist Nachbar eines LEEREN Feldes, kann
				// markiert werden
				if (spielbrett[x][y] == farbe && markierung[x][y] == false) { // eventuell
																				// equals();
																				// this.getFeld()
					if (spielbrett[x + 1][y] == Zustand.LEER
							|| spielbrett[x - 1][y] == Zustand.LEER
							|| spielbrett[x][y + 1] == Zustand.LEER
							|| spielbrett[x][y - 1] == Zustand.LEER) {
						// Stein wird markiert
						markierung[x][y] = true;
					}
				}
				// ein Nachbarstein ist bereits markiert, kann ebenfalls
				// markiert werden
				else if (markierung[x + 1][y] == true
						|| markierung[x - 1][y] == true
						|| markierung[x][y + 1] == true
						|| markierung[x][y - 1] == true) {
					// Stein wird markiert
					markierung[x][y] = true;
				}
			}// Ende innere for-Schleife
		}// Ende aeussere for-Schleife

		// Punkt [0][0]
		if (spielbrett[0][0] == farbe) {
			if (spielbrett[1][0] == Zustand.LEER
					|| spielbrett[0][1] == Zustand.LEER) {
				markierung[0][0] = true;
			}
			if (markierung[1][0] == true || markierung[0][1] == true) {
				markierung[0][0] = true;
			}
		}

		// Punkt [0][9]
		if (spielbrett[0][9] == farbe) {
			if (spielbrett[0][8] == Zustand.LEER
					|| spielbrett[1][9] == Zustand.LEER) {
				markierung[0][9] = true;
			}
			if (markierung[0][8] == true || markierung[1][9] == true) {
				markierung[0][9] = true;
			}
		}

		// Punkt [9][9]
		if (spielbrett[9][9] == farbe) {
			if (spielbrett[9][8] == Zustand.LEER
					|| spielbrett[8][9] == Zustand.LEER) {
				markierung[9][9] = true;
			}
			if (markierung[9][8] == true || markierung[8][9] == true) {
				markierung[9][9] = true;
			}
		}

		// Punkt [9][0]
		if (spielbrett[9][0] == farbe) {
			if (spielbrett[8][0] == Zustand.LEER
					|| spielbrett[9][1] == Zustand.LEER) {
				markierung[9][0] = true;
			}
			if (markierung[8][0] == true || markierung[9][1] == true) {
				markierung[9][0] = true;
			}
		}
		// Zeile 1
		for (int x = 1; x < 9; x++) {
			if (spielbrett[x][0] == farbe && markierung[x][0] == false) {
				if (spielbrett[x + 1][0] == Zustand.LEER|| spielbrett[x - 1][0] == Zustand.LEER || spielbrett[x][1] == Zustand.LEER) {
					markierung[x][0] = true;
				}
				else if (markierung[x + 1][0] == true|| markierung[x - 1][0] == true|| markierung[x][1] == true) {
					markierung[x][1] = true;
				}
			}
		}
		
		//letzte Zeile
		for (int x = 1; x < 9; x++) {
			if (spielbrett[x][9] == farbe && markierung[x][9] == false) {
				if (spielbrett[x+1][9] == Zustand.LEER|| spielbrett[x-1][9] == Zustand.LEER || spielbrett[x][8] == Zustand.LEER) {
					markierung[x][9] = true;
				}
				else if (markierung[x+1][9] == true|| markierung[x-1][9] == true || markierung[x][8] == true) {
					markierung[x][9] = true;
				}
			}
		}
		
		//linke Spalte
		for (int y = 1; y < 9; y++) {
			if (spielbrett[0][y] == farbe && markierung[0][y] == false) {
				if (spielbrett[0][y-1] == Zustand.LEER|| spielbrett[0][y+1] == Zustand.LEER || spielbrett[1][y] == Zustand.LEER) {
					markierung[0][y] = true;
				}
				else if (markierung[0][y-1] == true|| markierung[0][y+1] == true || markierung[1][y] == true) {
					markierung[0][y] = true;
				}
			}
		}
		
		//rechte Spalte
		for (int y = 1; y < 9; y++) {
			if (spielbrett[9][y] == farbe && markierung[9][y] == false) {
				if (spielbrett[9][y-1] == Zustand.LEER|| spielbrett[9][y+1] == Zustand.LEER || spielbrett[8][y] == Zustand.LEER) {
					markierung[9][y] = true;
				}
				else if (markierung[9][y-1] == true|| markierung[9][y+1] == true || markierung[8][y] == true) {
					markierung[9][y] = true;
				}
			}
		}
		boolean [][] markierungTest = markierung.clone();
		if(markierungTest.equals(markierung)){
			return -1;
		}
		}
		// Nach der letzten Iteration sind alle Steine der Farbe farbe
		// markiert, die nicht zu vollstaendig eingeschlossenen Ketten gehoeren
		// Steine der Farbe farbe die nicht markiert wurden sind vollstaendig eingeschlossen
		// also alle Steine die false sind und zur Farbe farbe gehoeren,sind vollstaendig eingeschlossen
		// vollstaendig eingeschlossener Stein, also entfernen: sprich Zustand.LEER
	
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (spielbrett[i][j] == farbe && markierung[i][j] == false) {
					spielbrett[i][j] = Zustand.LEER;
					// fuer jeden entfernten Stein den Zaehler
					// hochzaehlen
					entfernteSteine++;
				} else
					markierung[i][j] = false;
			}
		}
		return entfernteSteine;
		

	}// Ende Methode entferne
 
J

JohannisderKaeufer

Gast
überall wo du innerhalb der while-Schleife aus zeile 29
eine codezeile
Code: 
markierung[X][Y] = true;
hast muß dieser ein
Code: 
aenderung = true;
folgen!

Andernfalls durchläufst du die while-Schleife nur einmal, du sollst sie aber solange durchlaufen, bis es keine Änderungen mehr gibt!

Iteriere über alle Felder solange es Änderungen gibt!
 

Aktuelle Jobs

Neue Themen


Oben