KI-Einstieg - Hilfe bei erstem Einsatz - Seite 3 - Eingabe, Audio, Physik, Netzwerk, Scripting und KI

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

21

17.05.2012, 13:18

Hi ich bins wieder.

Für das Beispiel Tic tac Toe, bei dem ich den Algorithmus im moment am Austesten bin:

Hab ich das so richtig verstanden?

(Link)

Also die Zahlen bedeuten einfach, azf welches feld gesetzt wurde und wenn ich dann bis zum Schluss durchgeganmgen bin
und jede Situation dann bewertet hab, kann ich den besten weg rausfinden.

Richtig?

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Zum Seitenanfang

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

22

17.05.2012, 13:21

Außerdem finde ich, (jetzt kommt Aufruf an David), dass zu diesem Algorithmus eine Seite in unserem Wiki sehr passend wäre!

Kann bestimmt viele helfe und es würde das noch bis jetzt noch sehr lichte Angebot an Seiten des Wiki's erhöhen.

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Zum Seitenanfang

Informagic

Frischling

Beiträge: 52

23

17.05.2012, 13:43

Minimax-Algorithmus

Ich kann dir zum Verständnis des Minimax-Algorithmus und Alpha-Beta-Pruning hier ein wunderbares Video empfehlen:
http://www.youtube.com/watch?v=SO-oXQgvJt4
Das habe ich geschaut, bevor ich mal eine KI für "Vier gewinnt" geschrieben und darüber in der Schule einen Vortrag gehalten habe. Das Video ist zwar eine Stunde lang, aber über Minimax erzählt der lustige Inder eigentlich nur bis ca. 22:00. Danach geht er in Pruning-Geschichten rein (also Optimierungen, die den Algo schneller machen) und am Schluss noch irgendwas anderes, man muss auch nicht alles anschauen. Auf jeden Fall hab ich Minimax nach diesem Video das erste Mal so richtig verstanden. Programmieren lassen sich diese Bäume dann rekursiv.

In deinem Fall würde ich die Bewertung nach Punkten konkret vielleicht einfach so vornehmen: Wie David es schon sagte, legst du ein Raster an (im Optimalfall, wenn die Berechnung des Zuges dann noch performant genug ist, ist der Abstand zwischen zwei Rasterpunkten so groß, wie die Autos in einem Frame kommen), und gibst für die drei Möglichkeiten, zu fahren, in jedem Zug einfach die Anzahl der Rasterpunkte an, auf die es nach diesem Zug noch möglich wäre, zu fahren (von der man vielleicht noch die Rasterpunkte des Gegners abziehen könnte). Das ist alles. Wenn du diese Zählung effizient genug programmierst und das Raster nicht allzu fein machst, kannst du mit Alpha-Beta-Pruning dann einfach sehr weit rechnen und die KI wird automatisch immer gute Züge machen. Denn dann wird sie einfach durch stumpfes Ausprobieren automatisch herausfinden, wie sie sich selbst Freiräume behält und die der Gegner kleiner macht.

Wenn du noch fragen hast, beantworte ich sie gerne. Ich denke, ich kenne mich damit noch ganz gut aus.

Zum Seitenanfang

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

24

17.05.2012, 13:48

Ok danke werde mir das Video angucken und werde auch bestimmt nochmal auf dich zurück kommen!

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Zum Seitenanfang

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

25

18.05.2012, 12:22

Hi

Hab bevor ich das Video geguckt hab gedacht, ich hätte es verstanden, aber jetzt hab ich wirklich auch den Sinn verstanden!

Da ich noch nie vorher, solche "Bäume" programmt hab, wollte ich jetzt einfach mal die grunddtruktur machen und die bewerten-Funktion und
andere Sachen des Algorithmus.

Ich hab das so gemacht, dass ich ein structur für den Baumnode gemacht hab, die, wenn die kein Endknoten ist, ein vector mit Zeigern auf seine Child-knoten hat.
Außerdem hab ich auch eine struktur für das Spielfeld gemacht, worin der status des Spielfelds gespeichert ist.
Davon hat jeder node auch ein Element.
Das erstellen hab ich dann rekursiv gemacht und ich hab eine Funktion zum Anzeigen des jeweiligen Spielfeldes geschrieben, die auch rekursiv ist:

C-/C++-Quelltext

void Node::ShowField ()
{
    for(int x=0; x<nChilds.size(); x++)
        nChilds[x]->ShowField(); // Hier ist dann der felder!!!!

    cout << endl;
    for(int x=0; x<3; x++)
    {
        cout << "    ";
        for(int y=0; y<3; y++)
        {
            if(mField.mField[x][y] == 0)
                cout << "_ ";
            else if (mField.mField[x][y] == 1)
                cout << "O ";
            else if (mField.mField[x][y] == 2)
                cout << "X ";
        }
        cout << endl;
    }
    cout << endl;
};

Wenn ich jetzt, bevor der fehler kommt, im debug modus mir die Felder der einzelnen Childs des Rootknoten angucke,
stimmen sie mit dem überein, wie sie sein sollten.
Wenn ich aber dann rekursiv in die Funktion reingehe und dann in der ShowField() des ersten Childs mir die Felder aller anderen knoten angucke,
sind diese mit unglaublich hohen Werten definiert, als wären sie gar nicht definiert!

Mir is jetzt aufgefallen, dass das daran liegt, dass ich immer nur Zeiger auf die Childs speichere und wenn ich keine Zeiger speichern,
funktioniert es.

Woran liegt das?
Und gehe ich richtig vor mit dem "Baum"?

EDIT: Hab noch eine Frage:
Ich weiß nicht genau, wie ich die Bewerten-Funktion implementieren soll.
Ich wollte für jedes Kreuzchen (ich), was allein in einer Reihe ist, 1 Punkt geben.
Wenn zwei kreuzchen in einer reihe sind, 5 Punkte.
und wenn 3 kreuzchen in einer Reihe sind, 20 Punkte.
und für die Kreise natürlich dann Minuspunkte.

Teorethisch kann man das ja noch verbessern später.
Und soll ich, wenn zwei Childs die Selbe Punktzahl haben, nach dem Zufall entscheiden oder für den Anfang erst mal einfach alle Durchgehen und immer testen,
ob die bisherige höchspunktzahl überschritten wurde?

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »ProAmateur« (18.05.2012, 13:18)

Zum Seitenanfang

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

26

19.05.2012, 11:35

Also ich hab jetzt komplett hinbekommen

Auch wenn ich nicht gedacht hab, dass ich es schaffe!
Klappt gut.

Wäre sehr dankbar, wenn sich jemand dazu bereit erklären würde, meinen Code mal durchzugucken
und gegebenenfalls zu verbessern und Tipps zu sagen.
Würde ihn auch so ändern, dass er auch von anderen verständlich ist

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Zum Seitenanfang

Informagic

Frischling

Beiträge: 52

27

27.05.2012, 14:54

Ok sry dass ich erst so spät antworte, aber ich bin nicht regelmäßig in dem Forum und war im Urlaub.

Wie weit bist du jetzt eigentlich? Brauchst du noch Hilfe? Wie gut ist die Tron KI? Bist du zufrieden damit? Und das mit der Funktion zum Anzeigen eines TicTacToe-Feldes hatte jetzt wenig damit zu tun, oder?
Wie gesagt, für die Rating-Funktion für Tron hätte ich jetzt erstmal das Simpelste ausprobiert, was geht: Ich hätte als Punkte die Anzahl der verbleibenden Kreuzpunkte im Gitter vergeben, auf die es nach aktuellem Stand noch möglich ist, zu fahren, und davon die möglichen Rasterpunkte des Gegners abgezogen. Dann wird die KI immer betrebt sein, möglichst viele Rasterpunkte für sich selbst zu behalten, auf die sie später mal fahren kann, und die Fahrmöglichkeiten des Gegners zu beschränken.

Zum Seitenanfang

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

28

27.05.2012, 17:07

Nicht schlimm!
Wie wars denn da

Also ich hab den Algorithmus jetzt für das TicTacToe Spiel programmiert; funktioniert
auch gut (bis auf manchmalige Ausnahmen, wo er noch relativ wenig intelligent entscheidet).

Bevor ich jetzt anfange das auf mein tron zu übertragen, hab ich noch Fragen zum TicTacToe.
In dem Video, welches mir ja hier empfohlen wurde, gab es zwei Möglichkeiten.
Entweder man bewertet die verschiedenen Felder oder man gibt nur an, ob es ein WinNode oder ein LoosNode ist.

Da ich ja bei TicTacToe eig von der Performance her sehr weit gehen kann, würde es sich hier doch anbieten nur
Win/loose Nodes zu machen, oder? Obwohl ich jetzt schon auf Bewerten-Basis gemacht hab

Ich merke aber auch, dass das ganze ganz schön aufwendig ist.
Gibt es eine Möglichkeit, diese Berechnungen nachher von der GraKa übernehmen zu lassen?
Bei dem ersten Setzen, wo er ja noch 8 vers, möglichkeiten jeweils durchgehen muss, dauert es relativ lange,
aber danach geht es schnell.
Ich mein er muss ja beim ersten mal 9! verschienden Möglichkeiten testen und dann beim 2 mal setzen ja schon nur noch 7!.
Das is ja ein Unterschied!

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Zum Seitenanfang

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

29

27.05.2012, 18:20

Dafür gibts dann Alpha-Beta Pruning.
@Informagic:
Deine Bewertung kann er aber genau bei diesem Algorithmus benutzen. Dort wird ja mit einer Bewertungsfunktion gearbeitet. Diese sieht halt von Fall zu Fall verschieden aus aber der Grundsätzliche Algorithmus bleibt eigentlich der selbe. Und darum ging es ja. Das allgemeine Verständnis zu bekommen. Hinterher eine Bewertungsfunktion zu überlegen ist dann eh mit viel testen verbunden.

„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Zum Seitenanfang

ProAmateur

Alter Hase

Beiträge: 434

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

30

27.05.2012, 19:32

Ich bin mir halt noch nit sicher, ob ich das so gut geschrieben hab und ob das alles so stimmt.
Schorsch: Würdest du dir vll mal n bisschen zeit nehmen und in meinem Code gucken?
fals er zu "Schwierig" (nicht von Programmiertechnichen, sondern von meiner ordentlichkeit) ist,
kann du auch sagen,d ass es zu schwer ist.
Aber das wäre mir echt mal wichtig!
Verscuhe ihn auch so gut wie es nutr geht zu kommentieren!

"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Zum Seitenanfang

spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

KI-Einstieg - Hilfe bei erstem Einsatz

Minimax-Algorithmus

C-/C++-Quelltext

Ähnliche Themen