Matroids Matheplanet Forum Index
Moderiert von goeba
Mathematik » Didaktik der Mathematik » Kegelbahnkreuz
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Kegelbahnkreuz
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-10-24


Ich hoffe, folgendes von mir erdachte Kegelbahnkreuz-Spiel ist selbsterklärend. Das Ziel zu erreichen entspricht genau der Lösung einer zufallsverteilten linearen Optimierungsaufgabe.

(Für eine Anleitung auf das Fragezeichen klicken; zurück kommt man indem man rechts auf die Grünfläche klickt. Die Anzeige versteckter Hintergrundszahlen bitte ignorieren)

Fertig ist das Spiel noch nicht, aber gut genug für ein erstes Feedback. Ich habe vor, eine Grafik mit dem Leistungsverlauf angemeldeter Spieler hinzuzufügen; man soll es natürlich auch als Gast (so wie ihr jetzt) spielen können. Ach so..., es fehlen ja auch noch rollende Kugeln und Kegel die umfallen! 😃


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen. (Kol.2:9)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6701
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-10-25


Selbsterklärend ist das nicht!

Mir ist nicht klar, was passieren soll, wenn ich auf ein Kreuz klicke und was das Ziel ist, weiß ich auch nicht.

Die Bedeutung der angezeigten Zahlen ist mir ebenfalls unklar.
Sowohl die Zahlen rechts, als auch die versteckten (Klick auf Zahlenanzeige [ohne "q"!]).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-10-26


2020-10-25 01:21 - Kitaktus in Beitrag No. 1 schreibt:
Selbsterklärend ist das nicht!
Hast du die Anleitung gelesen?
(auf Fragezeichen klicken, für "zurück" rechts auf Grünfläche klicken)

2020-10-25 01:21 - Kitaktus in Beitrag No. 1 schreibt:
Die Bedeutung der angezeigten Zahlen ist mir ebenfalls unklar.
Die angezeigten Kegelbahn-Zahlen verden vertauscht, wenn man auf einen Kreis klickt. Die versteckten Zahlen sind für die Spielidee unwichtig; ich werde diese Anzeige demnächst entfernen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 368
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-10-26


Hallo Goswin, dass die Zahlen sich vertauschen habe ich bemerkt. Der Grund dafür erschließt sich mir aber nicht. Wann sich welche Kreuze wie bewegen nachdem man klickt ist leider viel zu kompliziert. Beim Spielen ist es mir so vorgekommen wie ein Zauberwürfel. Ich komme bei beiden durch Probieren nicht zum Ergebnis. Der Unterschied ist, dass ich beim Zauberwürfel jeden Schritt mühelos nachvollziehen kann und hier eben nicht.

Das Spielziel sollte auch klarer kommuniziert werden. Laut Anleitung braucht man eine Bahn. Entweder, es fehlt die Gewinnmeldung, oder das Ziel ist falsch beschrieben. 1-6 von 2x5 Bahnen bekommt man relativ gut hin. Dann ist Schluss. Ist das Ziel alle Bahnen gerade zu machen? Wo werden die Züge gezählt?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-10-26


Erst einmal mein Dank an Kitaktus und Scynja für ihr Feedback: das war ja genau was ich brauchte.


2020-10-26 02:08 - Scynja in Beitrag No. 3 schreibt:
Das Spielziel sollte auch klarer kommuniziert werden. Laut Anleitung braucht man eine Bahn. Entweder, es fehlt die Gewinnmeldung, oder das Ziel ist falsch beschrieben. 1-6 von 2x5 Bahnen bekommt man relativ gut hin. Dann ist Schluss. Ist das Ziel alle Bahnen gerade zu machen?

Baue *eine* gerade Bahn *irgendwo* von der rechten zur linken Spielhälfte, indem du auf die Räder in der Spielmitte klickst bzw tippst.   Versuche, das mit *möglichst wenigen* Spielzügen zu erreichen.

Ist es so deutlicher? Nur eine Bahn wird verlangt, wenn man mehr als zwei hinbekommt ist das reiner Zufall und nicht immer möglich.


Der Sinn des Ganzen ist, eine möglichst gute Strategie zu finden, mit der man systematisch eine Lösung erreicht. Es gibt Algorithmen, welche nur die Kegelbahnzahlen und Orientierungen benutzen und bewiesenerweise zum Ziel führen; die Erfahrung zeigt jedoch, dass es viel schnellere Stategien gibt die auch nur Bahnzahlen und Orientierungen verwenden, deren Erfolg aber leider nicht bewiesen ist.

Ich habe mir vorgenommen, künftig anzuzeigen in wieviel Zügen es bestenfalls von der jeweilig laufenden Stellung aus bis zu einer Lösung zu schaffen ist; ich suche noch nach der besten Art das auszurechnen, da es ja meist viele Lösungen gibt. Für ein Spielfeld mit \(n\times n\) Rädern geht es immer in \(\le\!n\) Zügen, aber das schafft man nur selten.


( Die Orientierung der Rädchen entspricht den Vorzeichen (-1,0,+1) aus den Einträgen einer Pivotiermatrix; das Lemma von Farkas garantiert die Existenz einer Lösung. )



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-11-18


2020-10-26 09:32 - Goswin in Beitrag No. 4 schreibt:
Der Sinn des Ganzen ist, eine möglichst gute Strategie zu finden, mit der man systematisch eine Lösung erreicht.

Wenn wir die Zahlen hinter den Rädern kennen würden und nicht nur deren Vorzeichen, dann könnten wir den dualen Simplexalgoritmus mit lexikografischer Spaltenwahl verwenden um eine Bahn zu bauen. Bei meiner Simulation für eine Spielfelgröße von 12 Strecken pro Bahn (mit gleichförmig verteilten ganzen Zahlen von -9 bis +9) schaffte dieser Algoritmus es bei \(2^{20}\) Versuchen in durchschnittlich 8.98 Iterationen (arithmetisches Mittel) und in maximal 33 Iterationen. Aber so etwas ist außerhalb der Spielregeln: wir sollen ja nur die Vorzeichen der Radzahlen verwenden (also die Orientierungen der Räder).


Falls es jemand tasächlich nicht immer schaffen sollte, mit der vorhandenen Information eine Kegelbahn zu bauen, folgt hier ein bekannter Algoritmus ("Kleinstindex-Algoritmus"), der bewiesenermaßen zum Ziel kommt:
(ki 1)
Untersuche die Reihe_00 und finde unter allen "Querläufern" (Räder die in die falsche Richtung zeigen) denjenigen mit kleinstem Index (Zahl neben der Kugel). Es sei \(r\) dieser Index.
(ki 2)
Untersuche die Reihe mit Index \(r\) und finde unter allen Querläufern dieser Reihe denjenigen mit kleinstem Index. Klicke darauf und gehe nach (ki 1).

Für dieselbe Spielfelgröße brauchte der Kleinstindex-Algoritmus im Schnitt 14.86 Iterationen und maximal 72 Iterationen. Das ist nicht überwältigend schnell, führt aber sicher zum Ziel. Die maximale Anzahl Iterationen ist hier insofern irrelevant, als dass dieser Algoritmus für eigens konstruierte Aufgaben eine exponentieller Schrittzahl benötigt.

Mein bisher bestes Verfahren brauchte für 12 Strecken pro Bahn im Schnitt 10.45 Iterationen und bei \(2^{20}(\approx\!10^6)\) Versuchen nie mehr als 48 Iterationen: das ist zwar langsamer als das Simplexverfahren, aber dafür spielregelgerecht und schneller als das Kleinstindexverfahren. Anderseits habe ich keinen Beweis für die Endlichkeit des Verfahrens ...*


*(Nachtrag) ... und aus einem einfachen Grund: Nach dreißig Millionen (\(2^{25}\)) zufallserzeugten Testaufgaben wurde eine Endlosschleife gefunden. So viel zum Aussagewert von Statistiken (natürlich habe ich noch weitere Algorithmen, wo ich bisher keine Endlosschleife finde 😁).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-11-20


2020-10-26 09:32 - Goswin in Beitrag No. 4 schreibt:
Der Sinn des Ganzen ist, eine möglichst gute Strategie zu finden, mit der man systematisch eine Lösung erreicht.

Falls jemand ein eigens erdachtes Verfahren von mir testen lassen  möchte, darf er sich gerne hier melden!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ritter
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.06.2009
Mitteilungen: 601
Herkunft: Dunkler Ort
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-12-14


2020-10-26 02:08 - Scynja in Beitrag No. 3 schreibt:
Entweder, es fehlt die Gewinnmeldung, ...

Ich bin mir nicht sicher, ob ich das Ziel richtig verstanden habe (von der Strategie ganz zu schweigen), aber ich hätte gedacht, dass folgendes eine Verbindung ist:


Ist das richtig?

Gruß, Ritter



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-12-14


2020-12-14 14:58 - Ritter in Beitrag No. 7 schreibt:
Ich bin mir nicht sicher, ob ich das Ziel richtig verstanden habe (von der Strategie ganz zu schweigen), aber ich hätte gedacht, dass folgendes eine Verbindung ist.

Ja, das ist eine als "Kegelbahn" vorstellbare Verbindung. Und Kegelbahnen müssen *gerade* sein, dürfen also nicht "kreativ um die Ecke abbiegen" (kommt freilich nur selten vor).

Und ja, es fehlt eine Gewinnmeldung: ich bin etwas langsam in Javascript und bisher nicht dazu gekommen, diese einzuprogrammieren.

Und eine Ungeschicklichkeit habe ich auch noch entdeckt: wenn man auf ein Rad klickt, das gleichzeitig nach *beiden* Richtungen zeigt, sollte gar nichts passieren. Leider ändert sich der Cursor trotzdem auf "Klickmodus", obwohl Klicken da sinnlos ist.


Hoffentlich hat das nicht die Spielfreude verdorben. Ich melde mich, sobald ich da (etwas) verbessert habe.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-12-20


2020-10-26 02:08 - Scynja in Beitrag No. 3 schreibt:
Das Spielziel sollte auch klarer kommuniziert werden. Laut Anleitung braucht man eine Bahn. Entweder, es fehlt die Gewinnmeldung, oder das Ziel ist falsch beschrieben.

Jetzt habe ich eine (lang ersehnte und mehrmals angeforderte) Gewinnmeldung eingebaut. Nicht sehr elegant, aber hoffentlich klar. Ich war mir anfangs gar nicht bewusst, wie wichtig so eine Gewinnmeldung ist.


Zum Spielziel:
Man muss nur *eine* Bahn bilden, nicht mehrere. Oft entstehen mehr als eine Bahn, doch ist das reiner Zufall.

Zur hintergründigen Didaktik:
Das Suchen einer Bahn entspricht der Lösung eines linearen Ungleichugssystems, und das entspricht der Lösung einer linearen Optimierungsaufgabe.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ritter
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.06.2009
Mitteilungen: 601
Herkunft: Dunkler Ort
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-12-25


Die Gewinnmeldung funktioniert. 😃
Die Auswirkungen nach einem Klick auf ein Feld sind nur durch Rumspielen allerdings noch sehr undurchsichtig. Zumindest für mich. 🙃 Müsste man wohl mal systematisch angehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-12-28


2020-12-25 15:52 - Ritter in Beitrag No. 10 schreibt:
Die Auswirkungen nach einem Klick auf ein Feld [...] müsste man wohl mal systematisch angehen.

Diese Auswirkungen sind kein Geheimnis und brauchst du nicht zu ergründen.
Die Orientierung der Räder entspricht den Vorzeichen der Einträge für ein zufällig erzeugtes lineares Gleichungssytem der Form:
\[
D\cap B=\emptyset,\qquad
\forall~i\in B\quad x_i= \sum_{j\in D} a_{ij}x_j
\] Klicken auf das \(a_{rs}\) zugehörige Rad entspricht der Auflösung des Systems nach \(x_i,~i \in B\cup s\!\setminus\!r\).

Es ist bewiesenerweise möglich, in \(\le\!4^n\) Schritten eine Bahn zu finden *ohne* die Einträge des Gleichungssystems zu kennen (siehe zum Beispiel Beitrag #4). So ein Verfahren ist insofern attraktiv, als dass es nicht von der Skalierung der Variablen abhängt, welche ja bei Anwendungen willkürlich gewählt wird.

Die bisher ungelöste mathematische Frage ist, wieweit eine Bahn auch in einer polynombeschränkten Anzahl von Schritten gefunden werden kann. Aber das braucht ein Gymnasiast nicht zu wissen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2021-01-10


2020-12-28 18:23 - Goswin in Beitrag No. 11 schreibt:
Es ist bewiesenerweise möglich, in \(\le\!4^n\) Schritten eine Bahn zu finden *ohne* die Einträge des Gleichungssystems zu kennen (siehe zum Beispiel Beitrag #4).
[...]
Die bisher ungelöste mathematische Frage ist, wieweit eine Bahn auch in einer polynomialbeschränkten Anzahl von Schritten gefunden werden kann.

Gemeint ist dort: "in \(\le\!4^n\) Schritten ohne das Gleichungssystem zu sehen". Grundsätzlich gibt es immer Lösungen, die nur \(\le n\) Schritte entfernt sind.

Nun ein wenig "Glaskugel-Fiction":
Da die anvisierten Bahnkreuzgrößen \(n\) klein sind, könnte man für jeden Zustand des Gleichungsystems anzeigen in wieviel Schritten (also \(\le n\)) eine Lösung vorhanden ist, natürlich ohne Hinweis darauf, welche Schritte das sind. Es gibt ja auch immer mehrere Lösungswege.

Das würde die Lösungssuche insofern erleichtern, als dass es eine triviale polynomialbeschränkte Suche ermöglicht: Falls wir bei einem Schritt der uns nicht näherbringt immer zurückgehen und einen alternativen Schritt versuchen, dann brauchen wir "nur" noch insgesamt \(\le n^3\) Schritte bis zu einer Lösung. Aber die Spielidee geht dadurch wohl nicht verloren, da bekannte Algorithmen es in "durchschnittlich" \(n^{1.5}\) Schritten schaffen (was immer da mit "durchschnittlich" gemeint ist). Es könnte freilich auch nichttriviale Vorgehensweisen geben, die mir gerade nicht einfallen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3786
Herkunft: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2021-01-23


Hallo Goswin,
wird ein Rad \(a_{kl}\) gespielt, dann dreht sich laut Hinweis (5) ein Rad \(a_{ij}\) nur, wenn von den Parallelogrammecken \(a_{ij}, a_{il}, a_{kj}, a_{kl} \) eine ungerade Zahl in dieselbe Richtung zeigen. Doch in der Umformung

\(a_{ij,neu} = a_{ij} - \frac{a_{il} a_{kj}}{a_{kl}}\)

wechselt \(a_{ij}\) nur in einem bestimmten Bereich das Vorzeichen. Ist mit Hinweis (5) beabsichtigt, dass man alle Drehungen des nächsten Zuges voraussehen kann (wäre mit der Ergänzung möglich, dass einmal Drehen und zurück nicht als Zug zählt) oder ist es beabsichtigt, dass man nicht alle Drehungen vorhersehen kann?

Viele Grüße,
  Stefan



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2021-01-31


2021-01-23 08:01 - StefanVogel in Beitrag No. 13 schreibt:
Ist mit Hinweis (5) beabsichtigt, dass man alle Drehungen des nächsten Zuges voraussehen kann (wäre mit der Ergänzung möglich, dass einmal Drehen und zurück nicht als Zug zählt) oder ist es beabsichtigt, dass man nicht alle Drehungen vorhersehen kann?

Hallo Stefan,
bei meiner bisherigen herkömmlichen Zählweise kann man nicht alle Drehungen voraussehen; man kann nur etwa 50% der Stillstände voraussehen.

Dass einmaliges Drehen und zurück nicht als Zug zählen soll ist ein interessanter Vorschlag, den ich unbedingt überdenken sollte. Wenn man diese Strategie bei jedem Zug maximal ausnützt, dann multpliziert sich die Anzahl der eigentlichen Züge ja "nur" mit \(n^2\); jeder polynombeschränkte Algoritmus mit der lockeren Zählweise würde also automatisch zu einem polynombeschränkten Algoritmus bei der herkömmlichen Zählweise führen.

Ob so ein "lockerer Algoritmus" leichter zu finden ist, ist natürlich fraglich. Aber eine Voraussage aller Räderbewegungen könnte vielleicht die Spielfreude steigern, so dass mehr Leute Algoritmen suchen. Wenn man mit dem Cursor über ein Rad streicht, könnten die drehträchtigen Räder irgendwie aufleuchten - was freilich ohne (gefühlte) Verzögerung geschehen müsste.

Ein beliebiges Zurückdrehen (mit Betonung auf zurück) braucht man überhaupt nicht zu zählen. Da man die bereits besuchten Konfigurationen des Systems (also besuchte Knoten des entsprechenden Johnson-Grafs) ja auch abspeichern kann, kann man grundsätzlich von irgendeiner dieser Stellungen aus weitermachen. Was aber durch irgendein Polynom eingeschränkt werden muss ist die kostenlose Anzahl der Drehungen in unbekanntes Terrain.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]