In meiner Klasse für Datenstrukturen wurde uns ein Projekt zugewiesen, in dem wir ein voll funktionsfähiges Quantum-Tic-Tac-Toe-Spiel erstellen müssen, in dem ein Spieler einem Bot gegenübersteht, der spielt, um zu gewinnen.
Der Professor hat vorgeschlagen, dass wir einen Spielbaum in unserer KI verwenden. Wie immer suche ich jedoch etwas herausfordernderes.
Kann jemand einen besseren, fortgeschritteneren Ansatz vorschlagen, den ich erforschen und umsetzen könnte?
Ich suche nicht nach etwas völlig Lächerlichem, das das Problem komplexer macht. Ich suche eher nach einem fortgeschrittenen Ansatz - wie der Verwendung eines A * -Algorithmus anstelle eines BFS.
Dein Wunsch, neue Dinge (selbstständig) zu lernen, ist gut. Jedoch ist eine komplizierte Lösung oft nicht die beste Lösung .
Es gibt einen guten Grund, warum Ihr Professor vorgeschlagen hat, einen Spielbaum für die KI zu verwenden. Es wird vorgeschlagen, weil es das richtige Werkzeug für den Job ist. Es gibt keinen besseren Ansatz, den Sie erforschen können, weil es der beste Ansatz ist.
Sie haben erwähnt, dass Sie sich in einer Datenstrukturklasse befinden (normalerweise eine erste oder zweite Klasse). Ich vermute, dass der Punkt Ihrer Aufgabe ist, über Baumdatenstrukturen zu lernen. Wenn Sie die Dinge komplizierter machen wollen, schreiben Sie zuerst die Baumversion und suchen Sie nach anderen Wegen, um das gleiche Problem zu lösen.
Es gibt 2 Teile um ein rundenbasiertes Spiel zu bewerten.
Der Spielbaum ermöglicht es dir, Züge im Voraus auszuprobieren, um zu sehen, wohin sie führen werden. Wenn das Spiel komplex genug ist, dass Sie nicht alle Möglichkeiten ( Ссылка ) berechnen können, dann brauchen Sie eine Möglichkeit zu bestimmen, wie "gut "Ein bestimmtes Board-Szenario ist. Eine schlechte Dienstprogrammfunktion für Schach könnte einfach Stückwerte zählen und die Position ignorieren.
Sie brauchen auch eine effiziente Möglichkeit, den Spielbaum zu durchqueren. Lesen Sie über Minimax, Alpha-Beta-Beschneidung, Negascout, etc.
Ich arbeite gerade an diesem spezifischen Problem: Ссылка
Ich hatte darüber nachgedacht, etwas fortgeschritteneres zu tun, aber ich bleibe nur bei dem guten Alpha-Beta-Suchalgorithmus. Mein Hauptproblem besteht darin, einen guten Algorithmus zu finden, um jeden einzelnen Board-Zustand zu "bewerten". QTTT ist viel komplizierter als Standard Tic Tac Toe, die Anzahl der zu durchsuchenden Zustände ist exponentiell größer. Ich habe den kompletten Standard-Tic-Tac-Toe-Spielbaum im Gedächtnis, mit dem ich schnell die Punkte für jeden "klassischen" Brettstand nachschlagen kann, aber dann muss ich irgendwie den Superpositionszustand bewerten. Die Anzahl der Zustände ist so groß, dass Sie nicht zu tief in den Baum gehen können, daher ist eine geeignete Bewertungsfunktion, um den Baum frühzeitig zu beschneiden, ein Muss.
Um Ihrer Implementierung eine Lernfunktion zu bieten, können Sie in einen Emulator für Donald Mitchie MENACE (Matchbox Erziehbare Noughts and Crosses Engine) .. .
Bearbeiten :
Wenn man sich das genauer anschaut, ist das schon ziemlich weit hergeholt, siehe zum Beispiel auf CodeProjet
Darüber hinaus, und während Sie ein statistisches Modell der Welt (oder hier der Tic-Tac-Toe-Welt) erwerben und zukünftige Handlungen auf einem solchen Modell aufbauen, ist intelligentes Verhalten, das von Ihrem Professor als nicht in Betracht gezogen betrachtet werden kann, weil es nicht berührt Schlüsselkonzepte, die Sie wahrscheinlich in der Klasse behandelt haben (Wissensrepräsentation, Entscheidungsbäume ...)
Tags und Links java artificial-intelligence