Zufallserzeugung durch KI

[NeUs]

Hallo,

erstma hallo an alle.

So nun zu meiner Frage: Ich schreib grad ein Schiffeversenkenspiel. Die KI kann natürlich ihr schiffe zu fällig auf dem Spielfeld platzieren. Die Anzahl der Schiff, deren Größe und die Spielfeld größe ist so bemessen das dies auch fast immer aufgeht. In einigen Fällen, setzt die KI ihre Schiffe aber so ungünstig, dass sie nicht alle verteilen kann, weshalb das Programm manchmal hängen bleibt.

Meine Frage ist nun daher ob es irgendwie möglich ist zu überprüfen wie Lang die KI dafür braucht?
Die Schiffe verteilt sie ja wenn es klappt blitzschnell, wenn sie z.b. dafür 2 Sek. brauch kann man dann sagen, dass sie das verteilen noch einmal neu machen soll?

 

[Atze]

klar sollte das gehen. du kannst beim platzieren doch einen timer starten (natürlich parallel), der bei zu langer wartezeit das platzieren abbricht, das feld cleared und neu beginnt. jedoch solltest du es auf eine gewissen anzahlt beschränken, sonst landest du inder nächsten schleife und er bleibt dort hängen

 

[Marco13]

Klingt nach Symptombekämpfung... sollte man nicht von vornherein verhindern, dass dieser Fall eintritt? Wie ist denn bisher (ganz grob) die Strategie zum Verteilen, und wann bleibt er dabei hängen?

 

[Atze]

Klingt nach Symptombekämpfung... sollte man nicht von vornherein verhindern, dass dieser Fall eintritt? Wie ist denn bisher (ganz grob) die Strategie zum Verteilen, und wann bleibt er dabei hängen?

stimmt! wäre natürlich besser das zu verhindern, wollte jetzt nur mal das aktuelle problem lösen.

p.s.: man könnte ihm aber auch dazu raten, ein "pazifistischeres" spiel zu schreiben und diese killerspiele zu vergessen

 

[NeUs]

Ja natürlich wäre es besser dieses Problem von vornherein auszschließen.

Also grobes vorgehen: Er guckt in einer Regelklasse nach wie viel schiffe er verteilen muss und welche Arten. Dann fängt er beim größten Schiff an und platziert dies zufällig. Danach folgen dann die anderen Größen bis hin zum kleinsten.
Zwischendurch guckt er halt schon, ob die Koordinaten schon belegt sind und ob es nach momentanen Regeln auch so ist dass das erzeugte schiff nicht genau neben einem anderen liegt.
Ich nahm an, dass dadurch das ich zuerst mit den großen Schiffen anfange, das Problem nicht auftritt. Was mich aber lügen gestraft hat, auch wenn es nur selten auftritt...

 

[0x7F800000]

Klingt nach Symptombekämpfung... sollte man nicht von vornherein verhindern, dass dieser Fall eintritt?

jupp, das sollte man. Wenn man zustände des Spielfeldes als Knoten und Entscheidungen bei der Positionierung als Kanten interpretiert, sollte man irgendwie halbwegs gezielt nach einem gültigen Zustand suchen (DFS, Backtracking). Wenn du bei jedem Fehlversuch immer vom Anfang startest, dann machst du genau das:
YouTube - Takeshi's Castle - Funny Door-Runs
Und wie dieses Beispiel zeigt, ist es eben nicht garantiert, dass du überhaupt am ziel ankommst, oder dass du es in vertretbarer Zeit schaffst.

 

[NeUs]

Ja eben als ich das geschrieben habe ist mir auch das Thema Backtracking in den Kopf gekommen.
Ich dachte nur ich kann dies umgehen, da ich dadurch vieles neu schreiben muss bzw. neu austüfteln muss.
Deshalb wäre die Methode des "neuverteilens" erstmal eine einfache gewesen.
Aber ihr habt schon recht, dass ich damit das Grundsätzliche Problem nur schön mache. Der bessere Weg ist es es gar nicht auftreten zu lassen.

 

[Firestorm87]

Beim Backtracking ist natürlich das Problem, dass es sich hierbei in der Regel um sehr strategische Vorgehensweisen handelt, die in diesem Fall abe einen Zufall simulieren sollen...

Backtracking und Zufall unter einen Hut zu bekommen ist schon nicht sooo einfach

 

[NeUs]

Ja dieses Problem ist mir zum Thema Backtracking auch in den Sinn gekommen.
Die KI muss ja entscheiden können wann sie alles Schiff verteilt hat und wann sie festhängt.

 

[Atze]

also wäre mein ansatz doch nicht so verkehrt!
es gäbe da auch noch die möglichkeit, alle möglichen kombinationen der entsprechenden flotte im voraus zu berechnen, diese zu speichern und beim setzen durch zufall eine davon auszuwählen, und die schiffe dann so zu platzieren.

 

[NeUs]

Hm naja gut um alles möglichen Belegungen zu bestimmen werde ich denke ich wieder auf das Problem treffen. Das ist die Lösung mit dem Timer eigentlich schon ein Ansatz.

Ach man und jetzt doch wieder daran setzten wo sich 2 KIs schon besiegen können.
Dachte ich kann langsam mal an die GUI.

 

[Firestorm87]

Naja alle möglichen belegungen zu berechnen sollte bei einem Schiffeversenken Feld nicht so lange dauern
Das wäre also durchaus eine legitime Variante

Das Problem beim kompletten neuanordnen ist eben, dass diese Funktion unter blöden zufälligen Vorraussetzungen niemals terminiert, da sie niemals eine gültige Lösung findet (weil z.B. sehr viele Schiffe plaziert werden sollen).
Berechnest du erst alle möglichkeiten kann das nicht passieren... HIer weißt du dann wenn es nur 0 gibt

 

[NeUs]

Also die möglichkeit sehr viele Schiff zu platzieren wird es nicht geben. Muss mir zwar noch genau überlegen wie ich festlege, wie viel Schiffe bzw. welche Schiffgrößen erlaubt sind. Aber es sollen nicht zu viele werden.
Aber ok die Idee alle möglichen Lösungen zu bestimmen ist im Grunde auch nicht schlecht. Muss ich mir nur erstmal etwas einfallen lassen wie man dies am ellegantesten bewerkstellig.

 

[faetzminator]

Ich würde es so irgendwie machen:

für alle schiffe // am besten beginnend mit dem grössten
  gib mir alle möglichkeiten, in welchem das schiff noch platz hat // x felder in einer linie horizontal oder vertikal beginnend bei x,y sind noch frei und nicht gleich neben einem betzten feld
  wenn anzahl möglichkeiten gleich 0
    brich mit error ab // und fange oben diesen ab und versuche es nochmals
  wähle mit random einen platz und setze das schiff dahin

 

[Marco13]

Backtracking und Zufall sind in diesem Fall gar nicht sooo kompliziert.... man könnte grob sowas machen wie

boolean platziereAlle(List<Schiffe> schiffe)
{
    if (schiffe.size() == 0) return true;
    Schiff schiff = schiffe.get(0);
    schiffe.remove(0);
    List<Position> positionen = findeAlleMöglichenPositionenFür(schiff);
    while (positionen.size() > 0)
    {
        Position position = nimmZufälligePositionRaus(positionen); 
        setze(schiff, position);
        if (platziereAlle(schiffe))
        {
            return true;
        }
        nimmWeg(schiff, position);
    }
    return false;
}

Kann sein dass da noch irgendwo ne Schleife drum muss, aber so grob...


EDIT: Ja, 9 Minuten um den Code hinzuschreiben...

 

[Firestorm87]

/ Auf der suche nach dem delete button

 

[0x7F800000]

es gäbe da auch noch die möglichkeit, alle möglichen kombinationen der entsprechenden flotte im voraus zu berechnen, diese zu speichern und beim setzen durch zufall eine davon auszuwählen, und die schiffe dann so zu platzieren.

Naja alle möglichen belegungen zu berechnen sollte bei einem Schiffeversenken Feld nicht so lange dauern

Ääääh, ja... bei einem 10x10 Feld mit 4332221111 Schiffen wäre die Größenordnung etwa 10^18, bei einem 20x20 feld mit insgesamt 80 zu verteilenden kästchen wäre das grob geschätzt in der Größenordnung 10^80 Kombinationen, paar dutzend nullen hin oder her... Viel Spaß beim Abspeichern. :autsch:

Was soll beim Backtracking so furchtbar schwer daran sein, nicht alle zweige nacheinander abzuarbeiten, sondern einen zufällig auszuwählen? Klar muss man da ein bisschen fummeln, aber das ist doch keine riesensache... :bahnhof:

 

[Firestorm87]

Ääääh, ja... bei einem 10x10 Feld mit 4332221111 Schiffen wäre die Größenordnung etwa 10^18, bei einem 20x20 feld mit insgesamt 80 zu verteilenden kästchen wäre das grob geschätzt in der Größenordnung 10^80 Kombinationen, paar dutzend nullen hin oder her... Viel Spaß beim Abspeichern. :autsch:

Ich weiß zwar nicht, wie du für ein paar Schiffe in einer 20x20 Matrix 10^80 möglichkeiten finden willst...
Aber die Rechnung müsstest du mir zeigen...
So viele möglichkeiten gibt es afaik nicht einmal für Sudokus

 

[0x7F800000]

Ich weiß zwar nicht, wie du für ein paar Schiffe in einer 20x20 Matrix 10^80 möglichkeiten finden willst...
Aber die Rechnung müsstest du mir zeigen...

Wie gesagt: es ist eine recht grobe schätzung. Ich habe einfach alle schiffe in einzelne Kästchen auseinandergesägt und die mindestabstand-regelungen nicht beachtet.

Dadurch ergeben sich [c]((20^2) über 80) ~= 4.228 * 10^85[/c] verschiedene Muster, wenn man die 80 kästchen frei auf den 400 feldern verteilen kann. Wenn man alles mit 4er-schiffen füllt, dann werden das ein bisschen mehr als [c](400 über 20) ~= 2.7*10^33[/c] Kombinationen. Wenn man da salat mit 1er- bis 5er-schiffen reinschmeißt, wird das irgendwas dazwischen. Wie gesagt, ein paar Dutzend Nullen hin oder her: passt eh in keinen Superrechner rein. Das tun kombinatorische Probleme irgendwie grundsätzlich nicht... :bahnhof:

 

[Atze]

ok, wenn ich so drüber nachdenke, war doch n nichtbedachter schnellschuss. hab an ein paar dutzend kombinationen gedacht :/

 

[Firestorm87]

Auch wenn Ich dir gerne eingestehen möchte, dass es vll für eine OnTheFly-Berechnung zu viele sind, so muss Ich dir bei deinen Zahlen weiterhin wiedersprechen....

Zum ersten gibt es für ein 4er Schiff nicht 20 Möglichkeiten auf einer 20^20 Matrix und zum anderen ist dieser Rechenweg grütze, da sich die Anzahl der Möglichkeiten x nicht auf x-1 reduziert, sobald Ich ein weiteres Schiff platziere...
Im günstigsten Fall ergibt sich x-8 (4x längs, 4x hochkannt), dieses funktioniert jedoch nur am Rand des Spielfeldes.
Bei einer zentralen Position sollte sich nur ein Bruchteil von x ergeben, da du ebenfall nicht mit einplanst, dass es auch möglichkeiten gibt, wo das Schiff nicht mehr rein passt (man kann das Schiff ja nicht knicken )

Falls Ich die Zeit finden sollte werde Ich mal nach einer guten Zahl ausschau halten...

 

[faetzminator]

Ist es nicht so, dass um ein Schiff alle anliegenden Felder (auch die diagonal anliegenden) ausser Betracht gezogen werden können, da in diesem Spiel keine angrenzenden Schiffe erlaubt sind? Das gibt auf ein Schiff der Grösse 1x4 einen "realen Platzverbrauch" von 3x6=18 Feldern, bzw. an in einer Ecke immer noch 2x5 Felder. Ich denke, das Verteilen der Schiffe sollte mit Backtracking ohne Probleme möglich sein. Ansonsten kann man das Backtracking immer noch manuell iterativ implementieren und spart sich so viel Speicher - dafür braucht man dann einfach mehr Berechnungszeit (in einem Stack wird jedes Mal, wenns nicht mehr aufgeht, gepoppt und die freien Felder neu berechnet).

 

[0x7F800000]

@Firestorm87
Nja, wie gesagt:

Wie gesagt: es ist eine recht grobe schätzung. Ich habe einfach alle schiffe in einzelne Kästchen auseinandergesägt und die mindestabstand-regelungen nicht beachtet.

Wenn ihr unbedingt etwas mit der mindestabstandregelung schätzen wollt, dann nehmt halt statt 20x20 Feld ein 60x60 feld, und tut für jedes der 20 1-kästchen Schiffe so, als ob es 3x3 felder einnehmen würde. Da kommt man wieder auf mindestens [c](400 über 20) = 2.788 * 10^33[/c] Kombinationen als gaaanz grobe untere Schranke.

Wie viele Kombinationen es exakt gibt, werdet ihr höchstwahrscheinlich nicht irgendwie in einer halbwegs geschlossenen Form ausrechnen können, und wenn, wird es euch ein Jahrzehnt mathematischer Untersuchungen kosten... Muss imho nicht unbedingt sein, wenn es lediglich darum geht, einen nicht-implementierbaren Lösungsansatz schnell zu verwerfen.

 

[Atze]

ist ja gut, ich schäme mich ja schon für meine idee! :/