Schiffe versenken



  • Hallo zusammen
    Wir arbeiten gerade an einem Algorithmus zur Erkennung von ungültigen Spielzügen in einem "Schiffe versenken" und kommen dabei einfach nicht weiter. Nun fragen wir uns, ob es möglicherweise einen bekannten und bewährten Algorithmus hierfür gibt? Das eigentliche Problem stellen die indirekt ungültigen Spielsituationen dar (dies sind Situationen, welche zwar an sich noch nicht ungültig sind, jedoch früher oder später in einer ungültigen Situation enden MÜSSEN).

    0 = gleich beschossen aber leer
    x = beschossen und treffer
    - = verdecktes Feld

    Bsp1: 0xxx---xx0 (Irgendwo auf dem Feld)

    Wir wissen also, dass links mindestens ein 4er Schiff und rechts mindestens ein 3er Schiff liegen muss. Nun wissen wir aber bspw. dass bereits 2 4er Schiffe versenkt wurden, also muss es sich rechts um ein 3er oder ein 5er Schiff handeln. Auf der linken Seite jedoch muss es sich demzufolge um ein 5er Schiff handeln, also kann es sich rechts doch nur um ein 3er handeln. Dann aber werden sich die Kreuze in der Mitte treffen und wir hätten ein 7er Schiff, was es jedoch gar nicht gibt, also kann diese Spielsituation nicht gültig sein...

    Bsp2: x--xx0 (Irgendwo auf dem Feld)

    Hier besteht die Möglichkeit, dass das linke Schiff sich in alle 4 Richtungen ausdehnen kann, oder aber es könnte sich auch um ein 1er Schiff handeln. Rechts muss es sich um ein 3er Schiff handeln oder es könnte zusammen mit dem linken Teil ein 5er Schiff bilden. Nehmen wir nun einmal an, wir hätten bereits ein 5er und 5 1er versenkt dann muss es rechts ein 3er sein und links ein Schiff unbekannter Grösse sein, welches sich jedoch nicht nach rechts ausdehnen darf. Nun müssen wir also nachschauen, ob wir nach oben, unten oder links ausdehnen dürfen ohne ähnliche Regeln zu verletzen usw... der Horror 😮

    Versteht ihr, was ich meine. Wir haben mittlerweise x solche Scenarien durchgekaut und kein uns bekannter Algorithmus bemerkt diese logische Fehler 😞

    Mfg Samuel

    P.S.
    Nun ja, einen Lösungsansatz hätten wir schon, aber bei diesem machen wir uns ziemliche Sorgen, was die Laufzeitperformance angeht:

    Wir hatten uns überlegt, wir müssten halt rekursiv versuchen, eine gültige Endsituation aus der gegenwärtigen Situation zu erstellen und wenn dies nicht möglich ist, wissen wir, dass die aktuelle Spielsituation nicht möglich ist. Aber wie gesagt, das wäre ja dann fast wie ein Minimax Algorithmus, der bis zum ENDE durchgespielt werden muss...


  • Mod

    Ishildur schrieb:

    Versteht ihr, was ich meine. Wir haben mittlerweise x solche Scenarien durchgekaut und kein uns bekannter Algorithmus bemerkt diese logische Fehler 😞

    nein, ehrlich, ich hab keinen plan was ihr da fuer probleme habt. entweder ihr trefft ein schiff oder ihr trefft es nicht, was aendern die markierungen daran welches schiff und von welchem typ ihr getroffen habt?



  • Das Problem ist, dass wir die Position der Schiffe des Gegners nicht kennen, weil unser super Professor darauf bestanden hat, dass wir eine PeerToPeer Netzwerktechnologie verwenden müssen. Aus diesem Grund kennen wir nur die Position unserer eigenen Schiffe. Aufgrund der Tatsache, dass es sich um ein Netzwerkspiel handelt, müssen wir jeden Zug, wenn wir über das Netzwerk empfangen validieren und im Falle eines ungültigen Zuges eine entsprechende Message an unseren Gegenspieler zurücksenden. Sukzessive können wir dan eruieren, wo sich die Schiffe des Gegners befinden, aber es geht eben darum, frühzeitig zu erkennen, wenn der Gegenspieler "bescheisst"


  • Mod

    euer gegenspieler wird euch wohl zurueckliefern was ihr versenkt habt, zaehlt einfach nach wieviele schiffe von diesem typ schon versenkt sind, und falls es zuviele sind, habt ihr den fehler.



  • Das tun wir bereits aber damit entdecken wir nur einen winzigen Bruchteil der möglichen Fehler 😞 Es geht eben darum, dass wir uns nicht darauf verlassen dürfen, was uns der Gegenspieler als Antwort auf unsere "Schüsse" liefert, sondern dass das Programm möglichts früh selbständig erkennt, wenn etwas nicht stimmen kann


  • Mod

    naja, erstmal koennt ihr das problem in 'inseln' aufteilen.

    zu jedem 'x' legt ihr dafuer eine box ab die sowohl in x als auch y die ausmasse vom laengsten vorhandenen schiff hat.

    ueberlappende boxen fasst ihr dann zusammen, sodass ihr vermutlich 'inseln' habt, die fuer sich loesbar sein muessen.

    nun versucht ihr insel fuer insel zu loesen, falls eine insel nicht loesbar ist, muss eine insel davor noch eine iteration weiter eine loesung generieren (das kann man auch rekursiv machen

    bool Game::Solve(Isle* pIsle)
    {
      while(NextPermutation(pIsle))
      {
        if(ValidSolution(pIsle)
           if(Solve(pIsle->Next())
             return true;
      }
      return false;
    }
    

    im simpelsten fall nimmt NextPermutation ein schiff (mit dem kleinsten anfangend) und setzt es auf das erste 'x' der insel mit einem ende. bei jedem aufruf rotiert es das schiff um 90grad oder setzt es dannach eins weiter auf das naechste 'x'.
    falls es mit einem schiff durchkommt, nimmt die funktion zwei schiffe, setzt erst das erste und auf ein nachfolgendes 'x' das zweite, jeweil die rotationen machend bei jedem durchlauf usw.

    ValidSolution checkt dabei z.b.
    -ueberlappen sich die schiffe?
    -ragt ein schiff ausserhalb der insel?
    -sind alle 'x' belegt und kein 'o' ?
    wenn alles zutrifft, return true; (ich hoffe ich habe keine bedingung vergessen).

    auch wenn das sehr stumpf klingt, soviele permutationen wird es wohl nicht geben, entweder weil am anfang die 'x' fehlen, oder weil gegen ende nicht mehr soviele schiffe vorhanden sind.
    das aufteilen in 'inseln' begrenzt den suchraum dabei erheblich und erlaubt es auch im weiteren verlauf die ergebnisse zu 'cachen' und eventuel nur die beim gegnerzug modifizierte inseln neu zu validieren.

    naja, nur ein vorschlag 😉



  • naja, nur ein vorschlag

    Ein äusserst interessanter!! 🙂 Ich habe deine Idee noch nicht bis ins Detail verstanden, allerdings hört es sich sehr vielversprechend an, vor allem die Idee mit den Inseln, um den Suchraum erheblich einzugrenzen Ich werde mir das mal im Detail ansehen und versuchen, zu implementieren 😉


Log in to reply