KI-Tipp für Starcraft 2

[exetex]

Hallo inbroodwar.de Commu und instarcraft.de Commu.^^

Ich habe gerade die "Q&A Runde mit Frank Pearce" gelesen und darüber Stand was wegen der KI im Game.
Ich finde es lobenswert vom Blizzard Int. das sie sich auch darum gedanken machen.

- Bizzard danke das ihr UNS, die Commu, an eurem neuen Projekt so teilhaben lässt -

Jetzt stell ich mir eine Frage:
Ist es nicht heutzutage möglich, die KI für Stacraft 2 so anzupassen, das es möglich ist, das sich die KI im Multiplayer so an den bzw die Spieler anpasst, so das sie extrem lernfähig ist und das man auch mal verliert, wenn man gegen sie Spielt?
Mir kam dieser Gedanke, weil ich denke das nicht alle Menschen, die Starcraft spielen, immer im Battle.net sind da sie kein Internet haben oder es andere Gründe dafür gibt zB "sind ja eh nur Hacker im B-Net".

Was ist eure Meinung dazu?
Sagt Blizzard dazu was auch?

 

[erdling]

Ist es nicht heutzutage möglich, die KI für Stacraft 2 so anzupassen, das es möglich ist, das sich die KI im Multiplayer so an den bzw die Spieler anpasst, so das sie extrem lernfähig ist und das man auch mal verliert, wenn man gegen sie Spielt?

der satz rockt

zum thema: ich bezweifle dass es lernfähige KI gibt. Man könnte Schwierigkeitsgrade einfügen, was Blizzard auch sicherlich vor hat.

Dann wird aber der schwierigste PC irgendwelche cheateigenschaften haben wie damals die supercomputer in sc, die immer mins geschenkt bekommen haben...

 

[NumbSchiller]

Schach ist im Vergleich zu BW ein äußerst "einfaches" Spiel. Das heißt die Möglichkeiten sind relativ begrenzt. Bei BW gibt unendliche viele Varianten und Arten zu spielen.

Für Schach ist man gerade soweit eine Ki zu programieren die mit dem besten Spieler der Welt mithalten kann...

ich kann mir nicht vorstellen dass es eine faire Ki gibt die bei bw mit einem menschlichen spieler mithalten kann

 

[IsCream]

Du meinst, dass BW im Vergleich zu Schach ein einfaches Spiel ist. Die Möglichkeiten in Schach sind um einige Potenzen höher als in BW. Bei BW ist eine Begrenzung im Schaden und in Counter-Drei oder Vierecken. bei schach kann jede Figur jede schlagen.

Auch sind Schachcomputer heute schon besser als Spieler es sind, weil sie einfach mehr Spielzüge im voraus berechnen können und auf verschiedene Wege zurückgreifen können als Menschen (ein wahnsinnig gutes Schachprogramm ist Fritz. Damit trainieren sogar Großmeister). Wenn du die KI richtig programmierst, sind die immer besser als menschen, unter der Voraussetzung, Mensch und machine spielen unter den gleichen Voraussetzungen und nur bekanntes kann eingesetzt werden.

 

[Picard]

Original geschrieben von erdling.


der satz rockt

zum thema: ich bezweifle dass es lernfähige KI gibt. Man könnte Schwierigkeitsgrade einfügen, was Blizzard auch sicherlich vor hat.

Dann wird aber der schwierigste PC irgendwelche cheateigenschaften haben wie damals die supercomputer in sc, die immer mins geschenkt bekommen haben...

klar gibts "lernfähige" ki, besser gesagt adaptierende. schon alleine wenn statistik betrieben wird (wieviele einheiten baut der spieler -> gib contra, aber nicht zu hart, er hat erst 5 spiele gemacht usw usf).

ob sowas im spiel sein wird, weis ich allerdings nicht.

 

[IPSZeRo]

Ne bessere KI wirds mit Sicherheit geben.
Wahrscheinlich wie bei WC3 mehrere Schwierigkeitsstufen.

Es ist auch bestimmt möglich ne KI zu implementieren die sehr schwer zu schlagen ist durch ihr perfektes micro und macro und den Maphack vorteil der wahrscheinlich weiterhin da sein wird.

Aber was man wirklich will ist eine menschlich spielende KI und das ist halt sehr kompliziert.
Die KI bekommt die aktuellen strategischen entwicklungen halt nicht so mit und benutz dem entsprechend nicht wie ein Mensch die Konter builds dagegen.
Aber evtl. schafft Blizzard es ja die KI so gut zu machen das man zumindest in der Anfangszeit noch große Probleme gegen sie hat.

 

[neustadt]

Der Grund wieso Schachcomputer so gut sind, ist weil man bei Schach mit genug Rechenpower ALLE Zuege vorrausberechnen kann. Der Schachcomputer macht dann immer den perfekten Zug.
SC ist um längen komplexer als Schach. Es gibt kein klar definiertes Spielbrett mit nur 64 gleichwertigen Feldern. Es gibt keine Resourcen. Es gibt kein Damagesystem. Spells, Tarnung, etc.etc.

Im Gegensatz zu Grafik, Physik und Budget hat die bei KI bei Computerspielen keine Riesenspruenge gemacht, im letzten Spielejahrzent. Spiele welche heute mit einer guten KI daherkommen, setzten alle kluge Script Events ein, um eine schlaue KI zu simulieren.

Heutige Spiele sind noch viel zu Komplex, als dass ein Computer ggn einen Menschen eine Chance hätte. Warum dass so ist? KP, damuesste man nen Informatiker hier Fragen. Jedenfalls ist Computer KI gerade erst auf dem Weg im Pokern ggn Profis zu gewinnen.

Wie gut die KI bei SC2 sein wird, hängt davon ab wie frueh sich Blizzard mit dem Thema KI-Skripts auseinandergesetz hat und wie wichtig Ihnen das Thema ist. Häufig wird die KI erst relativ kurz vor Release zusammen gebastelt. Zum Glueck ist Blizzard dafuer nicht bekannt. Ich gehe schon davon aus, dass die SC2 KI einen schlaueren Eindruck machen wird als bei War3. Die KI wird aber sicher nicht "wirklich" lernfähig sein. Sie wird also nicht in der lage sein, sich auf BOs einzustellen die sich erst im Laufe der Zeit erscheinen werden. Damit wirds auch nix mit der Hoffnung des OP, dass sich die KI im Laufe eines oder mehrerer Spiele, sich dem Spielniveau des Spielers anzupasst.
Wenn die Leute bei Blizzard wieder vergessen werden der KI zu sagen, dass sie eine gegnerische Sunken auf eigenem Creep anzugreifen hat, wird sie dass auch nach 1001 Spielen nicht raffen.

 

[Picard]

für nen computer sind unittables / managment usw einfach kein problem. probleme kriegen sie halt mit dem abstrakten denken. gute counters bringen usw - kein problem. schließlich "weis" er ja alles, kann über den nutzeraccount über des spielers lieblingsunits bescheid usw usf.

einen kreativen drop hinlegen (der nicht vorprogrammiert ist) ist dann schon eher schwierig - sowas wie "gehe mit 10units vor die base zum ablenken und droppe mit 2phaseprisms in die main". ist schon relativ harte arbeit dem computer "beizubringen", dass höheres terrain besser ist um darunterliegende einheiten anzugreifen. möglich ist heute schon verdammt viel, nur keine kreativität und viele der menschlichen aspekte des spiels. aber soweit ich noch weis haben die bei blizzard nen "very talented guy" an der KI werkeln. und verdammt, ich hab so nen geiles buch über gamedesign, da hatten sich auch etliche blizzardleute drin geäußert... borgen bringt sorgen ;(

 

[NumbSchiller]

dass die KI besser wird ist schon klar

aber meiner meinung nach ist schach wesentlich leichter zu programmieren als eine BW Ki... einfach weil es nur eine "map" gibt die auch noch sehr einfach strukturiert ist

man kann klar berechnen was wann passiert und wie der gegner reagieren kann
bei bw geht das nicht

mal ganz abgesehen von der entwicklung der strategien und den intuition

 

[KeYKa]

Das Problem bei einer KI ist doch wie oben gesagt, dass sie "Situationen" nicht richtig nutzen.

Gegner schleudert mir seine 10 XY Units entgegen, die kacken aber gegen meine total ab, weil ich halt gescoutet habe und die counterunit gebaut habe. Natürlich gehe ich zum Gegenangriff über, crushe ne Exe, oder whatever.

Der PC durchschaut das nicht so leicht.

Was nen PC halt stark macht ist die Fähigkeit absolut alles im selben Moment machen zu können.

Vorne im Kampf die Units kontrollieren, hinten Units nachbauen, bei Exe1 neue Sammler in Auftrag geben und bei Exe2 den gerade neu gebauten Sammler zum Mins ernten schicken.
Also der totale Überblick, der den menschlichen Spielern schlichtweg fehlt. Niemand - nichtmal die Kor Pros - können das alles gleichzeitig machen. Auch wenn sie nah dran sind

 

[Picard]

Original geschrieben von NumbSchiller
dass die KI besser wird ist schon klar

aber meiner meinung nach ist schach wesentlich leichter zu programmieren als eine BW Ki... einfach weil es nur eine "map" gibt die auch noch sehr einfach strukturiert ist

man kann klar berechnen was wann passiert und wie der gegner reagieren kann
bei bw geht das nicht

mal ganz abgesehen von der entwicklung der strategien und den intuition

nunja
vereinfacht gesagt kann man ne map auch mit nem schachbrett vergleichen.
stellst dir mal als koordinatensystem vor. jeder punkt (=spielfeld) hat beim schach nen wert 0 oder 1 (schwarz oder weiß). erweitere das mit ner 2 und definiere diese als baum. erweitere erweitere erweitere und prompt hast du ne broodwar map. im 3d isses natürlich nicht ganz soo einfach, aber auch nicht allzu schwierig. das betrifft halt die goto routinen.

aber ich denke die KI in SC2 wird schon top werden, sowohl die aktive als auch die passive

 

[aFrI]

hmmm dann braeuchte die cpu fuer jede unit ne wertigkeit, mit der sie erkennt, ob die eigenen units im vergleich zum gegner ausreichen und dann darauf beruhend ne entscheidung zu tech, wiederrum basierd, wieviel mins / gas so in der naehe is... moeglich is da bestimmt einiges.. aber umsetzung... koennen wir besser auf sc3 warten, dass sowas kommt xD

 

[Picard]

na die gibts doch. intern liegen doch sowieso die daten dafür vor (einheitentyp, schaden, bonusschaden), das wird einfach zusammengerechnet und ausgewertet, sachen von nen paar millisekunden.

 

[Kangaxx]

Was die Programmierung der KI angeht, ist Schach vieeel einfacherer als SC!! (Was nicht heißt das Schach auch für einen Menschen einfacherer zu spielen ist.)

Das ist doch schon an folgender Rechnung leicht einzusehen:
Beim Schach hat man maximal 140 verschiedene Möglichkeiten pro Zug.
Dies kommt so zustande:
8*4 (maximal 8 Bauern, jeder kann maximal 4 verschiedene Züge machen)
+ 2*14 (2 Türme, jeder kann maximal 14 verschiedenen Züge machen)
+ 2*14 (2 Läufer, ...)
+ 28 (Dame)
+ 8 (König)
+ 2*8 (2 Springer)
= 140

Was hier die Zahl so niedrig hält ist die Schachregel, dass maxmial eine Figur pro Zug bewegt werden kann, was bei SC anders ist: Hier kann im Prinzip in jedem Moment jede dem Spieler zur Verfügung stehende Einheit einen separaten Befehl bekommen. Dies exponenziert die Handlungsmöglichkeiten.

Nehmen wir an, wir spielen SC auf einer 96x96 Map (ohne Wasser etc., was wichtig für die Rechnung ist, damit jeder Punkt auf der Karte von jeder Einheit erreicht werden kann) und man hat Maximum-Supply, also 200 Units maximal. Nun vereinfachen wir noch und nehmen an jede Unit würde nur den move Befehl kennen. Dann kann jede Unit 96*96=9216 verschiedene Befehle ausführen. Somit können einem Paket von 200 Units die verschiedensten Kombinationen dieser Befehle erteilt werden. Wer ein wenig von Kombinatorik versteht, weiß dass es genau 9216^200 sind, was eine unvorstellbar große Zahl ist. Und jeder dieser möglichen Befehelskombinationen müsste auf ihren strategischen Wert überprüft werden.

Ok, zugegebenermßen kann man sehr, sehr viele dieser Möglichkeiten von vorneherein ausschließen, weil sie nur zu schlechten strategischen Lagen führen würden. Aber gerade diese Selektion, welche Möglichkeiten es sich lohnt zu überprüfen und welche nicht, ist halt nur schwer algorithmisierbar (gibt es das Wort überhaupt??). Das hängt von vielen Faktoren ab (allein schon von der Map).

Außerdem gestalltet sich die Alayse der Möglichkeiten auch noch viel komplexer als beim Schach. Beim Schach hat man nämlich feste Zeitpunkte zu denen die, durch die theoretisch möglichen Züge neu entstande Spielsituation beurteilt werden muss. Nämlich immer dann wenn der Computer am Zug ist. Bei SC kann aber eine der Möglichkeiten eine viel kürzere Zeit zu vollständigen Ausführung beanspruchen, als eine andere Möglichkeit. Sei z.B. Möglichkeit 1 das Stehenbleiben aller Units an ihrem Ort. Und Möglichkeit 2 das Bewegen von allen Units in die obere linke Ecke. Die Ausführung von Möglickeit 1 benötigt keine Zeit, während die Ausführung von Möglichkeit 2 wohl mehrere Sekunden dauern wird. Beim Schach dauert jeder Zug gleich lang, nämlich genau einen Zug des Gegners.

All dies erfordert wohl ganz andere Konzepte bei der KI-Programmierung von RTS-Spielen. Und zwar welche die nicht auf der Analyse aller möglicher Spielzüge basiert. Aber dieses Vermögen macht die Schachcompis gerade so stark.

Ok soviel daszu. Trotzdem bleibt Schach für den Menschen das schwierigere Spiel...

 

[neustadt]

Original geschrieben von Pikkart
für nen computer sind unittables / managment usw einfach kein problem. probleme kriegen sie halt mit dem abstrakten denken. gute counters bringen usw - kein problem. schließlich "weis" er ja alles, kann über den nutzeraccount über des spielers lieblingsunits bescheid usw usf.

Hm. Ja du hast mit Unitmanagement wohl Recht. Hier könnte sich evt. eine wirkliche Verbesserung der KI zeigen. Ich stelle mir dass so vor, dass sich der Computer die Armee des Gegners in verschiedene Eigenschaften aufteilt: Einheitenart (Air/Boden), Angriffsart (Air/Boden) und Schadensart (Melee/Range/Splash/Cast). Daraus sollte er dann berechnen können welche Unitverteilung er als Counter braucht.
Zusätzlich sollte es eine Art "Vorsicht-Faktor" geben. Dieser steigt, wenn sein Gegner ueber Gewisse UnitCombos verfuegt. Sair/Dt oder alles was Eco Drop/Harras zu tun hat. Je höher der Wert desto mehr Defensive fuer die eigene Eco wird gebaut.

Ich frage mich gerade in wie weit, dass nicht sogar fuer das Resourcen Management gelten kann. Ist seine Armee stark genug um eine Exe zu und halten und hat der Gegner keine Units ggen die er nicht kontern kann? Dann gogo Exe.
Es muesste wohl auch möglich sein eine zu fruehe Exe des Gegners zu bestrafen.
Wenn man davon ausgeht, dass der Computer alles weiß, kann er berechnen zu welchem Zeitpunkt ein Timing-Push 100% perfekt ist.

einen kreativen drop hinlegen (der nicht vorprogrammiert ist) ist dann schon eher schwierig - sowas wie "gehe mit 10units vor die base zum ablenken und droppe mit 2phaseprisms in die main". ist schon relativ harte arbeit dem computer "beizubringen",
dass höheres terrain besser ist um darunterliegende einheiten anzugreifen.

Hm, ich denke dass auch dies möglich sein sollte.
Zu den von vorhin erwähnten Unit Eigenschaften kommt eine Eco Drop/Harras Eigenschaft hinzu. Zusätzlich muessen dem Computer verschieden Angriffsziele einprogramiert (Eco / Exe / Armee des Spielers).
Wir gehen davon aus, dass der Computer die Verteidigung des Spielers kennt. Sowohl Armee, als auch Gebäude technisch.
Beispiel: Der Spieler hat eine Exe, keine Verteidigungsgebäude und eine Armee. Durch die Mobilität der Armee bleibt ein EcoVerteidigungswert des Spielers höher als der EcoDropWert des Shuttles. Der Computer fliegt mit dem Dropshuttle (Gebaut durch Skript) nur in die Nähe der Basis. Nun versucht der Computer einen Angriff auf ein weiteres Ziel: Exe. Der Spieler muss seine Armee zur Exe ziehen, wodurch der EcoVerteidiungsWert sinkt. -> Das Shuttle setzt sich in Bewegung.


Ich denke der Grundlegende Unterschied zwischen KI und Mensch ist, dass die Programierer alle Eigenschaften die Auswirkungen auf die Zielsetzung des Spiels (den Gegner zu Killen) haben, der KI beibringen muessen. Die Kreativität des Menschen findet aber immer Wege Eigenschaften stark zu verändern (z.B Verteidigungseigenschaft einer Basis durch Wall-In oder Assi kill auf Troy) oder neue, an welche die Programierer nicht gedacht haben.

Ich frage mich wie stark eine KI wäre, die das gesamte heutige Wissen ueber SC abdeckt. Ein Post zuvor hätte ich noch stark angezweifelt, dass sie in der Lage wäre einen Progamer zu schlagen. Jetzt bin ich mir nicht mehr sicher...

...Ja ich glaube sogar dass sie sogar unschlagbar wäre, denn es ist sicher möglich der KI (nahezu) perfekte Micro mit perfektem Macro und perfektem Multitask beizubringen. Selbst ein Klon aus Boxer, July und Bisu könnte da nicht mehr mithalten.
Achso, den allwissende Modus habe ich in Gedanken schon länger durch scouting ersetzt.


Solange bis es vllt eine neue Map gibt auf der die KI abspackt, weil etwas zuvor nicht bedacht worden ist. Sowas wie Troy oder 815 geht schon nichtmehr. Die heutige KI muss sich im klaren sein, ob ein Choke dicht ist oder wie viele und welche Units durchpassen. Es muesste also etwas extrem radikales sein, dass es warscheinlich auch unter spielern als 100%ig imba gilt, diese Eigenschaft auszunutzen. Quasi Bug oder so.



Ok Ende mit Philsophiestunde. Welcher Informatiker hier programmiert das als seine Diplomarbeit? Ich will sehen wie zwei KIs perfektes SC gegeneinander zocken!

 

[violett]

vom rein strategischem her ist schach sicherlich komplexer als bw, aber man darf das micro nicht unterschätzen.

man könnte wie im schach halt die ki immer updaten, in dem man sie mit den aktuellen replays versorgt und sie dann wie im schach den statistisch besten counter aus der gegebenen spielsituation errechnet.
problem dabei ist, das es viel mehr felder in starcraft gibt und das es kein rundenbasiertes spiel ist, die rechenleistung wäre viel größer.

 

[Master_Black]

Ich glaube nicht das die KI wirklich bahnbrechende Veränderungen in SC 2 durchlaufen wird, die KI in Warcraft 3 war ja auch nicht besser als die SC 1 KI, z.B. Inselmaps hat sie im Gegensatz zu SC 1 überhaupt nicht verstanden, baute einfach munter Einheiten und versauerte dann auf ihrer Insel, da sie keine Boote oder Zeppeline sinnvoll nutzen konnte, manchmal mit Glück landete sie mit einer Miniarmee, die schon an der Basedeff scheiterte. Klar waren diese maps Ausnahmen und genossen daher keine priorität beim KI entwickeln, aber dies zeigt eben das die KI nicht kreativ denken kann, sondern gescriptet ist. Oder in SC 1 versucht die KI eigentlich nie direkt die Eco anzugreifen, bzw. kurze Scheinangriffe durchzuführen um an anderer Stelle dann richtig anzugreifen, sie kennt nur echte Angriffe, aber harassen und den Gegner ablenken kann sie nicht. Und in Warcraft 3 gab es eigentlich nur 2 KI Level, denn Irrsinnig ist keine andere KI, sondern die gleiche, die aber mehr Ress erhält, als man eigentlich bekommt, also eigentlich spielt sie nicht bessser, sondern cheatet einfach. Ich vermute mal, dass einige Aspekte der KI verbessert werden, aber bis es wirklich Durchbrüche auf diesem Gebiet gibt dauert es wahrscheinlich noch, da die wenigsten Entwickler bei der KI Weiterentwicklung ihren Schwerpunkt setzen, sondern eben ehr Graphik.

 

[CyoZ]

Die Programmierung einer KI, die Top Spieler auch nur ein paar Tage schlagen kann würde Blizz wahrscheinlich mehr Ressourcen kosten als die Entwicklung aller ihrer bisherigen Spiele.

 

[team-gskill]

In KI's wimmelt es nur so von Rekursionen, welche ziemlich speicherhungrig sind, aber ansonsten eigentlich nur Vorteile haben.
Und wenn man schon ein grosses Team und viel Rechenleistung brauch, um eine ebenbürtige SchachKI zu schreiben, wird es für SC mit ihren 200 Unitsupplys wohl nicht einfacher.

 

[Sok4R]

Original geschrieben von exetex
Jetzt stell ich mir eine Frage:
Ist es nicht heutzutage möglich, die KI für Stacraft 2 so anzupassen, das es möglich ist, das sich die KI im Multiplayer so an den bzw die Spieler anpasst, so das sie extrem lernfähig ist und das man auch mal verliert, wenn man gegen sie Spielt?

aufgrund diese Satzes gehe ich mal davon aus dass du noch nie eine Zeile Programm-Code geschrieben hast oder dich mit der Spiele-Theorie beschäftigt hast.
Es geht, aber der Aufwand währe kolossal.

Zum Thema Schach vs. StarCraft: Schach ist um einiges einfacher: Das Spielfeld ist immer gleich, alle Felder sind gleichwertig. Die Ausgangsposition ist immer gleich, du siehst alles was ein Gegner macht. Dadurch kann eine KI viele Züge im vorraus berechnen (Spielbäume malen für Schach ist was herrliches =). Klar hast du immernoch viele Möglichkeiten (ein kompletter Spielebaum hat 64 Ebenen, das Teil explodiert aber in der Breite), aber verglichen mit StarCraft ist es geradezu lächerlich. Alleinschon daraus, dass du nicht jederzeit sehen kannst, was dein Gegner tut musst du vermutungen anstellen. Außerdem musst du das verhalten der KI explizit programmieren, was wieder in einem riesigen Aufwand endet.

Aber da heute ja breitbandige Internetleitungen für den größten Teil der Bevölkerung Nordamerikas und Westeuropas Normal ist, warum dann so einen riesiegen Aufwand zu betreiben, von dem nur ein Bruchteil der Leute einen nutzen hat. Deswegen wurde die KI entwicklung allgemein in den letzten Jahre vernachlässigt. Zudem lassen sich die sog. "Casual Gamer" mehr mit toller Grafik beeindrucken als mit der KI.

Vor ner weile gabs dazu einen sehr interessanten Artikel in der GameStar, mal gucken obs den auch online gibt.
€dit: http://www.gamestar.de/magazin/report/kuenstliche_dummheit/1477118/kuenstliche_dummheit.html
ich hätte auch noch die HP von meinem Prof. verlinkt, aber er hat leider schon alle Unterlagen gelöscht =/
War ein kleiner Absatz zu Spieltheorie drin, am beispiel des Springerproblems und Tic-Tac-Toe. Einfach mal danach googlen, gibts bestimmt einiges dazu im Internet.

 

[mTwNarutO]

Bezüglich Schach.

Man hat niemals die Maximalanzahl Möglicher Züge. Du wirst keine Situation haben wo du wirklich 140 verschiedene Züge machen kannst.

Das Beispiel an Möglichkeiten auf der 96x96 Map ist schon ziemlich krass... rechne das mal auf eine 256x256 hoch !

Schach ist nicht ansatzweise so komplex wie Starcraft.

 

[Master_Black]

Wie schon gesagt, Schach ist von den Möglcihkeiten stark begrenzt, z.B. entweder eine Figur ist auf dem Brett oder sie wurde geschmissen, aber in SC hat die Figur HP, die sich zudem noch teils verschieden regenerieren, Schilde, Energie usw. was ja auch nochmal mit einbezogen werden muss, nicht das der PC eine fast tote Einheit zum Angriff schickt oder seinen Angriff ohne Energie/Fähigkeitensupport durchführt. Außerdem muss die KI ja nicht nur erkennen was sie tun könnte, sondern müsste sich auch entscheiden was davon das sinnvollste ist, z.B. ob sie beim Gegner landet, ihre Armee vorher weiter ausbaut, eine Exe baut oder eine Kombination davon. Und sie kann im Gegensatz zu Schach auch nicht nach jeder Aktion neu berechnen was sie nun macht, da sie ja unter Zeitdruck steht und sofort handeln muss. Außerdem kennt die KI in Schach die genaue "Armee"zusammensetzung des Gegners, während sie in Starcraft nur Vermutungen anstellen kann, bzw. auch wenn sie die Gegnerarmee kennt, muss sie einschätzen wie der Gegner sie einsetzt, wie viele Ressourcen er hat um sie weiterauszubauen im Vergleich zu den eigenen. Oder z.B. wie sie ihre Armee am besten über die Karte verteilt um effektiv zu sein und sich bestimmte Dinge für den Notfall vorzubehalten wie z.B. Scannen um nicht im Notfall masakriert zu werden. Es gibt im Gegnsatz zu Schach viele Ungewissheiten für die KI, es sei denn man gibt ihr einen Wallhack, was aber auch nicht das wahre ist.

 

[team-gskill]

Euer Schachvergleich ist aber auch nicht ganz richtig, da ja die nächsten 1X Schritte vorrausberechnet werden müssen.
1500 Züge kommt wohl eher hin.
Eine KI die nur am Zug jede Möglichekeit durchrechnet würde gegen Kasparov ja schon nach 10min am Ende sein.

 

[mTwNarutO]

Okay, nehmen wir deine 1500 und verzehnfachen das, dann haben wir

15000 Züge die berechnet werden müssen.

Okay vergleichen wir mal...

256x256 = 65536

Das wären die Zugmöglichkeiten für eine Einheit...
Das aufs Maximum (400(!) scourges/linge) würde bedeuten:

65536^400 = 3,9081592266432387331746142836148e+1926

Alles klar ;D?

 

[team-gskill]

Schön. Mein Posting bezog sich nicht auf den direkten Vergleich.
Trotzdem danke für die Rechnung.

 

[Blackhand]

Es gibt zwei Unterschiede , suche in einem großen Raum und Machine Learning. Bei ersterem ist die tolle Rechnung 65536^400 = 3,9081592266432387331746142836148e+1926 relevant. Bei zweiterem nicht. Dort passiert nämlich ein induktives Lernen, das heisst aus Beispielszenarien wird eine Fehlerfunktion erstellt (vom Anwender) und diese dann bezüglich Randbedingungen optimiert. Aber selbst dieses Verfahren skaliert nicht.

Zur Eingangsfrage : Eine massiv adaptierende KI wird es nicht geben weil ihr dann einen Großrechner für die Berechnungen neben eurem eigentlichen PC braucht.

Und hier mal ein Beispiel, ich arbeite zur Zeit an einem Projekt das die Wassernutzung des Grand Coulee Staudamms in Colorado optimieren soll. Dabei wird das Machine Learning Verfahren Reinforcement Learning genutzt. Allein um das model zu berechnen hat mein laptop 14 Tage gebraucht.

Ich erwarte das sich die KI in Starcraft auf diverse Heuristiken stützen wird. Diese ermöglichen ein intelligent aussehendes handeln (es gibt einen Unterschied zwischen Intelligenten Systemen und Systeme die sich intelligent verhalten) ohne zuviel Rechenpower zu beanspruchen.

 

[Kangaxx]

Original geschrieben von Blackhand
Es gibt zwei Unterschiede , suche in einem großen Raum und Machine Learning. Bei ersterem ist die tolle Rechnung 65536^400 = 3,9081592266432387331746142836148e+1926 relevant. Bei zweiterem nicht.

Richtig. Ich wollte mit meiner Rechnung auch nur aufzeigen, dass das was Schachcomputer so stark macht, nämlich das Vorausberechnen aller möglicher Züge bei RTS-KI nicht funktionieren kann, da man eine viel zu große Rechenleistung benötigte.
Und dies wiederum wollte ich aufzeigen, um zu verdeutlichen, dass nur weil es heute Schachcomputer gibt, die den Weltmeister schlagen können, es nicht heißt, dass es heute auch möglich wäre RTS-KI's zu programmieren, die fair spielen und trotzdem 'nen Pro aus Korea besiegen könnten. Dies wurde ja hier am Anfang des Threads vermutet.

 

[Sok4R]

es muss nicht mal starcraft sein, es reicht schon go als vergleich.
schach-computer können heute die großmeister schlagen, aber die besten go programme werden von mittelmäßigen spielern niedergemacht. weil die zahl der möglichkeiten einfach zu groß ist und der rechnenaufwand ins unermessliche steigt. und wer will schon mehrer jahre warten bis die ki dann den perfekten zug macht? vor allem: an anfang gibt auch eine sehr große zahl von perfekten zügen die zum sieg führen, wie wählt die ki dann einen aus?

 

[neustadt]

Ich kann mir vorstellen, dass eine KI mit einer Mischung von Skripten und Berechungen von Warscheinlichkeiten (ähnlich wie beim Poker), sehr stark ist. Nicht funktionieren wird eine komplette Durchrechnung aller Möglichkeiten wie beim Schach, was hier auch viele so sehen. Das braucht die KI aber auch nicht. Um einen Menschen zu schlagen kann sie sich einfacheren Mitteln bedienen: Micro / Marco / Multitask gibt es beim Sachch nicht, sind aber bei SC von essentieller Bedeutung und können von eimem Computer gut ausgefuehrt werden.
Wie schwierig es ist eine solche KI umzusetzen, kann ich aber nur erahnen.

Erstmal vorweg die KI muss die Karte auf der gespielt wird kennen. Sonst gibts keine Chance auf Win, da sie nie den Gegner finden wuerde bevor der die KI 9pooled. Hierdurch bieten sich weitere vorteile: Die größe einer Karte relativiert sich. Eine ExLocation besteht zwar aus vielen Pixeln, defakto ist es aber nur ein Punkt den die KI ansteuern muss, um sich ein Bild ueber die Vorgänge beim Spieler zu machen. Ähnliches gilt fuer Mainbase. (schwierig wirds wenn die KI Proxys scoutet).

Ebenfalls eingeskriptet muessten die BOs sein, welche die KI bis zum ersten Scout durchzieht. Die weiteren Handlungen verlaufen dann ueber mein beschriebenes "Eigenschaften und Zielsetzungsmodell" (Ich hoffe das war verständlich, denn es war schon recht spät).

Sollte so eine KI nicht in der Lange sein kann durch Abwägung der vergangene Spielzeit und Scout eine sehr gute Einschätzung der Situation zu haben? Auch wenn Starcraft im Gegensatz zu Schach nicht vollständig durchzurechnen ist; das Ressourcensystem des Spiels beschränkt die "Spielzuege" der Spieler auf ein Maß welches ueberschaubar ist (wenn man im early game bleibt) und vorallem durch Mathemathik bestimmt wird, also algorithmierbar ist.

Was meint Ihr? Ist die Mathematik einfach genug, oder sind die Spielzuege des Gegners zu Komplex, welche die KI vorrausberechnen muss, wenn ihr ein scout nicht gelingt?

 

[Blackhand]

Was meint Ihr? Ist die Mathematik einfach genug, oder sind die Spielzuege des Gegners zu Komplex, welche die KI vorrausberechnen muss, wenn ihr ein scout nicht gelingt?

Bei Starcraft handelt es sich um einen diskreten Zustandsraum (ja auch die Zeit läuft im Rechner diskret ab). Das heisst eine Expansion in einen Suchbaum ist möglich. Wenn man die maximale Suchtiefe begrenzt kann man sogar lokal optimale Züge in relativ kurzer Zeit finden (je nach Verzweigungsgrad des Baumes). Die Frage ist wie modelliert man einen Zustand so das man suchen könnte (wenn man suchen wollte).
Weiterhin braucht man eine Bewertung von Zuständen um eine Effizienzmaximierung zu ermöglich. Das Kostet alles massiv Zeit.
Aus diesem Grund ist ein probabilistisches Verfahren mit einigen Heursitiken sicherlich effizienter. In etwa ein regelbasiertes System der Art , "hat der Spieler n Einheiten vom Typ <Einheitentyp> bau den Counter (bzw. baue die Gebäude dafür etc.)". Bei Regelbasierten Systemen muss man aber auch auf die Performanz achten, je mehr Regeln, um so mehr muss man überprüfen. Zudem muss man auch wie oben die Regeln bezüglich eine Bewertung ordnen. Und bei gleichwertigen Regeln zufällig auswählen. Weiterhin kann man hier multiple Regeln in einem Entscheidungszyklus wählen. (Counter bauen und eine Exe oder sowas).
Wenn ich die KI Entwickeln müsste würde ich wohl eine Mischung aus standartisiertem Verfahren (wähle eine aus 5 Start BO's zufällig u.ä.) und einem kleinen Regelsystem einbauen. Alles andere dauert zu lange. Eventuel noch einige gescriptete Aktionen die spezielle Spielzüge darstellen, wobei man hier wieder erkennen mus swann und wo man diesen Spielzug anbringen kann, oder man macht es zufällig, aber dann gibts vielleicht einen Drop in der eigenen Basis oder so Späße ;D

Ein anderer Interessanter (aber unpraktikabler) Ansatz wäre nicht eine Zentrale KI zu modellieren sondern jeder Einheit eine eigene KI geben (sogenannte Agenten) und dann Koordinationsverfahren der Agenten untereinander zu benutzen. Dieses Verfahren kann hochgradig Adaptiv sein ist aber auch aufwändig. Ich hab sowas mal in einer Gridworld umgesetzt, dabei gab es 6 Agenten die vs. andere 6 Agenten gespielt haben (CLIMA Competition) und Gold sammeln mussten. Man kann maximal 3 Gold sammeln und muss es dann zurück bringen. Dazu ist die Welt unbekannt. Man musste also die Agenten koordinieren das : schnell gescoutet wird, schnell Gold geholt wird, der Gegner wenig Gold bekommt. Bei SC wären das dann xxx Agenten mit yyy mehr an Möglichkeiten, also das skaliert sicherlich auch nicht. Aber wäre ein spannender Versuch

 

[Morpheus101]

Original geschrieben von NumbSchiller
Für Schach ist man gerade soweit eine Ki zu programieren die mit dem besten Spieler der Welt mithalten kann...
[/B]

Ist zwar OT, aber AFAIK haben sie das bei Schach bereits aufgegeben. Die Programme mit der größten Datenbank schneiden u Längen besser ab, als die mit der KI. :-)

 

[Blackhand]

Ist zwar OT, aber AFAIK haben sie das bei Schach bereits aufgegeben. Die Programme mit der größten Datenbank schneiden u Längen besser ab, als die mit der KI. :-)

Ob man nun die möglichen zukünftigen Züge live berechnet, oder vorher berechnet und in einer Datenbank ablegt kommt aufs gleiche... Beides sind keine intelligenten Verfahren. Allerdings kann man mit der DB sicherlich eine bessere Perfomanz erreichen. Aber das Grundprinziep ist das gleiche.

 

[neustadt]

Original geschrieben von Blackhand
Die Frage ist wie modelliert man einen Zustand so das man suchen könnte (wenn man suchen wollte). Weiterhin braucht man eine Bewertung von Zuständen um eine Effizienzmaximierung zu ermöglich. Das Kostet alles massiv Zeit.
Aus diesem Grund ist ein probabilistisches Verfahren mit einigen Heursitiken sicherlich effizienter. In etwa ein regelbasiertes System der Art , "hat der Spieler n Einheiten vom Typ <Einheitentyp> bau den Counter (bzw. baue die Gebäude dafür etc.)". Bei Regelbasierten Systemen muss man aber auch auf die Performanz achten, je mehr Regeln, um so mehr muss man überprüfen. Zudem muss man auch wie oben die Regeln bezüglich eine Bewertung ordnen. Und bei gleichwertigen Regeln zufällig auswählen. Weiterhin kann man hier multiple Regeln in einem Entscheidungszyklus wählen. (Counter bauen und eine Exe oder sowas).

Ich verstehe den Unterschied nicht so ganz. Wenn man einen Suchzustand (Scoutzustand) so moddeliert, dass es ein Ziel der KI ist dem nachzugehen sollte sie doch Einheiten mit verschiedenen Eigenschaften finden und daraus Konter Einheiten berechen.
Weil du aber Plan zu haben scheinst ^^ gibt es wohl einen Unterschied. In dem Fall verstehe ich es so, dass beides gebraucht wird. Moddelierungen von Zuständen um die Ziele der KI im Spiel zu berechnen (Geht ein Psidrop durch, kann ich selbst exen,...). Und Heursitiken um die passenden (Konter) Armeen zu bauen.

Wir scheinen jedenfalls gleicher Meinung sind: Es ist möglich eine gute SC1 KI zu schreiben. (Was eigentlich auch der GameStar Artikel ausssagt, den ich inzwischen gelesen habe. - THX 4 Link @ Poster)
Wieviel Aufwand es bedeuten wuerde, und ob sowas auf standard Hardware läuft ist aber nicht abzusehen.

Ein anderer Interessanter (aber unpraktikabler) Ansatz wäre nicht eine Zentrale KI zu modellieren sondern jeder Einheit eine eigene KI geben (sogenannte Agenten) und dann Koordinationsverfahren der Agenten untereinander zu benutzen. Dieses Verfahren kann hochgradig Adaptiv sein ist aber auch aufwändig. Ich hab sowas mal in einer Gridworld umgesetzt, dabei gab es 6 Agenten die vs. andere 6 Agenten gespielt haben (CLIMA Competition) und Gold sammeln mussten. Man kann maximal 3 Gold sammeln und muss es dann zurück bringen. Dazu ist die Welt unbekannt. Man musste also die Agenten koordinieren das : schnell gescoutet wird, schnell Gold geholt wird, der Gegner wenig Gold bekommt. Bei SC wären das dann xxx Agenten mit yyy mehr an Möglichkeiten, also das skaliert sicherlich auch nicht. Aber wäre ein spannender Versuch

Ich sehe schon einzelne Reaver ueber die Karte robben xD

 

[Komi[D'S]]

Man muss in die Diskussion um eine möglichst "gute" KI nicht nur einbeziehen, wie klug die KI in Bezug auf Kosteneffizienz und Aggressivität ist, sondern auch die Frage, ob sie in ihren Möglichkeiten "vermenschlicht" werden sollte oder nicht.
Erklärung: In BW ist sie durch eingebauten Maphack und maximales Multitasking (z.b. Einheiten die sich auf verschiedenen Bildschirmen aufhalten können unabhängig voneinander gesteuert werden oder mehrere Befehle können genau gleichzeitig gegeben werden) "verunmenschlicht". Das macht sie einerseits stärker, andererseits ist sie dadurch aber ein ungeeignetes Training für 1on1s gegen menschliche Gegner.

 

[Blackhand]

Ich verstehe den Unterschied nicht so ganz. Wenn man einen Suchzustand (Scoutzustand) so moddeliert, dass es ein Ziel der KI ist dem nachzugehen sollte sie doch Einheiten mit verschiedenen Eigenschaften finden und daraus Konter Einheiten berechen.

Naja, das ist nicht das was ich meinte. Ich meinte die Suche in einem Suchbaum, das hat in erster Linie nichts mit Scouten zutun. Stell es Dir so vor. Du hast einen Weltzustand A der gekennzeichnet ist durch die aktuellen positionen deiner Einheiten, dein aktuellen Rohstoffe usw.. Du hast jetzt einige Aktionen die Du ausführen kannst, zum Beispiel Rohstoffe ausgeben um Einheiten zu kaufen. Wenn Du etwas tust änderst Du den Zustand, du kommst also in einen anderen Weltzustand B. Wenn Du jetzt die Zustände als Kreise darstellst, und die Aktionen als Kanten zwischen den Kreisen dann bekommst Du einen Suchbaum. In diesem Baum gibt es dann standardisierte Suchalgorithmen (z.Bsp. Tiefensuche/Breitensuche) die man nutzen kann um eine optimale Aktionenfolge bezüglich des aktuellen Weltzustands zu bestimmen. Allerdings wäre so ein vollständiger Suchbaum in Starcraft gigantisch groß, d.h man muss Suchtiefe usw. einschränken. Suchverfahren dürften daher sehr schlecht skalieren, es sei denn man schränkt sie stark ein.
Regelbasierte Verfahren hingehend führen eine Regel R aus wenn die Voraussetzung V gegeben ist und das immer (es sei denn man versieht das Ganze mit einer Wschkeit, was auch geht). Das heisst hier wird nicht in einem Baum gesucht, hier wird zu einem Zeitpunkt t geprüft ob eine Voraussetzung erfüllt ist (der Spieler hat 10 Lufteinheiten -> baue AA )und dann die Regel ausgeführt. Man kann Regeln auch lernen (also neue Regeln zum Regelpool hinzufügen oder alte verwerfen) aber das skaliert dann nicht mehr so gut. Und je mehr Regeln man hat umso mehr muss man natürlich auch wieder überprüfen.

 

[Flopgun]

Einfach einen richtigen Menschen als Gegner nehmen und du hast 1zu1 was du willst?!

 

[Assplode]

Original geschrieben von Flopgun
Einfach einen richtigen Menschen als Gegner nehmen und du hast 1zu1 was du willst?!

schön war´s , geht aber nie immer

 

[Kangaxx]

Original geschrieben von Blackhand

Du hast einen Weltzustand A der gekennzeichnet ist durch die aktuellen positionen deiner Einheiten, dein aktuellen Rohstoffe usw.. Du hast jetzt einige Aktionen die Du ausführen kannst, zum Beispiel Rohstoffe ausgeben um Einheiten zu kaufen. Wenn Du etwas tust änderst Du den Zustand, du kommst also in einen anderen Weltzustand B. Wenn Du jetzt die Zustände als Kreise darstellst, und die Aktionen als Kanten zwischen den Kreisen dann bekommst Du einen Suchbaum.

Hm, erstmal hat man gar keinen Suchbaum, sondern nur eine große Masse an möglichen Handlungen (zu der Anzahl an Handlungen: siehe vorige Post von mir). Was fehlt ist nämlich eine Kantenfunktion, also eine Bewertung der Kanten, was einer Bewertung des neuen Zustands am Ende der Kante entspircht. Ohne diese ließe sich ja gar kein Suchbaum aufbauen. Die möglichen Handlungen müssen also erst einmal nach irgendwelchen schlauen Kriterien bewertet werden, so dass man ausgehend vom aktuellen Weltzustände dann anhand dieser Bewertung, die sich evtl. als Zahl zwischen 0 und 1 (0=mieß, 1=genial) darstellen lässt, einen Suchbaum aufbauen kann.

Aber wie schon gesagt, ist das ein ziemlich beschissenes Verfahren, weil vieeeeeeeel zu aufwändig.

Original geschrieben von Blackhand

Regelbasierte Verfahren hingehend führen eine Regel R aus wenn die Voraussetzung V gegeben ist und das immer (es sei denn man versieht das Ganze mit einer Wschkeit, was auch geht). Das heisst hier wird nicht in einem Baum gesucht, hier wird zu einem Zeitpunkt t geprüft ob eine Voraussetzung erfüllt ist (der Spieler hat 10 Lufteinheiten -> baue AA )und dann die Regel ausgeführt.

Die Idee ist gar nicht mal so schlecht. Vor allem entspricht sie wohl auch am ehesten dem menschlichen Denken beim SC spielen. Als Mesch vergleicht man ja auch ständig die aktuelle Spielsituation mit bekannten Voraussetzungen und reagiert dann entsprechend. Z.B. hält man Ausschau, ob der z-Gegner auf Mutten techt. Und wenn er es tut, baut man halt den Konter.

Mir fällt gerade auch noch eine andere Möglichkeit ein, die auf der Schachcompi-Methode basiert. Man muss ja einfach nur dem Compi die Möglichkeit nehmen unendlich viele Handlungen auf einmal durchzuführen. Sagen wir mal der Compi soll mit 400 apm spielen und die 400 Aktionen/Min sollen in gleichen Zeitabständen ausgeführt werden. Dann hat man nämlich schon eine mit Schach vergleichbare Situation. Es bleiben dann dem Compi in einem Moment nur noch 200*9216 statt 9216^200 mögliche Spielzüge, da er ja in einem Monent nur einen Befehl an eine Unit geben darf (zu den Zahlen: siehe mein erster Post in diesem Thread). Außerdem kann man das Raster von 1x1 goßen Feldern auch noch stark reduzieren, da es wohl egal ist, ob eine Unit zu Pixel (32,60) oder zu Pixel (31,60) geschickt wird. Eine Rasterung in 5x5 oder 10x10 große Felder würde wohl sachon genügen, was die Handlungsmöglichkeiten nochmal stark reduziert.

Aber, wenn ich mal gerade bedenke, dass ein guter Schachcompi für einen Zug mal gerne mehrere Minuten rechnet, ist dies wohl immer noch nicht befriedigend, da der Compi bei SC ja unter Zeitdruck steht und er es sich somit nicht leisten kann, 3 Minuten zu überlegen, ob er nun seine Units nach oben links oder unten rechts schickt.

 

[Blackhand]

Was fehlt ist nämlich eine Kantenfunktion, also eine Bewertung der Kanten, was einer Bewertung des neuen Zustands am Ende der Kante entspircht. Ohne diese ließe sich ja gar kein Suchbaum aufbauen.

Die Aktion die der Computer wählen kann ist die Kante. Dabei braucht man nicht zu bewerten (allerdings wäre eine Bewertung gegeben dem Zustand sinnvoller). Ziel wäre dann Möglichst kurz zu einem Siegzustand zu kommen. (quasi eine indirekte Bewertung) Bewertungen bei sovielen parametern sind auch nicht leicht zu finden

Die Idee ist gar nicht mal so schlecht. Vor allem entspricht sie wohl auch am ehesten dem menschlichen Denken beim SC spielen. Als Mesch vergleicht man ja auch ständig die aktuelle Spielsituation mit bekannten Voraussetzungen und reagiert dann entsprechend. Z.B. hält man Ausschau, ob der z-Gegner auf Mutten techt. Und wenn er es tut, baut man halt den Konter.

Jap, nur ist die Perfomanz abhängig von der Regelanzahl. Daher ist wohl eine Mischung zwischen Regeln und festen Scripts die beste.

 

[darkSinister]

es is zwar ganz schön hier über schach und die 237. potenz von einer zahl zu philosophiern, die keiner aussprechen kann, aba ihr vergesst einen gewaltigen unterschied zwischen schach und sc: beim schach kommt es nicht so sehr (jaja, nit unbegrenzt, blabla) auf die zeit an wie in sc.
und hierin seh ich es ganz einfach eine "bessere" KI zu erschaffen. einige bereits bei WCIII gemachte änderungen kombiniert mit dem faktor geschwindigkeit. die KI kann theoretisch alles gleichzeitig machen; so eine mikro wäre wohl auch mit verhältnismäßig schwacher intelligenz für unterdurchschnittliche spieler fast unmöglich zu schlagen... und für den rest gibts das bnet

so long