kleine spiele

[Freak2k]

Hallo,

ich programmiere schon seit langem allerlei anwendungen.
Doch ab und zu ist ein kleiner drang da, mal ein kleines spiel zu programmieren, allein der erfahrung wegen!
Ich denke da nicht an irgendwelche aufgeblasene ego shooter...sonder an kleine spiele, wie 4 gewinnt, XXO.... etc.

Der großteil der implementierung stellt meisten kein problem dar....doch die "KI"
Wie sage ich dem programm, welchen zug es machen soll?
Beispiel 4 gewinnt: ich werfe mein steinchen in eine spalte....kein problem.
jetzt ist der computer an der reihe....in welche spalte soll er sein steinchen werfen?

irgendwelche seiten, tutorials, etc

danke

 

[Dennis Wronka]

Erstmal folgendes: Halte Dich bitte auch im neuen Jahr an Gross- und Kleinschreibung.

Nun zum Thema:
Ich hatte vor vielen Jahren mal ein TicTacToe (oder XXO wenn's beliebt) in Pascal programmiert.
Dieses konnte anhand der aktuellen Situtation beschliessen welcher Zug zu tun ist. Also ob eine Reihe beendet, ein Sieg vereitelt oder gar eine Falle gebaut werden muss.
Eine Falle dabei stellt sich ungefaehr so dar: Feld X1,Y1 besetzt, Feld X2,Y1 vom Gegner besetzt, Feld X3,Y1 besetzt, falls nun X2,Y2 und X3,Y2 frei sind kann durch setzen des Feldes X3,Y3 bewirkt werden, dass man 2 Moeglichkeiten hat zu beenden.
Falls keine dieser Angaben zutrifft, zum Beispiel bei den ersten Zuegen entscheidet der Zufall.

Genau so kannst Du z.B. auch bei 4 gewinnt vorgehen. Jedes Mal wenn der Computer am Zug ist ueberprueft dieser ob er beenden kann oder eine gegnerische 3er-Reihe durch einen eigenen Stein blockieren muss und so weiter.

 

[hpvw]

Ein TicTacToe hatte ich auch mal in Pascal.
Bei einem so "einfachen" Spiel ist es noch möglich alle Situationen zu testen.
Dein Algorithmus tut also so, als ob er zunächst ein Feld für den Computer besetzt, dann ein Feld für den Spieler, dann wieder ein Feld für den Computer und so weiter. Das lässt sich rekursiv lösen.
Nun wird zunächst ein Teilbaum gesucht, bei dem alle Blätter zum Sieg führen. Ist einer gefunden, wird dieser Zug gewählt. Wird kein solcher Teilbaum gefunden, suchst Du nach einem, bei dem zumindest kein Blatt zur Niederlage führt und möglichst viele zum Sieg.
Bei TicTacToe ist das noch kein Problem, da nur neun Entscheidungen zu treffen sind und das Spiel bei zwei perfekten Spielern immer unentschieden ausgeht.
Bei anderen Spielen musst Du die Rekursion irgendwann abbrechen und die Situation bewerten. Möglicherweise sollte man die Situation bei jedem Versuch bewerten, um "schlechte" Teilbäume frühzeitig aus der Bewertung zu nehmen und darauf keine Rechenzeit zu verschwenden.

Noch ein Beispiel eines solchen Entscheidungsbaums für TicTacToe:
Angenommen der Spieler O findet die Situation S 1 vor. Er hat drei Möglichkeiten sein O zu setzen. Diese drei testet er und prüft was Spieler X setzen könnte. Für diesen bleiben zwei Möglichkeiten. Beide probiert er aus. Ist damit das Spiel noch nicht beendet (weil Spieler X gewonnen hat), besetzt Spieler O das letzte freie Feld. Die Situationen werden bewertet, indem festgestellt wird, ob Spieler O oder Spieler X gewonnen hat oder ob es ein unentschieden gibt. Daraus ergibt sich, dass er sein O in das Feld unten rechts malen sollte, da er hier noch gewinnen kann aber das schlechteste ein unentschieden ist.

                      Simulierte
     Entscheidung    Entscheidung 
      Spieler O       Spieler X    

                              o o x    o o x
                          --  o o x -- o o x  gewonnen  
               o o x     /    x x      x x o
           --  o o x ---|
          /    x         \    o o x
         |                --  o o x  verloren
         |                    x   x 
         |                  
         |                  
         |                  
S 1      |                    o o x    o o x
         |                --  o x x -- o x x  unentschieden
o o x    |     o o x     /    x o      x o o
o   x ---+---  o   x ---|
x        |     x o       \    o o x    
         |                --  o   x  verloren
         |                    x o x     
         |                  
         |   
         |
         |                    o o x    o o x
         |                --  o x x -- o x x  unentschieden
          \    o o x     /    x   o    x o o
           --  o   x ---|
               x   o     \    o o x    o o x
                          --  o   x -- o o x  gewonnen
                              x x o    x x o

Spielen beide Spieler nach einem solchen rekursiv erstellten Entscheidungsbaum, geht TicTacToe immer unentschieden aus.
Bei disem Spiel ließ sich auch "damals" mit beschränkter Rechenkapazität bereits der komplette Entscheidungsbaum bilden, so dass das Unentschieden zwischen zwei Computern sicher war. Bei anderen Spielen, wie Vier gewinnt, Dame, Schach, Mühle etc. gibt es zu viele Möglichkeiten, so dass Du Dir für jedes Spiel einen Bewertungsalgorithmus schreiben musst. Dieser ist natürlich individuell für das Spiel und bewertet die Situation eines nicht zuende aufgestellten Entscheidungsbaums.

Gruß hpvw

 

[Sunray]

[Offtopic]
Theoretisch könnte man doch aber alle diese Spiele bis zum letzten Zug durchrechnen oder? (Vorausgesetzt man hat genügend Zeit/Rechenkraft).
Sollte tatsächlich mal jemand in der Lage sein, Schach komplett zu berechnen, dann würde das Spiel doch absolut sinnlos....
[/Offtopic]

 

[hpvw]

Theoretisch könnte man doch aber alle diese Spiele bis zum letzten Zug durchrechnen oder? (Vorausgesetzt man hat genügend Zeit/Rechenkraft).

Im Prinzip ja, aber ...

Sollte tatsächlich mal jemand in der Lage sein, Schach komplett zu berechnen, dann würde das Spiel doch absolut sinnlos....

Sinnlos würde ich nicht sagen. Es könnte sich dadurch ergeben, ob Schach ein Spiel ist, bei dem immer schwarz oder immer weiss gewinnt oder, ob es ein Spiel, wie TicTacToe, ist, welches immer unentschieden ausgeht. Aber Schach ermöglicht so viele Varianten bei jedem Zug, dass es in absehbarer Zeit nicht vollständig berechenbar sein wird. Außerdem ist Schach nicht zwingend endlich. Dadurch ergibt sich entweder ein unendlich tiefer Baum oder man erhält einen Graphen, wenn man Situationen wieder auf bereits berechnete Situationen zurückführt.
Es ist also etwas komplizierter, als Spiele, die zwingend zum Ende kommen, wie TicTacToe oder auch vier gewinnt.

Gruß hpvw

 

[Alexander12]

Hi.

Microsoft hat auch Webcasts zur Spieleprogrammierung bereitgestellt. 3D sowie 2D, dort wird glaub auch das Thema KI behandelt.

Auf dieser Seite des Forums gibts dazu nen netten Thread.


MfG Alexander12