KI-Programmierung


Sephiroth

Sephiroth

Active Member
Joined
Jul 11, 2006
Messages
658
Age
34
Location
Germany>kaiserslautern>Hohenöllen
Website
Visit site
Hallo,
ich habe mir vorgenommen ein "Tic Tac Toe" spiel für den gp2x zu scripten.
tic-tac-toe.gif


Meine Frage, wie kannman grundlegend so eine KI programmieren, die intelligent auf die Züge des Spielers reagiert?

Ein einfaches
Wenn der Spieler ins Feld A3 sein Kreuz setzt setzt der cp seinen Kreis auf Feld B1.
ist es ja nicht, da das ja langweilig wäre.

Beim ersten Zug des Spielers hat der CP ja 8 möglichkeiten zu setzten, wie bringt man ihm bei welches ein potenzieller Siag-Weg wäre?

Also, ich verlange keinen komplette code oder so, einfach nur Grundlegend wie soetwas funktionieren könnte.

Bei Google habe ich nur etwas mit Zufallszahlen gefunden, aber es muss ja mehr hintendran stecken. Mit einfachen Zufallszahlen würden die Züge des CP ja keinen Sinn ergeben.

Hoffe mir kann jmd ein Grundgerüst der Vorgehensweise erläutern.


Gruss
 
Bei TicTacToe nützt keine KI. Wenn du den Film WarGames gesehen hast weisst du warum : Man kann nicht gewinnen, nur verlieren :wink:
 
ich habe früher mal sauch das problem gehabt

kam letztendlich da drauf den optimalen weg vorzugeben aber mit einer zufälligen chance (einstellbar) hat er nen falschen zug gemacht ->

nen andere lösungswweg dafür fiel mir nicht ein, ich kann heut nachmittag nochma disketten durchforsten und schauen ob ich den quellcode noch finde, oder der seitdem inne dutten gegangen ist (ja meine ersten c++ gehversuche als 13 jähriger)
 
Unbedingt lesenswert dazu ist auch der Artikel weiter unten :

-> Norman Do: How to Win at TicTacToe (PDF)
Click to expand...
Das isja interessant.!:)
ich habe früher mal sauch das problem gehabt

kam letztendlich da drauf den optimalen weg vorzugeben aber mit einer zufälligen chance (einstellbar) hat er nen falschen zug gemacht ->

nen andere lösungswweg dafür fiel mir nicht ein, ich kann heut nachmittag nochma disketten durchforsten und schauen ob ich den quellcode noch finde, oder der seitdem inne dutten gegangen ist (ja meine ersten c++ gehversuche als 13 jähriger)
Click to expand...
Wäre dir sehr dankbar...
Als 13jähriger? Da hab ich noch mit LEGo gespielt...xD

Gruss
 
Sephiroth said:
Wäre dir sehr dankbar...
Als 13jähriger? Da hab ich noch mit LEGo gespielt...xD

Gruss
Click to expand...

joar wie gesagt kann nix versprechen such gleich ma die disketten stapel vom dachboden zusammen und test dann mal durch

und ja genau das lego spielen hab ich ja damals auch gemacht, mit dem lego cybermaster, und den in not quote c programmieren, damit fings bei mir mit c++ an ;)

(basic v2 aufm c64 aber schon mit 8, dann kam i-wann qbasic, quickbasic, visual basic,... von daher hatte ich grundkenntnisse)
 
Dittboy said:
pff, mit 13 konnte ich x86 assembler schon besser als Deutsch. ;)
Click to expand...

Du solltest wohl immer Deine dreckigen Sachen relativ zum Bett mit einem Displacement im Zimmer auf einen SP definierten Haufen legen? :twisted:
 
Also, mal abgesehen davon, daß TicTacToe wie von andren ja schon gesagt gar keine KI benötigt, ist es sicher ein gutes Übungsprogramm für die KI-Programmierung.
Man kann bei TicTacToe die optimale Strategie zwar auf wenige if-thens reduzieren, aber dabei lernt man ja nix.

Eine übliche Vorgehensweise ist, alle möglichen Spielzüge bis zu einer festgelegten Grenze durchzuspielen und zu bewerten, und danach den besten davon zu wählen.

Angenommen, der Computer beginnt:
er muß nun alle 9 Möglichkeiten durchtesten.
Er tut so, als ob er das erste Feld besetzen würde, schaut sich daraufhin Deine 8 Antwortmöglichkeiten an, zu diesen wieder jeweils all seine 7 Antworten etc.
Jede Kette, die mit einem Sieg für den Compi endet, hebt die Bewertung für das erste Feld. Dann gehts weiter mit dem zweiten ... am Ende setzt er auf das Feld mit der besten Bewertung.
Bei TicTacToe endet diese Kette zum Glück schon nach spätestens 9 Halbschritten und die Anzahl der Möglichkeiten sinkt bei jedem Zug um eins, aber dennoch sind maximal 9*8*7*6*5*4*3*2 Varianten durchzurechnen, also 9! bzw. 362.880 Varianten, was nicht wenig ist.
Es wird weniger, weil viele Varianten bei weniger als 9 Zügen schon zu Ende sind. Dann sinds laut obigem (sehr interessanten, leider englischen) pdf nur noch 255.168 beim ersten Zug).

Aber wie kriegt man da jetzt ein wenig Zufall hinein, so daß der Computer nicht immer nur dieselben Züge macht?
Was taugt ein Schachcomputer, der immer mit dem selben Zug eröffnet?
Das geht eigentlich nur, wenn mehrere Zugmöglichkeiten sich die höchste Bewertung teilen, denn ansonsten müßte der Compi ja absichtlich einen Zug machen, der für ihn weniger gut ist.
Bei Schach liegt das Problem schon darin, wie die einzelnen End-Stellungen zu bewerten sind, da er unmöglich alle Varianten bis zum Ende durchkalkulieren kann.

Bei TicTacToe geht das - nach maximal 9 Halbzügen erweist sich ein Zug entweder als Sieg, oder eben nicht.
Trotzdem kannst Du unterschiedliche Bewertungsverfahren benutzen.
Wichtig ist nur, einen Zug, der zum Gewinn führt, als positiv zu bewerten. Man kann aber auch zusätzlich Züge, die zum Gewinn des Gegners führen, als negativ markieren. Oder eine zusätzliche Bewertung, wenn weniger als 9 Züge nötig sind.

Durch herumspielen an diesen Parametern kann man dann dafür sorgen, daß der Compi am Anfang nicht immer nur für das Mittelfeld die beste Bewertung ermittelt, sondern andere Felder mit gleich hoher Bewertung zur Auswahl stehen.

Naja, kein einfaches Thema, schon allein weil man es mit rekursiver Programmierung zu tun hat ... ;)
 
Also, mal abgesehen davon, daß TicTacToe wie von andren ja schon gesagt gar keine KI benötigt, ist es sicher ein gutes Übungsprogramm für die KI-Programmierung.
Man kann bei TicTacToe die optimale Strategie zwar auf wenige if-thens reduzieren, aber dabei lernt man ja nix.

Eine übliche Vorgehensweise ist, alle möglichen Spielzüge bis zu einer festgelegten Grenze durchzuspielen und zu bewerten, und danach den besten davon zu wählen.

Angenommen, der Computer beginnt:
er muß nun alle 9 Möglichkeiten durchtesten.
Er tut so, als ob er das erste Feld besetzen würde, schaut sich daraufhin Deine 8 Antwortmöglichkeiten an, zu diesen wieder jeweils all seine 7 Antworten etc.
Jede Kette, die mit einem Sieg für den Compi endet, hebt die Bewertung für das erste Feld. Dann gehts weiter mit dem zweiten ... am Ende setzt er auf das Feld mit der besten Bewertung.
Bei TicTacToe endet diese Kette zum Glück schon nach spätestens 9 Halbschritten und die Anzahl der Möglichkeiten sinkt bei jedem Zug um eins, aber dennoch sind maximal 9*8*7*6*5*4*3*2 Varianten durchzurechnen, also 9! bzw. 362.880 Varianten, was nicht wenig ist.
Es wird weniger, weil viele Varianten bei weniger als 9 Zügen schon zu Ende sind.

Aber wie kriegt man da jetzt ein wenig Zufall hinein, so daß der Computer nicht immer nur dieselben Züge macht?
Was taugt ein Schachcomputer, der immer mit dem selben Zug eröffnet?
Das geht eigentlich nur, wenn mehrere Zugmöglichkeiten sich die höchste Bewertung teilen, denn ansonsten müßte der Compi ja absichtlich einen Zug machen, der für ihn weniger gut ist.
Bei Schach liegt das Problem schon darin, wie die einzelnen End-Stellungen zu bewerten sind, da er unmöglich alle Varianten bis zum Ende durchkalkulieren kann.

Bei TicTacToe geht das - nach maximal 9 Halbzügen erweist sich ein Zug entweder als Sieg, oder eben nicht.
Trotzdem kannst Du unterschiedliche Bewertungsverfahren benutzen.
Wichtig ist nur, einen Zug, der zum Gewinn führt, als positiv zu bewerten. Man kann aber auch zusätzlich Züge, die zum Gewinn des Gegners führen, als negativ markieren. Oder eine zusätzliche Bewertung, wenn weniger als 9 Züge nötig sind.

Durch herumspielen an diesen Parametern kann man dann dafür sorgen, daß der Compi am Anfang nicht immer nur für das Mittelfeld die beste Bewertung ermittelt, sondern andere Felder mit gleich hoher Bewertung zur Auswahl stehen.

Naja, kein einfaches Thema, schon allein weil man es mit rekursiver Programmierung zu tun hat ... Wink
Click to expand...
>> :twisted: <<
Ich versuch mich mal einzuarbeiten und sehs als Übung für mein Praktikum nächstes Jahr, das ich wohl im KI-Forschungsinstiut in Kaiserslautern absolvieren werde..:)

Aber äußerst komplexes Thema Künstliche Inteligenz...

Vielen dank für die ausfühlichen Infos..

gruss
 
http://de.wikipedia.org/wiki/Rekursion
http://de.wikipedia.org/wiki/K%C3%BCnstliche_Intelligenz
http://www.ifi.unizh.ch/ailab/aiwiki/aiw.cgi
Click to expand...
Danke für die links!
machst du beruflich auch etwas ähnliches? Man könnte fast meinen du hättest da Ahnung.. :D

Hab ich etwas Lesestoff für meine Klassenfahrt nächste Woche!:)

Gruss
 
You must log in or register to reply here.

Similar threads

profpaule
java-programmierung
Replies
8
Views
3K
G.o.D
G.o.D
matzesu
"Unimog Simulation"
Replies
13
Views
4K
matzesu
matzesu
LecramOS
[Gelöst] SDL 2D Kollisionsabfrage bei bewegten Bild
Replies
2
Views
3K
LecramOS
LecramOS
S
  • Locked
Programmier-Grundstrucktur
Replies
7
Views
848
Joker
Joker
!BrainbuG!
GPH - Official Coding Contest
Replies
10
Views
2K
Vimacs
V
Back
Top