Vier Gewinnt: Spielbaumanalyse mit MiniMax-Algorithmus

[lukas93]

Hallo,

Ich bin momentan dabei für meine Facharbeit (Stufe 12 Gymnasium) ein 4Gewinnt Spiel mit künstlicher Intelligenz zu programmieren. Ich habe das Gui bereits fertig und eine spielbare Version die allerdings noch ein paar Makel hat... meine KI ist bis jetzt nur bedingt Intelligent! Hin und wieder kommen zwar ein paar gute und logische Spielzüge zu Stande aber oft werden Steine sinnlos gesetzt...

Woran kann das liegen?
ist mein Algorithmus falsch? wenn ja, warum funktioniert er dann manchmal?
oder kann es ein Problem sein, dass ich so nah an der GUI programmiert habe?

ich habe hier mal die entscheidenen Methoden für das setzen eines Steins durch die KI...
Rot minimiert, bei diesem Spiel und gelb wird per Hand gesteuert und maximiert...
die fehlenden methoden boolean pruefe[...] sind im gleichen Stil programmiert und haben nur andere x- und y- Werte zur Überprüfung

Ich hoffe, dass alles weitere gut genug kommentiert ist und ihr meine überlegung zum algorithmus und meine frage versteht

package Spiel;

import java.awt.Color;

public class ArtificialIntelligence {

	public static void setzen() {

		if (SpielFeld.spielFeld[5][3].getColor() == Color.white) {
			Schiedsrichter.steinSetzen(3, Color.red);
		} else {
			Schiedsrichter.steinSetzen(
					bewerten(SpielFeld.spielFeld, 2, Color.red, true),
					Color.red);
		}
	}

	/**
	 * @param feld das Spielfeld als array von Spielsteinen (7 felder breit, 6 hoch)
	 * @param tiefe die Tiefe die der Spielbaum haben soll
	 * @param c Farbe des Spielers der an der Reihe ist
	 * @param start ist true an der Wurzel des Baums
	 * @return
	 */
	public static int bewerten(SpielStein[][] feld, int tiefe, Color c,
			boolean start) {

		int y = -1; // Spalte -1 falls keine Spalte gewählt wurde
		int[] bew = new int[7]; // Array, mit den Bewertungen der 7 Spalten
		int max = -7380; // Wert wird definitiv überschrieben, weil selbst eine
							// niederlage besser wäre
		int min = 7380;
		int minIndex = -4370; // Index der spalte mit niedrigster Bewertung
		boolean wurzel = start; // Wurzel des Baumes?!

		for (int i = 0; i < 7; i++) {
			// wenn das oberste feld der Spalte leer ist..
			if (feld[0][i].getColor() == Color.white) {
				for (int j = 5; j >= 0; j--) {
					if (feld[j][i].getColor() == Color.white) {
						feld[j][i].setColor(c); // ..wird das unterste Freie
												// fällt gefärbt
						y = j;
						break;
					}
				}
				// und eine Bewertung vorgenommen indem erstmal der restliche
				// Baum generiert wird und bei einem Sieg für rot oder gelb die
				// bewertung von i vorgenommen wird
				if (Schiedsrichter.gewinnPruefung(feld, i, y, c)) {
					if (c.equals(Color.red)) {
						bew[i] = -2;
					}
					if (c.equals(Color.yellow)) {
						bew[i] = 2;
					}
				} else {
					// sonst wird, rekursiv bis zu den blättern des baumes
					// vorgegangen um i zu bewerten
					if (tiefe >= 0) {
						if (c.equals(Color.red)) {
							bew[i] = bewerten(feld, tiefe - 1, Color.yellow,
									false);
						} else {
							bew[i] = bewerten(feld, tiefe - 1, Color.red, false);
						}
					}
				}
				// Hier wird überprüft, ob irgendwo 3 Steine einer
				// Farbe in einer reihe sind
				if (pruefeLinksOben(feld, i, y, c)
						|| pruefeLinks(feld, i, y, c)
						|| pruefeLinksUnten(feld, i, y, c)
						|| pruefeUnten(feld, i, y, c)
						|| pruefeRechtsUnten(feld, i, y, c)
						|| pruefeRechts(feld, i, y, c)
						|| pruefeRechtsOben(feld, i, y, c)) {
					if (c.equals(Color.red)) {
						bew[i] = -1;
					}
					if (c.equals(Color.yellow)) {
						bew[i] = 1;
					}
				}
				feld[y][i].setColor(Color.white); // damit das Feld
													// wiederhergestellt ist
			} else {
				// wenn die spalte voll ist wird i mit 7380 bewertet, wenn rot
				// dran ist
				if (c.equals(Color.red)) {
					bew[i] = 7380;
				} else {
					bew[i] = -7380;
				}
			}
		}

		// Auswahl des besten weges
		for (int i = 0; i < 7; i++) {
			if (bew[i] < min) {
				min = bew[i];
				minIndex = i;
			}

			if (bew[i] > max) {
				max = bew[i];
			}

		}

		// bei mehrfach vorkommendem min wird jetzt der am weitesten rechts
		// verwendet anstatt dem ersten
		for (int i = 0; i < 7; i++) {
			if (bew[i] == min) {
				minIndex = i;
			}
		}

		// return: bei der Wurzel den Index, der niedirgsten Bewertung,
		// sonst die höchste bzw. niedrigste Bewertung
		if (c.equals(Color.red)) {
			if (wurzel) {
				return minIndex;
			}
			return min;
		} else {
			return max;
		}
	}

	public static boolean pruefeLinksOben(SpielStein[][] feld, int x, int y,
			Color farbe) {
		if (y > 2 && x > 2) {
			if (feld[y - 1][x - 1].getColor() == farbe
					&& feld[y - 2][x - 2].getColor() == farbe) {
				return true;
			}
		}
		return false;
	}

Ich hoffe ihr könnt mir dabei helfen
Mit freundlichen Grüßen
Lukas

 

[lukas93]

bin ich im falschen Teil des Forums mit meiner Frage? oder wird mein Problem nicht deutlich?

Lg Lukas

 

[Marco13]

Du hast etwas programmiert, und es funktioniert nicht. Den Code (und was damit erreicht werden soll) kann man nicht in vertretbarer Zeit nachvollziehen, geschweige denn den Fehler finden (sofern einer existiert - je nach Voraussicht und wie ausgefeilt die Bewertungsfunktion ist, können durchaus Züge gewählt werden, die ein Mensch als "dumm" ansehen würde - z.B. den ersten Stein ganz links und den zweiten ganz rechts... Die Bewertungsfunktion müßte vermutlich sowas wie die längste Kette von Steinen einbezeihen, und (wenn auch nur implizit?) auf "Zwickmühen" hinarbeiten). Dass nirgendwo sowas vorkommt wie

void berechne(..., int tiefe, String indent)
{
    System.out.println(indent+"Bei tiefe "+tiefe+" mache dies und das");
    ....
    berechne(...tiefe-1, indent+"    ");
    ....
    System.out.println(indent+"Bei tiefe "+tiefe+" ist das Ergebnis "+...);
}

legt auch die Vermutung nahe, dass du noch nicht besonders lange selbst gesucht hast, aber das kann täuschen...