# Künstliche Intelligenz



## Maddimini (25. April 2010)

Hallo 

Ich habe ein VierGewinnt Spiel und möchte dafür ein ComputerGegner erstellen, gegen den der User spielen kann.
Das Spielfeld ist ein Array [7][6].

Vielleicht kann mir jemand helfen, dass der Computer auch mit intelligenten Zügen spiel, bisher leider nur nach Zufallsprinzip. 
Oder mir wenigstens gute Taktiken verrät, die man implementieren kann. 


```
import java.util.Random;

public class Computerspieler
{
    Random zufallswurf;
    VierGewinnt feld;
    int[][] myfeld;
    int s;
    
    public Computerspieler()
    {

        myfeld = new int[7][6];
        
        for (int x=0;x<7;x++) {
            for (int y=0;y<6;y++) {
                myfeld[x][y]=0;
            }
        }
        zufallswurf = new Random();
       
    }

    
   public int gibZug(int[][] feld)
   {
       for (int x=0;x<7;x++){
           for (int y=0;y<6;y++){
               myfeld[x][y]=feld[x][y];
            }
        }        
      
        int x;
        do {
            x=zufallswurf.nextInt(7);
           } 
        
        while (myfeld[x][5]!=0);
        return x;
        }
        
    }
```

Vielen Dank


----------



## lgorse (25. April 2010)

Die einfachste Implementierung einer KI wäre, den Computer nach 3er-Reihen suchen zu lassen, um diese dann mit einem eigenen Stein unbrauchbar machen.

Startbelegung:

```
-O--
-O--
-O--
----
```

Computer setzt X:

```
-O--
-O--
-O--
-X--
```

Das kannst du dann noch erweitern, indem nach Möglichkeiten gesucht wird, wo direkt 2 Reihen unbrauchbar gemacht werden.


----------



## Kai008 (25. April 2010)

Bedenke beim setzen auch, das ein Feld weiter in der Mitte immer mehr wert ist als eins weiter außen.


----------



## Maddimini (25. April 2010)

okay, Danke 
ich habe jetzt:
1. Überprüfung ob man selber gewinnen kann
2. Überprüfung ob der Gegner eine Chance hat zu gewinnen.
3. Erster Stein wird in die Mitte gelegt.

was kann man noch so machen?


----------



## Tubbycore (26. April 2010)

Naja es gibt da noch ein Algorithmus dafür. Der heißt Minimax-Algorithmus kannst ja mal anguckn.


----------



## Maddimini (26. April 2010)

Danke für eure Hilfe


----------



## AlanHorman (13. August 2016)

Hallo,

ich möchte jetzt keinen neuen Thread eröffnen. Ich habe Probleme den Minimax-Algorithmus, wie auch den Alphabeta-Algorithmus richtig zu verstehen und als Programmiercode umzusetzen.
Ich möchte diese Algorithmen verstehen, um für ein Mühle-Spiel eine KI zu programmieren.


Was ich über den Minimax-Algorithmus bis jetzt weiß:
-Es handelt sich um einen Algorithmus, um einen Binären-Suchbaum-Struktur zu durchlaufen. Die Wurzel enthält den Anfangszustand vom Spiel und in den Kinderknoten sind die möglichen Schritte enthalten.
-Die Blätter vom Binären-Suchbaum enthalten die möglichen Endzustände vom Spiel.
-Der Spieler erhält immer maximale Werte und der Computer (KI) die minimalen Werte.

Beim Alphabeta-Algorithmus verstehe ich
-Eine Tiefensuche in der Binären-Suchbaum-Struktur, ohne wirklich sämtliche Blätter zu traversieren und ggf. Teilbäume ignorieren.

Jetzt meine Konkreten Fragen:

-Muss ich wirklich einen Binären Suchbaum programmieren, um eine KI zu entwickeln?
-Wie bestimme ich die Werte, die im Binären Suchbaum gespeichert sind?
-Wo finde ich übersichtliche Codebeispiele, wo gezeigt wird, wie ich Minimax und Alphabeta programmieren muss (C, C++, C#, Python, Java oder JavaScript)?


----------



## sheel (13. August 2016)

Hi



AlanHorman hat gesagt.:


> Muss ich wirklich einen Binären Suchbaum programmieren, um eine KI zu entwickeln?


a) Kein "binärer" Baum, außer beim betroffenen Spiel hat man nie mehr als zwei Zugmöglichkeiten.
b) Wenn man die Vorgänge vom Algo speichern will, ja, man braucht einen Baum. Wenn man nur daran interessiert ist, welchen Zug man machen will ... rekursive Funktionen mit jeweils lokalen einzelnen Variablen imitieren den "Baum" ganz gut. Kein Grund, die Datenstruktur selber zu programmieren.



AlanHorman hat gesagt.:


> Wo finde ich übersichtliche Codebeispiele, wo gezeigt wird, wie ich Minimax und Alphabeta programmieren muss


Sollte "eigentlich" nicht nötig sein, wenn man den Algo und Rekursion versteht. Sonst  (Allerdings hab ich auf die Schnelle keinen übersichtlichen _und_ fertigen Code gefunden, eben deswegen...).

...

Was jeder "Baum"knoten an Daten braucht:
a) Einen vollen Spielstand (was man da wie abspeichert hängt ganz vom Spiel ab. zB. bei Schach wäre es, welche Figur samt Farbe auf welchem Feld steht, welcher der zwei Spieler noch die Rochade machen darf, und welcher der vorhandenen Bauern zurzeit enpassant-fähig ist)
b) Welcher der zwei Spieler gerade dran ist.
c) Eine Zahl, die den Spielstand bewertet. Wertebereich kann man sich selber aussuchen, unter folgenden Bedingungen: Je höher, desto besser ist der aktuelle Spielstand für den Algo-verwendenen Spieler (KI), und je neidriger desto besser für den Anderen. Beim höchstmöglichen Wert hat die KI gewonnen, beim Niedrigsten eben der Andere. ... Ein mögliches (aber nicht gutes) Beispiel wäre 1 für A gewinnt, -1 für B gewinnt, und 0 für ein unfertiges Spiel und auch für Unentschieden. Der Algo arbeitet aber besser mit breiteren Wertebereichen.

Außerdem braucht man ein paar spezielle Funktionen, die beide vom Spiel abhängen:

a) Eine Funktion, die einen Spielstand von Punkt a darauf hin überprüft, ob jemand gewonnen hat (und auch wer) oder ob das Spiel noch offen ist.

b) Eine Bewertungsfunktion, die aus den Daten von Punkt a die Zahl aus Punkt c berechnet. Natürlich einhalten, dass höhere Werte besser für die KI sind usw.
Falls man nicht nur 1/-1/0 hat ist das oft schwierige Teil am Ganzen. Eine gute Werteermittlung (bessere Spielstände für den Algoverwender also bessere Zahlen) ist aber essentiell für den Erfolg vom Algo.

c) Eine Funktion, die aus einem Spielstand (aus a) und aus der Info wer gerade dran ist (aus b) alle möglichen nächsten Spielstände ermittelt. Also, genau einen Zug später.

...

Dann, die Idee von Minimax (in der einfachsten Form und ohne Heuristiken, und als Baum beschrieben):
Man ist gerade eben mitten im Spiel, udn die KI muss den nächsten Zug berechnen.

a) Dafür zuerst einmal den aktuellen Spielstand als Baumknoten abbilden (aber ohne Bewertungszahl c noch, also nur a und b)

b) Baumaufbau: Alle nächsten Spielstände generieren, von denen rekursiv wieder alle nächsten ... bis zu einer bestimmten (wählbaren) Tiefe. Je tiefer desto besser fürs Ergebnis, aber tiefer dauert auch länger. Ideal wäre natürlich ein kompletter Baum, aber für Spiele wie Schach etc. geht das einfach nicht.
(Falls man auf Spielenden stößt, bei denen natürlich keine weiteren Kindknoten generieren)

c) Für alle Blätter in dem Baum (egal ob Spielende oder einfach wegen der Tiefe dort aufgehört) die C-Zahl mit der Bewertungsfunktion berechnen.

d) Von unten nach oben wie folgt die Bewertung der Nicht-Blätter ermitteln: Wenn man die Bewertung für einen Knoten will, bei dem die KI dran ist, die höchste Bewerung der (direkten) Kindknoten nehmen. Für Knoten, wo der Gegner dran ist, stattdessen die niedrigste Bewertung der (direkten) Kindknoten.

Sinn dahinter: Wenn die KI dran ist, immer den Zug mit dem wahrscheinlich besten Ergebnis nehmen; aber immer auch annehmen dass der Gegner den für sich besten Zug macht (also den für die KI schlechtesten)

Die Schritte b, c und d können codemäßig eben leicht durch eine rekursive Funktion mit Parametern und Returnwert umgesetzt werden.

e) Fertiggerechnet, man ist wieder an der Baumwurzel: Das Kind der Wurzel hernehmen, das die höchste Bewertung hat, und genau diesen Zug machen.

Pseudocode b/c/d:

```
solve(spielstand, kiIstDran, wieTief)
{
     if(spielIstAus(spielstand) || wieTief < 1) return bewerte(spielstand);
     variablen zielwert, aktuellerwert
     if(kiIstDran) zielwert = kleinsterBewertungswert //kann mit max nur größer werden
     else zielwert = gröterBewertungswert //umgekehrt
     für jeden zielspielstand in (berechneAlleZüge(spielstand, kiIstDran))
     {
          aktuellerwert = solve(zielspielstand, not kiIstDran, wieTief - 1)
          if(kiIstDran) zielwert = max(aktuellerwert, zielwert)
          else zielwert = min(aktuellerwert, zielwert)
     }
     return zielwert;
}
```
Jetzt das für alle gerade jetzt möglichen Züge (bzw. deren Ergebnis-Spielstände) aufrufen, und den Zug mit dem höchsten Returnwert nehmen.

...

Alphabeta (wieder in der einfachsten Form und ohne Heuristiken) sind zwei Verschnellerungen, ohne das Ergebnis zu verschlechtern. Es geht darum, dass man anhand der Bewertungszahlen schon bekannter Knoten verschiedene Kind-Teilbäume einfach nicht berechnen braucht.

Voraussetzung im Code ist, dass man in solve() auch den aktuellen Zielwert des nächsthöheren Knoten bzw. der oberen aufrufenden Funktion hat, auch wenn die mit ihrem eigenen Schleifendurchgang noch nicht fertig ist.

```
solve(spielstand, kiIstDran, wieTief, obererZielwert)
{
     if(spielIstAus(spielstand) || wieTief < 1) return bewerte(spielstand);
     variablen zielwert, aktuellerwert
     if(kiIstDran) zielwert = kleinsterBewertungswert //kann mit max nur größer werden
     else zielwert = gröterBewertungswert //umgekehrt
     für jeden zielspielstand in (berechneAlleZüge(spielstand, kiIstDran))
     {
          aktuellerwert = solve(zielspielstand, not kiIstDran, wieTief - 1, zielwert)
          if(kiIstDran) zielwert = max(aktuellerwert, zielwert)
          else zielwert = min(aktuellerwert, zielwert)
     }
     return zielwert;
}
```

Idee 1: Im aktuell zu solve-nden Knoten ist die KI dran. In den Unteraufrufen von solve ist klarerweise der Gegner dran. Die KI nimmt den höchsten Wert ihrer Kinder, und die Kindern nehmen den niedrigsten Wert ihrer Kinder. Klar soweit.
Angenommen, der KI-Knoten hat drei Kinder, eins ist schon abgearbeitet, Wert 10. Sollte eins der zwei anderen Kinder höher sein wird natürlich der höhere Wert genommen, sonst bleibts bei 10.

Diese zwei noch zu prüfenden Kinder müssen also mindestens 10 (bzw. 11) erreichen, um überhaupt relevant zu sein.

Wenn eines der Kinder während der eigenen Schleife draufkommt, dass eines der Kindeskinder kleiner als 10 war ...
bei den Kindern ist ja der Gegner dran
=> kleinster Wert ist das Ergebnis
=> Ein Wert kleiner 10 bedeutet, es kann nicht mehr größer als 10 werden
=> Die noch offenen Kindeskinder können weggelassen werden, weil das Kind
selber schon nicht mehr über 10 kommen kann und damit unwichtig ist.


```
solve(spielstand, kiIstDran, wieTief, obererZielwert)
{
     if(spielIstAus(spielstand) or wieTief < 1) return bewerte(spielstand);
     variablen zielwert, aktuellerwert
     if(kiIstDran) zielwert = kleinsterBewertungswert //kann mit max nur größer werden
     else zielwert = gröterBewertungswert //umgekehrt
     für jeden zielspielstand in (berechneAlleZüge(spielstand, kiIstDran))
     {
          aktuellerwert = solve(zielspielstand, not kiIstDran, wieTief - 1, zielwert)
          if(kiIstDran) zielwert = max(aktuellerwert, zielwert)
          else zielwert = min(aktuellerwert, zielwert)
         
          if(not kiIstDran and zielwert < obererZielwert) return zielwert;
     }
     return zielwert;
}
```

Idee 2, das Umgekehrte dazu

```
if(kiIstDran and zielwert > obererZielwert) return zielwert;
```
(Sinn sollte klar sein).


----------

