3. Logikfrage -> Minimax bei 4 Gewinnt

Logikfrage -> Minimax bei 4 Gewinnt

  • T

    Hallo.
    Zurzeit programmiere ich ein 4Gewinnt und bin so weit eigentlich auch schon fertig, nur will ich nun eine vernünftige KI einbauen.
    Also habe ich mir einiges zum Minimax-Algorithmus durchgelesen und dachte mir, dass dieser die Lösung ist (Anfangs will ich es noch ohne Alpha / Beta - Pruning machen, also das hier auch bitte nicht vorschlagen)
    Nun Habe ich in der bewerten Funktion auch nur den Fall des Gewinnens / Verlierens, was für ein einigermaßen schweres Spiel bei höher Rekursionstiefe sorgen sollte (Tiefe = 😎
    Jedoch spielt die KI sehr schlecht und ich bin mir sehr sicher, dass es einfach nicht an der bewertungsfunktion liegen kann.
    Nunja komme ich mal zum relevanten Sourcecode:

    int game::AI(int depth, bool player){	
	/*printf("-------------------------------------\n");
	printf("depth: %i\n", depth);
	printf("player: %i\n", player);
	printf("Spielfeld:\n");
	for(int j=0; j<6; j++){
		for(int i=0; i<7; i++)
		{
			printf(" %i ", m_iGameTable[i][j]);
		}
		printf("\n");	
	}
	printf("-------------------------------------\n\n");*/
	if (depth == 0)
        return value(player);
    int score=-9999;
    for(int i=0; i<7; i++)
    {
		if(m_iGameTable[i][0]==0)
		{
			for(int j=5; j>=0; j--)
			{
				if(m_iGameTable[i][j]==0)
				{
					if(player)
						m_iGameTable[i][j]=1;
					else
						m_iGameTable[i][j]=2;
					int temp = -AI(depth-1,!player);
					if(temp>score)
					{
						score=temp;
						AI_row=i;
					}
					m_iGameTable[i][j]=0;
					break;
				}	
			}
		}
	}
//	printf("Score: %i\n", score);
	if(depth<difficulty)
	{
		return score;
	}
	else
	{
		for(int j=5; j>=0; j--)
		{
			if(m_iGameTable[AI_row][j]==0)
			{
				if(player)
					m_iGameTable[AI_row][j]=1;
				else
					m_iGameTable[AI_row][j]=2;
				break;
			}
		}
	}
}

    m_iGameTable entspricht meinem Spielfeld und ist ein Array[7][6].
    value ist die Bewertungsfunktion und player gibt an, wer gerade am Zug ist (Spieler oder Computer)

    Ich hoffe ihr könnt mir weiterhelfen.

    Mit freundlichen grüßen
    Artus

    0
  • ?

    MiniMax ist eher ungeeignet fuer 4Gewinnt, weil der Suchraum exponentiell gross ist.

    0
  • T

    Mit Alpha-/Beta-Pruning dann ja nicht mehr....
    Minimax ist eigentlich sogar sehr gut für 4 Gewinnt.
    Außerdem hat deine Antwort auch nicht miene Frage beantwortet.

    0
  • ?

    Du hast keine Frage gestellt. Nur dargelegt, dass deine KI schlecht ist.

    Wie bewertest du denn offene Positionen? Was bedeutet Recursionstiefe 8? Und wieviel Rechenzeit benoetigt er dafuer?

    0
  • T

    Rekursionstiefe ist eben die Tiefe, wie oft die Funktion sich selber aufruft.
    Also denkt die KI 8 Züge im Vorraus.
    Ich habe im Moment nur eine Bewertung fürs Gewinnen drinne, was vollkommen ausreichen sollte, wenn der Minimax richtig programmiert wäre.
    (KI gewinnt +9999, Gegner gewinnt -9999).
    Rechenzeit ist bei Rekursionstiefe 8 ziemlich lang(bei den ersten Zügen so um die 10 Sekunden, die Zeit geht aber schnell runter [weil das Spielfeld gefüllter ist])

    mfg

    0
  • ?

    Und was passiert, wenn nach 8 Zuegen noch keine eindeutige Gewinnposition erreicht wurde?

    0
  • J

    Deine KI spielt optimal, sobald sie einen Sieg sieht und sie tappt nicht in einfach Fallen, die sich mit etwas voraussicht vermeiden lassen. Jedenfalls wenn Dein minimax korrekt implementiert ist.

    Aber abseits dieser beiden Fälle spielt die KI mehr oder weniger zufällig. Sie hat keine Idee welcher Aufbau vielleicht in 10 Zügen gut sein könnte. Und genau das mußte ihr so noch mitgeben. Benachbarte Steine, die sich zumindest theoretisch noch zu einem 4er ergänzen lassen sind gut und ähnliches.

    0
  • T

    Naja das Problem ist, dass sie auf sehr einfache Fallen reinfällt...
    Hier ein Beispiel: (X==KI;O==Spieler)

    -- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- O  -- -- --

-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- X  -- -- --
-- -- -- O  -- -- --

-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- X  -- -- --
-- -- 0  O  -- -- --

-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- X  -- -- --
-- -- -- X  -- -- --
-- -- 0  O  -- -- --

-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- X  -- -- --
-- -- -- X  -- -- --
-- O  0  O  -- -- --

-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- X  -- -- --
-- -- -- X  -- -- --
X  O  0  O  -- -- --

-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- -- -- -- --
-- -- -- X  -- -- --
-- -- -- X  -- -- --
X  O  0  O  0  -- --

    Und das kann ja nicht Sinn und Zweck sein, denn das ist wohl der einfachste "Trick" überhaupt bei dem Spiel

    0
  • ?

    Tust du denn in jedem Knoten abfragen, ob eine Gewinnstellung vorhanden ist??? Denn nur am Suchhorizint eine die Stellungsbewertung aufzurufen bringt da nicht viel?? Tu vllt. mal den Code ein wenig kommentieren, damit man nachvollziehen kann, was die einzelnen Teile bezwecken sollen...

    0
  • ?

    Naja, bei der Tiefe 8 wird er sowieso nicht besonders stark spielen. Normalerweise dürfte es doch nicht so schwer sein das Spiel komplett durchzurechnen, das ist doch schließlich ein ziemlich triviales Spiel. Such doch mal Alpha-Beta-Algorithmus, Zugsortierung, Hashing. Damit kann man locker ein starkes Programm schreiben.

    0
  • K

    http://www.connectfour.net/Files/connect4.pdf

    Masterthesis fuer geloestes Connect 4.

    0
Anmelden zum Antworten