Laufzeitoptimierung

[Kokujou]

Hey! Ich hab ein paar Probleme und zwar entwickle ich gerade ein Schachspiel und versuche eine KI zu entwickeln.

Da ich leider nur ein Student bin und mir alles selbst beigebracht habe sieht mein Code für euch warscheinlich auch dementsprechend schlecht aus.

 

Ich hab mich schon am Multithreading versucht aber aktuell kommt mein Code beim erstellen eines Zustandsbaumes über eine Runde hinaus!

 

Ich hab den Code mal hochgeladen und hoffe ihr könnt mir etwas helfen.

Natürlich sollt ihr nicht jede Zeile überprüfen sondern einfach nur mal grob drübergucken, ob ihr was findet was ihr besser machen würdet.

 

das was aktuell am meisten Zeit frisst ist in Zeile 274 in der Funktion "RateState" der Punkt wo ich die OnSelect funktion aufrufe.

 

ich weiß es ist viel verlangt aber ich hoffe ihr habt ein paar Ideen wie ich es besser machen könnte. für eine schlechte KI reicht eine Runde zwar und die HS an der ich bin kann eigentlich schon froh sein wenn ich es schaffe ein 3D Pacman zu entwerfen, aber man will ja trotzdem was lernen!

 

http://pastebin.com/k3KgfdxV

 

PS: Außerdem ist mir aufgefallen dass die Ergebnisse der Bewertungsfunktion sich ständig ändern. immer wenn ich das programm starte sind da andere werte. ich glaube dass die threads irgendwie nicht fertiggestellt werden während die Movement Arrays der Figuren aktualisiert werden aber die RateState funktion frisst verdammt viel laufzeit deswegen muss ich die irgendwie in mehreren threads rechnen lassen.

[Overdozed (Dimitri)]

Hat zwar jetzt nichts mit deinem Problem zutun, aber hier

 

foreach (PFigur Figur in allFigures)
{
    tasks[allFigures.IndexOf(Figur)] = Task.Run(() => Spieler.OnSelect(allFigures, allFigures.IndexOf(Figur), current.Feld));
}

 

hättest du eventuell die for Schleife nehmen sollen um gleich den Index zu bekommen und hättest dir zwei Mal .IndexOf() sparen können.

 

for (int i=0; i<allFigures.Count; i++)
{
     tasks[i] = Task.Run(() => Spieler.OnSelect(allFigures, i, current.Feld));
}

[Kokujou]

Hat zwar jetzt nichts mit deinem Problem zutun, aber hier

 

foreach (PFigur Figur in allFigures)
{
 tasks[allFigures.IndexOf(Figur)] = Task.Run(() => Spieler.OnSelect(allFigures, allFigures.IndexOf(Figur), current.Feld));
}

 

hättest du eventuell die for Schleife nehmen sollen um gleich den Index zu bekommen und hättest dir zwei Mal .IndexOf() sparen können.

 

for (int i=0; i<allFigures.Count; i++)
{
  tasks[i] = Task.Run(() => Spieler.OnSelect(allFigures, i, current.Feld));
}

 

ich hab mal gehört dass man wann immer möglich lieber foreach nutzen soll. und da in diesem Fall eine Zählvariable nicht zwingend notwendig war dachte ich ich lass es so. hat denn jemand kommentare zu dem rest?

[Hrungdak]

Bei Unity sollst du wann immer möglich foreach NICHT nutzen. Der Link geht zu Gamasutra, da sind im Kommentarbereich auch noch einige Erklärungen drin. Leider habe ich keine Infos, ob das bei neueren Versionen immer noch so ist.

[Overdozed (Dimitri)]

Ohhh, dann hast du aber jetzt ein gutes Beispiel dafür, dass nicht alles, was irgendwo geschrieben wurde auch richtig sein muss. Die Performance einer for - und einer foreach Schleife kann unter Umständen sich etwas unterscheiden, der Unterschied liegt aber in Nanosekundenbereich. In den meisten Fällen ist aber die for-Schleife schneller, da bei einer foreach-Schleife mehr lokale Variablen erzeugt werden. Im Fall, dass du den Wert mehrfach in der Schleife verwendest kann unter Umständen die foreach-Schleife ganz gering schneller sein, bei dir ist das aber nicht der Fall.

 

Mal davon abgesehen, dass die Perfomanse dieser Schleifen vernachlässigt sein darf benutzt du hier eine schon Performance beeinflussende Funktion, nämlich die .IndexOf() Funktion. Diese ist meines Wissens nach sogar langsammer, als wenn du manuell die for-Schleife dafür erstellst und sollte nur in Spezialfällen benutzt werden. Also um nicht in die Details zu gehen würde die Performance deiner Funktion um MEHRFACHE steigern, wenn du das wie von mir oben bereits geschrieben machst Ob du diesen Unterschied aber tatsächlich spürst ohne mit Ausführungszeit zu debuggen ist eine andere Frage, der Unterschied ist aber SEHR groß.

[Overdozed (Dimitri)]

Hrungdak

 

Das ist ja ein Ding... ich hoffe sehr, dass das nicht mehr so ist, weil ich die foreach-Schleifen einfachheitshalber auch oft benutze.

[Hrungdak]

Hrungdak

 

Das ist ja ein Ding... ich hoffe sehr, dass das nicht mehr so ist, weil ich die foreach-Schleifen einfachheitshalber auch oft benutze.

Ja, vielleicht weiß jemand, ob das mittlerweile schon behoben ist. Kann ich leider nicht sagen. Das würde ich auch nicht überbewerten. Ob for oder foreach ist erst mal egal, das Spiel muss fertig werden. Über Performanceoptimierung sollte man sich einen Kopf machen, wenn es nötig ist.

 

Warum hast du mein Profil in deinem Beitrag verlinkt?

[Overdozed (Dimitri)]

Warum hast du mein Profil in deinem Beitrag verlinkt?

 

Das passiert wenn du den Profilnamen links oben kopierst Wird automatisch verlinkt

[Ikarus]

Kokujou, ich bin noch nicht soweit, um alles zu verstehen, was in C# geschrieben steht. Trotzdem habe ich mal versucht, in deinen 1.000-Zeilen-Code hineinzutauchen. Mit dem Aufruf in Unity 5.4.2f1 mit Visual Studio 2015 kommt es aber zu Fehlermeldungen:

Es fängt mit 7 Fehlern an, steigert sich nach ersetzen des "ö" durch "oe" zu 24, geht nach ändern von "ä" auf "ae" auf 12 zurück, um dann nach ersetzen von "ß" durch "ss" auf 2 zu enden. Ist aber zweimal derselbe Fehler, nämlich:

error CS0234: The type or namespace name `Tasks' does not exist in the namespace `System.Threading'. Are you missing an assembly reference?

Die Suche ergab, dass es wohl mit .NET 3.5.2 kein System.Threading.Tasks gibt, weil das erst mit 4.x eingeführt wurde, was bei Unity aber nicht implementiert ist.

[Overdozed (Dimitri)]

Ja, vielleicht weiß jemand, ob das mittlerweile schon behoben ist.

 

using UnityEngine;
using System.Linq;
using System.Diagnostics;
using System.Collections;
public class UnitTest : MonoBehaviour {
void Start()
{
	int[] array = Enumerable.Range(0, 1000000).ToArray();
	for (int i = 0; i < 100; i++)
	{
		Stopwatch watch = System.Diagnostics.Stopwatch.StartNew();
		Method1(array);
		watch.Stop();
		UnityEngine.Debug.Log("Method 1 executed in: " + watch.ElapsedMilliseconds.ToString() + " ms.");
	}
	for (int i = 0; i < 100; i++)
	{
		Stopwatch watch = System.Diagnostics.Stopwatch.StartNew();
		Method2(array);
		watch.Stop();
		UnityEngine.Debug.Log("Method 2 executed in: " + watch.ElapsedMilliseconds.ToString() + " ms.");
	}
}

static int Method1(int[] array)
{
	int a = 0;
	for (int i = 0; i < array.Length; i++)
	{
		a += array[i];
	}
	return a;
}
static int Method2(int[] array)
{
	int a = 0;
	foreach (int value in array)
	{
		a += value;
	}
	return a;
}
}

 

Scheint behoben zu sein: http://shot.qip.ru/00NDav-4oHGounEo/ + http://shot.qip.ru/00NDav-1oHGounEp/

 

Unity 5.4.2f2.

 

Da muss man zwar jetzt viel mehr testen, weil es z.B. durch die Systemdienste auf meinem System zu Schwankungen kommen kann, aber man sieht hier zumindest, bei der einfachen Nutzung des Wertes, dass die for-Loop sich viel stabiler zeigt und viel weniger schwankt.

[Sascha]

Du solltest noch angeben, welche Unity-Version du nutzt. Es gibt ja einen Editor Preview Build mit Mono 4, wo das definitiv kein Problem mehr ist. Der Tipp von wegen kein foreach in Unity existiert ja nur, weil Unity jahrelang auf Mono 2 rumgehockt hat und das da kaputt war.

[Kokujou]

Oh! Dann hab ich das total verdreht! tut mir leid OK, dann der erste Tipp: Foreach->For. Naja da ich meistens auch doppelte verkettungen habe könnte das schon nicht unwesentlich sein, danke!

 

Oh... Naja ich habe den graphischen Teil in Unity geschrieben, aber da die KI zu testen in Unity zu lange dauern würde habe ich ein separates Programm in VS15 geschrieben, deswegen spielt die Unity-Version auch keine Rolle. Kannst du vielleicht auch Visual Studio separat nutzen? Wenn nicht kannst du ja die Tasks durch Threads ersetzen. Ich hab zuerst auch mit Threads gearbeitet, dann aber gehört dass man wohl jetzt lieber Tasks benutzt. Ich hab beides ausprobiert und keinen Unterschied festegestellt. Generell hatte ich viele Probleme mit dem Multithreading.

 

Meine Unity-Version ist aktuell 5.3.5f1 aber wie gesagt benutze ich aktuell nur C#. was wenig ermutigend ist wenn ich die codes dann zusammenführe XD

 

 

 

 

Hab ich denn noch irgendwelche gravierenden fehler drin die beim überfliegen des Codes auffallen? Ich hatte befürchtet dass sofort ne Ansage kommt, wie schlampig mein Code ist, wie falsch und sinnlos mein Multithreading implementiert wurde etc...

Vor allem jetzt da mir das Multithreading so in meinen Code reinpfuscht dass jedes mal andere Feldbwertungen rauskommen (weiß der geier wieso).

Offensichtlich scheint die Funktion "FigurAsTarget" das Problem zu sein. Meine Theorie ist dass für alle threads offensichtlich die gleiche Figuren-Objekte verwendet werden.

Dass es praktisch geht: Thread 1-> Figur.Onselect -> Thread 2 -> Figur.Onselekt -> Thread 1 -> FigurAsTarget.

sodass die funktion mit werten einer anderen figur arbeitet. könnte das sein?

[Ikarus]

Da ich mit Multithreading bisher nicht das Geringste am Hut hatte, kann ich ja mal ganz naiv fragen: Kannst Du die verdächtige Funktion nicht dadurch isolieren, indem Du das Multithreading "abschaltest"?

[Kokujou]

könnte ich aber wenn ich das multithreading abschalte steigt die laufzeit schon bei einer iteration ins unermessliche!

allein jetzt braucht er für eine iteration das heißt um für eine runde alle schachzüge durchzuspielen 15 sekunden!

bei der 2. würde er erst fertig werden wenn ich ihn über nacht laufen lasse.

das bloße füllen des zustandsbaumes ist da nicht der knackpunkt das hab ich schon isoliert deswegen muss der fehler irgendwo anders liegen. ich hatte gehofft das problem durch multithreading zu lösen aber

 

darum brauch ich dringend hilfe! wenigstens die eine iteration muss er sauber machen sonst kann ich das ding unmöglich als bachelor arbeit einreichen

[Ikarus]

Jetzt komme ich auch noch mit den Vokabeln ins Schleudern:

Du sagst "Iteration" und "Runde".

Wenn ich Iteration so verstehe, dass für alle z. B. weissen Figuren alle erlaubten Züge angenommen werden (1. Halbzug) kombiniert mit allen erlaubten Zügen der schwarzen Figuren (2. Halbzug; zusammen mit 1. Halbzug = 1 Zug), wäre das eine Runde? Dann wären 15 Sekunden allerdings extrem viel.

[Kokujou]

Ja das passiert wenn man intelligent klingen will Mit Iteration war gemeint wenn der Suchbaum die Tiefe 1 hat. also alle weißen züge und das meine ich auch mit runde. Die schwarzen sind noch gar nicht drin. dann müsste ja für jeden möglichen weißen zug, alle möglichen schwarzen züge generiert werden.

 

ihr seht also meine frage kommt nicht von irgendwo. die laufzeit ist unterirdisch und ohne multithreading würde ich heute noch auf die 1. Iteration warten XD

[Ikarus]

Ich würde wirklich gerne deinen Code verstehen, aber da ist für mich noch zuviel Unentdecktes Land,

Aber bei 15 Sekunden für den 1. Halbzug kann etwas nicht stimmen.

Der Ablauf den ich erwarte ist:

(Mattprüfung und so Zeug, dann)

für alle beweglichen Figuren des aktuellen Spielers

{

1. Suche die nächstmögliche Figur

2. Suche alle begehbaren Felder für diese Figur

3. Bewerte die Stellung für alle diese begangenen Felder

}

 

Damit wäre die erste Iteration(?) abgeschlossen(??). Das kann nur wenige Sekundenbruchteile dauern

 

Dann, beginnend mit der besten Bewertung, die möglichen Gegenzüge ermitteln und Stellung bewerten.

 

Im Maximalfall wäre das:

(wieder Mattprüfung und so)

für alle bewerteten Stellungen

{

für alle beweglichen Figuren des anderen Spielers

{

1. Suche die nächstmögliche Figur

2. Suche alle begehbaren Felder für diese Figur

3. Bewerte die Stellung für alle diese begangenen Felder

}

}

 

Wenn dein Programm weiter so vorgeht für sagen wir mal insgesamt 6 - 8 Halbzüge, dürfte es schon besser spielen als die meisten Durchschnittsspieler. Und der Zeitbedarf pro Zug ist eher gering.

 

Das wirft die Frage auf, wo die Zeit bei deinem Programm verbraucht wird. Oder ob ein anderes Vorgehen verfolgt wird, was dann wieder die Frage nach der Zeit aufwirft.

[Kokujou]

also ich formuliere mal alles was ich bis jetzt habe in worten.

1. Zustandsbaum wird gefüllt. du siehst meine Klassen. hier werden die Züge generiert. ich schätze mal allein das "OnSelect", was immerhin jedes feld durchgehen muss und prüfen muss ob die Figur da drauf gehen kann, frisst viel zeit. dann gibts natürlich für jedes begehbare feld eine neue klasse die jedes mal auch ein neues Schachfeld hat im Format int[][]. Der Baum ist noch das geringste Problem, weil da der 1. Halbzug sofort berechnet wird ohne große verzögerung (Danke Console.Writeline )

2. Bewertet dann die Spielzüge und hier kommt das Problem. Zuerst mal muss OnSelect wieder für JEDE Figur auf dem Feld aufgerufen werden und das für JEDEN Zustand im Zustandsbaum. Also doppelt verkettet.

Das muss passieren damit ich herausfinden kann welche Figuren wie beschützt und wie bedroht werden. Das kombiniert mit den Materialwerten der Figuren ergibt dann den Wert des Feldes.

 

und selbst obwohl ich jeden Ratestate schon in einer Subroutine laufen lasse funktioniert es nicht so wie ich will!

 

ich hebe nochmal hervor die schlimmsten funktionen sind also:

RateState, FigurAsTarget, Spieler.OnSelect

sowie die Klassen State, Schachzug und Figur.

[Kokujou]

push?

[Kokujou]

Für alle die es noch interessiert: Das Problem lag in der OnSelect funktion. Nachdem ich dort alle try/catch blöcke rausgeschmissen hatte und die selbsterzeugten throw new exceptions die ich eingebaut hatte um aus der vernesteten schleife auszubrechen

(stattdessen hab ich mich doch für goto entschieden)

ist die laufzeit plötzlich optimal.

natürlich muss ich erst gucken ob keine weiteren fehler entstanden sidn aber yo...

[Djeurissen]

Wo ist denn da eine innere For-Schleife?

Ich sehe nur die Schleife bei jedem case aber ansonsten sind da keine Äußeren Schleifen. Dementsprechend solltest du an der exakt gleichen Stelle landen wenn du einfach ein break bei deinem throw schreibst.

 

Desweiteren sei anzumerken: Warum fängst du falsche Zugriffe auf dein Array mit Try-Catch ab?

Problem dabei, wie du schon bemerkt hast ist es extremst langsam eine Exception zu schmeissen und abzufangen, noch dazu ist es unsauber das für Flow-Controle zu missbrauchen.

Ich würde dir empfehlen If-Abfragen einzubauen die prüfen ob der Zugriff auf das Array erlaubt ist. Erst dann wird der Restliche Code ausgeführt.

 

Im Grunde verbrauchen die If-Abfragen damit kontinuirlich Performance. Die falschen Array-Zugriffe verursachen nur dann Performance Probleme wenn eine Exception geworfen wird.

Nun muss man aber folgendes bedenken, dein Schach Array ist nicht sonderlich groß. Dementsprechend kann es sehr gut sein das sehr oft Exceptions geworfen werden. In solchen Fällen sind If-Abfragen (Wenn sie performant geschrieben wurden) weitaus schneller.

Wenn man diese Abfragen dann noch in eine Methode packt die einen Boolean zurückgibt dann wird der Code auch leichter lesbar.