|
Das deutsche QBasic- und FreeBASIC-Forum Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
REZK
Anmeldungsdatum: 28.10.2004 Beiträge: 109 Wohnort: Stuttgart
|
Verfasst am: 31.10.2004, 14:52 Titel: wer hat schon eine ki für tictactoe geschrieben? |
|
|
Hallo,
Ich bin auf der Suche nach einer TicTacToe KI, die übersichtlich und verständlich geschrieben ist und einigermaßen stark sein sollte. Wer so etwas kennt (TicTactoe mit KI) kann den Quelltext mir schicken (paranoia71[ad]web.de) oder in diesen Thread posten.
Ich benötige eine solche KI, da ich selbst eine experimentelle KI für ein TicTacToe Spiel geschrieben hat, die den jeweiligen Zug berechnet, indem der Computer 10000 mal gegen sich selbst spielt und dann den "erfolgreichsten" Zug auswählt. Das Problem: Bisher bestehen die Spiele, in denen der PC gegen sich selbst spiel nur aus Zufallszügen (hier würde ich wenn jemand es erlaubt vielleicht seine KI einbauen), daher ist die Spielstärke OK, sie denkt aber nur 1 Zug voraus.
Danke im voraus, RESK
Wer sich das bisherige Spiel anschauen will: www.geocities.com/iroshdown/tictacto.bas |
|
Nach oben |
|
|
MisterD
Anmeldungsdatum: 10.09.2004 Beiträge: 3071 Wohnort: bei Darmstadt
|
Verfasst am: 31.10.2004, 15:25 Titel: |
|
|
Also bei sonenm simplen Spiel bringt ne KI garnix wenn ich das mal so sagen darf.
Ich hatte mir das durchgedacht und wenn jeder den besten Zug macht den er machen kann kommt am Ende ein unentschieden raus.
Bei dem Spiel gibts so wenige Mögichkeiten an Zügen, dass man die eigentlich alle definieren kann. Eine KI ist also nicht wirklich Sinnvoll..
Mal ein Beispielspiel:
1. Zug: setzt in eine Ecke da dass der Beste Anfang ist.
2. Zug: Gegner setzt in die Mitte da er sonst verliert.
3. Zug: der erste Spieler setzt in irgendein freies Feld was mit der von ihm besetzten Ecke in einer Linie steht um eine Chance auf eine dreierreihe zu haben.
4. Zug: Der Gegner blockiert die Reihe und bekommt dadurch selber die Chance auf eine eigene Reihe.
5. Zug: Der erste Spieler blockt ab.
6. Zug: Der Gegner versucht eine neue Reihe oder muss blocken
das geht dann bis zum 9. so weiter.....
->Unentschieden
Der Zweite Zug ist hier entscheidend. Legt der Gegner nicht in die Mitte kann der erste Spieler eine Zwickmühle aufbauen womit er gewonnen hat. Daher muss dieser auch im ersten Zug in die Ecke legen.
Legt der erste Spieler am Anfang nicht in die Ecke besteht das ganz Spiel nur aus Abblock-Zügen und führt ebenfalls zum Unentschieden. _________________ "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra |
|
Nach oben |
|
|
REZK
Anmeldungsdatum: 28.10.2004 Beiträge: 109 Wohnort: Stuttgart
|
Verfasst am: 31.10.2004, 15:36 Titel: re |
|
|
ja, mister d, du hast schon recht, eigentlich lohnt es sich nicht eine ki für ttt zu programmieren, aber ich wollte meinen oben schon erläuterten ansatz einmal in einem beispiel ausprobieren und da kam mir ttt gerade recht...
da er schon mit zufälligen zügen so schlecht nicht rechnet, denke ich, dass der ansatz auch für größere projekte nicht einmal so unsinnig ist.
vielleicht hat ja trotzdem einer eine ki... |
|
Nach oben |
|
|
Tomtitom
Anmeldungsdatum: 20.09.2004 Beiträge: 308
|
Verfasst am: 01.11.2004, 15:59 Titel: |
|
|
Also es hat mal jemand gesagt, eine gute KI besteht aus sehr sehr vielen If-Abfragen, dementsprechend ein Code http://www.jordanautomations.com/tictactoe.html (Tipp: auch mal Googeln)
hups, irgendwie funktioniert der Code nicht, dann nimm z.B. den http://www.qbasic.com/files/ttt.zip
Und zu deiner Methode an sich, also das ist schon interessant, was du machst, denn es hat schon einen Ansatz von evolutionären KI, aber ich vermute mal, du speicherst nicht die Ergebnisse.
Falls du aber mal doch sowas machen willst, würde mich dein Fortschritt interessieren. Möglichst aber für etwas komplexere Spiele wie 4gewinnt |
|
Nach oben |
|
|
REZK
Anmeldungsdatum: 28.10.2004 Beiträge: 109 Wohnort: Stuttgart
|
Verfasst am: 04.11.2004, 10:46 Titel: 4 gewinnt mit ergebnisse speichern |
|
|
@tomtitom
ich hab mir gestern überlegt, ob ich so ein Projekt wie von dir vorgeschlagen beginnen soll (4 gewinnt mit evolutionärer KI, die durch speichern d. ergebnisse von spiel zu spiel stärker wird).
Aber ich habe ausgerechnet, dass die datei, in der alle spielzüge gescheichert sein müssten so um die 20 Petabyte gross wäre. Aber ich werd mir noch was überlegen...
REZK _________________ Meine sämtlichen QB Projekte findet ihr hier |
|
Nach oben |
|
|
Skilltronic
Anmeldungsdatum: 10.09.2004 Beiträge: 1148 Wohnort: Köln
|
Verfasst am: 04.11.2004, 14:28 Titel: |
|
|
Hallo !
Ich finde, mit dem Begriff der KI wird oft etwas groszügig umgegangen.
Eine Datei anzulegen, in der bereits dagewesene Spielzüge und deren Folgen gespeichert werden reicht noch nicht aus. Das sieht man schon daran, dass ein halbwegs intelligenter Mensch dem die Regeln von 4 Gewinnt zum ersten mal erklärt werden, sofort spielen kann ohne vorher eine 20 Petabyte-Bibliothek angelegt zu haben.
Bei solchen Brett- und Kartenspielen ist es die einfachste Lösung, so vorzugehen wie man es selber in diesem Fall auch tut. Man geht im Geiste mehrere Spielzüge im Voraus durch und versucht so, die beste Möglichkeit zu finden. Da der Rechner dies sehr schnell und präzise tun kann, reicht das eigentlich auch schon aus, um mit uns Menschen mithalten zu können. Auch wenn man dabei dann nicht unbedingt von KI sprechen kann.
Natürlich lernt ein Spieler und wird mit der Zeit immer besser. Das ist auch der Grund, warum wir überhaupt noch gegen ein gutes Programm gewinnen können. Dieses intellligente Verhalten besteht aber nicht nur darin, eine Datenbank anzulegen und dann nachzusehen, ob man schonmal dieselbe Entscheidung treffen musste bzw. wenn ja, bei welcher Reaktion kam es zu welchem Ergebnis.
Ein Wesenselement der Intelligenz ist es, auch auf ganz neue Umstände noch eine angemessene Antwort zu finden. Das geschieht, indem eigentlich alle früheren Spielsituationen in die Bewertung miteinbezogen werden. Wie stark sie berücksichtigt werden, hängt dabei davon ab, wie "ähnlich" sie der neuen sind. Und ganau da liegt der Knackpunkt.
Letztendlich geht es dabei - wie so oft wenn von KI die Rede ist - um eine Mustererkenung. Das sieht man schon beim TicTacToe. Ein nicht unwichtiger Teil eines solchen Programms besteht ja darin, Reihen zu finden, die mit einem der nächsten Züge vervollständigt werden können. Dazu testet der Rechner Reihe für Reihe, Zeile für Zeile und die Diagonalen. Bei 4 Gewinnt wird das schnell unübersichtlich. Der Mensch geht anders vor. Er erkennt sozusagen "intuitiv" das Muster einer angefangenen Reihe. Egal wo und wie diese im Spielfeld liegt - man sieht sie eben einfach (meisstens). So wie wir einen Tisch erkennen, egal ob es ein runder aus Plastik mit einem Bein an einer Imbissbude ist, oder ein schwerer Wohnzimmertisch mit 4 Beinen. Ohne darüber nachzudenken. Das einem Bilderkennungsprogramm beizubringen ist nicht einfach.
Die Leistung hängt zwar von der Grösse der Wissensbasis ab, aber eben auch - wenn nicht vor allem von deren Auswertung. Sonst könnte niemand von einem Spieler mit weniger Erfahrung geschlagen werden. Und die Auswertung durch das Programm so gut zu machen, dass sie an die menschliche herankommt ist sehr, sehr schwierig. Schliesslich sind das Gehirn und die Augen seit ein paar hundert Millionen Jahren auf genau eine solche Mustererkennung und -auswertung getrimmt. Der Rechner dagegen ist von seiner ganzen Architektur nicht darauf ausgelegt, mit Begriffen wie ähnlich oder ungefähr umzugehen.
Speziell beim TicTacToe könnte so eine Datenbank doch ganz sinvoll sein. Selbst wenn man von allen Drehungen und Spiegelungen (Mustererkennung !) absieht, gibt es nur 10862 gültige Spielstände, von denen 6326 Siegstellungen sind.
Für kompliziertere Spiele ist es besser, einfach für mehrere Spielzüge im Vorraus alle Möglichkeiten durchzutesten. Da der Rechenaufwand dabei schnell ansteigt, muss man nur einen Kompromiss finden zwischen Spielgeschwindigkeit und der Zahl der Spielrunden, die vorberechnet werden sollen.
Wen's interessiert, dem schicke ich auf gerne mal ein 4-gewinnt, das ich selbst nach diesem Prinzip geschrieben habe. Der Code ist zwar gruselig und wird ausdrücklich nicht zur Nachahmung empfohlen, aber es läuft so einigermassen.
Gruss
Skilltronic |
|
Nach oben |
|
|
REZK
Anmeldungsdatum: 28.10.2004 Beiträge: 109 Wohnort: Stuttgart
|
Verfasst am: 04.11.2004, 16:16 Titel: |
|
|
@skill
ja, dein 4gewinnt kenne ich ja schon, du meines soweit ich weiss auch...
Eine Frage: Wie kommst du auf die 10862 Spielstände?? Ich werde sobald ich Zeit habe wahrscheinlich so ein TicTacToe mit einer Zugdatenbank, die sich mit jedem Spiel selbst erweitert programmieren.....
Im alten Forum habe ich noch etwas zu diesem Thema gefunden
http://212.168.28.138/cgi-bin/forum/forum.pl?session=&Imsg=34669
REZK _________________ Meine sämtlichen QB Projekte findet ihr hier |
|
Nach oben |
|
|
Skilltronic
Anmeldungsdatum: 10.09.2004 Beiträge: 1148 Wohnort: Köln
|
Verfasst am: 04.11.2004, 22:35 Titel: |
|
|
REZK hat Folgendes geschrieben: | @skill
ja, dein 4gewinnt kenne ich ja schon, du meines soweit ich weiss auch...
Eine Frage: Wie kommst du auf die 10862 Spielstände?? |
Du kennst mein 4gewinnt schon? Ich habe es doch erst an ein oder zwei Leute geschickt und das ist schon ewig her? Hm, dann bist du wohl einer davon. Mein Gedächtnis ist auch nicht mehr das beste...
Auf die 10862 Spielstände komme ich so. Die neun Felder konnen drei Zustände annehmen - leer, Kreuz und Kreis. Das macht maximal 3^9 = 19683 Möglichkeiten. Davon sind aber viele ungültig, die noch aussortiert werden müssen. Ich habe das so gemacht:
Code: |
CLS
GOSUB rechnen
DIM z%(19683)
FOR a = 0 TO 19682
w = a
FOR f = 0 TO 8
t(f) = FIX(w / q(f))
w = w - t(f) * q(f)
NEXT
s(1) = 0
s(2) = 0
FOR f = 0 TO 8
s(t(f)) = s(t(f)) + 1
NEXT
IF s(2) > s(1) OR s(1) - 1 > s(2) THEN z%(a) = -1
IF z%(a) = 0 THEN GOSUB test
IF k > 1 THEN z%(a) = -1
IF k = 1 THEN z%(a) = g
IF z%(a) = -1 THEN ung = ung + 1
IF z%(a) = 0 THEN gos = gos + 1
IF z%(a) = 1 THEN sga = sga + 1
IF z%(a) = 2 THEN sgb = sgb + 1
NEXT
PRINT "ungueltige : "; ung
PRINT "gueltige o. Sieg: "; gos
PRINT "Sieger 1 : "; sga
PRINT "Sieger 2 : "; sgb
PRINT "----------------------"
PRINT "Gesamt :"; ung + gos + sga + sgb
END
test:
g = 0
k = 0
FOR r = 0 TO 6 STEP 3
IF t(r) = t(r + 1) AND t(r) = t(r + 2) AND t(r) > 0 THEN g = t(r): k = k + 1
NEXT
FOR r = 0 TO 2
IF t(r) = t(r + 3) AND t(r) = t(r + 6) AND t(r) > 0 THEN g = t(r): k = k + 1
NEXT
IF t(0) = t(4) AND t(4) = t(8) AND t(4) > 0 THEN g = t(4): k = k + 1
IF t(2) = t(4) AND t(4) = t(6) AND t(4) > 0 THEN g = t(4): k = k + 1
RETURN
rechnen:
FOR a = 0 TO 8
q(a) = 3 ^ (8 - a)
NEXT
RETURN
|
Gruss
Skilltronic |
|
Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|