Künstliche Intelligenz rollt Stephens Würstchen

6 min

8.1.2021

ssr.jpg

Die Weih­nachts­fei­er­ta­ge lohn­ten sich doch gut zum Spie­len. Nur ei­gent­lich will man we­nigs­tens ein­mal im Jahr ent­span­nen, al­so war­um nicht je­man­dem an­ders den Auf­wand über­las­sen! Men­schen sind mir da­bei nicht zu­ver­läs­sig ge­nug, ver­trau­en wir lie­ber auf künst­li­che In­tel­li­genz. Na­tür­lich wird sie von mir selbst er­stellt, so kann nichts schief ge­hen und sie wird sich schon nicht ge­gen die Mensch­heit auf­rich­ten… »Ge­spielt« wird ein klei­nes, knif­fe­li­ges Puz­zle-Game na­mens Ste­phen's Sau­sa­ge Roll. Ich ken­ne mich nicht wirk­lich mit (künst­li­cher) In­tel­li­genz aus, ei­ne ef­fek­ti­ve KI da­für zu ent­wer­fen kann aber schon nicht so schwer sein.

Künstliche Intelligenz hier, da und überall

Der Be­griff KI oder AI fürs eng­li­sche Ar­ti­fi­cial In­tel­li­gence ist noch ein­mal un­ge­nau­er als die eben­falls tren­di­ge Be­zeich­nung Ray­t­ra­cing. Ne­ben dem Na­men für ei­ne fik­tio­na­le, di­gi­ta­le, un­kon­trol­lier­te und nor­ma­ler­wei­se bö­se En­ti­tät wird KI häu­fig als schein­ba­res Syn­onym für Ma­schi­ne oder Deep Lear­ning in den Me­di­en ge­nutzt. Oh­ne ge­nau­er auf die De­tails ein­ge­hen zu wol­len, ist die­ser An­satz al­ler­dings un­nö­tig um­ständ­lich zum Rol­len von Ste­phens Würst­chen – und nicht sehr span­nend.

Statt­des­sen wird ei­ne zu Ste­phen's Sau­sa­ge Roll bes­ser pas­sen­de, sys­te­ma­ti­sche Art ver­wen­det: AI Plan­ning. Hier­bei ist ein Start­zu­stand ge­ge­ben (zum Bei­spiel ro­he Würst­chen an be­stimm­ten Po­si­tio­nen) und mit Hil­fe von Ak­tio­nen (Wurst mit Spieß auf Grill rol­len) soll ein ge­wünsch­ter End­zu­stand er­reicht wer­den (al­le Würs­te ge­bra­ten). Die Fol­ge der ge­wähl­ten Ak­tio­nen er­gibt un­se­ren Plan, wel­cher letzt­lich ei­ne Rei­he von Tas­ten­drü­cken be­schreibt.

ai.jpg
Aufgabe der KI: Welcher Plan führt zum Erfolg?

Wenn die Ak­tio­nen, der Start­zu­stand und der Ziel­be­reich de­fi­niert sind, ha­ben wir im Prin­zip ei­ne leicht abs­trak­te Re­prä­sen­ta­ti­on des Spiels er­zeugt. Das Lö­sen an sich über­nimmt dann ein schon exis­tie­ren­der, all­ge­mei­ner Plan­ning-Pro­blem-Sol­ver, der an­hand un­se­rer ge­schrie­be­nen In­stanz die Ak­tio­nen in mög­lichst ef­fi­zi­en­ter Rei­hen­fol­ge aus­pro­biert, um hof­fent­lich schnell auf ei­nen Plan zu kom­men. Zum Ab­schluss ver­wen­de ich noch ein kur­zes Script, dass den Lö­sungs­plan in ei­ne Zei­chen­ket­te aus W, A, S und D über­führt, um zu se­hen, ob es im rich­ti­gen Ste­phen's Sau­sa­ge Roll tat­säch­lich klappt.

Man kann al­so sa­gen, dass bei AI Plan­ning das Rät­sel »im Kopf« des Sol­vers durch­ge­gan­gen und nach Be­rech­nungs­en­de in ei­nem Rutsch ei­ne Lö­sung aus­ge­spuckt wird. Da­her ist es eben es­sen­ti­ell, dass das Spiel lü­cken­los de­fi­niert ist und voll­kom­men durch den Spie­ler ge­steu­ert wird, sprich kei­ne un­vor­her­seh­ba­ren (Zu­falls-)Er­eig­nis­se ein­tre­ten. Selbst­ver­ständ­lich muss für die künst­li­che In­tel­li­genz die Dar­stel­lung des Spiels kor­rekt um­ge­setzt sein. Schleicht sich ein Feh­ler bei der Pro­gram­mie­rung ein, passt die Lö­sung nicht zum rich­ti­gen Sau­sa­ge Roll. Lei­der kann die Feh­ler­su­che beim Plan­ning et­was um­ständ­lich wer­den, was ja glück­li­cher­wei­se nicht eu­re Sor­ge sein muss.

Die Erschaffung von Yin und Yang

Ei­nen mi­ni­mal ge­naue­ren Blick auf den Kern der AI wür­de ich in die­sem Ab­schnitt noch ger­ne wer­fen, für all die­je­ni­gen, die sich da­von be­geis­tern las­sen. Not­wen­dig für den Sol­ver ist die Do­mä­ne (un­se­re Spiel­re­geln) und das Pro­blem (un­ser Le­ve­l­auf­bau). Nur zu­sam­men ver­voll­stän­di­gen sie sich und er­ge­ben ei­nen Sinn. Die Un­ter­tei­lung wird vor­ge­nom­men, um mög­lichst ein­fach wei­te­re pas­sen­de Pro­ble­me (Le­vel) für die Do­mä­ne zu schrei­ben. Bei bei­den Da­tei­en han­delt es sich um rei­nen Text, der dem PDDL-Stan­dard un­ter­liegt. Im Fol­gen­den sei bei­des aber zum ver­ein­fach­ten Ver­ständ­nis et­was um­for­mu­liert.

Den Haupt­aspekt stel­len Zu­stän­de dar, die durch ei­ne Men­ge von un­ter­schied­li­chen Ato­men be­stimmt wer­den. Als Wert kommt für je­des Atom le­dig­lich wahr oder falsch in Fra­ge, sprich das Atom gilt oder gilt nicht im je­wei­li­gen Zu­stand. Bei­spiel ei­nes Start­zu­stands wä­re: { Spie­ler auf Po­si­ti­on 0, nicht Spie­ler auf Po­si­ti­on 1, nicht Spie­ler auf Po­si­ti­on 2, nicht Wurst auf Po­si­ti­on 0, Wurst auf Po­si­ti­on 1, nicht Wurst auf Po­si­ti­on 2 }. Spie­ler und Wurst kön­nen al­so drei Po­si­ti­on ha­ben, dass sich je­doch je­der im­mer nur an ei­ner Stel­le zu­gleich be­fin­den darf, ver­bie­tet der Zu­stand al­lei­ne nicht. Das Ziel muss da­ge­gen kein ein­zel­ner Zu­stand sein, so wür­de { Wurst auf Po­si­ti­on 2 } al­le je­ne ab­de­cken, bei de­nen die­ses Atom wahr ist. Mit Start und Ziel zu­sam­men ha­ben wir nun ein ers­tes Le­vel.

tnssr.webp
Schema der KI: Welche Aktion ist vom aktuellen Zustand aus zielführend?

Da­mit vom Start­zu­stand über­haupt zu ei­nem Ziel­zu­stand ge­kom­men wer­den kann, braucht es die Ak­tio­nen der Do­mä­ne. Je­de Ak­ti­on hat ei­ne Vor­be­din­gung – das ist ei­ne Men­ge von Ato­men, die mo­men­tan wahr oder falsch sein müs­sen, um vom Sol­ver aus­ge­wählt wer­den zu dür­fen. Wird ei­ne ver­füg­ba­re Ak­ti­on ge­nom­men, ver­än­dert ihr Ef­fekt die an­ge­ge­be­nen Ato­me, was zu ei­nem neu­en Zu­stand führt. Ei­ne die­ser Ak­tio­nen könn­te sein:

Aktion: Bewegung nach rechts
Vorbedingung: Spieler auf Position 0
Effekt: nicht Spieler auf Position 0 und Spieler auf Position 1
und wenn Wurst auf Position 1 dann nicht Wurst auf Position 1
und Wurst auf Position 2

Da­mit wir nicht ver­se­hent­lich auf un­ser di­ckes Würst­chen tre­ten, wird beim Ef­fekt noch un­ter­schie­den, ob ein Wie­ner im Weg steht und ver­scho­ben wer­den muss. Sol­che Spe­zi­al­be­feh­le sind al­ler­dings nur ein­ge­schränkt ein­setz­bar und idea­ler­wei­se soll­ten Ak­tio­nen ei­gent­lich bloß aus mit »und«-ver­knüpf­ten Ato­men be­stehen.

Schon mit die­ser ei­nen Ak­ti­on kä­me man di­rekt vom Start­zu­stand un­se­res ers­ten Le­vels zu ei­nem Ziel. Doch was soll man bei Le­veln ma­chen, die aus vier, fünf oder hun­der­ten Po­si­tio­nen be­stehen? Hier­für lässt sich die Po­si­ti­ons­ei­gen­schaft als Ob­jekt­typ ver­wen­den, um et­was Fle­xi­bi­li­tät zu er­hal­ten. Ge­naue­res da­zu spa­ren wir uns je­doch. Ihr soll­tet nur mit­neh­men, dass es nicht selbst­ver­ständ­lich ist, ob Po­si­ti­on i di­rekt links, rechts, über oder un­ter Po­si­ti­on j liegt, oder doch ganz wo an­ders. Da­bei ist das noch das ein­fachs­te an un­se­rer Wurst-KI.

Die Schwierigkeit von Stephen's Sausage Roll

Ich hof­fe je­der kennt die­ses tol­le Puz­zle und so er­wäh­ne ich ein­zig aus rei­ner For­ma­li­tät die grund­le­gen­den Her­aus­for­de­run­gen. Wie ihr euch er­in­nern könnt sind die Be­we­gungs­mög­lich­kei­ten ab­hän­gig von der Aus­rich­tung Ste­phens Würst­chen­pik­sers im Ver­hält­nis zum Spie­ler. Mit der Ga­bel in den Hän­den kann sich nicht seit­wärts be­wegt wer­den, statt­des­sen muss man sie ro­tie­ren, um in al­le Him­mels­rich­tun­gen ge­hen zu kön­nen. Das wä­re halb so wild, wenn die­ses Mons­ter­teil kein ei­ge­nes Feld ein­neh­men wür­de. Apro­pos gro­ße Din­ger, die Wie­ner neh­men je­weils selbst zwei Fel­der ein und müs­sen ex­akt ein Mal von oben und ein Mal von un­ten ge­bra­ten wer­den. Ins Was­ser darf uns auch nichts fal­len und au­ßer­dem muss der Spie­ler zur Start­po­si­ti­on zu­rück­keh­ren.

obj.jpg
Modellierung der KI: Boden | Wurst & Grill | Spieler & Startposition

Zu­min­dest für die ers­te In­sel – auf wel­che wir uns be­schrän­ken – sind das die wich­tigs­ten Hür­den, wel­che vie­le Leu­te auf ei­ne har­te Pro­be stel­len. In ei­nem emp­feh­lens­wer­ten Vi­deo der Ga­me­Star zei­gen zwei Schla­wi­ner schön, wie man er­folg­los mit Pren­geln spielt. Pro­ble­ma­tisch für die KI ist zu­sätz­lich der Um­gang mit meh­re­ren Würs­ten in ei­ner Rei­he. Ver­schiebt die Spiel­fi­gur wäh­rend ei­nes Zugs ein Würst­chen, müs­sen sich al­le Würs­te die da­hin­ter im Weg lie­gen eben­falls be­we­gen. Die un­zäh­li­gen Kom­bi­na­ti­ons­mög­lich­kei­ten aus ver­schie­de­nen Ori­en­tie­run­gen lie­ßen sich nicht ver­nünf­tig nie­der­schrei­ben, wenn man mehr als ein oder zwei Würs­te er­lau­ben will. So­mit muss ei­ne an­de­re Re­prä­sen­ta­ti­on ver­wen­det wer­den, die den­noch zu ei­nem lo­gisch äqui­va­len­ten Zu­stand führt.

Im vor­he­ri­gen Ab­schnitt ver­sprach ich je­doch nicht tie­fer auf die Im­ple­men­tie­rung ein­zu­ge­hen. Ihr könnt ger­ne über­le­gen, mit wel­chem Prin­zip man das Pro­blem um­ge­hen könn­te. Wenn das In­ter­es­se be­steht, dass ich auf ei­nen Punkt ge­nau­er ein­ge­he, könnt ihr das ru­hig als Kom­men­tar äu­ßern. Bei ge­nug Le­ser­inter­es­se fin­det das viel­leicht Platz in ei­nem zwei­ten Teil mit der zwei­ten In­sel.

Die künstliche Intelligenz in Aktion

Da sich un­se­re er­schaf­fe­ne In­tel­li­genz nicht durch Ler­nen ver­bes­sert und man mei­nes Wis­sens nach auch nicht den »Ge­dan­ken­gang« des Sol­vers aus­ge­ben kann, ist das Ver­hal­ten ver­mut­lich nicht ganz so span­nend wie bei Ma­schi­ne Lear­ning – aber ein be­geis­te­ter Freund mein­te dar­aus müss­te ich un­be­dingt ein You­Tube-Vi­deo ma­chen. Als Sol­ver wird üb­ri­gens Fast Down­ward ver­wen­det. Die­ser stellt die Zu­stän­de des Plan­ning-Pro­blems als Graph dar und pro­biert mit ei­nem Such­al­go­rith­mus zu ei­nem Ziel­zu­stand zu ge­lan­gen. Der Pfad dort­hin sind die da­für aus­zu­füh­ren­den Ak­tio­nen.

Da euch na­tür­lich die Lö­sun­gen der ge­sam­ten ers­ten In­sel ge­zeigt wer­den, seid ihr hier noch ein­mal ge­warnt! Vor al­lem ver­steht man auch bes­ser was vor sich geht, wenn man selbst Hand an Ste­phens Wie­ner ge­legt hat. Und nur dass ihr euch nicht wun­dert, das nicht be­son­ders schwe­re Lau­fen zwi­schen den Le­veln über­neh­me ich – die KI ist sich da­für zu ete­pe­te­te.

Auch wenn es recht über­schau­ba­re Pro­ble­me sind, ist die im­mense Be­rech­nungs­ge­schwin­dig­keit er­staun­lich. Die meis­ten Rät­sel sind in ei­nem Se­kun­den­bruch­teil ge­löst! Ein paar Se­kun­den län­ger be­nö­ti­gen le­dig­lich zwei Le­vel, bei de­nen man sich das Zu­rück­ge­hen an die Start­po­si­ti­on ver­bau­en kann. Die Ge­schwin­dig­keit ist da­bei maß­geb­lich be­ein­flusst durch die Qua­li­tät der Re­prä­sen­ta­ti­on, aber auch des Sol­vers, be­zie­hungs­wei­se des­sen »Such­tak­tik«.

In­so­fern bin ich mit dem Er­geb­nis durch­weg zu­frie­den und ich hof­fe es war für euch als Au­ßen­ste­hen­de in­ter­es­sant ge­nug. Wenn euch et­was de­tail­lier­ter an­spricht, dann gebt wie ge­sagt ger­ne Feed­back.