Nehmen wir als Beispiel einen 5x5 Tic-Tac-Toe. Nehmen wir an, meine KI ist an der Reihe. Dann,
Hier sind meine Fragen:
Ist es effizient, 25 Threads zu verwenden? Was bedeutet die Verwendung von 25 Threads?
Ist es 25 mal schneller (höchstwahrscheinlich nicht)? Worauf kommt es an? Auf dem Computer natürlich, aber woher weiß ich, wie viele Threads basierend auf den Ressourcen des Computers in Ordnung sind?
Ist meine Idee gut ? Danke.
Für eine typische compute-bound -Anwendung ist es eine gute Faustregel, so viele Threads zu verwenden, wie Sie Hardwarekerne (oder Hyperthreads) haben. Wenn Sie mehr Threads als Kerne verwenden, wird Ihre Anwendung nicht schneller. Stattdessen wird Ihre Anwendung mehr Speicher als erforderlich verwenden. Jeder Thread hat typischerweise einen Stack von 0,5 bis 1 MByte ... abhängig von Ihrer Hardware und der Java-Version. Wenn Sie zu viele Threads erstellen, führt die zusätzliche Speicherbelegung zu einem erheblichen Leistungseinbruch. d. h. mehr threads = & gt; langsameres Programm!
Eine andere Sache, die in Betracht gezogen werden sollte, ist, dass Java-Threads in einer typischen JVM teuer zu erstellen sind. Wenn also ein Thread nicht (in seiner Lebenszeit) genügend funktioniert, besteht die Gefahr, dass Sie mehr Zeit mit der Erstellung von Threads verbringen als mit der Verwendung mehrerer Kerne in der Berechnung.
Schließlich können Sie feststellen, dass sich die Arbeit nicht gleichmäßig über alle Threads verteilt, abhängig von Ihrem minmax-Algorithmus ... und dem Spielstatus.
Wenn ich dies implementieren wollte, würde ich damit beginnen, es als eine Anwendung mit einem einzigen Thread zu implementieren, und dann:
Wenn und nur wenn es schneller gehen muss, würde ich dann den Code untersuchen und (wenn nötig) eine Überwachung hinzufügen, um zu sehen, wie man die Berechnung in genügend große Stücke zerlegt, die parallel ausgeführt werden.
Schließlich würde ich diese Ergebnisse verwenden, um eine Multi-Thread-Version zu entwerfen und zu implementieren.
Ich würde auch Alternativen betrachten ... wie Java 7 fork / join statt Threads verwenden.
Um Ihre direkten Fragen zu beantworten:
Ist es effizient, 25 Threads zu verwenden?
Wahrscheinlich nicht. Es wäre nur effizient, wenn Sie so viele Kerne hätten (unwahrscheinlich!). Und selbst dann werden Sie nur dann eine gute Beschleunigung erzielen, wenn Sie viele Threads verwenden, wenn Sie mehr durch paralleles Ausführen von Threads erzielen, als Sie aufgrund von Thread-bezogenen Gemeinkosten verlieren. (Mit anderen Worten, es hängt davon ab, wie effektiv Sie diese Threads verwenden.)
Was bedeutet die Verwendung von 25 Threads?
Ich nehme an, dass you bedeutet, dass Sie 25 Threads erstellt oder gestartet haben, entweder explizit oder mit einer vorhandenen Thread-Pool-Implementierung.
Aber die Quintessenz ist, dass, wenn Sie (sagen wir) 4 Kerne haben, höchstens 4 dieser 25 Threads gleichzeitig ausgeführt werden können. Die anderen Threads warten ...
Ist es 25 mal schneller (höchstwahrscheinlich nicht)? Worauf kommt es an? Auf dem Computer natürlich, aber wie kann ich wissen, wie viele Threads basierend auf den Ressourcen des Computers in Ordnung sind?
Der primäre Faktor, der die Leistung begrenzt, ist die Anzahl der Kerne. Siehe oben.
Was passiert, wenn ich zu viele Threads verwende (nichts, denke ich ...)?
Zu viele Threads bedeuten, dass Sie mehr Arbeitsspeicher verwenden und Ihre Anwendung aufgrund von Speicherbandbreitenkonkurrenz, Konkurrenz für physische Speicherseiten und zusätzlicher Speicherbereinigung langsamer läuft. Diese Faktoren sind anwendungs- und plattformabhängig und schwer zu quantifizieren; d.h. vorhersagen oder messen.
Abhängig von der Art Ihrer Anwendung (d. h. genau, wie Sie die Algorithmen implementieren) können zu viele Threads zu zusätzlichen Sperrenkonflikten und Thread-Kontextwechsel führen. Das wird auch Ihre Anwendung verlangsamen.
Es ist unmöglich vorherzusagen, was passieren würde, ohne den eigentlichen Code zu sehen. Aber die Anzahl der Kerne gibt Ihnen eine theoretische Obergrenze, wie viel Beschleunigung möglich ist. Wenn Sie 4 Kerne haben, können Sie mit Multi-Threading nicht mehr als eine 4-fache Beschleunigung erreichen.
Also, die Threading-Antworten sind in Ordnung, aber es scheint mir, dass sie die Alpha-Beta-Beschneidung der Minimax-Suche übersehen haben.
Wenn Sie einen Thread für jeden "nächsten Zug" von Ihrer aktuellen Position aus starten, ist es langsam und schmerzhaft, diese Threads miteinander zu sprechen. Aber wenn sie nicht miteinander reden können, dann bekommst du nicht die Tiefenverstärkung, die von Alpha-Beta-Beschneidung kommt, bis eine Ebene weiter unten.
Dies wird gegen die Effizienz des Ergebnisses wirken.
Für allgemeine Fälle, in denen die Berechnungszeit verbessert wird, tendiert der beste Fall dazu, 1 Thread pro Kern zu sein, entweder mit einer einfachen Zuweisung von Aufgaben zum Thread, wenn sie alle ähnliche Zeit haben (z. B. Matrixmultiplikation) oder mit einer "Menge" Aufgaben, wobei jeder Thread den nächsten nicht begonnenen Thread übernimmt, sobald er seine aktuelle Aufgabe beendet. (Dies hat einige Sperraufgaben, aber wenn sie im Vergleich zu den Auflösungskosten klein sind, ist es sehr effektiv).
Also, für ein 4-Kern-System und ~ 25 natürliche Aufgaben können Sie auf eine Beschleunigung im Bereich von 3,5-4x hoffen. (Sie würden 4 parallel ~ 5 mal tun, dann unordentlich beenden). Aber im Minimax-Fall haben Sie den Alpha-Beta-Beschneidungs-Aspekt verloren, von dem ich verstehe, dass er die effektive Breite von N auf etwa sqrt (N) reduziert. Für ~ 25 Fälle bedeutet das einen effektiven Verzweigungsfaktor von 5. Das bedeutet, dass 4 Kerne verwendet werden und das Überspringen von Beschneidungen für die erste Stufe könnte Sie tatsächlich verletzen.
Also, wo verlässt uns das?
Wie alle meine Freunde gesagt haben, benutzen Sie so viele Threads wie Ihre Maschine Kapazität hat.
Aber wenn du sie zu dir hinzufügst, solltest du auch den Algorithmus verbessern.
zum Beispiel in 5x5 Tic Tac Toe bekommen beide 12 oder 13 Züge. die Anzahl der möglichen Züge beträgt also nCr (Kombinationsgleichung) Basis 25C12 = 5.200.300. so jetzt haben Sie die Anzahl der Thread jetzt zur besten Auswahl haben Sie beste Weg, die beste Lösung zu finden sind nur 12 (Wining Position) & amp; 12, um schlechtesten Zustand zu verlieren, alle anderen sind Zeichnungsbedingung. Also, was Sie tun können, ist einfach überprüfen Sie diese 12 Zustand von Threads & amp; Lassen Sie zusätzliche Kombination mit Berechnung, die Sie 12 erstellen müssen! * 12 keine der Threads, die sehr niedrig ist, verglichen mit 25!.
Daher wird die Anzahl der Threads sinken. Sie können weiter darüber nachdenken, um die Anzahl der Threads zu verringern.
wenn deine Bewegungen mehr und & amp; mehr können Sie mit Alpha-Beta-Beschneidung gehen, so dass Sie Ihren Algorithmus auch verbessern können.
Wenn Sie Threads verwenden, um Speicherverluste zu vermeiden, verwenden Sie sie einfach für die ersten Aufrufe von mini-max und kombinieren Sie dann das Ergebnis des Threads, um die Ausgabe zu erhalten. Es ist eine Verschwendung, wenn Sie 25 Threads oder eine so große Zahl verwenden, weil die verfügbaren Cores weit weniger sind als das. Sie können also nur Threads einplanen, die den verfügbaren Cores gleichzeitig in verschiedenen Zuständen entsprechen, und alle Ergebnisse kombinieren das Ende.
Hier ist Pseudocode: -
%Vor%Betrachten Sie die Symmetrie Ihres Problems. Es gibt tatsächlich nur eine sehr begrenzte Anzahl von "einzigartigen" Anfangsbewegungen - der Rest ist der gleiche, aber für die Reflexion oder Rotation (daher von identischem strategischem Wert). Die einzigartigen Züge für ein 5x5 Board sind:
%Vor%Oder nur 6 erste Züge. Bam - Sie haben nur die Komplexität um & gt; 4x ohne Threads reduziert.
Wie andere schon sagten, helfen mehr Threads als Cores normalerweise nicht beim Beschleunigen, es sei denn, einzelne Threads verbringen ihre Zeit mit "Warten" - für Eingaben, Speicherzugriff, andere Ergebnisse. Es könnte sein, dass sechs Threads ein guter Ausgangspunkt wären.
Nur um Sie von der Symmetrie zu überzeugen, markiere ich gleichwertige Positionen mit der gleichen Nummer - sehen Sie, wenn Sie zustimmen
%Vor%Dies gilt auch, wenn Sie um ein Vielfaches von 90 Grad rotieren oder über Diagonale oder von links nach rechts, von oben nach unten reflektieren.
PS: Ich weiß, dass das nicht wirklich die Frage beantwortet, die du gestellt hast, aber ich glaube, dass es sehr direkt deine zugrundeliegende Frage angeht - "wie löse ich effizient 5x5 Tic-Tac-Toe erschöpfend". Als solche werde ich nicht verärgert sein, wenn Sie eine andere Antwort wählen, aber ich hoffe, dass Sie meinen Rat beherzigen werden.