Es ist sehr beachtlich, dass ein Informatik-Professor das Thema Scrabble für eine Bachelorarbeit vorgeschlagen hat. Leider ist diese Arbeit (wie üblich) so geschrieben, dass sie nur Fachleute lesen und verstehen können. Außerdem wurde eine für theoretische Zwecke besser geeignete, ziemlich vereinfachte Form des Scrabble-Spiels behandelt.
Obwohl diese Arbeit also keine unmittelbaren praktischen Anwendungen finden wird, hoffe ich, dass sie dazu beiträgt, vermehrtes wissenschaftliches Interesse an Scrabble insbesondere auch im deutschsprachigen Raum zu wecken.
Zitat von linhart im Beitrag #2Obwohl diese Arbeit also keine unmittelbaren praktischen Anwendungen finden wird, hoffe ich, dass sie dazu beiträgt, vermehrtes wissenschaftliches Interesse an Scrabble insbesondere auch im deutschsprachigen Raum zu wecken.
Das wäre wirklich vonnöten! Insbesondere in Anbetracht der Tatsache, dass es Wikipedianer [1] gibt, die die Relevanz von Scrabble auf dem Niveau von nationalen Meisterschaften mit der von Meisterschaften im Sackhüpfen, Teebeutelwerfen oder Fußnägelschneiden auf eine Stufe stellen...
Zitat von linhart im Beitrag #2 Leider ist diese Arbeit (wie üblich) so geschrieben, dass sie nur Fachleute lesen und verstehen können. Außerdem wurde eine für theoretische Zwecke besser geeignete, ziemlich vereinfachte Form des Scrabble-Spiels behandelt.
Da mir das notwendige Fachwissen fehlt, habe ich leider überhaupt nicht verstanden, worum es genau geht, d.h. was die Untersuchung von Christoph Hube genau bezweckt und was das Ergebnis seiner Forschung besagt. Aber ich würde schon gern wenigstens in groben Zügen verstehen, was hier eigentlich bewiesen wurde. Es wäre schön, wenn es einen populärwissenschaftlich, allgemein verständlich formulierten Abstract gäbe.
Auch ich freue mich sehr darüber, dass Scrabble durch dieses Thema hier so einen wissenschaftlichen Stellenwert bekommt.
Der klassischen Feststellung, dass der Erfolg beim Scrabble (z.B. einem Turnier) bestimmt wird durch die vier Faktoren - Wissen (Wortschatz, Spiel- und Grammatikregeln,), - Können (Grundrechenarten, Stochastik, flexibles, schnelles Denken), - Glück, Zufall und - Psychologie (eigene mentale Vorbereitung, Einschätzen des Spielpartners), wird hier ein fundierter Beitrag zugeordnet, der zumindest die mathematische Komponente ausführt.
Es ist nicht leicht, allgemein verständlich zu erklären, um was es in dieser Bachelor-Arbeit geht. Es ist jedenfalls ziemlich weit von dem entfernt, was man sich außerhalb der Informatik unter Komplexität vorstellt.
Grob gesagt, geht es darum, wie stark der notwendige Speicherplatz (zur Lösung eines Scrabble-Problems mit dem Computer) ansteigt, wenn man das Scrabble-Brett immer mehr vergrößert. Es stellt sich heraus, dass Scrabble in dieser Hinsicht nicht so komplex wie Schach und Go ist. Man darf aber daraus nicht schließen, dass dasselbe auch für den "gewöhnlichen" Komplexitätsbegriff gilt. Vor allem sagt das überhaupt nichts aus, wenn man nur Spiele mit fixer Brettgröße betrachtet (wie insbesondere beim Schach und Go üblich).
Der Hauptwert solcher Untersuchungen besteht wie gesagt darin, dass Scrabble überhaupt wissenschaftlich untersucht wird.
Zitat von linhart im Beitrag #6Der Hauptwert solcher Untersuchungen besteht wie gesagt darin, dass Scrabble überhaupt wissenschaftlich untersucht wird.
Ja, dass Scrabble Gegenstand einer wissenschaftlichen Untersuchung ist, ist wirklich bemerkenswert!
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!
Für mich ist das alles nun etwas verständlicher, wenngleich ich immer noch große Probleme habe, den Inhalt dieser Arbeit zu verstehen. Das liegt aber vermutlich an meinen mehr als verstaubten mathematischen Kenntnissen ...
Gero
Download: Geros Superdic, was sonst! | Discussion: Forum | News: Twitter | ... und im übrigen bin ich der Meinung, dass Wordfinder beim online-Spiel pfui sind!
Die Einleitung dieses Artikels ist durchaus gut lesbar geschrieben. Insbesondere wird darauf hingewiesen, dass es bei Scrabble um zwei unterschiedliche "Tasks" geht: Einerseits um das Bilden von Wörtern aus den vorhandenen Buchstaben, und andererseits um die Suche nach einer geeigneten Anlegestelle. In der Arbeit wird gezeigt, dass jedes dieser beiden Probleme "hart" ist. Die Autoren kommen daher zu folgendem Schluss:
Zitat Thus, we establish that during the course of a game, Scrabble players need to perform not one, but two computationally hard tasks, which is probably the reason why Scrabble is so much fun to play.
In der Bachelorarbeit entsprechen die Kapitel 4 und 5 diesen beiden "Tasks".
Besten Dank für deine verständliche Erklärung. Intuitiv hätte man das sicher auch so erwartet (wobei ich meine, solche überraschenden Aussagen gehört zu haben, dass Go komplexer sei als Schach). Eine Sache bleibt für mich offen:
Zitat von CoVou im Beitrag #8Erstmal 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).
Kannst du abschätzen, was das bedeutet? (Ich rate: eine lineare Abnahme der Komplexität ohne großen Einfluss)
@linhart: Ah ja genau, das ist der Artikel, danke! Ich konnte den vorhin auf die Schnelle nicht finden.
Wie schon richtig erwähnt, wird in dem Artikel Scrabble auf zwei verschiedene Aufgaben aufgeteilt, das Bilden eines Wortes und das Suchen nach einer Position. Es hätte gereicht, zu zeigen, dass eine der beiden Aufgaben PSPACE-vollständig ist, damit das Gesamtproblem PSPACE-vollständig ist. Die Vollständigkeit wird im Artikel (und in der Arbeit) aber für beide Aufgaben gezeigt.
Zitat von Scotty im Beitrag #11Kannst du abschätzen, was das bedeutet? (Ich rate: eine lineare Abnahme der Komplexität ohne großen Einfluss)
Also meiner Meinung nach wurde das Spiel soweit verändert, dass man eigentlich schon von einem eigenen Spiel reden kann, also quasi einem Alternativ-Scrabble. Deswegen finde ich es schwierig, die Ergebnisse direkt auf das "richtige" Scrabble zu beziehen. Alleine der Zufallsfaktor macht ja nochmal ganz schön was aus, so dass ein Rechner da sicherlich noch deutlich mehr zu kniffeln hätte. In wie weit das für eine höhere Komplexitätsklasse reicht, wage ich nicht direkt abzuschätzen. Da fehlt mir als einfacher Student die Erfahrung und auch das Fachwissen ^^
Offenbar scheint es ja aber so zu sein, dass Scrabble sich nicht so leicht auf Komplexität untersuchen lässt wie manch ein anderes Brettspiel.
Wie schön, dass du uns hier näher erläuterst, was deine Bachelorarbeit eigentlich genau besagt. Vielen Dank! Jetzt ist schon manches etwas klarer geworden!
Ich hätte da aber noch eine kleine Frage: Du gebrauchst in deinem Aufsatz häufig den Begriff der Härte bzw. hart, z.B. in dem Passus: Wir betrachten die Vollständigkeit nun am Beispiel der Klasse NP. Zunächst sei eine Sprache L NP-hart, falls für alle Sprachen aus NP gilt, dass sie auf L <pol-reduzierbar sind. Zusätzlich kann die NP-Härte aufgrund der Transitivität auch durch eine Reduktion von einer anderen NP-harten bzw. NP-vollständigen Sprache aus gezeigt werden (Zitat, Seite 13).
Was ist denn da mit "hart" gemeint? Oder ist das so zu verstehen: hart = pol-reduzierbar Oder wäre "schwierig" hier ein Synonym für "hart"?
Ich müsste deine Arbeit jetzt, wo du uns so schöne Erklärungen geliefert hast, sowieso noch einmal neu lesen. Bin leider noch nicht dazugekommen... Aber es ist für einen Nichtinformatiker wie mich wirklich eine ganz schön happige Lektüre... So was liest man nicht mal so eben nebenher...
________________________________
PS: Guck mal oben in der Navigationsleiste des Forums ganz links. Da blinkt doch bei dir ein kleiner Briefumschlag! CoVou, da musst du mal draufklicken...
Kann man das Ergebnis deiner Bachelorarbeit bzw. von Lampis et al. irgendwie auf das Programm Scrabble3D übertragen/beziehen/anwenden?
Könnte man sagen, dass die Tatsache, dass Scrabble PSPACE-vollständig ist, der Grund dafür ist, warum die Spielanalyse [1] von Scrabble3D so (relativ) lang dauert? Und wenn ich die Spielanalyse eines 3D-Spiels (also eines dreidimensionalen Spiels im Würfel statt eines zweidimensionalem auf einem üblichen Spielbrett) mache und dann etwa noch ein Joker auf dem Bänkchen ist, dann kommt's mir so vor, als ob mein RAM-Speicher ganz schön ausgelastet ist, weil z.B. das Pendeln zwischen verschiedenen Programmen oder Fenstern dann sehr langsam/zeitverzögert geht, und das, obwohl mein PC hardwaremäßig nicht unbedingt zu den schlechtesten gehört... (Hm, vielleicht war das eine dumme Lieschen-Müller-Frage... )
Ist mit SPACE hier also der RAM-Speicher gemeint? (Hm, das war vielleicht noch so eine dumme Frage... )
Übrigens:
Mir bereiten deine weiterführenden theoretischen Fragen im Kapitel 6 Fazit auf Seite 56 Vergnügen - insbesondere die hier: Was ist das kleinste Alphabet bzw. Wörterbuch, für das das Scrabble-Problem immer noch PSPACE-hart ist? (Zitat, Seite 56)
--------------------------
[1] Spielanalyse: Der Computer berechnet jeweils den punktreichsten Zug, der möglich gewesen wäre.
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.
Sie sind vermutlich noch nicht im Forum angemeldet - Klicken Sie hier um sich kostenlos anzumelden
Download (Sourceforge.net)
Manual (Wiki)
Fanship (Facebook)
News (Twitter)
Offline
OpenSource! 
)
