Die Idee ist einfach. Ein Computer spielt gegen dich Mühle. Auf dem Tisch liegt das Spielbrett vom Spiel Mühle. Der menschliche Spieler bewegt die Spielsteine per Hand, wobei die Künstliche Intelligenz von oben das Spielbrett beobachtet und seine Anweisungen für die Spielzüge auf dem Display anzeigt. Natürlich soll der Computer nicht leicht zu besiegen sein.
Open CV http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_tutorials.html
Spielidee (zunächst Mini-Mühle, dann Mühle) http://brettspiele.onlinespiele1.com/onlinespiele1_brettspiele_3.htm
Camera Calibration: http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_calib3d/py_calibration/py_calibration.html#calibration
1. Bildinput verarbeiten
2. Spiel programmieren
3. Dem Computer das Spiel beibringen (KI erstellen)
4. Schnittstellen finden und zusammenfügen
Die Schnitstelle zwischen Python und der Kamera haben wir mit dem Packet „OpenCV“ für Python gefüllt. Das Packet ermöglicht es Bilder von allen angeschlossenen und internen Kameras aufzunehmen, zu betrachten, zu speichern und weiterzuverarbeiten.
Das Packet wird importiert mit import cv2
spielbrett =
Ein Bild Aufnehmen: cv2.VideoCapture(#Kamera)
Die Zählung der Kameras beginnt bei 0 wobei dies meistens die interne Kamera anspricht.
Das aufgenommene Bild wird in eine Variable gelsen:
bild = cv2.VideoCapture(#Kamera).read()
Die variable „bild“ ist ein Tupel, die erste information ist „True“ und die zweite enthällt ein Array mit den Pixeldaten von dem Foto.
Das Bild wird folgendermaßen angezeigt:
cv2.imshow("Anzeige",bild[1]) cv2.waitKey(0)
waitkey ist dafür da, dass gewartet wird, während das Bild angezeigt wird.
Ein Bild Speichern:
cv2.imwrite("Dateiname.png", bild[1])
In Graustufen ändern:
cv2.cvtColor(bild[1], cv2.COLOR_BGR2GRAY)
Damit der Computer auch etwas mit dem Bild anfangen kann muss es auf bestimmte Charakteristiker Untersucht werden. Wir haben uns entschieden zunächst die Ecken des Mühle Spielbretts ohne Spielfiguren finden zu lassen, damit es möglich ist ein GRundgerüst zu erstellen, also zu wissen wo die Felder sind.
Dazu verwenden wir Eine Funktion von Open CV: Harris Corner DEtection. corner Harris()
.
Hinter dieser Funktion steht ein Mathematischer Algorythmus, welche einzelne Regionen (Die größen kann man vorgeben) auf Unterschiede in der Helligkeit. Diese Werden in einem Tupel (u,v)Dargestellt, der folgendermaßen berechnet wird:
Um Ecken aufzuspühren muss diese Fuktion maximiert werden. Die Maximierte Fuktion sieht ungefähr so aus:
wobei
Nun weden die Eigenwerte von M, λ_1 und λ_2 berechnet. Mithilfe dieser Werte kann nun bestimmt werden in welchem Bereich eines Bildausschnitts sich Ecken befinden und wo nicht. Folgende Grafik veranschaulicht dies:
Wir haben in unser Bild von dem Mühlespielbrett einmal alle gefundenen Ecken mit grünen Pixeln eingezeichnet:
Dies ist ein großer Erfolg, denn jetzt ist deutlich wo sich die Felder befinden und somit wo eine Spielfigur sein kann.
Die Beleuchtung des Spielbretts erschien uns eine Wichtige Komponente der Bilderkennung, also haben wir verschiedene Belichtungswinkel ausprobiert, um dann festzustellen, dass es nur einen sehr kleinen unterschied macht, wenn man das Brett separat belichtet oder mit der Raumbeleuchtung erhellt. Wichtig ist nur überhapt licht zu haben, so dass nicht zu hohe Kontraste entstehen, die als Ecken gedeutet werden könnten. Die beleuchtung spielte eine größerer Rolle, als wir dasa Bild von dem Brett, zur besseren Ecken Findung über den Schwellwert komplett auf Schwarz oder Weiß gebracht haben. Allerdings hat sich herrausgestellt, dass es besser ist wenn man das Bild in Graustufen betrachtet, um eben diesen Faktor der Beleuchtung auszuklammern.
Da uns einiges Grundwissen aus der Linearen Algebra fehlt unterbrechen wir hier und fahren fort mit dem zweiten Teil des Projekts. Hier offen geblieben sind folgende Fragen:
Um es ersteinmal für die Kamera und die Rechenkraft des Computers einfach zu halten, entschieden wir uns für die kleine Version der Mühle mit nur 16 Feldern. Dies Musste jetzt samt Spielbrett und Spielregeln virtuell erzeugt werden. Hierbei ist es wichtig in kleinen Arbeitsschritten vorzugehen und nicht alles auf einmal programieren zu wollen, weil man sich dann zu sehr verzettelt, man sollte allerdings das Ziel im Auge behalten.
Das Spielbrett ist aufgebaut als Array. Jede Liste im Array steht für eine Zeile auf dem Spielbrett und jeder Listeneintrag in dem 'W','S' oder 'x' steht für ein Spielfeld. Die stellen an denen kein Spielfeld ist, sind mit „-“ oder „|“ gekennzeichnet, diese werden nie verändert. Zur verdeutlichung habe ich das bild einer tabelarischen Darstellung des Mühlebretts mit der selben Spielkonstelation wie im Array hinzugefügt.
[['W','-','S','-','W'], ['|','S','W','x','|'], ['S','S',' ','x','x'], ['|','W','x','x','|'], ['S','-','W','-','x']]
Wir haben uns auch alternative Formen des Spielbretts ausgedacht, doch die zuerst genannt stellte sich als am praktisten harraus. Da Das ganze folgende Programm auf dieser Struktur basiert ist es auch nicht einfach diese wieder zu ändern. Alternative Idden waren folgende:
[['A1',' ','A3','00','A5'], ['00','B2','B3','B4','00'], ['C1','C2','00','C3','C4'], ['00','D2','D3','D4','00'], ['E1','00','E3','00','E5']] [[(0,0),'---',(0,2),'---',(0,4)], [' | ',(1,1),(1,2),(1,3),' | '], [(2,0),(2,1),' ',(2,3),(2,4)], [' | ',(3,1),(3,2),(3,3),' | '], [(4,0),'---',(4,2),'---',(4,4)]]
Damit nicht immer ein Array mit viele Klammern und Anführungszeichen zu sehen ist, wenn wir uns das Spielbrett anschauen wollen, gibt es die Funktion zeig_brett
, die folgende Ausgabe liefert
def zeige_brett(brett): for i in brett: print " ".join(i)
W - S - W | S W x | S S x x | W x x | S - W - x
def neues_spiel(brett): for x in range(0,5): for y in range(0,5): if brett[x][y] == 'W': brett[x][y] = 'x' elif brett[x][y] == 'S': brett[x][y] = 'x'
Da aus der Spielbrettstruktur kein eindeutiges Schema für erlaubte Züge hervorgeht, muss dies per HAnd eingetrag werden. Die Ideale DAtenstruktur hierfür ist ein Wörterbuch, denn es ordnet einem Feld mehrere andere Felder zu, auf die man von dem ersten Feld aus ziehen kann, falls es frei ist. Dieses Wörterbuch wird später für die findung eines Zugs wichtig werden.
{ (0,0):[(0,2),(2,0) ], (0,2):[(0,0),(1,2),(0,4)], (0,4):[(0,2),(2,4) ], (1,1):[(2,1),(1,2) ], (1,2):[(1,1),(0,2),(1,3)], (1,3):[(2,3),(1,2) ], (2,0):[(0,0),(2,1),(4,0)], (2,1):[(2,0),(3,1),(1,1)], (2,3):[(2,4),(1,3),(3,3)], (2,4):[(0,4),(2,3),(4,4)], (3,1):[(2,1),(3,2) ], (3,2):[(3,1),(4,2),(3,3)], (3,3):[(3,2),(2,3) ], (4,0):[(2,0),(4,2) ], (4,2):[(4,0),(3,2),(4,4)], (4,4):[(4,2),(2,4) ]
} def alle_zuege(farbe, brett):
'''gibt eine Liste für alle möglichen Züge einer Farbe aus''' startpunkte = [] l =[] wb = {} for i in felder_liste(brett, farbe): if ein_zug(i, brett) != False: wb.update(ein_zug(i, brett)) return wb
Eine Mühle entsteht genau dann wenn ein Spieler drei Steine seiner Farbe in einer Reihe hat, dafür gibt es in unserem Spielbrett genau 8 verschiedene Möglichkeiten, welche alle in diesem Array festgehalten sind. Hiermit kann überprüft werden ob eine Mühle vorliegt, das tut die untern stehende Funktion pruefe_muele
. Diese Funktion greift auf das Array muehlen
zu um eine Liste aller Mühlen zu erzeugen die aktuell im Spiel sind.
[[(0,0),(0,2),(0,4)], [(0,0),(2,0),(4,0)], [(0,4),(2,4),(4,4)], [(1,1),(1,2),(1,3)], [(1,1),(2,1),(3,1)], [(1,3),(2,3),(3,3)], [(3,1),(3,2),(3,3)], [(4,0),(4,2),(4,4)]] def pruefe_muehle(farbe, brett): '''gibt die muehlen auf dem aktuellen Feld in einer liste aus''' l=[] for situation in muehlen: feld1 = brett[situation[0][0]][situation[0][1]] feld2 = brett[situation[1][0]][situation[1][1]] feld3 = brett[situation[2][0]][situation[2][1]] if feld1 == feld3 and feld3 == feld2 and feld1 != 'x': l.append(situation) return l
Diese Funktion kann einem sagen auf welchen Feldern gerade schwarze, weiße oder gar keine Figuren sind, dafür muss man für das z ein w, s oder 'x' einsetzen, sofern diese vorher definiert wurden.
def felder_liste(brett, z): ''' gibt eine liste mit allen Spielfeldern in denen z steht''' l=[] for x in range(0,5): for y in range(0,5): if brett[x][y] == z: l.append((x,y)) return l
Die zweite Funktion verät einem den tatsächlichen Spielstand in zahlen, d. h. wie viele Steine einer Farbe sich momentanx auf dem Brett befinden.
def spielstand(farbe, brett):
''' gibt die anzahl von weißen und schwarzen Figuren auf dem spielbrett aus''' k=0 for n in brett: k += n.count(farbe) return k
def wer_ist_am_zug(n, erste_farbe): if (n-1)%2 == 0: return erste_farbe else: if erste_farbe == w: return s else: return w
def move_to(start, ziel, farbe, brett): '''bewege einen Spielstein auf ein benachbartes Feld''' brett[start[0]][start[1]]='x' brett[ziel[0]][ziel[1]] = farbe
def ein_zug(position, brett): '''gibt eine Wörterbuch mit allen tatsächlich möglichen Zügen eines steins von einer bestimmten Position aus''' wb = {} l= [] for i in moegliche_zuege[position]: if i in felder_liste(brett, 'x'): l.append(i) wb[position] = (l) if len(wb) != 0: return wb else: return False
def stein_wegnehmen(farbe, brett): '''gibt eine liste mit allen steinen die nach einem zug weggenommen werden können''' l=[] for i in moegliche_zuege: if brett[i[0]][i[1]] != farbe and brett[i[0]][i[1]] != 'x': if i not in sum(pruefe_muehle(farbe, brett),[]): l.append(i) return l
def ziehen(brett, farbe): '''sucht den besten Zug für eine der farben und führt ihn aus''' if len(alle_zuege(farbe, brett)) == 0: print str(farbe)+' hat verloren' else: start= random.choice(alle_zuege(farbe, brett).keys()) ziel = random.choice(alle_zuege(farbe, brett)[start]) move_to(start, ziel, farbe, brett)
def wegnehmen(vor_zug, nach_zug, brett, am_zug): if vor_zug != nach_zug and len(nach_zug)>= len(vor_zug): stein = random.choice(stein_wegnehmen(am_zug, brett)) brett[stein[0]][stein[1]] = 'x' print str(am_zug) +' hat einen Stein weggenommen'
def spielende(brett): '''Der Gewinner wird zurückgegeben''' if len(alle_zuege(w, brett)) == 0 or spielstand(w, brett) <= 2: return s if len(alle_zuege(s, brett)) == 0 or spielstand(s, brett) <= 2: return w
Steine setzen
def steine_setzen(farbe, brett): neues_spiel(brett) n=0 while n<=11: n= n+1 am_zug = wer_ist_am_zug(n, farbe) vor_zug = pruefe_muehle(am_zug, brett) feld = random.choice(felder_liste(brett, 'x')) brett[feld[0]][feld[1]] = am_zug nach_zug = pruefe_muehle(am_zug,brett) print str(am_zug)+' setzt:' zeige_brett(brett) print'_________________' if wegnehmen(vor_zug, nach_zug, brett, am_zug) == True: zeige_brett(brett) print '__________'
n=0 print 'Setzen:' steine_setzen(w,spielbrett) print 'Spielstart:'
while True: if n == 0: zeige_brett(spielbrett) n=n+1 am_zug = wer_ist_am_zug(n,w) print '____________________' print str(am_zug) +' zieht:' vor_zug = pruefe_muehle(am_zug, spielbrett) ziehen(spielbrett, am_zug) nach_zug = pruefe_muehle(am_zug,spielbrett) wegnehmen(vor_zug, nach_zug, spielbrett, am_zug) zeige_brett(spielbrett) if spielende(spielbrett) != None: print 'spiel ist vorbei' print n break