Antworte auf:  Kegelbahnkreuz von Goswin
Forum:  Didaktik der Mathematik, moderiert von: goeba

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.12, eingetragen 2021-01-10 15:47    [Diesen Beitrag zitieren]

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.11, eingetragen 2020-12-28 18:23    [Diesen Beitrag zitieren]

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 polynomialbeschränkten Anzahl von Schritten gefunden werden kann. Aber das braucht ein Gymnasiast nicht zu wissen.


Ritter
Aktiv
Dabei seit: 16.06.2009
Mitteilungen: 600
Herkunft: Dunkler Ort

 Beitrag No.10, eingetragen 2020-12-25 15:52    [Diesen Beitrag zitieren]

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.9, eingetragen 2020-12-20 00:22    [Diesen Beitrag zitieren]

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.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.8, eingetragen 2020-12-14 21:42    [Diesen Beitrag zitieren]

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.


Ritter
Aktiv
Dabei seit: 16.06.2009
Mitteilungen: 600
Herkunft: Dunkler Ort

 Beitrag No.7, eingetragen 2020-12-14 14:58    [Diesen Beitrag zitieren]

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


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.6, eingetragen 2020-11-20 17:02    [Diesen Beitrag zitieren]

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!


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.5, eingetragen 2020-11-18 12:26    [Diesen Beitrag zitieren]

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 😁).


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.4, eingetragen 2020-10-26 09:32    [Diesen Beitrag zitieren]

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. )


Scynja
Aktiv
Dabei seit: 23.02.2011
Mitteilungen: 363
 Beitrag No.3, eingetragen 2020-10-26 02:08    [Diesen Beitrag zitieren]

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?


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Beitrag No.2, eingetragen 2020-10-26 00:12    [Diesen Beitrag zitieren]

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.


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6640
Herkunft: Niedersachsen

 Beitrag No.1, eingetragen 2020-10-25 01:21    [Diesen Beitrag zitieren]

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"!]).


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1560
Herkunft: Chile, Ulm

 Themenstart: 2020-10-24 15:33    [Diesen Beitrag zitieren]

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! 😃


 
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]