4-Gewinnt mit guter KI

[Norbie]

Im Kern ist mein 4-Gewinnt so ausgelegt, dass sie für belibige Feldgrößen ausgelegt ist. Wenn du es mit heutigen Rechnern schaffst ein 20*20 Feld zu lösen, bist du gut. Ich hab nur ersteinmal 7*6 genommen, weil das Standart ist, und es bei größeren Feldern ewig überlegt. Die Komplette Spielidee ist also sicherlich nicht durchgerechnet, nur ein Sonderfall.

Das ist auch gut so, sonst hätte der Mensch wohl keine Chance. Wenn er gewinnen will, braucht er also einfach die Spielfeldgröße erhöhen

Menschen haben ebend mehr Überblick als die armen Computer mit ihrem Tunnelblick

[Norbie]

Hi noch mal.

Ich hab das ganze Programm nocheinmal etwas optimiert. Es dürfte jetzt keine Fehler, wie das nichtnutzen einer Gewinnchance mehr machen. Das ganze ist ein wenig schneller und stärker. Also alle die, die mein 4-Gewinnt schon einmal geschlagen haben, bitte ich noch einmal um ein paar Minuten Zeit.

Ich schaffe es leider nicht zu gewinnen. Auch gegen das alte Programm nicht. Mir fehlen dazu wohl ein paar Gehirnwindungen

Link nochmal:
http://nevu.ne.funpic.de/downloads.php? ... =downloads

[stbi]

im 1. Versuch ...

Code: Alles auswählen

  X O
X O X
O OOOOO
X OXOXX
X XOOXX
X OOXOX
1234567

Du hast gewonnen! Respekt   <ENTER><ENTER> -> ENDE

[Norbie]

Verdammt

Wenn ich ihn aber noch tiefer suchen lasse, überlegt er eine Minute lang.
Naja, ist es eben nur ein 4-Gewinnt für einsteiger bis 12 jahre

[DrShrek]

[quote="Norbie"]...
Ich schaffe es leider nicht zu gewinnen. Auch gegen das alte Programm nicht...[quote]
Wahrscheinlich noch kein 12 Jahre alt.

[merlin]

gibt es das pdf auch in irgendeiner form ins deutsche übersetzt?

[Konne]

Lol sowas genau im gleichen Stryle hab ich auch für meinen GTR (Grafischer Taschen Rechner) geschrieben... Nur ohne halt im Multiplayer da der Rechner bei KI aufgegeben hat schnell zu sein^^

[Kaeru Gaman]

beim dritten versuch gewonnen... (mußte erst warmlaufen )

respekt! das ist die beste KI, gegen die ich seit langem ein mini-game gespielt hab.

wie lang ist der source für die KI?


leider ist die oberfläche nicht so schick, ich vermute mal, dein hauptaugenmerk
lag auf der KI, und das hat sich wirklich gelohnt.

wenn du das mit ner schicken grafischen oberfläche versehen willst,
helf ich dir gern mit den grafix...

[Norbie]

hi!
Die beste KI?
Hast du die ganzen vorigen Posts nicht gelesen?
Naja egal, schön das es einem gefallen hat!
Hier ist der gesammte Quellcode!
Nachdem ich aus der Schule zurück bin, werde ich ihn noch etwas kommentieren, und links posten, die das Prinzip der Ki erklären.
Ich will nicht unbedingt noch ne GUI dazu entwickeln, dass kannst du aber gerne machen, und es als dein Eigentum verkaufen für jediglich 170% Gewinnbeteiligung

Code: Alles auswählen

;spielintern sind die steine und leeren felder natürlich durch Zahlen dargestellt
#weiss=-1
#schwarz=1
#leer=0

OpenConsole()

;Wie groß darf das Feld sein?
#xsize=7
#ysize=8

;Wieviele Züge soll die KI vorraus denken?
#suchtiefe=6


;Da purebasic keine Lokalen Arrays kennt habe ich mir etwas eigenes Gebastelt mit Memorys. 
;Es gänge auch anders und effizienter aber das wusste ich damals noch nicht.
Procedure get(adresse.l,x.l,y.l)
;  If x>=1 And x<= #xsize And y>=1 And y<= #ysize

    ProcedureReturn PeekL(   adresse + (((y-1)*(#xsize)+(x-1))*4) )  
;    Else
;  Debug "fehler bei aufruf von get x="+Str(x)+" y="+Str(y)
;  EndIf
EndProcedure


Procedure set(adresse.l,x.l,y.l,wert.l)
;If x>=1 And x<= #xsize And y>=1 And y<= #ysize
  PokeL(   adresse + (((y-1)*(#xsize)+(x-1))*4), wert )  
;Else
;  Debug "fehler bei aufruf von set x="+Str(x)+" y="+Str(y)  
;EndIf
EndProcedure

Procedure new_feld()
  ProcedureReturn AllocateMemory(#xsize*#ysize*4)
EndProcedure

Procedure del_feld(adresse)
  ProcedureReturn FreeMemory(adresse)
EndProcedure

Procedure mov_feld(adresse1, adresse2)
  CopyMemory(adresse2, adresse1, #xsize*#ysize*4)
EndProcedure




;ein erweiterter Print befehl....
;BRAUCHT DIE KI NICHT
Procedure exprint(x,y,text.s)
  ConsoleLocate(x,y)
  Print(text)
EndProcedure

;dieser Befehl gibt das Spielfeld aus
;BRAUCHT DIE KI NICHT
Procedure show(adresse.l)
  ClearConsole()
  ;For x=1 To #xsize
  ;  For y=1 To #ysize
  ;    exPrint(x,y," ")
  ;  Next
  ;Next
  
  For x=1 To #xsize
    For y=1 To #ysize
      If get(adresse,x,y)<>0
        ConsoleLocate(x-1,#ysize-y)
        If get(adresse,x,y)=#weiss
          ConsoleColor(12,0)
          Print("X")
        Else
          ConsoleColor(10,0)
          Print("O")
        EndIf
        ConsoleColor(15,0)
      EndIf
    Next
  Next
  
  For x=1 To #xsize
    exPrint(x-1,#ysize, Hex(x))
  Next
  
EndProcedure


;Die funktion testet wer im übergebenen Feld gewonnen hat und gibt den gewinnr zurück oder null
Procedure gewinner_in(feld)
  For x=1 To #xsize-3
    For y=1 To #ysize
      wert=get(feld,x,y)
      If wert=get(feld,x+1,y) And wert=get(feld,x+2,y) And wert=get(feld,x+3,y) And wert<>#leer
        ProcedureReturn wert
      EndIf
    Next
  Next
  For x=1 To #xsize
    For y=1 To #ysize-3
      wert=get(feld,x,y)
      If wert=get(feld,x,y+1) And wert=get(feld,x,y+2) And wert=get(feld,x,y+3) And wert<>#leer
        ProcedureReturn wert
      EndIf
    Next
  Next
  For x=1 To #xsize-3
    For y=1 To #ysize-3
      wert=get(feld,x,y)
      If wert=get(feld,x+1,y+1) And wert=get(feld,x+2,y+2) And wert=get(feld,x+3,y+3) And wert<>#leer
        ProcedureReturn wert
      EndIf
    Next
  Next
  For x=1 To #xsize-3
    For y=4 To #ysize
      wert=get(feld,x,y)
      If wert=get(feld,x+1,y-1) And wert=get(feld,x+2,y-2) And wert=get(feld,x+3,y-3) And wert<>#leer
        ProcedureReturn wert
      EndIf
    Next
  Next
  ProcedureReturn #leer
EndProcedure

;Mit dieser Funktion kann man ganz einfach einen "Stein einwerfen",
; man muss nur Farbe und spalte angeben
Procedure zug_in(feld,spalte,farbe)
  For y=1 To #ysize
    If get(feld,spalte,y)=#leer
      set(feld,spalte,y,farbe)
      ProcedureReturn 1
    EndIf
  Next
  ProcedureReturn 0
EndProcedure

;die Funktion entfernt den Obersten stein in der angegebenen Spalte
Procedure zug_back_in(feld,spalte)
  For y=#ysize To 1 Step -1
    If get(feld,spalte,y)<>#leer
      set(feld,spalte,y,#leer)
      ProcedureReturn 1
    EndIf
  Next
  ProcedureReturn 0
EndProcedure

;Diese funktion testet ob noch ein Stein in eine Bestimmte spalte passt
Procedure zug_possible_in(feld,spalte)
  If get(feld,spalte,#ysize)=#leer    
    ProcedureReturn 1
  EndIf
  ProcedureReturn 0
EndProcedure




;Diese Funktion bewertet den aktuellen SPielstand, um so besser es für einen Spieler aus sieht, um so
;höher ist der zurückgegebene wert
Procedure einfache_bewertung(feld, farbe)
  bewertung.l=0
  
  siegwertung=0
  gewinner=gewinner_in(feld)
  If gewinner=farbe
    steine=0
    For x=1 To #xsize
      For y=1 To #ysize
        If get(feld,x,y)<>#leer
          steine+1
         EndIf
      Next
    Next
    ProcedureReturn 10000-steine
  ElseIf gewinner=farbe*-1
    steine=0
    For x=1 To #xsize
      For y=1 To #ysize
        If get(feld,x,y)<>#leer
          steine+1
         EndIf
      Next
    Next
    ProcedureReturn -10000+steine
  EndIf

  
  
  
  
  
  ; Dreiertest   sehr wichtig!
  dreiertest=0
  For x=1 To #xsize-2
    For y=1 To #ysize
      wert=get(feld,x,y)
      If wert=get(feld,x+1,y) And wert=get(feld,x+2,y) And wert<>#leer
        If wert=farbe
          dreiertest+1
        Else
          dreiertest-1
        EndIf
      EndIf
    Next
  Next
  For x=1 To #xsize
    For y=1 To #ysize-2
      wert=get(feld,x,y)
      If wert=get(feld,x,y+1) And wert=get(feld,x,y+2) And wert<>#leer
        If wert=farbe
          dreiertest+1
        Else
          dreiertest-1
        EndIf
      EndIf
    Next
  Next
  For x=1 To #xsize-2
    For y=1 To #ysize-2
      wert=get(feld,x,y)
      If wert=get(feld,x+1,y+1) And wert=get(feld,x+2,y+2) And wert<>#leer
        If wert=farbe
          dreiertest+1
        Else
          dreiertest-1
        EndIf
      EndIf
    Next
  Next
  For x=1 To #xsize-3
    For y=4 To #ysize
      wert=get(feld,x,y)
      If wert=get(feld,x+1,y-1) And wert=get(feld,x+2,y-2) And wert<>#leer
        If wert=farbe
          dreiertest+1
        Else
          dreiertest-1
        EndIf
      EndIf
    Next
  Next
  ;zentrumstests
  halbzentrum=0
  For x=#xsize-(#xsize*4)/10 To #xsize-(#xsize/10)
    For y=1 To #ysize
      If get(feld,x,y)=farbe
        halbzentrum+1
      ElseIf get(feld,x,y)=farbe*-1
        halbzentrum-1
      EndIf
    Next
  Next 
  
  ;Verbundenheitstest
  verbunden=0
  For x=1 To #xsize
    For y=1 To #ysize
      If get(feld,x,y)=farbe
        If y-1>=1 And x-1>=1
          If get(feld,x-1,y-1)=farbe
            verbunden+1
          EndIf 
        EndIf
        If y-1>=1
          If get(feld,x,y-1)=farbe
            verbunden+1
          EndIf
        EndIf
        If y-1>=1 And x+1<=#xsize
          If get(feld,x+1,y-1)=farbe
            verbunden+1
          EndIf
        EndIf
        
        If x+1<=#xsize
          If get(feld,x+1,y)=farbe
            verbunden+1
          EndIf
        EndIf
          
        If x+1<=#xsize And y+1<=#ysize
          If get(feld,x+1, y+1)=farbe
            verbunden+1
          EndIf
        EndIf
          
        If y+1<=#ysize
          If get(feld,x,y+1)=farbe
            verbunden+1
          EndIf
        EndIf
          
        If y+1<=#ysize And x-1>=1
          If get(feld,x-1,y+1)=farbe
            verbunden+1
          EndIf
        EndIf          
                    
        If x-1>=1
          If get(feld,x-1,y)=farbe
            verbunden+1
          EndIf
        EndIf         
           
      EndIf
    Next
  Next
    
    ;Mit dem ändern der Zahlenkonstanten kann man die Prioritäten ändern und somit die entscheidungen der ki
    bewertung=bewertung+verbunden*1
    bewertung=bewertung+halbzentrum*4
    bewertung=bewertung+dreiertest*10
  ;tttttttttttttttttt
  ProcedureReturn bewertung
EndProcedure


;Das ist die eigentliche Ki
Procedure NegaMax(orgfeld,farbe,wechselfarbe, tiefe)
  feld=new_feld()
  mov_feld(feld,orgfeld)
    best= -2000000000

    If tiefe <= 0 Or gewinner_in(feld)            
        wert=einfache_bewertung(feld,wechselfarbe)
        del_feld(feld)
        ProcedureReturn wert
    EndIf
    

    For x=1 To #xsize
    If zug_possible_in(feld,x)
        zug_in(feld,x,wechselfarbe)
        ;show(feld)
        ;Input()
        val=-NegaMax(feld,farbe,wechselfarbe*-1,tiefe-1); // Note the minus sign here.

        zug_back_in(feld,x)

        If (val > best)
            best = val;
            If tiefe=#suchtiefe
              bestmov=x
            EndIf
        EndIf
     EndIf
     
   
     Next
      del_feld(feld)
    ProcedureReturn best

EndProcedure


;Diese Funktion gibt die Spalte zurück, in die die Ki werfen will.
;die funktion will das spielfeld haben, welche farbe die ki hat und wie weit sie denken soll (suchtiefe)
Procedure ki_zug(orgfeld,farbe, suchtiefe)
 feld=new_feld()
  mov_feld(feld,orgfeld)
    best= -2000000000

    If gewinner_in(feld)            
      ProcedureReturn 0
    EndIf
    
    ;direkte gewinn, verlustsuche
    
    For x=1 To #xsize
      If zug_possible_in(feld,x)
        zug_in(feld,x,farbe)
          If gewinner_in(feld)=farbe
            ProcedureReturn x
          EndIf
        zug_back_in(feld,x)
        
        zug_in(feld,x,farbe*-1)
        If gewinner_in(feld)=farbe*-1
            ProcedureReturn x
        EndIf
        zug_back_in(feld,x)
      EndIf
     
   
     Next
    

    For x=1 To #xsize
    If zug_possible_in(feld,x)
        zug_in(feld,x,farbe)
        
        val=-NegaMax(feld,farbe,farbe*-1,suchtiefe-1); // Note the minus sign here.

        zug_back_in(feld,x)

        If (val > best)
            best = val;
            bestmov=x
        EndIf
     EndIf
     
   
     Next
      del_feld(feld)
    ProcedureReturn bestmov
EndProcedure


spielfeld=new_feld()
show(spielfeld)







Repeat
    zeit=GetTickCount_()
  kizug=ki_zug(spielfeld,#weiss, #suchtiefe)
  zeit=GetTickCount_()-zeit
  zug_in(spielfeld,kizug,#weiss)
  show(spielfeld)
  exprint(20,20,Str(zeit))
  If gewinner_in(spielfeld)=#weiss
    show(spielfeld)
    exprint(0,#ysize+6,"Du hast VERLOREN! LOOSER!!!! <ENTER><ENTER> -> ENDE")
    Input()
    Input()
    End
  EndIf
  
  
  
  Repeat
    exprint(0,#ysize+5,"In welcher Spalte moechten sie ziehen?      ")
    PrintN("")
    benutzerzug=Val(Input())
    exprint(0,#ysize+6,"                                ")
  Until benutzerzug>=1 And benutzerzug<=#xsize And zug_possible_in(spielfeld,benutzerzug)
  zug_in(spielfeld,benutzerzug,#schwarz)
  show(spielfeld)
  If gewinner_in(spielfeld)=#schwarz
    show(spielfeld)
    exprint(0,#ysize+6,"Du hast gewonnen! Respekt   <ENTER><ENTER> -> ENDE")
    Input()
    Input()
    End
  EndIf

Until gewinner_in(spielfeld)

[Kaeru Gaman]

thnx für den code!

habs erstmal nur gezogen, muss mir zeit nehmen, durch deinen code zu steigen,
um die teile zu trennen, die KI allein zu haben.

mit "beste KI" meinte ich in einem mini-game.

logisch gibts ne menge KIs, und auch etliche die besser sind,
aber die sind dann auch länger.

was mich beeindruckt hat, war, diese spielstärke in lediglich 11KB vorzufinden.

ich komm noch aus C64 zeiten, damals mußte man so programmieren können.
heutzutage haben das viele vergessen, und proggen nach dem motto:
speicher und rechenleistung haben wir doch genug, lass es uns zukacken.

wenn du gerne KIs proggst, schau doch mal hier rein: c-evo
ein civ-clone, der dafür ausgelegt ist, KI dafür selbst zu schreiben.