Legemöglichkeiten im Brettspiel Carcassonne (Nerd-Frage)
Hallo, liebe Gemeinde! Wir sind hier eine kleine Gruppe, die sehr gerne das Brettspiel Carcassonne spielt. Wer es kennt, weiß, dass das Spielfeld am Ende der Partie immer sehr unterschiedlich aussehen kann, weil es für die 72 Landschaftskärtchen nunmal sehr viele Möglichkeiten gibt, sie anzulegen. Ich bin ein kleiner Mathe-Nerd, der sich zwar für Zahlen und Themen der Mathematik interessiert, aber zu dumm ist, etwas damit anzustellen. Jedenfalls frage ich mich, ob man wohl mathematisch bestimmen kann, wieviele Legemöglichkeiten das Spiel Carcassonne (ich gehe mal vom Grundspiel mit den 72 Kärtchen aus) gibt.
Kann man errechnen, wie viele mögliche "End-Spiel-Landschaften" möglich sind?
Es herrscht da ein kleiner Streit unter der Spielgruppe. Die einen sagen, ja. Es gibt schließlich eine definierte Menge von 72 Kärtchen und immer wenn eine gezogen wurde, gibt es ja nur noch 71 Karten, aus denen gezogen wird - also eine "normale" LaPlace-Wahrscheinlichkeit (?) Andere sagen, jede Karte hat ja unterschiedliche Anlegemöglichkeiten, je nachdem, ob dort ein Stadtstück, eine Straße, Kloster usw. zu sehen ist. Wenn ich mich dann z.B. dafür entscheide, die Straße anzulegen, gibt es ja wiederum viele Möglichkeiten, wo genau ich sie auf dem bereits vorhandenen Feld anlege. Dann kommt noch das Zeitproblem: es kommt ja darauf an, wann die Karte ins Spiel kommt. Ein reines Stadtstück hat am Anfang der Partie nur sehr wenige Anlegemöglichkeiten, weiter später im Verlauf hat dasselbe Stück evtl. schon deutlich mehr Möglichkeiten. Demnach sei es also unmöglich, eine exakte Anzahl der Möglichkeiten zu berechnen.
Jetzt halten mich bestimmt alle für einen totalen Nerd :D Aber ich finde es faszinierend, welche mathematischen Dimensionen in diesem Spiel stecken. Alle Mathe-Freaks, Informatiker und sonstige mathematisch Beleckten bitte mitgrübeln! Danke! ;)
Im Anhang: Eine mögliches End-Spiel-Gebilde - wie viele gibt es noch?
4 Antworten
Wie man die obere Grenze berechnen kann wurde weiter unten schon erwähnt.Allerdings ist zu beachten, dass das nur zutrifft wenn es 72 unterschiedliche Karten gibt, man muss also noch beachten dass es mehrere Karten gibt die "gleich sind". Das ganze wird wohl ziemlich komplex, ist deswegen aber umso interessanter
Ich bin mit dem Spiel nicht ganz vertraut, aber ich denke, man müsste die Anzahl der Möglichkeiten mit Hilfe von "Wahrscheinlichkeitsbäumen" bestimmen können:
Es gibt ja wohl verschiedene Typen von Karten mit verschiedenen Anlegemöglichkeiten. Für das Spiel ist es m. E. nicht wichtig, welche spezielle Karte gelegt wird, sondern nur, welcher Typ.
Jeder Typ bildet die "Wurzel" eines "Baumes". An jede Wurzel zeichnet man nun einen "Ast" für jeden Kartentyp, den man an die "Wurzel" anlegen kann, und für jede Art, wie man diesen Typ anlegen kann. An jedem Ast macht man nun das gleiche und so weiter, bis der Baum 72 Stufen hat. Dabei muss man noch beachten, dass in keinem Ast ein Kartentyp öfter auftritt, als er im Spiel vorhanden ist.
Wenn man nun die "Spitzen" aller Bäume zählt, erhält man theoretisch die Anzahl aller Möglichkeiten. Dabei ist diese Zahl allerdings erheblich zu hoch, denn theoretisch kann die gleiche Endfigur bei jeder enthaltenen Karte als "Wurzel" begonnen haben. Um das zu eliminieren, müsste man m. E. erst jeden Baum mit der Anzahl der im Spiel enthaltenen Karten seines "Wurzeltyps" vervielfachen, dann die Spitzen zählen und die Gesamtzahl durch 72 teilen. Dann sind aber immer noch die Möglichkeiten enthalten, wie aus einer "Wurzel" auf verschiedenen Wegen das gleiche Endbild erreicht werden kann. Dazu habe ich aber jetzt so keine Idee, das zu berücksichtigen :(
Selbstverständlich kann man das berechnen, ich kann dir nur leider nicht sagen wie genau.
Recht artverwandt zu Carcassonne ist das chinesische GO und auch dort kann man exakt bestimmen, wieviele Möglichkeiten es gibt: 4,63 × 10^170 Beim Schach sind es gerade einmal 10^43.
Hoffe hier meldet sich noch jemand, der das genauer ausführen kann, aber dass man es berechnen kann steht völlig außer Frage.
Ich mutmaße mal, daß der Zeitpunkt des ziehens einer Karte nicht entscheidend ist, da auch dieser Umstand wieder mathematisch ausgedrückt mit in die Berechnung einfließen kann.
In dem Zusammenhang interessant: Graphentheorie und Kombinatorik. Beides mal bei Wikipedia eingeben.
die anzahl der möglichkeiten is berechenbar, denn man kann ja für den fall, dass es endlich viele möglichkeiten gibt, alle nacheinander ausprobieren in endlicher zeit. (auch wenn das vmtl. länger dauert, als euch lieb ist).
ein computer-programm sollte das lösen können. der Computer wird aber einige Zeit lang brauchen.
d.h.: eine konkrete einfache formel zur berechnung wird wohl nicht so einfach zu finden sein, allerdings ist es möglich alle legemöglichkeiten durchzugehen. dazu zeige ich nur schnell, dass es zumindest nur endlich viele möglichkeiten gibt.
mit endlich vielen karten kann man logischerweise nur einen endlich langen "strich" ziehen. in dem fall 72 karten lang. dabei ist außer acht gelassen, dass diese garnicht so gelegt werden dürfen, d.h.: ich erhalte mehr möglichkeiten als es regelkonform wäre.
man überlegt sich schnell, dass alle "legungen" (definiere ich als wort für "was dann eben da liegt") in ein quadrat reinpassen mit diagonale (72 * 2)-1, nämlich von der mitte aus nach rechts 72 karten und nach links 72 karten. die mitte ist doppelt gezählt, also hat man 143. dabei ist die diagonale "geradelinig" aus den karten gelegt, und die seitenkanten des quadrats sind "eck"-linig diagonal gelegt. schwer zu beschreiben.
alle legungen sind also dort drinnen, damit kann ich nun ohne darauf zu achten, ob die legung zusammenhängend ist, mit einfachster kombinatorik die maximale anzahl an "formen" der legungen bestimmen. das sind nämlich 143 * 142 * 142 * 141 * .... * 71.
nun kann ich jedes teil in 4 versch. ausrichtungen drehen, und erhalte eine obere abschätzung der vertauschungen der karten innerhalb einer legung durch (72 * 4)!, wobei die " * 4" durch die dreh-richtungen kommt und ich jedes gedrehte teil als neues teil definiere, also 72 * 4 karten mit fester ausrichtung habe.
damit ist eine obere grenze (143! * 288!)/70!
rechnungen ohne gewähr. nun sind viele dieser möglichkeiten nicht regelkonform, aber jede legung ist entweder regelkonform oder nicht regelkonform. durch streichen jeder falschen legung hat man dann natürlich alle legungen bestimmt.
das problem ist lösbar. die lösung ist mir aber völlig unbekannt.
ja alle möglichkeiten sind bereits mit drin, weil ich auch die regelwidrigen zulasse. und dann am schluss überprüfe ich nur, was regelkonform war.
Wow, Danke für deine ausführlich Antwort! Es war sehr interessant, sie zu lesen und im Kopf entstanden sofort etliche Bilder meines Tisches, wo die Karten draufliegen :) Denke, dass deine Überlegung schon stark in die richtige Richtung geht. Sehe ich das richtig, dass man mit deiner Methode (stark vereinfacht: erstmal alles hinlegen und dann kucken, was nicht geht) die Zeitkomponente außer Acht lassen kann? Irgendwie denke ich aber, dass es schon relevant ist, wann eine Karte ins Spiel kommt...oder sind all diese Möglichkeiten schon in deinen "All-Möglichkeiten" mit drin? Herrje, in meinem Kopf wuselt es schon. Das wird ganz schön haarig hier. Vielleicht kommt gleich noch ein Philosoph und beleuchtet das von einer ganz anderen Seite :P