MinMax Algorythmus

  • VB.NET

Es gibt 13 Antworten in diesem Thema. Der letzte Beitrag () ist von raist10.

    MinMax Algorythmus

    Hallo @ all

    Ich habe mir im Internet den MinMax Algorythmus angeguckt aber verstehe Ihn leider nicht so ganz. Ich möchte gerade ein Schachspiel programmieren, welches die nächsten 7 Schritte voraus plant und habe gelesen das soll damit funktionieren. Könnte mir pls mal jemand erklären wie der Algorythmus funktioniert und vllt auch bisschen Code schreiben? SOll jetzt nicht der komplette Algorythmus sein - wills schon selber machen - aber bisschen zur Verdeutlichung. Habs leider so nicht wirklich verstanden wie der Funktionieren soll.

    Hoffe auf eure Hilfe. Viele Grüße
    Crosaider
    Bitte. Hier ist meine Hilfe.
    Nur hab ich überhaupt nicht verstanden, wie wir Dir helfen sollen. :S
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Dann solltest Du endlich mal was zu diesem Algorithmus schreiben, am besten den ganzen Code.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Croasider schrieb:

    Hier ist ein Pseudocode allerdings bekomm ich den nicht ganz richtig umgesetzt.

    Suchst Du jemanden, der Dir diesen Code nach VB überträgt?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Ich würde mal ganz Frech behaupten dass die Programmierung von Künstlicher Intilligenz nicht mal eben so schnell gemacht ist. Da steckt viel Arbeit dahinter und es wird für dich und die meistens von uns hier so gut wie unmöglich sein dieses ordentlich zu Programmieren. Eine richtige ordentlich Programmierte KI kostet viel Zeit und Nerven. Wenn sie dann auch noch performant sein soll viel Spaß. Ein Arbeitskollege von mir, welcher Studierter Informatiker ist programmier nun schon seit ca. sechs Monaten an einem Schachspiel mit KI nur um es ideal Optimiert zu bekommen.

    Ich würde dir davon abraten.

    lg.
    lg.

    LucaWelker
    Hab mich jetzt doch für den AlphaBeta Algorithmus entschieden siehe hier.

    Habe mal versucht den Pseudocode in VB umzuwandeln aber irgendwie macht der im mom nur scheiße. Fehler an solche vom Compiler oder Laufzeitfehler treten keine auf. Was habe ich falsch gemacht? Muss aber sagen hab am Anfang hier bisschen geschummelt, der Algorythmus wird nicht für Schach sondern ein anderes Spiel ;) Sry hatte erst vor das zu machen habe mich dann aber umentschieden.

    Spoiler anzeigen

    VB.NET-Quellcode

    1. Private Function Max(ByVal tiefe As Integer, ByVal alpha As Integer, ByVal beta As Integer)
    2. Dim wert As Integer
    3. If tiefe = 0 Then
    4. Return Bewerten()
    5. End If
    6. Dim ListeX As New List(Of Integer)
    7. Dim ListeY As New List(Of Integer)
    8. Zuege(Position(0), Position(1), ListeX, ListeY) 'Züge generieren
    9. For i = 0 To ListeX.Count - 1
    10. Spielfeld(ListeX(i), ListeY(i)) = 2 'Zug ausführen
    11. Spielfeld(Position(0), Position(1)) = 1 'Zug ausführen
    12. wert = Min(tiefe - 1, alpha, beta)
    13. Spielfeld(ListeX(i), ListeY(i)) = 1 ' Zug zurücksetzen
    14. Spielfeld(Position(0), Position(1)) = 2 'Zug zurücksetzen
    15. If wert >= beta Then
    16. newPos(0) = ListeX(i)
    17. newPos(1) = ListeY(i)
    18. Return beta
    19. End If
    20. If wert > alpha Then
    21. alpha = wert
    22. End If
    23. Next
    24. Return alpha
    25. End Function


    VB.NET-Quellcode

    1. Private Function Min(ByVal tiefe As Integer, ByVal alpha As Integer, ByVal beta As Integer)
    2. Dim wert As Integer
    3. If tiefe = 0 Then
    4. Return Bewerten()
    5. End If
    6. Dim ListeX As New List(Of Integer)
    7. Dim ListeY As New List(Of Integer)
    8. Zuege(Position(0), Position(1), ListeX, ListeY) 'Züge generieren
    9. For i = 0 To ListeX.Count - 1
    10. Spielfeld(ListeX(i), ListeY(i)) = 2 'Zug ausführen
    11. Spielfeld(Position(0), Position(1)) = 1 'Zug ausführen
    12. wert = Max(tiefe - 1, alpha, beta)
    13. Spielfeld(ListeX(i), ListeY(i)) = 1 ' Zug zurücksetzen
    14. Spielfeld(Position(0), Position(1)) = 2 'Zug zurücksetzen
    15. If wert <= alpha Then
    16. newPos(0) = ListeX(i)
    17. newPos(1) = ListeY(i)
    18. Return alpha
    19. End If
    20. If wert < beta Then
    21. beta = wert
    22. End If
    23. Next
    24. Return beta
    25. End Function


    Und wie genau muss ich den beim ersten Start aufrufen? Habe da ja noch keine alpha bzw. beta Werte. Würde mich über eure Hilfe freuen :)
    Hast Du denn diesen AlphaBeta Algorithmus auf dem Papier (nicht im Quelltext) vollständig verstanden?
    Erst dann hat es Zweck, ihn zu programmieren, und erst, wenn Du ihn uns erklären kannst, hat es Zweck, Hilfe zu erbitten.
    Schließlich sind das doch Deine Hausaufgaben. :D
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Das ist genau das was ich meinte. Solange du nicht verstanden hast wie der Algorythmus in der theorie funktioniert wird er auch praktisch nie so funktionieren wie er soll.

    Und wer versucht Pseudocode aus Wikipedia etc. in funktionierenden Code umzuwandeln kann die theoretische Funktionsweiße nicht verstanden haben.

    lg.
    lg.

    LucaWelker
    Ich habe mir jetzt mal den Pseudo-Code auf Wikipedia angesehen ... ich würde jetzt mal schätzen für die Umsetzung in echten VB-Code dürfte dafür locker einige 100.000 Zeilen Code nötig sein. ^^

    Der Pseudocode ist eindeutig nicht für die Übernahme in echten Code gedacht sondern liefert nur ein Prinzip.

    Du musst Dir für diese Funktion erstmal Gedanken machen wie Du überhaupt eine Bewertung eines Zuges gestalten willst. Denn das Prinzip ist doch das der Code zu jedem Zeitpunkt jeden möglichen Zug bis zur gewünschten Tiefe bewertet.

    Also ... wonach soll bewertet werden und vor allem wie?

    Hier mal ein kleiner Ansatz:

    1. Datenbank erstellen und sagen wir mal die letzten 100.000 Schachspiele aller Großmeister dort einpflegen ... eh klar, je mehr desto besser. Dabei muss für jeden Zug folgendes auswertbar sein: Komplette Anfangsstellung des Spieles vor dem Zug und welche Züge folgten diesem Zug. Am sinnigsten wäre es natürlich wenn Du auch eine Möglichkeit schaffst alle Folge-Züge eines einzigen Zuges bei einer einzigen Stellung aus allen gespeicherten Spielen in einer Abfrage ermitteln zu können.

    2. Jetzt kannst Du in jeder Situation jeden Zug bewerten der bekannt ist. Alle Spieleinträge durchsuchen und die Spiele rausholen die gerade der aktuellen Aufstellung entsprechen, danach jeden Zug der in diesen DB-Spielen gemacht wurde bewerten ... z.B. bis Tiefe 7, einfach durchprüfen was wurd wie bewegt und wie oft wurde bei dieser Bewegung inkl. der nächsten 7 nachfolgenden Bewegungen das Spiel gewonnen wurde, dabei natürlich alle gleichen Züge zu einer gesamten Zugbewertung zusammen führen ... je höher die Zahl desto besser die Bewertung. Und der Zug der die höchste Bewertung hat wird dann angewendet.

    Das Prinzip ist simple ... bloss an die Umsetzung würde ich mich wirklich nicht ran trauen, ausser mein Auftraggeber hat seeehr viel Geld und seeehr viel Zeit übrig. ^^

    Gruß

    Rainer