Genetischer Algorithmus findet Unschlagbare Zerg-Build Order

[HaiZhung]

Hallo Freunde,
viel Spaß mit folgender Zerg-Buildorder:

10 extractor-trick to 11
11 overlord
11 spawning pool
15 extractor
16 queen (stop drones here)
18 overlord
18 roach warren
17 overlord (yes, two)
spawn-larva on queen when she pops
roach x7

Ein genetischer Algorithmus hat diese Build order gefunden, und auf TeamLiquid wird sie schon als unhaltbar bezeichnet. Alle Details findet ihr in z.B. diesem Artikel:

http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/

Wenn ich es kurz umreissen soll: Der Algorithmus nimmt einige "normale" Build orders, ein Ziel ("so schnell wie möglich 7 roaches") und probiert dann über standard-genetische Veränderungen neue Build orders aus. (Etwas neues bauen, eine probe cutten, einen overlord dazwischen schieben, etc.)

Er schmeißt dabei "schlechte" Generationen raus, und nur die mutierten Generationen die ihre Eltern toppen kommen weiter. Was dabei rauskam könnt ihr ja sehen.

Ihr könnt das Ding auch selbst nehmen und damit rumspielen. (Natürlich ist das Programm nicht von mir, aber Open Source) Momentan beherrscht das Programm nur Zerg; was umso erstaunlicher ist, weil es für Zerg am schwierigsten ist, BOs zu finden!
http://code.google.com/p/evolutionchamber/

 

[EvilLord]

sehr reißerisch der Titel :-) ich mags ja nicht so recht glauben. wird aber heute abend ausgiebigst getestet

 

[NacktNasenWombi]

und warum soll sie unschlagbar sein?

 

[Ymy]

weil der supercomputer es so ausgerechnt haT!

Btw soll die Bo die beste sein um auf die MEISTEN anderen BOs zu antworten.
Ist also nicht unschlagbar ^^


Ma schauen wann die erste große Zergwelle auch in den niedrigeren bereichen anfängt einfach alles zu ownen 8()

 

[Deleted_504925]

und warum nutzt sie den extractor trick, der sich als schlechter als 9 ovi rausgestellt hat?

 

[Ymy]

weil der Supercomputer halt nanosekunden genau rechnet. Bei seiner perfekt ausgeführten BO scheint der 11er besser zu sein

btw nice wie Endieg s thread zu dem thema untergeht XD

 

[dabegi]

Ähhh und dann? Hab ich 7 roaches, mit denen kann ich dann auf ner riesen map zum gegner kriechen und wahrscheinlich ned viel reißen. Oder ich lass die roaches sinnlos in meiner base rumstehen....

Versteh ich ned... HILFE!

 

[Xkl1]

genetischer Algorithmus...man muss schon Worte zusammen schmeißen die wenig Sinn ergeben damit viele draufklicken am Thread

Ich bezweifle, dass diese BO so toll sein soll. Gegen was auch?

Toll du hast 7 Roaches und dann?

Bringt dir wenig wenn der Protoss zB mit FF blockt

 

[endieg]

weil der Supercomputer halt nanosekunden genau rechnet. Bei seiner perfekt ausgeführten BO scheint der 11er besser zu sein

btw nice wie Endieg s thread zu dem thema untergeht XD

ich war schneller :P

 

[HaiZhung]

Der Extraktortrick und doppelt Ovis sind zwei Sachen, die man glaube ich nur sehr schwer erklären kann. Man müsste selbst die BO in vielen Variationen ausprobieren, um zu verstehen, wieso sie genau so am besten klappt wie der Algorithmus sie rausgefunden hat. Der Artikel den ich verlinkt habe geht darauf nochmal ein bisschen mehr ein.

Genetischer Algorithmus ist ein Standardbegriff aus der Informatik.

http://de.wikipedia.org/wiki/Genetischer_Algorithmus

Wieso sie Unschlagbar ist - Das habe ich aus dem TL thread entnommen. Anscheinend scheint ein All-In Push mit 7 roaches + queen + drones teilweise nicht zu halten sein.

 

[gnj]

Die ist sicherlich nicht unschlagbar...

 

[Ymy]

kann jemand mal das Programm oder die Bo testen und sagen wie dad ausschaut?
Hat der toss da schon überhaupt nen protektor?
Wird einfach alles umgemoscht von den roaches? :X

 

[Xkl1]

Genetischer Algorithmus ist ein Standardbegriff aus der Informatik.

http://de.wikipedia.org/wiki/Genetischer_Algorithmus

Danke, als Genetiker dachte ich schon ihr klaut uns unsere Wörter

 

[Deleted_504925]

nach 8k berechneten spielen ist er immer noch der meinung man bräuchte 2 spawn pools für 6 banelinge

 

[Paranoijaa]

Was mich wundert, hier schreiben alle "was bringt mir das?" Es geht doch schlicht weg darum das diese BO extrem schnell das Ergebnis 7 Roaches erzielt. Sie hat doch, nach meinem Verständnis, nicht zum Ziel eine ImbaAllRoundLösung zu sein. Soll soviel heißen wie: Auf kleinen Maps ist dies eine extrem schnelle Variante mit vielen Roaches mächtig Druck zumachen. Das sie nicht als FE Built taugt sollte jedem Grundschüler bewusst sein.
Mein Vorschlag, wenn man also einfach nur maulen will weil man seine Foren Beiträge in die Höhe treiben muss um Achievments freizuschalten sollte man doch bitte in Offtopic gehen.

So, nun aber noch zum Thema. Bin mal gespannt ob sie verwendung finden wird. Gab ja auch mal diese "unschlagbare" 5RR BO, sie war gut aber eben auch nur ein semi Allin. Wenn sie ebenfalls nur ein Allin ist wird sie sich nicht durchsetzen.

 

[BaBaUTZ]

Ein Algorithmus in einem Spiel/einer AI kann überhaupt nur dann "unschlagbar" sein, wenn vollständige Informationen vorliegen. Dies ist nicht gegeben, da Starcraft 2 (wie fast jedes RTS) unterschiedliche Maps hat, die z.T verschiedene BO's favorisieren. Gleiches gilt für die Startposition. Das Topic wäre aber ein guter Artikel für bild.de, wenn es dort um Starcraft gehen würde.

(Über die Problematik, dass das Teil an sich erstmal fehler- und exploitfrei programmiert werden muss, brauchen wir noch nicht mal zu reden).

 

[ExTraxx]

werd ma schaun ob das wirklich klappt,!!!!

 

[gelle]

Btw soll die Bo die beste sein um auf die MEISTEN anderen BOs zu antworten.

nein falsch, es soll die beste buildorder sein, um schnell 7 roaches zu bekommen. das halte ich auch durchaus für möglich. die frage wie gut die build order ist, richtig sich dann eher danach, wie gut schnell 7 roaches sind.

 

[quiT]

Ja, die Ueberschrift hat was von bild.de...
Ich finde es aber schon faszinierend - das Spiel ist ein paar Monate alt und schon werden -zig tausende BO's berechnet und ganze Programme um das Spiel entwickelt. Bin mal gespannt was es in ein paar Monaten/Jahren so alles gibt bzw. herausgefunden wird.

 

[Cheezy]

imo müsste das GeNERischer Alghorithmus heißen und nicht genetisch,

 

[Cosmos]

Was soll da großartig neues kommen.
Es wird ein paar BOs für jede Rasse geben. Der der besser scoutet kontert das was der Gegner macht. Das läuft dann auf ein Makrospiel hinaus. Irgendwie sowas.

Abgesehen davon - Roaches werden wahrscheinlich wieder irgendwie schwächer gemacht. Weil Blizz wird DAS nicht so stehen lassen. Lächerlich wie einfach man damit gewinnt.

 

[suN]

Wenn ich für meinen Hund die BO spiele, dann verliert er immernoch damit.
Wirklich fragwürdig ob das was bringt.

 

[Deleted_504925]

naja is halt nen bo simulator, nicht mehr und nicht weniger, das das ding nicht automatisch games für euch gewinnt ist doch klar

 

[Ymy]

Man muss halt an sich selbst arbeiten aber diese bo ist schon recht schnell.
Hab es etwas schlampig ausgeführt aber schon nach 4:30 6 roaches und eine im bau gehabt :X
Da würde auf scrapstation zb grad der 10 pooler mit den ersten 6 lingen ankommen.
Gegen einen schnellen rush ist man aber ausgeliefert.

 

[theAzzi]

Wurde ja schon nen paar mal gesagt:

Das ding ist nett um nen timing push zu basteln, mehr kann es nicht.

Thread Titel ist schon sehr auf Bild Niveau, das stimmt.

 

[kirdie]

imo müsste das GeNERischer Alghorithmus heißen und nicht genetisch,

Hast du dir den verlinkten Wikipediaartikel überhaupt angeschaut?

 

[Xkl1]

meine BO

So ich hab den Build ausprobiert und bin nicht happy damit!

Ich hab aus Spass auch einen eigenen Build ausprobiert und mit damit sogar schneller!

10 Overlord
13 Pool
13 Extraktor
15 Overlord
15 Queen (stop drones here)
17 roach warren
16 Overlord

gas drones bei 175 gas komplett zum mineral abziehen, vorher schon teils wenn es sich dem 175er neigt.

Bei ganz exakt min 5:00 habe ich 7 Roaches!

Mit der unschlagbaren BO von oben komm ich auf ein paar Sekunden mehr, bzw wenn man sie perfekt baut, auf wieviel kommt ihr, auf unter 5min komm ich aktuell nicht.

Und ob man 1 sek mehr oder weniger braucht, macht sie nicht unschlagbar

btw: replay als beweis für meine BO in 5:00 min

 

[SoFar]

Das war schon vor nem Monat Thema bei TL...
Programm ist ganz nützlich, aber mehr auch nicht.

Und der Threadtitel ist UNSINN. X_X Unschlagbar... lol!

 

[HaiZhung]

Dann hast du was falsch gemacht. Mit der BO kann man die 7 Roaches bei 4:45 haben:

http://www.youtube.com/watch?v=KH1ucvJomlY&feature=player_embedded

 

[Xkl1]

Das Problem, die Roaches sind langsam, gegen einen anderen Zerg hilft es dir daher evtl nur bedingt!

Bis dahin hat der mit 14pool, 14hatch auch schon was.

 

[freetgy]

besser als 6-pool alle mal

 

[Brusko651]

hmm hübsche allin-BO, werd ich gleich ausprobieren (ich hol mir ein paar easy wins in der ladder hehe)

Ob die build order wirklich optimal ist wär ich mir aber nicht so sicher. Die Werte die das verwendete Programm verwendet sind vermutlich nicht ganz genau. Es kommt da ja auf Bruchteile von Sekunden an. Kann mir zB nicht vorstellen dass das Programm genau weiß wie lange man für einen extractor trick braucht. Auch das Mineralieneinkommen, das ja nicht mit der Anzahl der Dronen linear ansteigt, ist vermutlich nicht exakt im Programm verankert.
Aber grundsätzlich find ich die Idee eines evolutionären build-order-optimierers seehr cool :]

Achja, und falls ich es noch nicht gesagt habe: Die buildorder ist nice! Auf sowas wäre ein Mensch vermutlich nicht so bald gekommen.

 

[Sokrates]

Habs ausprobiert.. Wenn z.b der protoss scouted macht er nen wall in mit forcefields, dann bringt die taktik gar nichts mehr.

 

[EvilLord]

hat er da schon so viele sentrys um die choke ewig zu blocken?

 

[Robb]

ne, vorallem nich auf scrap station

 

[Sinsnickers]

Hat gestern jemand gegen mich gemacht, habe mich schon gewundert woher so schnell die Roaches gekommen sind.. habe es natürlich nicht gehalten bekommen, bin aber nur Gold Zerg also hat das nicht wirklich viel zu sagen

 

[quiT]

hmm hübsche allin-BO, werd ich gleich ausprobieren (ich hol mir ein paar easy wins in der ladder hehe)

Ob die build order wirklich optimal ist wär ich mir aber nicht so sicher. Die Werte die das verwendete Programm verwendet sind vermutlich nicht ganz genau. Es kommt da ja auf Bruchteile von Sekunden an. Kann mir zB nicht vorstellen dass das Programm genau weiß wie lange man für einen extractor trick braucht. Auch das Mineralieneinkommen, das ja nicht mit der Anzahl der Dronen linear ansteigt, ist vermutlich nicht exakt im Programm verankert.
Aber grundsätzlich find ich die Idee eines evolutionären build-order-optimierers seehr cool :]

Achja, und falls ich es noch nicht gesagt habe: Die buildorder ist nice! Auf sowas wäre ein Mensch vermutlich nicht so bald gekommen.

Ohne das Programm genauer zu kennen, behaupte ich einfach mal das es zu genau ist. Es wird die Zahlenwerte so nehmen, als wuerde man perfekt klicken, kein lag bzw. delay haben und auch immer die guenstigste Drohne auswaehlt zum bauen.

 

[Nocci]

Was hier für ein Aufruhr herrscht nur wegen der reißerischen Bild überschrift...

Ziel des Programms ist es doch einfach eine Zielvorgabe (xy supply an units xyz) möglichst schnell zu erfüllen und es folgt dabei einem genetischen Algorithmus (Verbesserung -> Veränderung beibehalten, Verschlechterung -> Änderung verwerfen).

Wenn sich der 7 Roach Rush als extrem schwer zu halten herausstellt und selbst gut scoutende Pros ihn die meiste Zeit nicht halten können wird wahrscheinlich gepatcht werden, ansonsten...

Gratz, nun gesellen sich zu 4-Gate-only Protoss eben auch noch 7-RR Zerg in die hohen Diamond Regionen


Zum Programm selbst:
Ich seh's irgendwie mit gemischten Gefühlen, zum einen nimmt es einem viel Arbeit ab wenn's darum geht die frühe Phase unterschiedlicher BOs auszutesten, was dazu führen kann, dass der Spielraum für Kreativität schneller erschöpft ist. Andererseits kann man dadurch wiederum diverse imbalance im early schneller identifizieren, was wiederum dazu führen kann, dass das Spiel allgemein früher gebalanced wird.

 

[Brusko651]

hier ist ein guter post aus den comments zu dem artikel:

This is a novel idea, however I assume this uses some model to produce outputs as opposed to running the build orders in SC 2 itself?　My primary concern with such an approach would be that the error caused by the model would be greater than the difference between competing strategies. This is only worsened when you consider human error.

Das ist das was ich auch mit meinem post gemeint habe, er hats aber vielleicht noch besser ausgedrückt.

 

[Hafish]

Ist ja ganz nett, nur gibt es zwei gravierende Probleme, selbst wenn das Programm tatsächlich so funktioniert wie es soll:

1) Es werden keine dynamischen Faktoren berücksichtigt. Das Programm versucht so schnell wie möglich das angegebene Ziel zu erreichen. Im der Beispiel-BO werden zum Beispiel zwei Overlords direkt hintereinander gebaut. Das mag ja vielleicht sinnvoll sein, wenn man sowieso keine Ressis ausgeben kann, weil man ja auf Roaches spart und wenn man das Supply braucht. Aber was wenn man zwischendrin irgendetwas gescoutet hat, was einen zum Abbruch der Strategie zwingt, z.B. einen Air Tech oder von mir aus auch Marauder? Dann hat man auf einmal einen Nachteil. Ein Mensch könnte sowas mit einplanen und z.B. sagen "ok, mit Komponente x verzichte ich auf einen kleinen Vorteil zugunsten einer selten vorkommenden, aber dafür umso schlimmeren Abweichung."
Genauso ist es zum Beispiel mit einem (auch im Video angesprochenen) frühen Zerglingpush. Möglicherweise könnte man den mit einem Spinecrawler halten. Aber den Spinecrawler kann man nicht einbringen, weil dann irgendwie die Berechnung nicht mehr sauber hinhaut.

Extremes Beispiel: Wenn die Bedingung ist, so schnell wie möglich 10 Broodlords zu kriegen, dann wird das Programm vermutlich früher oder später herausfinden, dass es sinnvoll ist, erstmal 3 Exen zu bauen und bis 70 Supply Drones zu pumpen. Aber das lässt völlig außer Acht, dass es dazu natürlich nie kommen wird, wenn der Gegner sich nicht Bronze-mäßig einbunkert. Wenn der Gegner plötzlich beschließt go zu machen, dann ist es einfach zu spät zum Reagieren. Denn der optimale Weg sieht einfach nicht vor, dass man zwischendrin gestört wird. Ein Switch ist dann nicht mehr möglich, er ist verbaut durch die "Optimierung". Ein Mensch hätte direkt am Anfang gesagt "naja, um vor einem Go geschützt zu sein, muss ich eigentlich nach der ersten Hatch direkt mal nen Pool bauen, obwohl das das angestrebte Ziel nicht fördert.

2) Der zweite Nachteil ist aber irgendwie viel gravierender. Man muss das Ziel selbst vorgeben. Ok, dann nimmt einem der Computer immer noch die Arbeit ab, selbst den Optimalen Build zu finden (mit den Nachteilen aus 1.). Aber trotzdem ist doch genau diese Zielvorgabe gerade das entscheidende. Der wichtigste Schritt ist doch gerade zu sagen "hey, ich glaub eine geile Strat wären ganz früh 7 Roaches". Was tut der Terraner, der in dem Video verloren hat? Er kann nicht eingeben: "ich hätte gern einen Konter für 7 Roaches nach 5:30 mins". - Nein. Er muss sagen: Ich hätte gern in 5:30 mins 7 Marauder und einen Bunker. Nur, wenn er den Schritt im Kopf schon gemacht hat, kann er kann er das Programm einen Build finden lassen (wenn es den gibt).

Wenn man jetzt beide Punkte kombiniert, kommt man zu dem Schluss, dass das Programm, bzw. die Art von Algorithmus eben nicht in der Lage ist das Problem zu lösen: Denn man muss als Mensch immer mehr Möglichkeiten mit einplanen, die dann als zusätzliche Bedingungen mit Einfließen. In dem Broodlord Beispiel muss die Bedingung eben nicht sein "10 Broodlords", sondern "10 Broodlords, Pool spätestens bei 15 supply". Dann verliert man gegen einen Terran der Mit 80 Supply go macht und erweitert die Bedinungen um mind. xy Units nach 8 Minuten." usw..
Damit der Algorithmus also wirklich beeindruckend ist, müsste er nicht versuchen eine Bedingung durch Selektion herauszufinden, sondern ganze KIs evolutionär zu entwickeln. Nur das sprengt den Rahmen, die Rechenkraft, vermutlich auch die Skills des Autors und vor allem den Sinn des Spiels!

Das Programm ist also in meinen Augen bestenfalls eine kleine Spielerei, um einem das nervige Rumprobieren abzunehmen. Aber die Strategie selbst muss man doch selbst "erfinden". Insofern ist auch die zugegebenermaßen "gelungene" Überschrift verwirrend: Es scheint, als hätte das Computerprogramm etwas entwickelt, tatsächlich hat es nur fast auf Trial-and-Error-Level eine bereits gefundenen Strategie optimiert - was der Erfinder früher oder später selbst gemacht hätte.

Abgesehen davon finde ich, dass es dazu gehört, Builds auszuprobieren. Wie langweilig ist es denn bitte wenn der Computer das macht? Aus informatischer Sicht ist es sicherlich in gewissem Maße genial, aber doch nicht aus spielerischer oder gar E-Sport Sicht...