# "KI" für Schiffeversenken!



## pyr0t0n (2. Mrz 2008)

Aloah,

ich habe ein Schiffeversenken programmiert auch leicht Grafisch, welches aber nicht mein problem ist. Das Spiel wird gegen den Computer gespielt nur ist dieser mir noch ein bisschen zu Blöde.

Hier erstmal meine aktuelle Funktion für den Computer Zug


```
public void ComputerZug(Ship[] player_ship, int anzahl_3er, int anzahl_4er, int anzahl_5er)
    {
        int zufall;
        int x=0;
        int y=0;
        boolean getroffen=false;
        
        if(treffer.size() <= 0)
        {
            naechster_zug_x = ZufallInt(anzahl_felder)-1;
            naechster_zug_y = ZufallInt(anzahl_felder)-1;
            while(map1.getStatus(naechster_zug_x, naechster_zug_y) == 2 || map1.getStatus(naechster_zug_x, naechster_zug_y) == 3)
            {
                naechster_zug_x = ZufallInt(anzahl_felder)-1;
                naechster_zug_y = ZufallInt(anzahl_felder)-1;
            }
        }
        if(treffer.size()>0)
        {
            if(treffer.size()>=2)
            {
                for(int a=0;a<=treffer.size()-1;a++)
                {
                    Punkt p = (Punkt)treffer.get(a);
                    x_pos[a] = p.getX();
                    y_pos[a] = p.getY();
                }
                for(int a=0;a<x_pos.length;a++)
                {
                    for(int b=0;b<x_pos.length;b++)
                    {
                        if(x_pos[b] == x_pos[a]+1)
                        {
                            if(x_pos[b]+1 < anzahl_felder)
                            {
                                naechster_zug_x = x_pos[b] +1;
                                naechster_zug_y = y_pos[b];
                            }
                            if(map1.getStatus(naechster_zug_x, naechster_zug_y) == 2 || map1.getStatus(naechster_zug_x, naechster_zug_y) == 3)
                            {
                                if(x_pos[b]-1 > 0)
                                {
                                    naechster_zug_x = x_pos[b] -1;
                                    naechster_zug_y = y_pos[b];
                                }
                                if(map1.getStatus(naechster_zug_x, naechster_zug_y) == 2 || map1.getStatus(naechster_zug_x, naechster_zug_y) == 3)
                                {
                                    naechster_zug_x = ZufallInt(anzahl_felder)-1;
                                    naechster_zug_y = ZufallInt(anzahl_felder)-1;
                                }
                                else
                                {
                                    break;
                                }
                            }
                            else
                            {
                                break;
                            }
                        }
                    }
                }

            }
            Punkt p = (Punkt)treffer.get(0);
            x = p.getX();
            y = p.getY();
            if(map1.alleFelderUmPunktBesetzt(x, y))
            {
                treffer.remove(0);
            }
            if(x+1 < anzahl_felder && x-1 >= 0 && y+1 < anzahl_felder && y-1 >=0)
            {
                while(map1.getStatus(x, y) == 2 || map1.getStatus(x, y) == 3)
                {
                    zufall = ZufallInt(4);
                    switch(zufall)
                    {
                        case 1: x = x +1; break;
                        case 2: y = y +1; break;
                        case 3: x = x -1; break;
                        case 4: y = y -1; break;
                    }
                }
                naechster_zug_x = x;
                naechster_zug_y = y;
            }
        }
        for(int c=0; c<(anzahl_3er + anzahl_4er + anzahl_5er); c++)
        {
            if(player_ship[c].shipHit(naechster_zug_x, naechster_zug_y))
            {
                map1.schussSetzen(naechster_zug_x, naechster_zug_y, true);
                getroffen = true;
                treffer.add(new Punkt(naechster_zug_x, naechster_zug_y));
            }
        }
        if(!getroffen)
        {
            map1.schussSetzen(naechster_zug_x, naechster_zug_y, false);
        } 
    }
```

Zum ablauf:

1) Wenn keine Treffer verzeichnet sind schiesse zufällig.
2) Sollten Treffer vorhanden sein, dann schiesse um diese Felder drum herum wenn auf das Feld noch nicht geschossen wurde. (getStatus abfrage)

Hat da von euch vllt jemand ne bessere Idee ? Habe mal gegooglet und bin auf einen Source von einer Uni gestoßen welche mit ner Sektor Klasse gearbeitet haben, allerdings nicht Kommentiert was die Klasse genau macht.


----------



## 0x7F800000 (2. Mrz 2008)

naja, mit schritt 1 wäre ich einverstanden, beim schritt 2 berücksichtigst du in keiner weise die lage oder die länge des schiffes... [zumindest wenn deine ausgeschriebene beschreibung zutrifft] den code will ich mir nicht so wirklich anschauen...

Bessere idee: weiß nicht ob die besser ist, aber auf jeden fall interessanter: schreib dir ein evolutionäres system, in dem neuronale netzwerke gegeneinander antreten und der fitteste survived...  :wink: das spiel an sich ist ja eh megaöde, so ein neuronales netztwerkchen würde aber alle voll umhauen wenn es richtig funzt 

good luck have fun


----------



## pyr0t0n (2. Mrz 2008)

aloah,

erstmal danke für die antwort

also im 2ten schritt berücksichtige ich wirklich nicht die länge und die lage, wobei so eine länge ja auch unbekannt ist du weisst ja auch net direkt wie lang das schiff vom computer ist wenn dus triffst sondern erst wenns zerstört ist.

und neuronale netze interessieren mich eh wennde da ne java bezogene anleitung hast her damit


----------



## 0x7F800000 (2. Mrz 2008)

pyr0t0n hat gesagt.:
			
		

> also im 2ten schritt berücksichtige ich wirklich nicht die länge und die lage, wobei so eine länge ja auch unbekannt ist du weisst ja auch net direkt wie lang das schiff vom computer ist wenn dus triffst sondern erst wenns zerstört ist.


ja, mit der länge da hast du eigentlich recht... (sry, hab die regeln nicht mehr so present im hirn^^ :wink: ) aber die lage solltest du unbedingt berücksichtigen: ein schiff ist nämlich immer gerade und geht nie "um die ecke" also wenn du schon zwei kästchen gefunden hast, dann ist zwar nicht die länge, aber die lage determiniert, da machts 0 sinn links oder rechts davon am schiff vorbeizuschiessen


			
				pyr0t0n hat gesagt.:
			
		

> und neuronale netze interessieren mich eh wennde da ne java bezogene anleitung hast her damit


ja, interessiert mich auch... aber irgendwie find ich keine "freie minute" um mich damit zu befassen, verdammter stress  :cry:


----------



## Campino (4. Mrz 2008)

Naja, du kannst noch weiter aussortieren: 

1) Sobald du zwei Felder hast, ist die Lage des Schiffes bekannt. jetzt musst du noch maximal zwei Mal vorbeischießen. Nämlich am Vorderen und hinteren Ende um festzustellen, wie lang das Ding genau ist. 

2) Schiffe dürfen sich nicht berühren. Felder direkt neben einem Schiff kannst du also auschließen. Manchmal lässt sich aus dieser Regel die Lage des Schiffes bestimmen. 

3) Du weißt wieviele Schiffe welcher Länge stehen. Sobald du alle Zweier versenkt hast, musst du in Lücken, wo maximal noch ein Zweier reinpasst, nichtmehr reinschießen. Manchmal lässt sich aus dieser Regel die Lage des Schiffes bestimmen. Eventuell wird einer der beiden nötigen Fehlschüsse aus 1) überflüssig. 

4) Ergänzung zu 3: Alle Schiffe sind mindestens zwei Felder lang. Direkt neben eine Stelle, an die man schonmal geschossen hat zu schießen, lohnt sich nur, wenn dort ein Schiff stand. 

Am Besten vergibst du für jedes Feld einen Wert, der angibt, was da ist. 0= da hab ich ein Schiff getroffen, 1 für da ist Wasser, 2 für da kann nichts stehen, 3 für da muss was sein, ich hab aber noch nicht hingeschossen. Jetzt musst du mit den oben genannten Regeln die Werte für alle Felder berechnen. Dann schießt der Rechner zuerst auf die 3er, dann auf die ohne Wert. 

campino


----------



## 0x7F800000 (4. Mrz 2008)

aha, und wenn man sich ein halbes jahr zeit zum programmieren einer GodLike-KI für "schiffeversenken" nehmen will, kann man noch ein fettes verfahren entwickeln, dass für die ganzen felder Wahrscheinlichkeiten ausrechnet, wie und wo die schiffe am wahrscheinlichsten verteilt sind, diese KI würde selbstverständlich nicht immer zweimal hintereinander auf dasselbe getroffene schiff ballern (das bringt ja nicht so viele informationen) sondern stattdessen nachrechnen, welches feld man beschießen sollte um möglichst viele Kombinationen auszuschließen usw usw usw...

Das ganze ist zwar schön und gut, hat aber einen hacken: dieses spiel wird nämlich kein mensch spielen, und das gewonnene wissen über schiffeversenken-godlike-KI wird man absolut nirgendwo sonst anwenden können... In der selben zeit kann man 1000 interessantere sachen üben...


----------



## Campino (4. Mrz 2008)

Mein Modell muss man um 4 für "Ich hab auf dem Feld daneben ein Schiff und weiß dessen Lage noch nicht, hier zum Ausprobieren" ergänzen. 

Natürlich kann man, um den Gegner in Sicherheit zu wiegen aus Prinzip als Letztes auf die 3er- Felder schießen. Dann muss man nur mit weniger Informationen nach anderen Schiffen suchen  

Andrey: ein halbes Jahr muss man sich dafür nicht nehmen, aber für einen Anfänger ist das eine doch mal eine nette Übung. Und gegen GodLike- Schachcomputer spielen, ähm, verlieren auch immer wieder Leute. 

Echte Profis sorgen für einstellbaren Schwierigkeitsgrad indem man einstellen kann, welche der vier Regeln der Rechner den jetzt verwenden soll (spannend wäre herauszufinden, welche Regel wieviel Einfluss auf das "Spielgeschick" des Computers hat). 

PS: Das ist so aber keine KI, ich würde es eher als "scheinintelligentes, regelbasiertes System" bezeichnen


----------



## pyr0t0n (5. Mrz 2008)

hey danke Campino so hab ich das noch gar nicht betrachtet ich werds mal versuchen umzusetzen.


----------



## Janus (6. Mrz 2008)

aber sei nicht überrascht, wenn du den pc danach nicht mehr schlagen kannst


----------



## pyr0t0n (6. Mrz 2008)

naja kommt ja drauf an wer die schiffe schneller findet ^^ habs jetzt mal in die richtung umgebaut allerdings plagt mich nun seit mehreren stunden ein problem ich weis nicht ob ich einfach zu müde bin.

und zwar folgendes: wenn ich meine schiffe an den Rand platziere dann trifft der Computer eines davon ja irgendwann und sollte dann auf den 3 Felder (weil ich ja nicht über den rand schiessen kann nur 3) drum herum nach einem zweiten treffer suchen. Aber diese schei** drecksmaschine schisst nur auf ein Feld um den eigneltichen treffer und schisst danach wieder Zufällig. PLatziert man die eigenen schiffe aber vom rand weg mitten ins Feld funktioniert er sucht sich bei dem schiff den zweiten treffer und versenkt es dann auch innerhalb der nächsten züge. Aber hier mal mein Code vllt findet ja einer von euch meinen gedankenfehler.


```
public void ComputerZug(Ship[] player_ship, int anzahl_3er, int anzahl_4er, int anzahl_5er)
    {
        int x=0;
        int y=0;
        boolean getroffen=false;
        boolean moegliche_felder=false;
        boolean vertikal=false;
        boolean ein_treffer=true;
        
        for(int a=0; a<anzahl_felder;a++)
        {
            for(int b=0; b<anzahl_felder;b++)
            {
                if(taktik_map.map[a][b] == GETROFFEN)
                {
                    if(a+1<anzahl_felder && taktik_map.map[a][b] == GETROFFEN && taktik_map.map[a+1][b] == GETROFFEN)
                    { 
                        vertikal = false; 
                        ein_treffer = false; 
                    }
                    if(b+1 < anzahl_felder && taktik_map.map[a][b] == GETROFFEN && taktik_map.map[a][b+1] == GETROFFEN)
                    { 
                        vertikal = true; 
                        ein_treffer=false; 
                    }
                    if(a-1 > 0 && taktik_map.map[a][b] == GETROFFEN && taktik_map.map[a-1][b] == GETROFFEN) 
                    { 
                        vertikal = false; 
                        ein_treffer=false; 
                    }
                    if(b-1 > 0 && taktik_map.map[a][b] == GETROFFEN && taktik_map.map[a][b-1] == GETROFFEN) 
                    { 
                        vertikal = true; 
                        ein_treffer=false; 
                    }
                    if(!vertikal && !ein_treffer)
                    {
                        if(a+1 < anzahl_felder && taktik_map.getStatus(a+1, b) != WASSER_GESCHOSSEN && taktik_map.getStatus(a+1, b) != GETROFFEN)
                        {
                            taktik_map.map[a+1][b] = MUSS_WAS_SEIN;
                        }
                        if(a-1 >0 && taktik_map.getStatus(a-1, b) != WASSER_GESCHOSSEN && taktik_map.getStatus(a-1, b) != GETROFFEN)   
                        {
                            taktik_map.map[a-1][b] = MUSS_WAS_SEIN;
                        }
                    }
                    if(vertikal && !ein_treffer)
                    {
                        if(b+1 < anzahl_felder && taktik_map.getStatus(a, b+1) != WASSER_GESCHOSSEN && taktik_map.getStatus(a, b+1) != GETROFFEN)
                        {
                            taktik_map.map[a][b+1] = MUSS_WAS_SEIN;
                        }
                        if(b-1 >0 && taktik_map.getStatus(a, b-1) != WASSER_GESCHOSSEN && taktik_map.getStatus(a, b-1) != GETROFFEN)   
                        {
                            taktik_map.map[a][b-1] = MUSS_WAS_SEIN;
                        }
                    }
                    if(ein_treffer)
                    {
                        if(a+1 < anzahl_felder && taktik_map.map[a+1][b] != GETROFFEN && taktik_map.map[a+1][b] != WASSER_GESCHOSSEN)
                        {
                            taktik_map.map[a+1][b] = MUSS_WAS_SEIN;
                        }
                        if(a-1 > 0 && taktik_map.map[a-1][b] != GETROFFEN && taktik_map.map[a-1][b] != WASSER_GESCHOSSEN)
                        {
                            taktik_map.map[a-1][b] = MUSS_WAS_SEIN;
                        }
                        if(b+1 < anzahl_felder && taktik_map.map[a][b+1] != GETROFFEN && taktik_map.map[a][b+1] != WASSER_GESCHOSSEN)
                        {
                            taktik_map.map[a][b+1] = MUSS_WAS_SEIN;
                        }
                        if(b-1 > 0 && taktik_map.map[a][b-1] != GETROFFEN && taktik_map.map[a][b-1] != WASSER_GESCHOSSEN)
                        {
                            taktik_map.map[a][b-1] = MUSS_WAS_SEIN;
                        }
                    }
                }
            }
        }
        for(int a=0; a<anzahl_felder;a++)
        {
            for(int b=0; b<anzahl_felder;b++)
            {
                if(taktik_map.map[a][b] == MUSS_WAS_SEIN)
                {
                    x = a;
                    y = b;
                    if(taktik_map.map[x][y] != WASSER_GESCHOSSEN && taktik_map.map[x][y] != GETROFFEN)
                    {
                        moegliche_felder = true;
                        break;
                    }
                }
                if(moegliche_felder) break;
            }
            if(moegliche_felder) break;
        }
        if(!moegliche_felder)
        {
            x = ZufallInt(anzahl_felder)-1;
            y = ZufallInt(anzahl_felder)-1;
            while(taktik_map.map[x][y] == WASSER_GESCHOSSEN || taktik_map.map[x][y] == GETROFFEN)
            {
                x = ZufallInt(anzahl_felder)-1;
                y = ZufallInt(anzahl_felder)-1;
            }
        }
        for(int c=0; c<(anzahl_3er + anzahl_4er + anzahl_5er); c++)
        {
            if(player_ship[c].shipHit(x, y))
            {
                map1.schussSetzen(x, y, true);
                getroffen = true;
                taktik_map.map[x][y] = GETROFFEN;
            }
        }
        if(!getroffen)
        {
            map1.schussSetzen(x, y, false);
            taktik_map.map[x][y] = WASSER_GESCHOSSEN;
        } 
    }
```


----------

