• Announcements

    • Lars

      Allgemeine Forenregeln   03/13/2017

      Forenregeln Nimm dir bitte einen Moment um die nachfolgenden Regeln durchzulesen. Wenn du diese Regeln akzeptierst und die Registration fortsetzen willst, klick einfach auf den "Mit der Registrierung fortfahren"-Button. Um diese Registration abzubrechen, klick bitte einfach auf den "Zurück" Button deines Browsers. Wir garantieren nicht für die Richtigkeit, Vollständigkeit und Brauchbarkeit der Nachrichten und sind auch nicht dafür verantwortlich. Die Beiträge drücken die Meinung des Autors des Beitrags aus, nicht zwangsläufig das, wofür die Forensoftware steht. Jeder Nutzer, der denkt, dass ein veröffentlichter Beitrag unzulässig bzw. störend ist, ist aufgefordert uns unverzüglich per E-Mail zu kontaktieren. Wir haben das Recht störende Beiträge zu löschen und bemühen uns, das in einem realistischem Zeitraum zu erledigen (sofern wir beschlossen haben, dass die Löschung notwendig ist). Du akzeptierst, durchgehend während der Nutzung dieses Services, dass du dieses Forum nicht dazu missbrauchen wirst, Inhalte zu veröffentlichen, welche bewusst falsch und/oder verleumderisch, ungenau, beleidigend, vulgär, hasserfüllt, belästigend, obszön, sexuell belästigend, bedrohlich, die Privatsphäre einer Person verletzend oder in irgend einer Art und Weise das Gesetz verletzen. Des Weiteren akzeptierst du, dass du keine urheberrechtlich geschützte Inhalte ohne Erlaubnis des Besitzers in diesem Forum veröffentlichst. Mit dem Klick auf den "Mit der Registrierung fortfahren"-Button, akzeptierst du zudem unsere Datenschutzerklärung und stimmst der Speicherung deiner IP-Adresse und personenbezogenen Daten zu, die dafür benötigt werden, um dich im Falle einer rechtswidrigen Tat zurückverfolgen zu können bzw. permanent oder temporär aus dem Forum ausschließen zu können. Es besteht keine Pflicht zur Abgabe der Einwilligung, dies erfolgt alles auf freiwilliger Basis.   Zusatzinformationen Der Forenbetreiber hat das Recht, Nutzer ohne Angabe von Gründen permanent aus dem Forum auszuschließen. Des Weiteren hat er das Recht, Beiträge, Dateianhänge, Umfrage, Blogeinträge, Galleriebilder oder Signaturen ohne Angabe von Gründen zu entfernen. Mit der Registrierung verzichtest du auf alle Rechte an den von dir erstellten Inhalten, bzw. treten diese an das Unity-Insider.de und Unity-Community.de ab. Dies bedeutet im Klartext, dass das Unity-Insider.de und Unity-Community.de frei über deine Texte verfügen kann, sofern diese nicht wiederum die Rechte anderer verletzen. Es besteht weiterhin kein Anspruch von registrierten Nutzern bzw. ehemaligen registrierten Nutzern darauf, dass erstellte Inhalte und/oder die Mitgliedschaft (User) wieder gelöscht werden (Erhaltung der Konsistenz dieses Forums).   Einwilligungserklärung Wenn du mit der Speicherung deiner personenbezogenen Daten sowie den vorstehenden Regeln und Bestimmungen einverstanden bist, kannst du mit einem Klick auf den Mit der Registrierung fortfahren-Button unten fortfahren. Ansonsten drücke bitte Zurück. Stand: 07.03.2011
Sign in to follow this  
Followers 0
Kokujou

Optimiertes Erstellen eines großen Suchbaums

32 posts in this topic

Yo!

Ich bin gerade beim Thema KI und will einen Suchbaum entwickeln für ein Kartenspiel. Es geht über 8 Runden und da dachte ich mir das klingt ja nicht so viel. Aber 8!^2 ist immer noch über eine Milliarde.

Aktuell benutze ich Multithreading in der Form, in jedem Zug jeder Folgezug in einem eigenen Thread gerechnet wird, zusätzlich muss ich leider die Threads begrenzen, damit Unity nicht crasht. Und ich wollte fragen ob es nicht irgendeine Möglichkeit gibt das ganze prozedere noch weiter zu beschleunigen. Ansonsten würde es wohl etwa 10 Tage dauern den Suchbaum zu erstellen. Wenn man es wenigstens auf 24 Stunden reduzieren könnte, könnte ich den Baum einmal aufbauen und dann speichern.

 

Share this post


Link to post
Share on other sites

Die Anzahl der Threads begrenzen (Threadswitches/Contextswitches könnten wenn du es mit den Threads übertreibst dafür sorgen dass ein Switch mehr Zeit in Anspruch nimmt als die Threadausführung selbst).

ReaderWriterLockSlim verwenden anstatt lock

Locks wenn möglich ganz vermeiden. Nichts muss gelockt werden wenn keine Teilen des Speichers verwendet wird.

Locks minimieren -> Divide & Conquer

Datenstrukturen so wählen dass sie Speichereffizient sind.

Den Profiler verwenden um Engpässe aufzudecken.

Share this post


Link to post
Share on other sites

Wie könnte ich die Threads denn verringern? Aktuell führe ich ja einen Thread pro Knoten aus. man hat bei mir 8 mögliche Züge also sind es im 1. Zug 1 Thread, danach 8, dann 64, dann 64*7, 64*7^2 etc... also komme ich am Ende auf 8!^2+1 threads. Aber mir schien es die sinnvollste Lösung weil ja wirklich alle Threads gleichzeitig gerechnet werden müssen.

Ich hab sie auch schon auf 10.000 begrenzt und gesagt, wenn mehr als 10.000 threads aktiv sind warte bis die anderen fertig sind und rechne dann weiter. Weil Unity ja ein Limit an Threads hat, aber das ist wohl nicht was du meintest.

Das mit dem ReadWriterLockSlim werde ich sofort probieren!

Aber Locks habe ich eigentlich nur an dem Punkt, wo die Daten in den Baum eingetragen werden. Weil der Suchbaum ja global sein muss und alle Threads ihre werte eintragen müssen. Zwar an verschiedenen Stellen aber das würde trotzdem zu Fehlern kommen.

Wäre es für dich hilfreich Codeausschnitte zu sehen?

Share this post


Link to post
Share on other sites

Es kommt darauf an, was du in jedem einzelnen Thread berechnest. Oft kann man beispielsweise 10 Rechenschritte (die du gerade in 10 Threads machst) in einem Rechenschritt zusammenfassen, dabei hat man dann statt 1000 Threads nur noch 100 etc.
Wenn du es mit der Anzahl der Threads übertreibst, wird die Berechnung auf einer CPU deutlich langsamer als ohne Threads. Deine CPU hat nur X Kerne und darauf müssen sich die Threads verteilen, soll heißen wenn deine CPU beispielsweise 8 Kerne hat können nur 8 Threads tatsächlich nebenläufig arbeiten, alle anderen Threads arbeiten dann sowieso wieder sequentiell. Meist ist eine leicht erhöhte Anzahl von Threads in Relation zu den tatsächlichen Prozessorkernen noch sehr sinnvoll. Beispielsweise wenn deine CPU 8 Kerne hat können 16 Threads sehr gut "bedient" werden. Sollte deine Rechenoperation pro Thread relativ einfach sein (und sich der Algorithmus sehr gut in nebenläufige Rechenschritte zerlegen lassen), dann wäre ein Compute Shader sehr sinnvoll, da die GPU viel nebenläufiger arbeiten kann als eine CPU (da sie viel mehr "Recheneinheiten" besitzt).

Zusammenfassend solltest du dir eine maximale Anzahl an Threads setzen (sozusagen einen Threadpool) und diese Anzahl nicht überschreiten. Die Berechnung des Baumes wird dann auf diese Threadanzahl "heruntergebrochen".

Share this post


Link to post
Share on other sites

Wenn du verschiedene Stellen hast wieso ist es denn dann ein Problem wenn da was eingetragen wird? Wenn das Problem das ist dass du irgendwo Add machen musst, dann kannst du dir eventuell die Datenstrukturen oder gar den Baum schon voroptimieren, wie genau müsstest du selbst herausfinden ;)

 

Um die Anzahl der Threads zu limitieren erstelle einfach nur eine begrenzte Anzahl an Threads, zB 1 Thread pro CPU Kern, gebe diesen Threads dann einfach vereinzelte Aufgaben (Berechne X) welche nacheinander abgearbeitet werden. Dafür eignen sich Tasks. Die mMn so nicht in Unity funktionieren, aber man kann sich ein kleines Tasksystem ja schnell selbst bauen.

 

Erstelle X Threads.

Pro Thread:

  Solange nicht abgebrochen:

    Warte bis vorhandensein von Aufgaben signalisiert wurde

    Thread nimmt sich aus gelocktes Set Y eine Aufgabe und verarbeitet diese

 

Wenn nötig füge Aufgabe in gelocktes Set Y, signalisiere vorhandensein von Aufgaben

 

Was für Codeausschnitte hättest du denn gerne?

Share this post


Link to post
Share on other sites

Die Frage war ob ich EUCH einen Codeausschnitt zeigen sollte.

 

Es ist vielleicht sinnvoll mal etwas zu zeigen damit ihr seht, was ich machen will. Erstmal ne kleine Einfuhrung: es geht um Hanafuda. Jeder Spieler hat 8 Karten, das Feld hat ebenfalls 8 Karten. Das Spiel selbst hat 4x12 Karten, 12 Monate mit je 4 Karten. Man paart Karten von der Hand mit Karten vom Feld und fügt sie seiner Sammlung hinzu. Heißt es gibt nur exakt 8 Runden mit je 2 Spielzügen.

Jetzt zur Praxis: der StateTee ist vom Typ List<List<State>>, ich füge 16 leere Ebenen inklusive dem Startzustand hinzu, Dann gehe ich jede Ebene durch und erstelle dann für jeden enthaltenen Zustand Folgezustände deren Anzahl der der verbleibenden Handkarten des aktiven Spielers entspricht. Nachdem die Ebene durch ist muss ich erstmal warten (ich benutze übrigens Threading.Thread und nicht Task weil... naja Unity eben) bis alle Threads fertig sind. Alle Threads trage ich in einer Liste ein und lösche sie immer nachdem alle fertig sind. So kann ich sie auch auf x Threads beschränken.

while (threads.Count > 10000)
	for (int i = 0; i < threads.Count; i++)
		if (i == threads.Count - 1 && !threads[i].IsAlive)
			threads.Clear();

Jetzt dazu was passiert um einen zustand zu berechnen, also das was in den einzelnen Threads läuft:

State parent = StateTree[level][node];
if (!parent.isFinal)
{
	List<Card> aHand = Turn ? parent.PHand : parent.KIHand; //Hand des SPielers/Gegners
	for (int i = 0; i < aHand.Count; i++)
	{
		List<Card> matches = new List<Card>();
		for (int j = 0; j < parent.Feld.Count; j++)
		{
			if (parent.Feld[j].Monat == aHand[i].Monat)
				matches.Add(parent.Feld[j]); // Passende Karten auf dem Spielfeld
		}
		if (matches.Count == 2)
		{//Zug Anwenden und zur Liste hinzufügen undzwar für beide möglichen Optionen
			for (int choice = 0; choice < 2; choice++)
			{
				Move move = new Move(new List<Card>() { matches[choice] }, aHand[i]);
				State child = new State(parent, move, Turn);
				StateTree[level + 1].Add(child);
			}
		}
		else
		{ // Zug anwenden aber nur für eine Option
			Move move = new Move(matches, aHand[i]);
			State child = new State(parent, move, Turn);
			StateTree[level + 1].Add(child);
		}
	}
}

 

PS: Ist es vielleicht Sinnvoller die Tiefenkonstruktion zu bevorzugen? Wenn ihr euch den Suchbaum als Matrix vorstellt erstelle ich ja eine Zeile nachd er anderen. Wäre es sinnvoller vielleicht eine Reihe nach der anderen zu erstellen? Oder fällt euch sonst eine Form der Optimierung ein?

Share this post


Link to post
Share on other sites

Aber wenn ich das überfliege braucht man dafür immernoch einen Suchbaum. Ich bin neu in Sachen KI und versuche es daher mit 3 verschiedenen Ansätzen.

1. will ich einen kompletten Suchbaum aufstellen, um dann gezielt nach Zielzuständen suchen zu können und diese zum Ziel für meine KI zu machen.

2. Will ich eine statische Lernformel entwickeln mit der jeder Zustand bewertet wird. Ich glaube das wäre dann sogar etwa diese MinMax Thematik oder?

2a. Beim der ersten Version sollen alle Karten die nicht aufgedeckt sind statistisch ermittelt werden, sodass man eine gewisse Unsicherheit dabei hat und die KI agiert wie ein richtiger Spieler

2b. Beim zweiten Mal sollen dann sämtliche zugedeckten Karten bekannt sein.

Das ganze entspricht dann den Schwierigkeitsstufen leicht - normal - schwer.

 

Apropos geht es beim Performance sparen ja nicht wirklich um die Suche, was natürlich auch nicht unwichtig ist, aber vor allem geht es um die Konstruktion. Bei der Suche spart man schon enorm viel Zeit indem man weiß in welcher Ebene ist und welchen Zug man wählt. Deswegen hab ich das ganze als Matrix angeordnet.

Share this post


Link to post
Share on other sites

Ok, deine Denkweise ist korrekt und die Bewertungsmethode/Lernformel ist genau der MinMax Ansatz.

Was du allerdings falsch verstehst ist wie man einen Suchbaum aufbaut. Was viele Leute als "aufbauen" bezeichnen ist nichts weiter als der Programmfluss vom Algorithmus.

 

public void Suchbaum(Problem p)
{
	foreach(var action in p.GetActions())
		Suchbaum(p.ApplyAction(action));
}

Was macht der Code? Er geht durch jede Action und ruft sich rekursiv auf. Das ist Tiefensuche, wie du bereits erwähnt hast. Hier wird nur Methaphorisch ein Baum aufgebaut, es existiert aber niemals wirklich eine Datenstruktur Baum.

public void Suchbaum(Problem problem)
{
	Stack stack = new Stack();
	stack.Add(problem.InitialState());

	while(stack.IsNotEmpty())
	{
		var newStates = problem.GetNewStates(stack.Pop());
		stack.AddRange(newStates);
	}
}

Was macht der Code hier? Er generiert "Zweilenweise" alle neuen Zustände. Das nennt man Breitensuche. Auch hier wird ein Suchbaum aufgebaut, allerdings stellt man sich den auch hier nur wieder vor.

 

Der oben gezeigte Code dient nur als Beispiel. Ich bezweifle das der auch nur ansatzweise funktioniert.

Share this post


Link to post
Share on other sites

Nunja das ist ja auch mein Code. Mehr oder weniger. Aber man brauch doch eine tatsächliche Datenstruktur dafür denn die Informationen müssen ja rigendwo stehen damit man darin suchen kann.

Am Ende muss man doch auf die Züge der Gegner reagieren. Was ist sonst der Fall, willst du jedes mal den kompletten Suchbaum aufbauen wenn eine Aktion dran ist?

Oder war dein Rat jetzt eher die Tiefensuche zu bevorzugen?

Und am Ende hast du ja auch den Stack angelegt. Ich meine warum die Datenstruktur nicht aufbauen? Das frisst doch höchstens Festplatten oer allerhöchstens Arbeitsspeicher. Und das auh nur höchtens im Megabyte bereich.

Share this post


Link to post
Share on other sites

Üblicherweise Minimax mit alpha Beta pruning. Du wirst anfangs nicht bis zum Ende rechnen können, da es zu lange dauert und wirst somit wohl eine  Methode finden müssen eine Bewertungsfunktion zu definieren, die dir eine Tendenz anzeigt wie nahe am gewinnen/verlieren der jeweilige Spieler ist.

Wenn die Anzahl der Möglichkeiten gegen Ende weniger wird in deinem Spiel wirst du vielleicht nachher die Tiefe ändern können, so dass du im Spielverlauf dann bis zum Ende rechnen kannst.

Das wären die normalen Lösungsansätze für so ein Spiel und eine "optimale" Spiele KI. Schwierigkeitsgrade sind natürlich dann nicht mehr drin, weil man immer davon ausgeht, dass die Spieler die beste Lösung wählen.

Für mich war hierbei die Evaluationsfunktion das schwerste. Für jeden Spielstatus muss man halt berechnen können wie gut das ist. Das ist schon bei 4 Gewinnt nicht einfach und hängt natürlich arg vom Spiel ab.

Share this post


Link to post
Share on other sites

Darum habe ich ja ein sehr unkomplexes Spiel gewählt. Mein erstes Spiel mit KI war schach das hat auch gut geklappt mit der Bewertungsfunktion und das obwohl ich nur die Suchtiefe 1 benutzt habe. Jetzt bin ich in der Komplexität etwas runtergegangen.

Ich meine das Spiel hat nur 8x2 Spielzüge, MAXIMUM. das kann doch eigentlich nicht so schwer sein oder? Und man würde den Baum ja auch nocht zur Laufzeit erstellen. Aber es wäre sinnvoll die Laufzeit wenigstens auf 24 Stunden runterzubrechen, damit ich den Baum über Nacht in eine Datei schreiben kann, diese am Anfang des Spiels laden kann und so dann ein schönes Suchproblem anwenden kann.

Wobei jetzt wo ich das so sage klingt das Prinzipiell sehr gut aber ich hab leider total vergessen dass der Spielfeldaufbau ja zufällig ist und nicht konstant womit dieser Ansatz am Ende wirklich hinfällig ist. Verdammt.

Trotzdem es geht ja bei der Sache auch darum etwas zu lernen. Ich hab euch ja jetzt den fraglichen Code gezeigt fällt euch irgendeine Möglichkeit ein die Laufzeit dieses Alogirthmus zu zehnteln?

Share this post


Link to post
Share on other sites

Ich kann dir nicht direkt viel zu deinem Code sagen, aber prinzipiell hast du folgende (Performance)Probleme:
a- die Bewertung des aktuellen Zustandes
b- die optimale Speicherung eines Zustandes
c- eine optimale Datenstruktur für alle möglichen Zustände (beispielsweise Baum)
d- Zusammenfassung der Bewertungen der einzelnen Zustände je Baumzweig

An jedem dieser 4 Baustellen kann man nun Optimierungen vornehmen.
a.)
Möglichst wenig Rechenschritte (Instruktionen) für die Ermittlung / Bewertung eins Zustandes. Verwendung von möglichst einfachen (schnellen) Rechenoperationen.
Die Berechnung von 16 Zuständen kannst du nun beispielsweise auf 16 parallele Threads auslagern. Bei mehr Zuständen müssen diese Threads geshared werden (Pooling).
b.)
Möglichst effiziente Speicherung eines Zustandes (beispielsweise binäre oder komprimierte Speicherung). Das Auslesen und Schreiben eines Zustandes sollte möglichst performant sein, d.h. wiederum wenig Instruktionen zum Schreiben und zum Lesen eines Zustandes.
c)
Möglichst performante Datenstruktur für die Speicherung der einzelnen Zustände. Hier beispielsweise die Verwendung eines Binärbaumes oder ähnlichen Struktur für den schnellen Zugriff auf die Zustände und eine schnelle Speicherung.
d.) Hier kenne ich mich zu wenig aus, aber die denke es ist mehr oder weniger ebenfalls eine Baumstruktur die die Gesamtbewertungszustände je Knoten enthält., d.h. die Teilknoten einen Knotens erzeugen eine Bewertung und diese werden rekursiv nach oben durchgereicht und "aufakkumuliert".

Zusammenfassend denke ich der Algorithmus geht nun vom Baum-Rootknoten von links nach recht die Teilknoten durch und verwendet dabei den Threadpool für die Bewertung der einzelnen Zustände, er speichert dabei jeweils eine Gesamtbewertung je Rootknoten, diese kann theoretisch weiter verfeinert werden, wenn der Algo tiefer hinabsteigt.
Natürlich muss ab einer gewissen Baumtiefe (Abbruchgedingung Baumtiefe) die Berechnung abgebrochen werden, damit der Algorithmus auch die anderen Knoten noch bewerten kann (jeweils immer von links nach rechts).
Soviel von mir, ich muss allerdings dazusagen, ich habe mich noch nicht im Detail damit beschäftigt. Es sind nur Ideen, wie ich die Sache angehen würde. Und man kann her sehr viel optimieren, aber man arbeitet immer nur mit einem fixen Theadpool (beipielsweise 16 Threads) und diese werden auf die jeweils durchzuführenden Berechnungen aufgeteilt.

Share this post


Link to post
Share on other sites

Oh man... die Bewertung des Zustands ist aktuell noch nichtmal im Algorithmus enthalten. Ich steh noch ganz am Afnang damit krieg ichw arscheinlich nochmal +10 tage. Obwohl die Bewertung ja nicht unbedingt amBaum gemacht werden muss das heißt nicht sofort bei erstellung. Nimmt man die Suchproblematik sucht man ja eigentlich nur nach Endzuständen und weniger nach dem mit den meisten Punkten. DBei dem Spiel kann ich mir was das angeht eine komplexe Bewertungsfunktion sparen aber hier gehts ja auch ums allgemeine also yo..

Aber das führt mich zu ein paar Fragen.
zu b.: Sind Evaluationen sinnvoll in Datenstrukturen? Was ist mit Listen? Lieber Listen oder Arrays? und was ist mit vordefinierten funktionen oder Linq Erweiterungen? Sollte man sie benutzen oder lieber vermeiden. Sowas wie Find, Exists, Cast<> ...

zu c.: Was würdet ihr für eine Datenstruktur vorschlagen wenn man einen Baum eines selbstdefinierten Typs haben will? Spontan fallen mir nur Array und Listen ein, aber es gibt bestimmt auch spezielle Baum Datenstrukturen. Diese müssten aber generisch sein.

zu d.: heißt das du schlägst vor in einer Datenstruktur sämtliche Zustände unterzubringen und in einer anderen nochmal separat die Bewertungen? wäre es nicht viel klüger das alles in einer zu kombinieren und die Bewertung in der Klasse unterzubringen die man für einen Zustand gewählt hat?

Zuletzt möchte ich in dieser Diskussion noch ein Thema ansprechen dass mich persönlich am meisten fertig macht und das ist dieses Chaos mit Referenzen und Werten. Ich weiß nie wann in meinem Algorithmus nun der tatsächliche Wert oder nur eine Referenz übergeben wird. Ich komm auch immer ins grübeln darüber wann es Sinnvoll wäre die Referenz zu übergeben um nicht kopieren zu müssen.
Ein Beispiel: Bei meinem Schachspiel habe ich in der Klasse für Spielfiguren ja auch deren Position auf dem Spielfeld hinein geschrieben und diese dann verständlicherweise verändert. Dafür musste ich aber unbedingt den Wert übergeben was dazu folgt dass ich  jede einzelne verdammte Figur in jedem Knoten völlig neu erzeugen m musste. Das frisst natürlich enorm viel Zeit. Ich hatte auch zuerst den Ansatz mit der DeepCopy aber da in den Klassen auch andere Klassen und Referenzen auf meinen suchbaum waren habe ich die ja auch gleich mitkopiert und mir so meine Laufzeit noch mehr zerschossen.

Kurze Anmerkung zu meiner Motivation: Meine Bachelorarbeit behandelte oberflächlich das Thema KI und es ist klar im Schach einen Zustandsbaum aufzustellen ist unmöglich. Aber weil ich das da nicht geschafft habe wollte ich diesmal wo es ja deutlich überschaubarer ist, es hinkriegen um in meiner Masterarbeit etwas neues anzubringen. Leider schaff ich es jetzt hier nichtmal üüber 3 spielzeuge hinaus. Bei Schach hab ich es irgendwann mal auf 7 Züge gebracht, was komisch ist da es da eigentlich viel mehr Spielzüge gibt auch in den ersten Runden besonders.

Und jetzt noch ein letzter Punkt: Was meint ihr zum Thema maschinelles Lernen? Könnte man das irgendwie unterbringen? Ich hab ja praktisch den "statischen" Ansatz indem ich eine Bewertungsfunktion selbst aufstelle, aber dort die Gewichte mit einer Fehlerfunktion anzupassen dazu müsste ich unzählige Spiele durchzocken undd das könnte wieder viel Laufzeit fressen besonders weil man ja 1000+ Iterationen braucht um zum Ziel zu kommen.

Share this post


Link to post
Share on other sites

Irgendwie versteh ich das Problem nicht. Warum willst du das komplette Spiel in irgendeiner Datenstruktur festhalten was genau bringt dir das?

Den Code den ich dir gezeigt habe kann man ja ganz leicht erweitern, einfach Bewertungsfunktion einbauen, Zieltest etc..

Was du versuchst ist wenn das Spiel beginnt alle möglichen Züge zu generieren. Und was dann? Was machst du mit den Zügen, du wirst niemals genug Zeit haben alle zu generieren. Selbst wenn du die Zeit dafür hast musst du dann nochmal über alle drüberlaufen und auswerten. In dem Fall wirst du aber niemals alle auswerten können d.h du hast wieder viel zu viel generiert.

Ich habe mal ein Programm geschrieben was ganz Simpel ein Schieberätsel lösen kann und zwar exakt mit diesem Ansatz. Dafür habe ich niemals eine Datenstruktur Baum benötigt weil diese bereits implizit generiert wird.

 

Wenn du wirklich eine Datenstruktur Baum haben willst dann gibt es da haufen Ansätze: Balancierte-Bäume (B-Baum, AVL-Baum), Binäre Bäume, selbst Heaps sind nichts weiter als Bäume. Die Bäume nutzt man aber nicht dazu irgendwelche Probleme zu lösen sondern schnell nach Daten zu suchen. Heaps suchen schnell nach dem größten Wert, Binäre Bäume finden in O(Log(n)) irgendwelche Werte, B-Bäume werden dazu genutzt um effektiv Daten zu suchen und zu speichern (Datenbanken)

Und so weiter.

 

Um zu verhindern das du immer Kopien erzeugen musst fällt mir eine einzige Lösung ein. Falls jemand was besseres hat immer her damit:

public void SolveProblem(Schachfigur s)
{
	s.Move(irgendwoHin);
	//Irgendwelche anderer Code
	s.Move(wiederZurück);
}

 

Share this post


Link to post
Share on other sites

Am Ende muss es doch so oder so immer in einer Liste festgehalten werden. Die Tiefe in der du die Züge aufbaust bestimmt die Qualität der KI. Man will doch Züge des Gegners vorhersehen und darauf reagieren. Wenn du immer nur bis zu Tiefe 1 gehst und dir genau eine Ebene ausgeben lässt musst du die ja trotzdem irgendwo zwischenspeichern, du machst also auch nichts anderes als ich, nur dass ich meine Datenstruktur nicht lokal sondern global speichere.

Einer der KI-Ansätze ist doch dass man das gesamte Spiel als Suchproblem definiert. Also praktisch nach allen Zuständen suchen in denen man das Spiel gewonnen hat oder besser gesagt nach allen in den der Gegner nicht gewinnen kann (diese Unterscheidung ist bei meinem aktuellen Spiel wichtig).

Gäbe es z.B. Beim Schach ein Spiel dass ALLE möglichen Schachbretter gespeichert hätte könnte die KI doch niemals verlieren, weil sie immer den Zug wählen würde, in dem man am Ende die meisten Gewinnmöglichkeiten hat. Wäre lustig sie gegen sich selbst spielen zu lassen XD Bei statischen Spielen funktioniert das super, denn dann könnte man diesen Suchbaum einfach speichern und statt zu berechnen dann einfach abrufen oder optional in der Datei suchen.

Und nebenbei das mit dem Move funktioniert leider auch nicht. Denn sobald du sie wieder zurück bewegst, haben sie ja in allen Folgezuständen wieder die Position des root zustands und du hast nichts geändert. Was man tun könnte ist wirklich nur das Schachfeld festzuhalten und daraus eben alles abzuleiten aber das bedeutet wieder rechnen, rechnen rechnen, weil du da daraus erstmal die Figuren rauslesen musst, ihre Zugmöglichkeiten etc...

Share this post


Link to post
Share on other sites

besonders würde mich interessieren wie das mit anpassbaren Lernfunktionen ist ob es da einen populären Ansatz für Spiele gibt.

Share this post


Link to post
Share on other sites

Ich beziehe mich mal auf ein Schachspiel, da ich das andere Spiel nicht kenne.
(ich fange mal mit b an, ich schreibe später noch etwas zu den anderen Punkten)
zu b.)
Mit effizient meinte ich, daß man die Positionen eines Schachspieles und deren Figuren in einem 2D-Array ablegen könnte, mit 64 Positionen (8x8 Array) und mit dem Type Datentyp Byte, daß macht in Summe einen Speicherverbrauch von 64 Bytes.
Oder man definiert folgende Datenstruktur:
Figurenanzahl: 9
Positionen: 8x8 = 64 

Ziel binäre Speicherung:
Figur: 1001 (4 Bit)
Feld:  1000000 (7 Bit)
=
Gesamt 11 Bit für die Speicherung benötigt.
Ergebnis: Für die Speicherung von 16 Plätzen werden mindestens 22 Bytes benötigt (hier muss man Bits auslesen) oder 32 Bytes (wenn man Byteweise ausliest)

Ob diese Speicherung nun performanter ist als das Array hängt nun stark davon ab, wie der Bewertungsalgorithmus die Positionen und die Spielfiguren auswertet. Daher könnte das Array zwar mehr Speicher verbrauchen, aber beim Zugriff performanter sein. Findet man einen Algorithmus der den Spielstand des Brettes "binär" bewertet, dann könnte die binäre Speicherung schneller sein.
Wobei ich diese binäre Speicherung für einen mathematisch erzeugten Algorithmus schon als fast ummöglich zu konstruieren betrachten würde, aber als ein Eingabemuster für ein neuronales Netz, welches den Spielzustand lernend bewerten soll, vermutlich schon wieder ziemlich ideal ist (da auch ein neuronales Netz schneller eine Ausgabe erzeugen kann, wenn der Input kleiner ist).

 

Share this post


Link to post
Share on other sites

Hmm, vielleicht reden wir aneinander vorbei... Ich verstehe deine Vorgehensweise so:

Du baust ganz am Anfang des Spiels den Suchbaum auf und nutzt diesen dann um später Lösungen zu finden. Verstehe ich das richtig? Falls ja, was passiert wenn der Suchbaum zu groß wird? Dann wirst du ja sehr warscheinlich für den ersten Zug nicht den kompletten Suchbaum durchsuchen sondern nur eine Näherungslösung nutzen.

Soweit sogut jetzt kommt der 2te Zug. Wir haben den ersten Zug bereits hinter uns d.h die erste Ebene von unserem Suchbaum wird nicht mehr benötigt, was machst du also damit? Das gleiche gilt für den 3ten Zug 4ten Zug etc etc etc.

Was ist wenn du nicht genug Speicherplatz hast um den Suchbaum zu speichern? Wie entscheidest du welche Daten gelöscht werden und welche nicht.

 

Was ich einfach nicht kapiere warum zur Hölle sollte man jemals auch nur in Betracht ziehen den GESAMMTEN SUCHBAUM zu generieren. Das wird nie und nimmer klappen. Es gibt einen Grund warum für sowas Zufallssuchalgorithmen entwickelt wurden.

Share this post


Link to post
Share on other sites

Figuren haben ja noch andere Eigenschaften die man nicht vergessen darf, beim Schachspiel ist das besonders kompliziert. Das wichtigste und umfangreichste dabei ist die Frage, welche Felder sie begehen können, was wichtig ist um daraus Folgezüge zu konstruieren. Dazu wiederum wird die Farbe der Figur und deren Typ (Bauer, Turm, ... ) benötigt.  Ich habe das als 8x8 Matrix geregelt aus Integer-Werten. Integer-Werte deswegen weil man verschiedene Arten des ziehens hat. Schlagen, Normales laufen, Rochade und andere Sonderzüge, Blockade durch eigene Figur, das alles wird in meinem Algorithmus verwendet der sogar ziemlich gut ist bis auf die Schachmatt-Erkennung.

Ich habe natürlich auch für jeden Zustand ein 2D-Feld angelegt allerdings nicht vom Typ Byte sondern Integer, ganz einfach weil ich byte noch nie verwendet habe XD

Vor allem interessiert mich die Frage. Wirkt es sich positiv auf die Laufzeit auf einfach "Komprimiertere" Datenstrukturen zu verwenden? Ich meine das dürfte doch eigentlich keine Rolle spielen. Selbst wenns um Festplattenspeicher geht hat man 100MB/s+ das wird niemals ausgereizt. wichtiger ist doch die Berechnungen zu reduzieren oder? Und wenn man jetzt die Positionen die ich z.B. als eine Art Integer Array zusammengefasst habe {x,y} jetzt in einem einzigen byte speichert müsste man dann doch dekomprimieren und das wäre doch wiederum teurer, was die Laufzeit angeht oder?

Zur zweiten antwort: Ja so wäre das etwa geplant. Besonders wenn der Suchbaum schon existiert kostet er ja nur die Laufzeit die es braucht um die Daten zu importieren. Du würdest deine aber zur Laufzeit erzeugen. Natürlich hast du recht, dass bereits vergangene Züge nicht mehr gebraucht werden aber das ist eine Sache des Speichermanagements. Und so viele Daten dass du in "Textform" in den Mega oder sogar Giga bereich kommst musst du erstmal generieren.

Du wirst mir sicher zustimmen wenn ich sage, dass je mehr Züge der algorithmus voraus sehen kann, umso besser ist er oder? Das kommt auch vom theoretischen Aspekt der Denkweise eines Spielers gleich. Man überlegt ja, welche Züge könnte der Gegner machen wenn ich das und das mache und das für x verschiedene Züge.

Allerdings fällt mir spontan auch ein, dass man den Suchbaum sozusagen entschlacken könnte. Überlegt mal: Man baut zuerst direkte Folgezüge auf, bewertet diese und baut dann für den BESTEN Zug oder optional die 2,3,4 besten Züge den Baum tiefer auf, also a la Tiefensuche bzw Tiefen"konstruktion". Dann berechnest du die x wahrscheinlichsten Züge des Gegners und konstrukierst für diese dann wieder die y Folgezüge berechnest den wahrscheinlichsten etc... damit würdest du praktisch alle "unsinnigen" Züge auf den Müll schmeißen.

Man hätte dann eben nur das Pech, wenn der Gegner einen unvorhergesehenen Zug macht kannst du deinen ganzen Minimalbaum in die Tonne schmeißen XD

Share this post


Link to post
Share on other sites

Zu der Frage, ob sich die Datenstrukturen auf die Laufzeit auswirken, ganz klar ja. Ganz einfaches Beispiel:, Du führst eine Addition und eine Multiplikation entweder mit Integerwerten aus oder mit Floatwerten, da bist du mit Integerwerten immer schneller. Natürlich habe ich mit der binären Speicherung ggf. übertrieben, aber daß war ja auch nur ein Beispiel das zeigen sollte, wie man nach einer "idealen" Datenstruktur sucht, die die durchzuführenden Berechnungen ideal ergänzt und wie gesagt als Eingabemuster für ein neuronales Netz - welches den Zustand des Spielbrettes bewerten soll - wäre diese binäre Speicherung ideal, da es alle Eingabeparameter bündelt.
zu c)
Einen Baum, der in Form einer doppelt verketteten List vorliegen kann, da ich vermute man braucht nicht zwingend einen Binärbaum, da der Algorithmus sich mehr oder weniger immer von oben nach unten durchhangelt (und zurück) und nicht gezielt bestimmte Knoten abfragen muss.
zu d) Ich denke man kann alles in einem Baum ablegen.

zu "Chaos mit Referenzen")
Hier verstehe ich das Problem nicht ganz. Wenn du die Positionen der Spielfiguren und deren Typ in einem 2D-Array ablegst, dann wird dieses Array direkt ausgelesen und auch direkt beschrieben. Wenn du ein Objekt einer "Spielfigur"-Klasse hast welches seine Position auf dem Spielfeld zusätzlich führt, so gibt es hier eine Setter-Methode mit der die Position von Außen übergeben werden kann.

Share this post


Link to post
Share on other sites

Ich verstehe etwas wie neuronale Netze funktionieren aber nicht so ganz wie man sie auf ein Spiel anwendet. Im Prinzip ist ein neuronales Netz doch auch nur eine Bewertungsfunktion. Du schickst ne Zahl rein die wird durch irgendwelche Schichten gejagt wo sie verändert wird und am Ende kommt ein ergebnis raus. 

die Arrays sind alle vom Typ Integer. Aber ich habe eine Klasse für Figur mit den Eigenschaften Farbe, Position, mögliche Bewegungen, Typ, ...

Wenn ich jetzt z.B. den Root-Zustand übergebe rechnen ja x Threads gleichzeitig an dem Root zustand die Folgezustände aus. Also folgender Fall:
Thread 1 schiebt den Bauern im Root zustand 2 Felder vor. Dann kommt Thread 2 und nimmt eine andere Figur, der Bauer ist aber auch da bereits verändert worden da sie ja alle mit der gleichen Figur arbeiten. Das heißt in diesem Zug wurden 2 Figuren verändert. Das war das Problem das ich hatte ich hatte bei meinem Algorithmus ständig verschiedene Werte wenn ich das Spiel starte, weil die Threads ja die Referenzen verwenden und keine neuen Figuren erzeugen.

Share this post


Link to post
Share on other sites

Es sollte machbar sein, dass du deine Bewertungsfunktion als neuronales Netz realisierst. Dafür musst du einen Vektor definieren den du an das Netz übergibst der den aktuellen Stand wiedergibt.

Um das Netz zu trainieren musst du natürlich noch die "Lösung" kennen. Also für den aktuellen Status den Wert wie gut das Spiel für den Spieler aussieht. Du braucht ja ein Trainingsdatenset.

Und dann sind wir wieder bei null ^^ Naja fast.

Share this post


Link to post
Share on other sites

Also man gibt x Eingabegrößen an ein neuronales Netz. Dieses Netz hat y Schichten durch die diese Größen gejagt und  modifiziert werden.

Beim machinellen Lernen geht man ja so vor dass man sich eine Formel sagen wir mal Wert=ax+by+cz aufstellt, wobei a-c dann die Gewichte sind die man dann durch eine Lernfunktion anpasst, wobei man die Abweichung von dem Optimalwert misst. Das problem ist aber dass die Form der Formel nicht verändert wird also z.B. dass es eben bei + bleibt und man nicht ne Potenz reinkriegt oder man plötzlich 3^x daraus zaubert.

Und ein neuronales Netz kann das... hab ich das so richtig verstanden? dann wäre das vielleicht ein guter experimenteller Ansatz.

Könnte mir jemand diese Thematik näher erklären? Algorithmisch.

Share this post


Link to post
Share on other sites

Google mal nach OpenCV und Neural Network. Da solltest du einiges finden.

zb:

http://bytefish.de/blog/machine_learning_opencv/

https://takinginitiative.wordpress.com/2008/04/23/basic-neural-network-tutorial-c-implementation-and-source-code/

 

Wir haben damals in der Vorlesung relativ simpel gearbeitet und zur Handschrifterkennung mehr ode rweniger nur ein etwas bearbeitetes Bild in das Netz gegeben zum anlernen. Also als Input array. Dieses spukte dann aus welche Zahl es erkannt hat nachdem es fertig angelernt war.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0