# # R-Programm Bleistift-TENNIS mit Künstlicher Intelligence (KI) # # Umsetzung für Zeitschrift WURZEL 08/12 (Details siehe in dieser Ausgabe) # Autor: Arne Ring, Oxford (arne.ring@lycos.com) # Weitere Informationen: Wikipedia, Tennis (Bleistiftspiel) # #============================================================================== # # Zum Spielen in die freie Statistik-Software R ab Version 2.10 notwendig # Download und Details zur Programmierung in R, siehe www.r-project.org # # Nach Laden dieses R-Programms kann man einfach mit # spiel(stratno2=1,auto=2) # gegen den Computer spielen. # # Um den Computer zunächst zu trainieren, sollte man ihn zunächst gegen sich selbst # spielen lassen, wobei 10.000 - 1.000.000 Spiele zu Beginn sinnvoll sind: # spielkette(anzahl=10000,update=TRUE,training=MAXPERSPIEL) # #============================================================================== # # Regeln: # Spielfeld mit zwei Feldern auf jeder Seite -3<=B(t)<=3 # Start: 50 Punkte für beide Spieler (P1(0)=P2(0)=50) # Ball auf Mittellinie (B(0)=0) # * Pro Zug gleichzeitiges Ziehen beider Spiele bis zur vorhandenen Punktzahl # (0<=Z1(t)<=P1(t), 0<=Z2(t)<=P2(t), Z(t)=0 nur bei P(t)=0) # * Höherer Zug schlägt den Ball ( S(t)=sign(Z1(t)-Z2(t) ) # - Wenn S(t)=1 und B(t) in {1,2}, dann B(t+1)=B(t)+1 # - Wenn S(t)=1 und B(t) in {0,-1,-2}, dann B(t)=+1 # - Entsprechend umgekehrt wenn S(t)=-1 # - Bei Gleichstand kein Schlag # * Spiel endet bei B(t) in {-3,3} oder Z1(t)=Z2(t)=0 # * Wertung: Wenn zum Schluss Ball im Feld: 1 Punkt; Ball herausgeschlagen 2 Punkte # #============================================================== # # Zugraum ist (P1,P2,B,Z1) - zu jedem Zustand (P1,P2,B) eine Wahrscheinlichkeit für den Zug Z1 # * Dimension: 50x50x4x50 = 500000 (nur Zustände -2,-1,1,2 notwendig) pro Spieler # * Wahrscheinlichkeit bestimmt sich aus Anzahl der Punkte, die Z1 gemacht hat # - p(Z1|(P1,P2,B))= |Z1|+SUM(Z1i) (i=1-50) # - Vorbelegung: Alle unerlaubten Züge (Z1>P1) mit 0 belegen, alle anderen mit einem geeigneten Wert # - Bei Gewinn eines Ballwechsels bekommen alle Züge, die zum Gewinn führten, Punkt(e) # - Bei Verlust werden Punkt(e) abgezogen # - Minimale Belegung pro Zustand festlegen (außer für Zustände, die zu Beginn 0 sind) # #============================================================== # # Dieses R-Programm erlaubt das Spielen gegen den Computer, wobei der Computer # selbständig lernt, seine Strategie zu verbessern. # Bei der Standard-Lernstrategie erhalten alle Züge, die zum Sieg führten, einen # Pluspunkt, bei Verlust einen Minuspunkt (bis zur erlaubten Mindestpunktzahl die >=1 ist). # # Die anderen Strategien unterscheiden sich davon durch # * Mindestpunktzahl (1,2,5) für mögliche Züge # * Standard-Initialisierungswert (1,2,5,10) für mögliche Züge # * Nutzung der Zustandswerte zur Ermittlung der Wahrscheinlichkeit (Linear, Wurzel etc.) # * Lernzuwächse (positiv vs. negativ sowie in Bezug auf unterschiedliche Wertung - (+2,+1,-1,-2) # - Wie Gewinnpunkte (+2,+1,-1,-2) # - Betonung des Herausschlagens (+5,+1,-1,-5) # - Gleichbewertung des einfachen Gewinnens (+1,+1,-1,-1) # - Höhere Zuwächse (+10,+5,-5,-10) - besonders mit Wurzel-Nutzung # - Kurze Spiele weniger Punkte als lange Spiele # #=============================================================== # # Umsetzung des Spiels in R # # Die folgenden Objekte und Funktionen werden definiert: # 0) Grundregeln # MAXPERSPIEL - Start mit 50 Punkten # # 1) Initialisierung der Strategien # NUMBSTRAT - Anzahl der möglichen Strategien (hier 16) # defstrat - Initialisiert die Strategien # straty - die Strategiematrix für alle Strategien, 4-dimensional # (Punktanzahl Sp1, Punktanzahl Sp2, Ballort (3-> Mitte), nächster Zug) # # 2) Interne Funktionen # askstrat - eine Strategie wird nach ihrem nächsten Zug gefragt # * Dies ist die zentrale Möglichkeit zur möglichen Einbettung anderer KI-Strategien # ballplace - Ermittelt den nächsten Ballort # updatestrat - Aktualisiert die KI-Matrix # # 3) Spielfunktionen zum Nutzeraufruf # spiel - Spiel gegen den Rechner # * Startet Spiel # * Startet ZUG # * Fragt Züge beider Strategien ab # * Setzt den Ball, fragt nach ENDE, sonst neuer ZUG # * Bei ENDE, Modifikation der Algorithmen, Zählen der Gewinne pro Strategie # * neues Spiel # # spielkette - Training des Rechners gegen sich selbst, auch als Turniermodus # * inkl. Auswertung der erzielten Punkte # * Tuniermodus: alle Züge die nur wenig wahrscheinlich zum Gewinn führen, werden als Wahrscheinlichkeit "0" geführt. # ###################################################################### # Initialisierung ###################################################################### MAXPERSPIEL =50 # ==> Spieldefinition GLOBAL # Funktion zur Initilisierung der KIs defstrat<-function(INITPUNKT=1) { # INITPUNKT=1 ==> Alle "erlaubten" Züge erhalten diese positive Punktanzahl stratyx=rep(0,(MAXPERSPIEL +1)*(MAXPERSPIEL +1)*5*(MAXPERSPIEL +1)) dim(stratyx)<-c(MAXPERSPIEL +1,MAXPERSPIEL +1,5,MAXPERSPIEL +1) # Spielstart for (i4 in 2:MAXPERSPIEL ) # Spielbeginn, wenn Ball noch in der Mitte liegt, alle Züge bis zur Maximalzahl sind möglich stratyx[(MAXPERSPIEL +1),(MAXPERSPIEL +1),3,i4] = MAXPERSPIEL +1+INITPUNKT-i4 # erlaubte Züge, außer Nullzügen for (i1 in 2:(MAXPERSPIEL )) for (i2 in 1:(MAXPERSPIEL )) for (i4 in 2:(MAXPERSPIEL )) if (i4<=i1 && i4<=i2+1) # Nur erlaubte Züge und nie mehr als Gegner+1 (Effizient !) for (i3 in 1:5) if (i3!=3) # Wenn der Ball nicht mehr in der Mitte liegt, muss die Punktanzahl der beiden Spieler voneinander verschieden sein stratyx[i1,i2,i3,i4]=INITPUNKT else if(i1==i2) # Wenn die aktuelle Punktanzahl beider Spieler gleich ist stratyx[i1,i2,i3,i4]=INITPUNKT # Nullzüge - nur erlaubt, wenn der Spieler keine Punkte mehr besitzt for (i2 in 1:(MAXPERSPIEL )) for (i3 in 1:5) stratyx[1,i2,i3,1]=INITPUNKT return(stratyx) # Rückgabe der initialisierten Strategie } ######################################################## # 1) Definition der einzelnen Strategien ######################################################## NUMBSTRAT=16 # Insgesamt werden 16 Strategien erstellt # 1. INPOINT (Standard-Initialisierungswert (1,2,5,10)) # 2. MINPOINTS<=INITPUNKT (Untere Grenze der KI-Punkte (1,2,5) (kann nicht unterschritten werden, damit erlaubte Züge immer möglich bleiben) # 3. TURNIERPUNKT>=MINPOINTS (Alle Zustände mit diesen Turnierpunkten werden auf 0 gesetzt (Achtung: prüfen) # 4. LEARNPOINTS[,1/2/3] (Lernpunkte für Spielausgang 1, 2 und 3) # 5. ACCELPOINTS[,1/2] (Zusatzpunkte für schnelles Ende: A1-Anzahl max. Schritte, A2 Anzahl Zusatzpunkte) # 6. PROBUSE (Funktion zur Bestimmung der Wahrscheinlichkeiten: 1=Linear, 2=Wurzel) INPOINT =c(2,2,2,2, 2,2,2,2, 5, 5, 5, 5, 5, 5, 5, 5) length(INPOINT) MINPOINTS =c(1,1,1,1, 1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1) length(MINPOINTS) LEARNPOINTS=rep(0,3*NUMBSTRAT) dim(LEARNPOINTS)<-c(NUMBSTRAT,3) LEARNPOINTS[,1]=c(1,1,1,1, 1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1) LEARNPOINTS[,2]=c(1,1,2,2, 1,1,2,2, 1, 1, 2, 2, 1, 1, 2, 2) LEARNPOINTS[,3]=c(1,2,3,5, 1,2,3,5, 1, 2, 3, 5, 4, 8, 4, 8) ACCELPOINTS1 =c(5,5,5,5, 5,5,5,5, 0, 0, 0, 0, 0, 0, 0, 0) #length(ACCELPOINTS1) # nur als Kontrolle ACCELPOINTS2 =c(1,1,1,1,-1,-1,-1,-1,0, 0, 0, 0, 0, 0, 0, 0) #length(ACCELPOINTS2) # nur als Kontrolle PROBUSE =c(1,1,1,1, 1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1) #length(PROBUSE) # nur als Kontrolle ################### ## ## Diese Funktion sollte nur bei ERSTMALIGER Initialisierung laufen, da sonst das bisher erworbene KI-Wissen überschrieben wird ! ## ################### erstinit<- function() { zuz=defstrat(INITPUNKT=2) straty<<-rep(0,NUMBSTRAT*dim(zuz)[1]*dim(zuz)[2]*dim(zuz)[3]*dim(zuz)[4]) dim(straty)<<-c(NUMBSTRAT,dim(zuz)) for (ii in 1:NUMBSTRAT) straty[ii,,,,]<<-defstrat(INITPUNKT=INPOINT[ii]) # Felder zur späteren Ermittlung der gewonnenen Spiele jeder KI LERNSPIELE <<-rep(0,NUMBSTRAT) # Anzahl der Spiele, die ins Update der Strategie einfließen (es fließen ggf. auch Spiele ein, die zum Update der KI genutzt wurden, ohne dass diese KI selbst gespielt hat) GESPIELT <<-rep(0,NUMBSTRAT) # Anzahl der gespielten Spiele SIEGPOINTS <<-rep(0,NUMBSTRAT) # Anzahl der gewonnenen Punkte } ################### # Entweder initialisieren oder laden erstinit() #load("X:\\xxxxxxxxxxx\\tennis.RData") ################################ # 2) Spielfunktionen ################################ # # askstrat - Frage eine Strategie, welchen Zug sie als nächstes auswählt # PROBUSE: linear: p(Z1|(P1,P2,B))= Z1 / SUM(Z1i) # Wurzel: p(Z1|(P1,P2,B))= Wurzel(Z1) / SUM(Wurzel(Z1i)) askstrat=function(stratno=1,points1=50,points2=50,ball=0,autop=1) { veccy1=c(0,straty[stratno, points1+1, points2+1, ball+3,]) if (PROBUSE[stratno]==1) # Lineare Funktion veccy=veccy1 else # Wurzel-Methode (gewichtet große Werte geringer) veccy=apply(as.matrix(ceiling(veccy1+ 100*sqrt(veccy1)-100)),1,function(x) max(x,0)) if (autop==2) # Wenn dieses Flag gesetzt ist, wird der Vektor der Wahrscheinlichkeiten während der Abfrage gezeigt print(veccy) # print(round(veccy/sum(veccy),digits=3)) choice=ceiling(runif(1,min=0,max=sum(veccy))) # Zufallszahl zur Bestimmung des aktuellen Zuges vecu=veccy lvec=length(veccy) for (ii in 1:lvec) vecu[ii]=sum(veccy[1:ii]) sele=max((1:lvec)[vecuzz2) if (bx<=0) # Ball geht über das Netz in Feld 1 bz=1 else bz=bx+1 # Ball bleibt auf gleicher Seite, geht ein Feld weiter } else if (bx>=0) bz=-1 # Ball geht über das Netz in Feld 1 else bz=bx-1 # Ball bleibt auf gleicher Seite, geht ein Feld weiter } # # updatestrat - Aktualisiert die KI-Strategien abhängig vom Spielausgang (und der Vorgaben jeder KI) # updatestrat=function(stratnos,chain,win) { chainy=colSums(abs(chain)) # Nur positive Werte werden verändert, da dies die erlaubten Züge sind sele=max((1:length(chainy))[chainy>0]) for (kk in stratnos) # Alle gewählten Strategien werden aktualisiert { accel=(sele<=ACCELPOINTS1[kk])*ACCELPOINTS2[kk] # Eventuelle Acceleration-Punkte hinzuzählen pointy=(LEARNPOINTS[kk,abs(win)]+accel)*sign(win) LERNSPIELE[kk]<<-LERNSPIELE[kk]+1 # Aktualisierung der Anzahl der gewerteten Spiele for(ii in 1:sele) # Aktualisierungsschleife; nie Anzahl der minimalen Punkten unterschreiten { coly=chain[,ii] straty[kk,coly[1]+1,coly[2]+1, coly[3]+3, coly[4]+1] <<- max(c(straty[kk,coly[1]+1,coly[2]+1, coly[3]+3, coly[4]+1]+pointy, MINPOINTS[kk])) straty[kk,coly[2]+1,coly[1]+1, -coly[3]+3, coly[5]+1] <<- max(c(straty[kk,coly[2]+1,coly[1]+1, -coly[3]+3, coly[5]+1]-pointy, MINPOINTS[kk])) } } } ################################################## # Einzel-Spiel # * Welche KI-Strategien spielen gegeneinander (auch menschlicher Spieler kann sich KI als Gedankenstütze wählen # * Werden auch die anderen KI-Strategien in Bezug auf das Spielergebnis aktualisiert? # * Startpunktzahl und Startballort (speziell für Trainingszwecke) ################################################## spiel=function(stratno1=1,stratno2=2,auto=1,updatall=TRUE, Z1=MAXPERSPIEL,Z2=MAXPERSPIEL,B=0) { # Option "auto" # auto=1 ==> two automatic players # auto=2 ==> one automatic player, with automatic hint # auto=3 ==> one automatic player # # stratno1 - first player's strategy (or own help strategy) # - if set to 0, no help strategy at all # stratno2 - second player's strategy (or machine strategy) # - if set to 0, random choice of machine # # updatall - TRUE - alle Strategien lernen vom Spiel # - FALSE - nur beteiligte Strategien lernen # # Z1, Z2, B - Startwerte für Spiel # recordstatus=rep(0,5*MAXPERSPIEL) dim(recordstatus)<-c(5,MAXPERSPIEL) # records all stati - max number is MAXPERSPIEL as 1 point is always taken # Punkte1, Punkte2, Ball, Choice1, Choice2 # start timel=1 # Erster Zug # Spielschleife while ((Z1>0 || Z2>0) && abs(B)<3) # Ends when both players have no points or ball is out { zug1=askstrat(stratno=stratno1,points1=Z1,points2=Z2,ball=B,autop=auto) zug2=askstrat(stratno=stratno2,points1=Z2,points2=Z1,ball=-B,autop=auto) if (auto>1) # for interactive games { cat("STATUS: ","Your remaining points: ", Z1, "Other remaining points: ", Z2, "Ball at: ", B, "\n") # if (auto==2) # cat("Proposal: ",zug1,"\n") zug1=-1 # Abfrage der Korrektheit der Abfrage # * positive ganze Zahl, nur gleich 0 wenn keine Punkte mehr verfügbar # * Nicht mehr als verfügbare Punkte, und nicht mehr als 1+verfügbare Punkte des Gegners (Effizienz!) while ((zug1<0) || (zug1>min(Z1,Z2+1)) || ((zug1==0) && (Z1!=0)) || (zug1 != floor(zug1))) zug1=type.convert(readline("Your draw: ")) cat("Other draw",zug2,"\n") } recordstatus[,timel]=c(Z1,Z2,B,zug1,zug2) # print(recordstatus) Z1=Z1-zug1 Z2=Z2-zug2 B=ballplace(zug1,zug2,B) timel=timel+1 } # # Auswertung - Punktwertung # if (abs(B)==3) points=2*sign(B) else points=sign(B) # # Update der Strategien, Auswertung der Performance # jede bekommt Kette der Zustände und die Ergebnisse # GESPIELT[stratno1]<<-GESPIELT[stratno1]+1 GESPIELT[stratno2]<<-GESPIELT[stratno2]+1 if (B != 0) { if (updatall) updatestrat(stratnos=1:NUMBSTRAT,chain=recordstatus,win=B) else updatestrat(stratnos=c(stratno1,stratno2),chain=recordstatus,win=B) if (B>0) SIEGPOINTS[stratno1]<<-SIEGPOINTS[stratno1]+B else SIEGPOINTS[stratno2]<<-SIEGPOINTS[stratno2]-B } if (auto==1) return(points) else return(c("Punktewertung",points)) } # # end: spiel # ######################################################## ################################ # Training der KI-Strategien gegen sich selbst, auch als Turniermodus ################################ spielkette<-function(anzahl=100,update=TRUE,training=MAXPERSPIEL,strategien=(1:NUMBSTRAT)) { # anzahl - der Einzel-Spiele # # update - TRUE - alle Strategien lernen vom Spiel # - FALSE - nur am Spiel beteiligte Strategien lernen # # training - 0 - die Startzustände werden jedesmal zufällig neu gesetzt # - 6-(MAXPERSPIEL-6) - Spiel beginnt bei gewählter Zahl für S1 und leicht abweichender Zahl für S2 zufälliger Lage des Balls # - 1-5, (MAXPERSPIEL-6)-MAXPERSPIEL -Spiel beginnt bei gewählter Zahl für S1 und S2 und Ball in der Mitte # startr=c(GESPIELT,SIEGPOINTS,LERNSPIELE) # Status zu Beginn der Spielkette dim(startr)<-c(NUMBSTRAT,3) for (io in 1:anzahl) { strat1=strategien[ceiling(runif(1,min=0,max=length(strategien)))] # Wahl Strategie 1 strat2=strat1 # Dummy zu Schleifenstart while (strat2==strat1) # Zur Vermeidung des Spielens gegen sich selbst strat2=strategien[ceiling(runif(1,min=0,max=length(strategien)))] # Wahl Strategie 2 if (training==0) # Zufälliger Start { xx3=ceiling(runif(1,min=-3,max=2)) # Ballort if(xx3==0) { xx1=ceiling(runif(1,min=0,max=MAXPERSPIEL)) xx2=xx1 } else { xx1=ceiling(runif(1,min=0,max=MAXPERSPIEL-1)) xx2=ceiling(runif(1,min=0,max=MAXPERSPIEL-1)) } } else if(training<=5 || training>=MAXPERSPIEL-6) # Fester Start, Ball in der Mitte { xx1=max(min(training,MAXPERSPIEL),1) xx2=max(min(training,MAXPERSPIEL),1) xx3=0 } else # Variabler Start, Ball zufällig { xx3=ceiling(runif(1,min=-3,max=2)) # Ballort if(xx3==0) xx3=1 # Mitte in diesem Training nicht zulässig xx1=max(min(training,MAXPERSPIEL),1) xx2=xx1+ceiling(runif(1,min=-6,max=5)) # Spieler 2 mit +/-5 Punkten } # if((xx1-xx2)*xx3<0) cat(xx1," ",xx2," ",xx3,"\n") # Ausgabe, nur als Kontrolle spiel(stratno1=strat1,stratno2=strat2,auto=1,updatall=update, Z1=xx1,Z2=xx2,B=xx3) } endr=c(GESPIELT,SIEGPOINTS,LERNSPIELE) # Status am Ende der Spielkette diffy=endr-startr diffy[,3]=round(diffy[,2]/(diffy[,1]+.000001),3) print("Spiele, Punkte, Quote") print(diffy) } ################################################################################################# # Mögliche Aufrufe ################################################################################################# spiel(auto=3) # Spiel gegen Computer, KI-Strategie ist zufällig spiel(auto=2) # Spiel gegen Computer mit Ausgabe der Spielmatrix, KI-Strategie ist zufällig spiel(auto=3, stratno2=5) # Spiel gegen Computer mit Ausgabe der Spielmatrix, #5 ist die KI-Strategie spielkette(anzahl=1000,strategien=1:4,update=TRUE) # 1000 Spiele der Strategien #1-4 untereinander, die anderen Strategien lernen mit ######## # Beispiel: Situation von Tabelle 1 aus dem Wurzel-Artikel # startr=c(GESPIELT,SIEGPOINTS,LERNSPIELE) dim(startr)<-c(NUMBSTRAT,3) for (ii in 1:10000) { spiel(Z1=3,Z2=4,auto=1,B=2,stratno1=1,stratno2=2, updatall=FALSE) spiel(Z1=3,Z2=4,auto=1,B=2,stratno1=3,stratno2=4, updatall=FALSE) spiel(Z1=3,Z2=4,auto=1,B=2,stratno1=5,stratno2=8, updatall=FALSE) spiel(Z1=3,Z2=4,auto=1,B=2,stratno1=9,stratno2=12, updatall=FALSE) spiel(Z1=3,Z2=4,auto=1,B=2,stratno1=14,stratno2=16,updatall=FALSE) } endr=c(GESPIELT,SIEGPOINTS,LERNSPIELE) # Status am Ende der Spielkette diffy=endr-startr diffy[,3]=round(diffy[,2]/(diffy[,1]+.000001),3) print("Spiele, Punkte, Quote") diffy # # Spezialtraining 1: jeweils x*100 Spiele mit aufsteigender Punktanzahl # for (ii in 5:MAXPERSPIEL) { cat(ii," ") spielkette(anzahl=ii*100,training=ii) } # Turnier spielkette(anzahl=10000) # 4 best against each other: 16, 14, 12, 8 spielkette(anzahl=1000,strategien=c(8,12) ,update=FALSE) spielkette(anzahl=1000,strategien=c(14,16),update=FALSE) spielkette(anzahl=1000,strategien=c(8,14) ,update=FALSE) spielkette(anzahl=1000,strategien=c(12,16),update=FALSE) spielkette(anzahl=1000,strategien=c(8,16) ,update=FALSE) spielkette(anzahl=1000,strategien=c(12,14),update=FALSE) ################# # Sichern des Workspaces #save.image("X:\\xxxxxxxxxxx\\tennis.RData") # to clean up workspace if KI knowlegde not used #rm(ACCELPOINTS1,ACCELPOINTS2,askstrat,ballplace,defstrat,erstinit,ii, #GESPIELT,INPOINT,LEARNPOINTS,LERNSPIELE,MAXPERSPIEL,MINPOINTS,NUMBSTRAT, #PROBUSE,SIEGPOINTS,spiel,spielkette,updatestrat,straty) ########