Mathesis Wiki

• Installation des opencv Pakets für linux und windows-Betriebssysteme
• Funktionalität der Kamera mithilfe von Treibern testen
• Erfassung eines Bildes auf dem Rechner mittles Python
• Erstellung einer TUB-Cloud

Die Kamera könnte beim Erfassen von farbigen Spielfeldern Probleme aufweisen, da sie die Farbsättigung reduziert Im Vordergrund zu sehen ist die Original-Flasche, während auf dem Bildschirm die blassere Version vorzufinden ist, welche doch eher der Medium-Wasserflasche daneben ähnelt.

• Stativ optimal für unsere Kamera ausgerichtet
• Spiel „Mini-Mühle“ als Versuchsobjekt ausgewählt
• Gewinnmöglichkeiten des Spiels auf Papier ausgewertet
• Einstieg in die Programmierung mit OpenCV z.B ein Bild in Graustufen anzeigen

import cv2

#bild aufnehmen
c = cv2.VideoCapture(1)
x=c.read()
#bild anzeigen
win=cv2.namedWindow("Anzeige")
cv2.imshow("Anzeige",x[1])
cv2.waitKey(0) #damit gewartet wird, waerend das Bild angezeigt wird

Ziel bis nächste Woche:

• Mühle Spielen lernen (Spielsystematik verstehen)
• Open CV tutorial durcharbeiteny

Heute haben wir am Programmcode gearbeitet, sodass der Computer unser Bild in Graustufen, sowie Schwarz-Weiß, direkt von der Kamera wiedergibt. Mit der Harris Corner Detection aus OpenCV ist es uns außerdem gelungen sowohl maßgeschneiderte Beispielbilder eines Mühle-Spielbretts von Google, als auch unser selbsterstelltes Spielfeld erkennen zu lassen.

Die gefundenen schnittpunkte sind blau markiert

Finden von Schnittpunkten

import cv2
import numpy as np
from matplotlib import pyplot as plt
img= cv2.VideoCapture(1)
x=img.read()
farbbild = x[1]
graubild = cv2.cvtColor(farbbild, cv2.COLOR_BGR2GRAY)
graubild = np.float32(graubild)
dst = cv2.cornerHarris(graubild,2,3,0.04)
result is dilated for marking the corners, not important
dst = cv2.dilate(dst,None)
#Threshold for an optimal value, it may vary depending on the image.
farbbild[dst>0.01*dst.max()]=[255,0,0]
cv2.imshow('dst',farbbild)
if cv2.waitKey(0) & 0xff == 27:
    cv2.destroyAllWindows()
  

Berechnung vom Schwellwertbild:

  bild =x[1]
  ret,th1 = cv2.threshold(bild,127,255,cv2.THRESH_BINARY)
  th2 = cv2.adaptiveThreshold(bild,255,cv2.ADAPTIVE_THRESH_MEAN_C,\
               cv2.THRESH_BINARY,11,2)
  th3 = cv2.adaptiveThreshold(bild,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,\
             cv2.THRESH_BINARY,11,2)
  titles = ['Original Image', 'Global Thresholding (v = 127)',
  #'Adaptive Mean Thresholding', 'Adaptive Gaussian Thresholding']
  images = [bild, th1, th2, th3]
  for i in xrange(4):
    plt.subplot(2,2,i+1),plt.imshow(images[i],'gray')
    plt.title(titles[i])
    plt.xticks([]),plt.yticks([])
  plt.show()

Zunächst haben wir das Spielbrett modifiziert, dass kein Kreis an Punkten mehr pro Ecke erkannt wird, sondern bestenfalls nur noch ein Punkt pro Ecke. Dazu haben wir auch eine USB-LED-Lampe verwendet, um den Einfluss von Licht und Schatten zu minimieren. Nebenbei gab es von Stefan einen kleinen Exkurs in die Mathematik, welche hinter der Harris-Corner Detection steckt. Auch eine Erklärung zur Homography in OpenCV war beinhaltet, da wir diese für später benötigen.

Nun gilt es die einzelnen Punkte (Pixel), welche wir auf einem Beispielbild ausgegeben bekommen (welches wir seit heute auch speichern können und wissen, wo es gespeichert wird), mit von uns ausgewählten Koordinaten zu verbinden. Diese haben wir in eine Liste gepackt:

  
  mini_muele_punkte = [(0,0),(6,0),(12.25,0),(24.5,0),
		(0,6),(6,6),(12.25,6),(24.5,6),
		(0,12.25),(6,12.25),(12.25,12.25),(24.5,12.25),
		(0,24.5),(6,24.5),(12.25,24.5),(24.5,24.5)]

Allerdings gibt es gegenüber unserer 16 Punkte 480 computergenerierte, welche alle sehr nahe aneinander liegen, wie man an dieser Ausgabe sehen kann:

 [[  13.79937553   13.79937553   13.79937553 ...,   -0.39828128
  -0.39828128   -0.39828128]
[  13.79937553   13.79937553   13.79937553 ...,  138.36488342
 138.36488342   35.59000015]
[  13.79937553   13.79937553   13.79937553 ...,  138.36488342
 138.36488342   35.59000015]
  ..., 
[   5.81878948    5.81878948   24.76422119 ...,   11.91031265
  11.91031265    4.71875   ]
[   6.44175768    7.93257809   24.76422119 ...,   18.23632812
  18.23632812   10.52464867]
[   6.44175768    7.93257809    7.93257809 ...,   18.23632812
  18.23632812   10.52464867]]

Somit müssen für das nächste Mal 16 von den 480 Punkten behalten und der Rest entweder rausgeworfen oder ignoriert werden, damit der Computer spezifische Positionen hat, auf die er sich beziehen kann.

  punkte=[]
  b,h=dst.shape
  maximum=dst.max()
  for j in range(0,h):
   for i in range(0,b):
	if dst[i,j]>0.01*maximum:
		punkte.append([i,j])
  #graubild[dst>0.01*dst.max()]=2
  #print graubild
  print punkte
  print len(punkte)
  

Größtenteils diente der Arbeitstag zunächst zur Organisation des weiteren Verlaufs des Projekts, sodass die Arbeit noch rechtzeitig beendet werden kann.

Danach entschieden wir in der Gruppe, die Arbeit an der Bilderkennung vorerst ruhen zu lassen, um ein funktionierendes Spiel auf die Beine zu stellen. Dabei verwenden wir die Regeln und den groben Ablauf, der hier zusammengefasst wurde: http://www.info-wsf.de/index.php/M%C3%BChle

Zur Ordnung des Spielfeldes und der Sortierung der Gewinnmöglichkeiten und Spielzüge, war viel Schreibarbeit via Stift und Zettel nötig. Diese Prinzipien haben wir nun versucht, in Programmcode zu übersetzen:

 
 
  spielbrett_01 =[['A1','  ','A3','00','A5'],
		 ['00','B2','B3','B4','00'],
		 ['C1','C2','00','C3','C4'],
		 ['00','D2','D3','D4','00'],
		 ['E1','00','E3','00','E5']]
  spielbrett =[['W','-','x','-','S'],
		 ['|','x','x','S','|'],
		 ['W','S',' ','x','S'],
		 ['|','W','S','W','|'],
		 ['W','-','S','-','S']]
 # x:= echtes feld
 #0 := kein Feld

 muehlen =			[[(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)]]

 spielbrett[muehlen[0][0][0]][muehlen[0][0][1]]='W'

 def zeige_brett(spiel):
for i in spiel:
	print " ".join(i)
	
 def pruefe_gewinnpos(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

 def leere_felder(brett):
''' gibt eine liste mit allen leeren Spielfeldern'''
l=[]
for x in range(0,5):
	for y in range(0,5):
		if brett[x][y] == 'x':
			l.append((x,y))
return l

 def spielstand(brett):
''' gibt die anzahl von weißen und schwarzen Figuren auf dem spielbrett aus'''
weiss=0
schwarz=0
for n in brett:
	weiss += n.count('W')
	schwarz +=n.count('S')
print 'weiss: ' +str(weiss)
print 'schwarz: '+str(schwarz)

Heute habe ich (Lea) alleine am Projekt weitergearbeiet. Ich habe mich auf die Vertiefung der Spielfunktion konzentriert. Folgende Funktion beispielsweise schaut nach zu welchem freien feld ein bestimmter Stein einen Zug machen kann:

  def ein_zug(position, brett):
'''gibt eine Liste mit allen tatsächlich möglichen Zügen eines steins von einer bestimmten position aus'''
l = []
for i in moegliche_zuege[position]:
	if i in felder_liste(brett, 'x'):
		#print i
		l.append(i)
if len(l) != 0:
	return l
else:
	return False

Mithilfe dieser Funktion kann man für eine Farbe alle Felder finden zu denen man ziehen kann:

  def alle_zuege(farbe, brett):
'''gibt eine Liste für alle möglichen Züge einer Farbe aus'''
l =[]
for i in felder_liste(brett, farbe):
	l.append(ein_zug(i, brett))
l =[i  for i in l if i != False]
l=sum(l,[])
return l

Mit dieser Information kann man Beispielsweise prüfen ob eine Mühle vorliegen würde wenn der Zug ausgeführt wird. Der nächste Schritt wird sein Züge zu simulieren und durchführen zu lassen. Beim durchführen von Zügen wird die Funktion move_to helfen, welche auch zur erstellung von prorgnosen hilfreich wird.

  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]] = str(farbe)

Als nächstes sollen berechnungen über mehrere Spielzüge angestellt werden um herrauszufinden welcher Zug zu einem Gewinn führen kann.

Wir haben uns dazu entschieden, nächste Woche im Wissenschaftsfenster einen 10-minütigen Vortrag über unser Projekt zu halten. Deshalb entwarfen wir eine grobe Gliederung, um über das Wochenende daran zu arbeiten. Außerdem einigten wir uns auf eine PowerPoint-Präsentation.

Zudem haben wir den Programmcode von letzter Woche, in welchem das Spiel schon mit je 3 Spielfiguren komplett von selbst gespielt wird (allerdings noch ohne KI), so bearbeitet, dass auch die Spieler S (schwarz) & W (weiß) nacheinander auf ein leeres Spielbrett ihre 6 Steine legen und danach das Hauptspiel beginnt. Hier der Code:

  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 '__________'

Nachdem wir unseren Vortrag am Montag beim Wissenschaftsfenster hinter uns gelassen haben, konzentrierten wir uns darauf, das zu vervollständigen, was wir am Ende der Präsentation versprochen haben, nämlich die KI.

Um zunächst einmal alle günstigen Situationen zu erhalten, welche den Sieg bringen oder zum sicheren Sieg führen würden, mussten wir unser Spielfeld von einer Tabelle aus Arrays in einen String umwandeln und wieder umgekehrt.

Von der Tabelle zum String:

  def tabelle_to_string(brett):
    t= ''
    for x in range(0,5):
	    for y in range(0,5):
		    if brett[x][y] == 'W' or brett[x][y] == 'S' or brett[x][y] == 'x':
			    t = t + brett[x][y]
    return t
			
  print tabelle_to_string(spielbrett)
  #WSWSWxSSxxWxxSWx
  

Vom String zur Tabelle:

  def string_to_tabelle(string):
b =[]
while len(string) != 0:
	a=[]
	for i in range(0,5):
		a.append(string[i])	
	string = string[5:]
	b.append(a)
return b

Danach musste Dominic leider aus privaten Gründen gehen und Lea arbeitete alleine an der KI weiter. In dem folgenden Programmabschnitt wurde versucht, alle Möglichkeiten in einem Wörterbuch abzulegen. Dies ist dann mithilfe von Listen ermöglicht worden, wobei erstmal alle erreichbaren Positionen auf dem Spielfeld erzeugt werden, was ungefähr 3^16 ist. Um diesen Programmcode vielleicht noch zu optimieren, wird noch die Dauer des Rechenprozesses ausgegeben, welche ca. 4 Minuten beträgt:

  wb ={

  }

  def ALLE_positionen():
    m = (0,1,2)
    alles= [(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15,i16) 
      for i1 in m
      for i2 in m
      for i3 in m
      for i4 in m
      for i5 in m
      for i6 in m
      for i7 in m
      for i8 in m
      for i9 in m
      for i10 in m
      for i11 in m
      for i12 in m
      for i13 in m
      for i14 in m
      for i15 in m
      for i16 in m]
    print(len(alles))
    return alles

  def test1():
    [i for i in range(43000000)]

  def test():
    m = (0,1,2)
    alles= [(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10) 
      for i1 in m
      for i2 in m
      for i3 in m
      for i4 in m
      for i5 in m
      for i6 in m
      for i7 in m
      for i8 in m
      for i9 in m
      for i10 in m]
    print(len(alles))
    return alles

  def situationen(liste):
    if liste.count(2) <=6 and liste.count(1)<= 6 and liste.count(1) >2 and liste.count(2) > 2:
	    wb[liste] = 0
    if liste.count(2) >= 3 and liste.count(1) == 2:
	    wb[liste]= 1
    if liste.count(1) >= 3 and liste.count(2) == 2:
	    wb[liste] = -1

  l = ALLE_positionen()
  start= time.time()
  while len(l) != 0:
  	    situationen(l[0])
    del l[0]

  end = time.time()
  dauer = end - start
  print "Dauer:", dauer

  # 1 Weiß gewinnt
  # -1 Schwarz gewinnt
  # 0 unentschieden \ noch nicht bekannt

  #1 schwarz
  # 2 weiß
  start = time.time()
  with open("bsp.pickle","w") as f:
    p=cpickle.Pickler(f)
    p.dump(wb)
  end = time.time()
  dauer =end - start
  print 'Dauer:', dauer

  start = time.time()
  with open("bsp.pickle", "r") as f:
    u=cpickle.Unpickler(f)
    wb2 = u.load()
  end = time.time()
  dauer =end - start
  print 'Dauer:', dauer

Heute, am ersten der drei Projekttage, ist Lea leider erkrankt, weshalb Dominic alleine versucht, an der KI und dem Spiel weiterzuarbeiten. Als erstes wurde die Dokumentation mit dem Protokoll für Tag 11 vervollständigt, wobei die Arbeitsschritte vom letzten Mal zunächst revidiert werden mussten. Leider beherrsche ich Programmiersprachen trotz alledem leider so gut wie gar nicht und deshalb habe ich mich, neben ein wenig angeeignetem Verständnis für das Programm, mit einer Konsolen-Ausgabe für das Spiel beschäftigt, damit nicht mehr der Computer gegen sich selbst spielt, sondern auch ein Individuum während des Spiels eingreifen kann.

Hier die kleine Überlegung in gedankenhaften Quellcode gebracht (ACHTUNG, vermutlich komplett falsch, noch ungetestet):

Als Ausblick für den morgigen Tag hoffe ich, dass Lea wieder mit an Bord ist, um mehr und besser als heute voranzukommen, da die Arbeit mit mir alleine leider stagniert und ich auch kaum gezielte Fragen stellen kann, da ich mich während des Semesters zu wenig mit dem Lernen von Python beschäftigt habe.

Da der programmierende Kopf der Gruppe (Lea) leider immer noch fehlt und die Zeit aufgrund der Vorträge, sowie aus privaten Gründen, etwas knapp wurde, ist das Projekt nicht vorangekommen. Es wurde sich mit dem Verstehen von Pickle, welches zur Weiterarbeit benötigt wird, beschäftigt, was letztendlich jedoch nicht geglückt ist.

Dies ist der letzte Projektwochentag und somit auch die letzte Möglichkeit, in diesem Semester noch an dem Projekt weiterzuarbeiten. Damit wenigstens an etwas gearbeitet wird, habe ich mich erneut mit dem beschäftigt, was unser Porgramm alles benötigt, um zu funktionieren.

Da alle Positionen, die einen Zug vor einer Gewinnposition stehen, relativ simpel zu codieren waren, habe ich mir dieses vorgenommen:

gewinnpos =             [[(0,0),(0,2),(2,4)],
			[(0,0),(0,4),(1,2)],
			[(0,2),(0,4),(2,0)], #Block1Ende
			[(0,0),(2,0),(4,2)],
			[(0,0),(4,0),(2,1)],
			[(2,0),(4,0),(0,2)], #Block2Ende
			[(1,1),(2,1),(3,2)],
			[(1,1),(3,1),(2,0)],
			[(2,1),(3,1),(1,2)], #Block3Ende
			[(1,1),(1,2),(2,3)],
			[(1,1),(1,3),(0,2)],
			[(1,2),(1,3),(2,1)], #Block4Ende
			[(1,3),(2,3),(3,2)],
			[(1,3),(3,3),(2,4)],
			[(2,3),(3,3),(1,2)], #Block5Ende
			[(3,1),(3,2),(2,3)],
			[(3,1),(3,3),(4,2)],
			[(3,2),(3,3),(2,1)], #Block6Ende
			[(0,4),(2,4),(4,2)],
			[(0,4),(4,4),(2,3)],
			[(2,4),(4,4),(0,2)], #Block7Ende
			[(4,0),(4,2),(2,4)],
			[(4,0),(4,4),(3,2)],
			[(4,2),(4,4),(2,0)]] #Block8Ende
			
#gewinnpos beschreibt alle Möglichkeiten, die einen Zug vor einer Mühle stehen.
#Ausgeschlossen sind natürlich jene Züge, bei welchen ein gegnerischer Stein im Weg steht.
#z.B. wenn schwarz Steine bei [(0,0),(0,2),(2,4)] hat und weiß (0,4) dazwischen besetzt.

Die Beschreibung setzt voraus, dass man weiß, wie das Spielfeld aufgebaut ist. Deshalb hier die Mitschrift zum Prozess:

Da der Code auch schon für die Ansammlung an Möglichkeiten eine Mühle zu erzielen funktioniert hat, könnte er theoretisch auch für die Gewinnpositionen korrekt sein, was ich zwar bezweifle, aber vielleicht klappt er.

'''def pruefe_gewinnpos(farbe, brett):
	u=[]
	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':
			u.append(situation)
	return u'''

In der TUBcloud wurde eine Mühle Version für C++ und eine für Java hochgeladen. Diese dient zur Hilfe und Orientierung, wenn man nicht weiter weiß.