Die Härte ist in diesem Fall ein Begriff aus der theoretischen Informatik, wobei das Wort eigentlich eine falsche Übersetzung des englischen Wortes "hard" ist, was ja eher "schwierig" bedeutet. Deswegen ist "schwierig" innerhalb der theoretischen Informatik tatsächlich ein Synonym für hart. Ein Problem ist hart, wenn es zu den "schwierigesten" Problemen einer Komplexitätsklasse gehört, also wenn sich alle Probleme der Klasse auf dieses eine Problem reduzieren lassen. Im Prinzip heißt PSPACE-hart also, dass das Problem nicht nur in PSPACE liegt, sondern zu den komplexesten Problemen von PSPACE gehört.

Was genau macht denn die Spieleanalyse von Scrabble3D? Berechnet sie ähnlich wie ein Schachcomputer welche Züge sinnvoll sind, um von der gegebenen Situation aus zu gewinnen? Dann könnte man das sicher irgendwie (ich bin mir aber nicht sicher wie ^^) in Beziehung stellen, aber selbst dann gilt natürlich immer noch, dass das Scrabble in meiner Arbeit sich von dem Brettspiel-Scrabble unterscheidet.

Der RAM-Speicher direkt ist nicht gemeint, aber es geht in die Richtung. Für die Komplexitätsanalyse werden in der Informatik sogenannte Turing-Maschinen verwendet. Das sind sehr sehr simple, theoretische Computer, die als Speicher ein oder mehrere Bänder mit Symbolen benutzen. Der bei einer Berechnung verwendete Platz ist dann die Anzahl der benötigten Felder auf dem Band, wobei ein Feld immer ein Symbol beinhalten kann und Felder natürlich überschrieben werden können. Warum benutzt man solche theoretischen Maschinen und nicht richtige Rechner? Unter anderem, weil sich Turing-Maschinen durch ihren einfach Aufbau sehr gut vergleichen lassen.

Hallo an alle hier im Forum! Ich bin der Autor der oben genannten Bachelorarbeit. Bussinchen hat mich per Mail angeschrieben und ich dachte, ich gucke mal vorbei und versuche ein wenig zu erklären, worum es in meiner Arbeit geht und was das Ergebnis ist :)

Erstmal freue ich mich natürlich, dass ihr Interesse an meiner Arbeit habt. Das ist ja gerade bei einer Bachelorarbeit nicht selbstverständlich. Die Idee für die Arbeit kam von einem wissenschaftlichen Mitarbeiter des Instituts für Theoretische Informatik hier in Hannover. Vorweg will ich auf jeden Fall nochmal klar stellen, dass die Methoden und Ergebnisse der Arbeit nicht von mir stammen, sondern aus dem erwähnten Artikel von Lampis und co (finde ich online gerade leider nicht). Der Artikel ist einer von vielen Artikeln zum Thema Spiele-Komplexität. Zur Spiele-Komplexität gibt es auch einen wikipedia-Artikel: http://de.wikipedia.org/wiki/Spiel-Komplexit%C3%A4t , dort findet ihr weiter unten eine Liste mit einigen untersuchten Spielen und den zugeordneten Komplexitätsklassen.

Um zu verstehen, was die Einordnung in eine Komplexitätsklasse bedeutet, muss man erstmal wissen, was Komplexität im Sinne der Informatik bedeutet. Mal angenommen ihr habt ein Programm, das eine Zahl bekommt und damit etwas berechnet, dann ist es ja ganz nützlich zu wissen, inwiefern die Länge der Eingabe die Rechenzeit oder den Speicherplatz des Programms beeinflusst. ZB rechnet ein Taschenrechner bei bestimmen Operationen mit großen Zahlen ja länger als mit kleinen Zahlen. Wenn der Rechner unabhängig von der Eingabe immer die gleiche Zeit benötigt, ist die Rechnenzeit konstant. Wenn das nicht der Fall ist, dann gibt es ein Wachstum, das ihr wahrscheinlich aus dem Mathe-Unterricht kennt. Man unterscheidet unter anderem zwischen linearem, polynomiellem und exponentiellem Wachstum. Lineare Zeitkomplexität bedeutet, dass wenn ich die Länge der Eingabe verdopple, das Programm dann auch ungefär doppelt so lange braucht. Polynomiell ist schlechter und exponentiell sehr viel schlechter.

Eine Komplexitätsklasse ist nichts anderes als eine Menge (also eine Sammlung) von Problemen, die alle eine bestimmte Komplexität besitzen. Also für die jedes Programm, das man schreibt, nicht besser sein kein als diese Komplexität. Das kann man in vielen Fällen formal beweisen, aber nicht immer. Wichtig ist auch noch, dass es zwei Betrachtungen gibt, einmal die Komplexität der Zeit (wie Lange braucht ein Programm) und die Komplexität des Platzes (wie viel Speicher braucht das Programm). Man kann aber zeigen, dass diese beiden Eigenschaften zusammenhängen.

Ich habe in meiner Arbeit gezeigt, dass "Scrabble" (warum ich das in Anführungszeichen schreibe, kommt gleich noch) PSPACE-vollständig ist. Also ganz grob gesagt, benötigt es polynomiellen Speicherplatz, abhängig von der Eingabe. Das "vollständig" konkretisiert das ganze noch zusätzlich. Wenn ihr jetzt in die Liste bei Wikipedia guckt, sehr ihr zB, dass Schach EXP(für exponentiell)TIME-vollständig ist. Ganz grob gesprochen, kann man also sagen, dass die Aufgaben, die ein Spieler bei Schach bewältigen muss, komplexer sind als bei "Scrabble". Bestimmt habt ihr schon mal von den regelmäßigen Duellen zwischen Schach-Profis und Schachcomputern gehört, bei soetwas spielen solche Berechnungen eine wichtige Rolle, um abschätzen zu können, was ein Computer kann und was nicht. Denn Computer sind eigentlich nicht sonderlich schlau, sie sind eben nur verdammt schnell und können sich eine Menge merken.

Jetzt kommt das große Aber. Denn wie ich in meiner Arbeit geschrieben habe, hat das in dem Artikel betrachtete Scrabble-Spiel nur noch teilweise etwas mit dem Scrabble Brettspiel zu tun. Erstmal fällt der komplette Zufallsfaktor weg, das heißt der Spieler weiß genau, wann er welche Steine ziehen wird. Und zusätzlich sind Spielfeld, Spielsteine und Wörterbuch stark manipuliert (und variabel). Deswegen würde ich das Ergebnis eher als ein Indiz für die Komplexität des Scrabble-Brettspiels betrachten, nicht als wirklichen Beweis. Vielleicht gibt es in Zukunft aber auch noch Artikel, die sich intensiver mit dem Thema beschäftigen und dann vielleicht auch näher am tatsächlichen Brettspiel liegen.

Ich selbst habe übrigens auch mehrere Woche gebraucht, um überhaupt in Ansätzen zu verstehen, was in dem Artikel gemacht wird. Die Theoretische Informatik ist auch nicht ohne Grund unter Informatikern als sehr mathematisch und abstrakt verschrien ^^ Es war aber trotzdem interessant, sich mit dem Thema auseinanderzusetzen. Außerdem hat es mich dazu motiviert, das Brettspiel mal wieder aus dem Schrank zu holen und ein paar Runden zu spielen.

Ich hoffe, ich konnte einen kleinen Einblick in die Ideen hinter der Arbeit bieten. Falls es noch Fragen gibt, versuche ich natürlich sehr gerne, diese zu beantworten!