Schachcomputer und 4Gewinnt mit KI
-
Ich wüßte gerne mal wie solche Schachcomputer funktionieren, die man für die Reise mitnehmen kann. Ich habe so ein Ding schon einige Jahre im Schrank und frage mich, wie dieses kleine Ding es schafft, in hohen Stufen überhaupt einen großen Suchbaum aufzubauen. Umso höher man die Stufe einstellt umso länger überlegt die Machine, aber bräuchte er dann nicht auch automatisch mehr Speicher für dem Baum?
Ich frage deshalb, weil ich mich mit Mikrocontrollern beschäftige und gerne ein 4gewinnt mit Computergegner bauen würde. An sich ist alles schon fertig, aber der Computergegner ist leider nicht sehr stark, da er keine Züge im voraus berechnen kann, sondern einfach nur stupide guck, wo er die größtmögliche Reihe bauen kann.
Ich habe mir diesbezüglich auch schon den Min-Max-Algorithmus angeschaut, allerdings ist das ein rekursives Verfahren, welches für einen Mikrocontroller ungeeignet ist, da die Stacktiefe auf ca. 30 begrenzt ist und der RAM sich auf ca 1,5KB beschränkt.Hättet ihr Realisierungsvorschläge diesbezüglich?
Das einzige was mir einfällt es vielleicht zu versuchen, indem man den Min-Max-Algorithmus nicht rekursiv programmiert, sondern das ganze mit Zeigern verkettet und dann halt imperativ.
-
Sorry....kann jemand den Beitrag nach Spieleprogrammierung verschieben? Danke!
-
Dieser Thread wurde von Moderator/in kingruedi aus dem Forum Rund um die Programmierung in das Forum Spiele-/Grafikprogrammierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
max rekursionstiefe 30 --> max 30 züge vorausdenken.. ist eigentlich schon nicht schlecht für ne 4 gewinnt ki
-
ausserdem könntest du die Tiefe vielleicht noch künstlich erhöhen indem du in deiner Funktion 2 Züge vorausplanst. Ist etwas aufwendig aber schon hast du die Anzahl der Züge verdoppelt.
Aber 30 ist für 4 gewinnt auch ausreichend denke ich
(wirst allerdings wohl nicht ganz auf 30 kommen, die anderen Funktionen wollen ja auch noch was
)
-
Solche Schachcomputer haben halt außer dem Suchbaum noch ein paar Tricks dabei
Zum Beispiel ne schicke Eröffnungsbibliothek.Außerdem haben sie bestimmt ne Bewertungsfunktion, die ihnen zu einer aktuellen Situation irgendwie eine Bewertung geben können: Bei vielen Schachprogrammen am Rechner kann man da die einzelnen Werte für Bauern etc. noch einstellen. Vielleicht auch die Anzahl der bedrohten Figuren, wie gut die gedeckt sind etc.
Außerdem gibt es die Technik und unklaren Brettsituationen doch noch etwas tiefer zu suchen, um die gut bewerten zu können, während in klaren Situationen das vielleicht nicht nötig ist. => Verlagerung der Rechenzeit.
Außerdem kann man, um die Situation einzuschätzen mal eine Partei zwei Züge hintereinander machen lassen. Das verschafft möglicherweise einen Eindruck darüber, wie groß die Möglichkeiten des Gegners sind: Kann er nur eine Figur schlagen und sich dann wieder zurückziehen? Oder kann er was schlimmeres machen?
-
Außerdem haben sie bestimmt ne Bewertungsfunktion, die ihnen zu einer aktuellen Situation irgendwie eine Bewertung geben können
Ja, eine Bewertungsfunktion wird ja sowieso benötigt, allerdings spielt die KI natürlich umso besser, je weiter man voraus denkt.
max rekursionstiefe 30 --> max 30 züge vorausdenken.. ist eigentlich schon nicht schlecht für ne 4 gewinnt ki
Stimmt, es sind ja gar nicht so viele die ich brauchen würde, allerdings compiliert mir der Compiler erst gar keine rekursiven Funktionen
-
ZzetT schrieb:
Ja, eine Bewertungsfunktion wird ja sowieso benötigt, allerdings spielt die KI natürlich umso besser, je weiter man voraus denkt.
Das stimmt nur bedingt. Bei einer optimalen Bewertungsfunktion wäre ein tieferes Vorausdenken absolut unnötig. Ich kann Dir auch sagen, wie die optimale Bewertungsfunktion aussieht, leider ist sie nicht so richtig gut auszuwerten.
max rekursionstiefe 30 --> max 30 züge vorausdenken.. ist eigentlich schon nicht schlecht für ne 4 gewinnt ki
Stimmt, es sind ja gar nicht so viele die ich brauchen würde, allerdings compiliert mir der Compiler erst gar keine rekursiven Funktionen :-([/quote]
Dann bau Dir selbst einen Stack und leg die Sachen dort ab.
-
Das stimmt nur bedingt. Bei einer optimalen Bewertungsfunktion wäre ein tieferes Vorausdenken absolut unnötig. Ich kann Dir auch sagen, wie die optimale Bewertungsfunktion aussieht, leider ist sie nicht so richtig gut auszuwerten.
Ich denke wir sollten uns darauf einigen, dass es am besten ist einen Mittelweg zu finden zwischen Vorausdenken und guter Bewertungsfunktion.
Andererseits, mit 32Mhz werde ich den Suchbaum eh nichts sehr groß aufbauen können, das würde ein bisschen lange dauern denke ich, da es ja in jeder Stellung meistens 7 mögliche Antwortzüge gibt(kann man natürlich alles noch etwas eingrenzen).Aber um mal auf die Bewertungsfunktion zu sprechen zu kommen: Ich würde es erstmal so implementieren, dass die KI Stellungen gut bewertet, bei denen große Reihen vorkommen, die noch zu 4ern ausgebaut werden können. Vielleicht zusätzlich noch Zwickmühlen gut bewerten oder ähnliches.
An was dachtest du denn da? Würde mich mal interessieren, wie deine Bewertungsfunktion im Groben aussehen würde!?Dann bau Dir selbst einen Stack und leg die Sachen dort ab.
Den Stack selbst zu bauen wäre sicherlich ne Idee, mal sehen wie weit man die Kapazitäten von dem kleinen Ding ausreizen kann.
-
ZzetT schrieb:
Ich denke wir sollten uns darauf einigen, dass es am besten ist einen Mittelweg zu finden zwischen Vorausdenken und guter Bewertungsfunktion.
Garkeine Frage. Ich wollte nur sagen, daß aus rein theoretischer Sicht kein Bedarf für irgendeine Suche besteht.
Da wir in der Praxis leider nach wie vor mit endlicher Rechenzeit auskommen müssen brauchen wir das natürlich trotzdem.ZzetT schrieb:
Aber um mal auf die Bewertungsfunktion zu sprechen zu kommen: Ich würde es erstmal so implementieren, dass die KI Stellungen gut bewertet, bei denen große Reihen vorkommen, die noch zu 4ern ausgebaut werden können. Vielleicht zusätzlich noch Zwickmühlen gut bewerten oder ähnliches.
An was dachtest du denn da? Würde mich mal interessieren, wie deine Bewertungsfunktion im Groben aussehen würde!?Ja, solche Merkmale zu definieren ist sicher sinnvoll. Am besten sowohl für sich selbst, als auch für den Gegner, so daß Du immer jedes Merkmal zweimal hast.
Die ganzen Merkmale könntest Du zum Beispiel alle mit ner Gewichtung versehen und addieren. Daraus wird dann die endgültige Bewertung der Situation. Dadurch hast Du nur noch ein paar Parameter übrig, die Du entsprechend einstellen mußt. Damit kannste dann entweder von Hand ein bissel rumspielen, oder aber versuchen sie einzulernen.