Verschoben! KI Algorithmus - Schiffe versenken

Neue Frage »

Stefan342 Auf diesen Beitrag antworten »
KI Algorithmus - Schiffe versenken
Hi,

ich mache mir gerade einige Gedanken zu dem Spiel "Schiffe versenken". Dabei suche ich nach dem besten Weg mit dem Computer eine gute Trefferquote zu erzielen.

Der Computer muss dabei verschiedene Faktoren berücksichtigen:

1. Variable Spielfeldgröße
2. Unterschiedliche Schiffgrößen
3. Wechselnde Anzahl von Schiffen

Nun suche ich nach einem idealen Suchalgorithmus. Für Tipps bin ich deshalb seh dankbar! smile
Mazze Auf diesen Beitrag antworten »

Ich nehme mal an das Du keine komplizierten Verfahren suchst. Aber ich frage mich ob Du damit in einem Matheforum richtig bist. Man kann das ganze äußerst mathematisch halten aber das wäre hier einfach mit Kanonen auf Spatzen. Ich würde es einfach Regelbasiert halten :

Es gibt 3 Mengen : U = Menge der unentdeckten Felder, E = Menge der Entdeckten Felder, S = Felder auf denen ein Schiff getroffen wurde. Dann hat man




Ist kein Schiff getroffen oder alle getroffenen Schiffe sind vollständig aufgedeckt, dann wähle zufällig ein Feld aus U. Da wir mal ohne Vorwissen herangehen würde ich die Felder gleichverteilt wählen.

Ist ein Schiff neu getroffen worden, suche um das Trefferfeld. Ist ein Schiff vollständig versenkt entferne alle umliegenden Felder (sofern nicht schon entfernt) aus U und füge sie in E ein.

Die Entscheidung ob ein Schiff vollständig abgeschosse ist kann entweder durch aufdecken der Grenzfelder an Bug und Heck getroffen werden, oder aber wenn schon Schiffe versenkt worden sind kann mit unter schon früher aufgehört werden. Wenn ein Schiff mit 5 Feldern das Größte war und abgeschossen wurde und wir aktuell ein Schiff beschiessen und 4 Felder erledigt haben, so könnte man auch hier wieder mit Schüssen ins Blaue fortfahren. Das Ganze kann anhand der Menge S entschieden werden.
Silencer Auf diesen Beitrag antworten »

Dadrueber hab ich auch schonmal nachgedacht smile

Was ich mir einmal gedacht hatte, war, dass man prinzipiell ja die Wahrscheinlichkeit, ein Schiff zu treffen, maximieren muss. Lt einfacher Wahrscheinlichkeitsrechnung kann man feststellen, dass diese Wahrscheinlichkeit direkt mit der Anzahl der Schiffe, die auf diesem Feld liegen koennen, zusammenhaengt (damit braucht man keine Fliesskommazahlen, das ist immer gut).

Damit musst du dann im endeffekt einfach nen Rechner nehmen und fuer jede Schiffsgroessen alle moeglichen Positionen nehmen und auf einer Matrix, die so gross ist wie das Spielfeld, da 1 draufaddieren, wo das Schiff draufliegt.

Danach muss man dann erstmal dahin feuern, wo die Zahl am groessten ist (Falls das uneeindeutig ist -> Randomisierung oder mehr Nachdenken fuer eine Strategie ueber mehrere Level, d.h., einen Koordinatenvektor suchen, bei dem im Endeffekt die Gesamtwahrscheinlichkeit dann maximal wird (durch das Verhalten hier kann man dann beispielsweise auch die Schwierigkeit anpassen)). Danach muss man noch die umliegenden Felder anpassen, da durch einen Wassertreffer natuerlich die Wahrscheinlichkeiten der umliegenden Felder sinken koennen.

Das funktioniert lustigerweise auch fuer unendlich grosse Spielfelder mit arbitraeren Schiffsformen (wird dann nur etwas kompliziert, effiziente Algorithmen dafuer zu finden).
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »