Kartenspiel

[randomnick]

Schönen guten Tag,

Ich möchte ein simples Kartenspiel in Java implementieren. Es funktioniert wie folgt:
Man hat 9 Karten mit den Zahlen 1 bis 9 aufgedeckt auf einem Tisch liegen. Nun würfelt man mit zwei Würfeln eine Augensumme. Man muss Nun entprechend eine oder zwei Karten umlegen, zum Beispiel: Man würfelt eine 5 und 4 = 9. Jetzt kann man entweder die 7 und 2, 1 und 8 oder 9 umlegen. Umgelegte Karten dürfen in der nächsten Runde nicht verwendet werden. Falls man keine Karten entsprechend mehr umlegen kann werden die offenen Karten als Bonuspunkte notiert. Ziel ist es möglichst viele Punkte zu erreichen.

Mein Programm soll jetzt den optimalen Zug angeben, also welche Karten ich am besten umlegen sollte, damit ich am Ende eine maximale Punktzahl erreiche.

Bisher habe ich folgens programmiert:

 package klassen;

public class Karten {

	private boolean[] karten = new boolean[8];
	private int summenkonto = 0;

	// Konstruktor mit Initialisierung
	public Karten() {
		for (int i = 0; i < karten.length; i++) {
			karten[i] = true;
		}
	}
	
	public int getSummenkonto() {
		return summenkonto;
	}

	public void neuerWurf() {
		summenkonto = (int) (Math.random() * 6 + 1);
		summenkonto += (int) (Math.random() * 6 + 1);
	}
	
        //Backtracking..

}

Mein Problem liegt beim Backtracking. Was muss ich der Backtrackingmethode für Parameter übergeben? Und wie soll Backtracking eine Lösung finden wenn man gar nicht die nächsten Züge sprich Augensummen kennt?

Mit freundlichen Grüßen

randomnick

 

[Gast2]

Mein Problem liegt beim Backtracking. Was muss ich der Backtrackingmethode für Parameter übergeben? Und wie soll Backtracking eine Lösung finden wenn man gar nicht die nächsten Züge sprich Augensummen kennt?

Du musst dann alle Möglichkeiten in deinem Spielbaum durchgehen. Sprich du hast deinen aktuellen Zustand (offenen geschlossene Karten) + dein Würfelwurf.
Zunächst schaust du welche möglichkeiten mit deinem aktuellen würfelwurf möglich sind. Auf dieser Menge von neuen Zuständen machst du dann weiter. Jeden Zustand musst du mit jedem möglichen Würfelergebnis weiterverfolgen.
Du könntest dir mal ausrechnen wieviele Möglihckeiten es dann in deinem Baum gibt.

Wenn das zuviele sind dann kannst du z.b. sagen dass dein Programm nur die nächsten x Züge berechnen soll und sich dann somit schon vorher für einen Zug entscheidet (der dann aber nicht unbedingt der beste sein muss!).
Oder du wendest eine Heuristik an die dir Spielzüge gewichtet. Dann kannst du zuerst vielversprechende Spielzüge komplett (bis zum ende) durcharbeiten, und wenn danach dann noch Zeit ist die weniger vielversprechenden Züge. So eine (gute) Heuristik ist aber nicht immer einfach zu finden

 

[randomnick]

Vielen Dank für die schneller Antwort, ich hab bereits einige Sachen verändert und hoffe, dass ich mit Ihrer Hilfe den Algorythmus bald fertig haben werde. Ich bitte trotzdem den Thread noch nicht links liegen zu lassen, da ich stark davon ausgehe, dass bei der Umsetzung noch ein paar Fehler auftreten werden.

Mit freundlichen Grüßen

randomnick

 

[Landei]

Es heißt "Algorithmus", und hat mit Rhythmus nichts zu tun, sondern mit einem Herren Al-Chwarizmi, der sich jedesmal im Grab umdreht, wenn jemand seinen (durch die Lateinisierung bereits entstellten) Namen verhunzt...

 

[randomnick]

Es heißt "Algorithmus", und hat mit Rhythmus nichts zu tun, sondern mit einem Herren Al-Chwarizmi, der sich jedesmal im Grab umdreht, wenn jemand seinen (durch die Lateinisierung bereits entstellten) Namen verhunzt...

Danke für den Hinweis.

Du musst dann alle Möglichkeiten in deinem Spielbaum durchgehen.

Das habe ich in Java so gemacht:

	public void moeglichkeiten(int summe) {
		boolean gefunden1 = false;
		boolean gefunden2 = false;
		int i = 0;
		int j = karten.length - 1;
		int k = 0;

		// sucht nach Kombinationsmöglichkeiten z.B. 2+3 oder 1+4 für die Summe 5
		while (gefunden1 == false && i < karten.length - 1) {
			if (karten[i].getNummer() + karten[j].getNummer() == summe) {
				karten[i].setAufgedeckt(false); // beide Karten werden umgedreht
				karten[j].setAufgedeckt(false);
				gefunden1 = true;
			} else {
				i++;
				if (i == j - 1) {
					i = 0;
					j--;
				}
			}
		}
		// sucht nach einer Karte mit der Nummer gleich der Summe z.B. 5 für die Summe 5
		while (gefunden2 == false && k < karten.length - 1) {
			if (karten[k].getNummer() == summe) {
				karten[k].setAufgedeckt(false); // Karte wird umdreht
				gefunden2 = true;
			} else {
				k++;
			}
		}
	}

Hinweis: Ich habe ein Array vom Typ Karte erstellt. Die Klasse Karte behinhaltet sowohl die Nummer also auch den Status (aufdeckt oder zugedeckt als boolean).

Jeden Zustand musst du mit jedem möglichen Würfelergebnis weiterverfolgen.

Mein Problem: Wie mache ich das am besten? Mit normalen IF-Abfragen schreibe ich mir die Finger wund

 

[Gast2]

Wie mache ich das am besten?

Stichwort: Rekursion!

Du kannst dein Problem ja auf sehr viele kleine Probleme aufteilen. Die Methode löst dann jeweils ein Teilproblem und gibt das Ergebnis an die aufrufende Instanz weiter.

Hier mal nen Beispiel zur Rekursion:

public int fakultaet(int i) {
    if (i == 1) {
        return 1;
    } else {
        return i * fakultaet(i-1);
    }
}

 

[randomnick]

Danke für die schnelle Antwort!
Rekursion ist ein gutes Stichwort, jedoch braucht man wie ich auch an Ihrem Beispiel sehe immer eine Abbruchbedingung. Wie könnte in meinem Fall eine Abbruchbedingung lauten?

"Abbrechen, wenn es keine Möglichkeiten mehr gibt" ?

 

[Gast2]

Je nachdem wie du das konzeptionierst:
- Brich ab wenn du das Ende des Baumes (keine Spielzüge mehr möglich) erreicht hast
oder
- Brich ab wenn du das Ende des ........ oder wenn du x Schritt tief im Baum bist. (Damit berechnest du dann die nächsten x Spielzüge.

Dein Algorithmus muss dann jeden Spielzug bewerten und wie am Ende den mit dem höchsten Wert ausführen.

 

[randomnick]

Uploaded with ImageShack.us

Ich habe mal einen Spielbaum - wenn auch eher unschön - mit den ersten Zweigen simuliert. Folgendes:
Bei den ersten 3 Ästen sieht man die Möglichkeiten, die es gibt. Bei den nächste (zwölf) Ästen jedoch die möglichen Augensummen 2-12. danach müsste dann wieder die Möglichkeiten für jede Augensumme folgen usw. bis es keine möglichkeiten mehr gibt.

Soweit so gut, ich weiß leider nicht wie ich so einen Baum realisieren soll, denn die Äster "wechseln" zwischen Möglichkeiten und Augensummen.

Außerdem wie soll ich die veränderten Karten abspeichern. Muss ich für jeden Zug ein neues temporäres Feld anlegen und zwischenspeichern?

Zur Gewichtung habe ich mir das so vorgestellt: Am ende des Baumes (also wenn es keine Möglichkeiten mehr gibt Karten umzulegen) werden die restlichen Karten als Bonuspuntke zusammen gezählt. Der Zug mit den meisten Bonuspunkten wird am stärksten gewichtet und am Ende ausgeführt bzw. als bester Zug vorgeschlagen.