|
Das deutsche QBasic- und FreeBASIC-Forum Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
gripslund
Anmeldungsdatum: 09.03.2006 Beiträge: 10 Wohnort: Quesitz
|
Verfasst am: 06.07.2017, 22:02 Titel: Kombinationsspiel |
|
|
Hier mal ein einfaches Kombinationsspiel für die Konsole.
Statt Farben werden die Ziffern 1 bis 6 verwendet.
Damit es einfacher ist, gibt es keine Zahl mehrfach. Kann man natürlich auch einbauen
Code: |
' Kombinationsspiel
' Es werden vier VERSCHIEDENE Zahlen ermittelt (1-6).
' Richtige Zahl an richtiger Position -> o
' Richtige Zahl an falscher Position -> x
' Es werden nur die Zahlen 1 bis 6 verwendet.
Cls:Randomize Timer
Dim As Integer x(4)
Dim As String xs(4),ys(4)
Dim As Integer ll,ver
Dim As String a
Print "Kombinationsspiel V1.0 (1-6)":Print
' vier Zahlen ermitteln (verschiedene)
x(1)=Int(Rnd(1)*6)+1
Do
x(2)=Int(Rnd(1)*6)+1
Loop Until x(2)<>x(1)
Do
x(3)=Int(Rnd(1)*6)+1
Loop Until x(3)<>x(2) And x(3)<>x(1)
Do
x(4)=Int(Rnd(1)*6)+1
Loop Until x(4)<>x(3) And x(4)<>x(2) And x(4)<>x(1)
'Print x(1);x(2);x(3);x(4) 'Kontrollausgabe
For ll=1 To 4
xs(ll)=Right(Str(x(ll)),1)
Next
xs(0)=xs(1)+xs(2)+xs(3)+xs(4)
'Print " ";xs(0) 'Kontrollausgabe
ver=0
Do
ver=ver+1:Print ver;". Versuch: ";
For ll=1 To 4
ys(ll)=""
Next
'Eingabe
For ll=1 To 4
Do
ys(ll)=InKey
Loop While ys(ll)<"1" Or ys(ll)>"6"
Print ys(ll);
Next
Print " ";
'doppelte Eingabe?
If ys(1)=ys(2) Or ys(1)=ys(3) Or ys(1)=ys(4) Or ys(2)=ys(3) Or ys(2)=ys(4) Or ys(3)=ys(4)Then
Print
ver=ver-1
Continue Do
EndIf
a=""
'richtige Position?
For ll=1 To 4
If ys(ll)=xs(ll) Then a=a+"o"
Next
'richtige Zahl
If ys(1)=xs(2) Or ys(1)=xs(3) Or ys(1)=xs(4) Then a=a+"x"
If ys(2)=xs(1) Or ys(2)=xs(3) Or ys(2)=xs(4) Then a=a+"x"
If ys(3)=xs(1) Or ys(3)=xs(2) Or ys(3)=xs(4) Then a=a+"x"
If ys(4)=xs(1) Or ys(4)=xs(2) Or ys(4)=xs(3) Then a=a+"x"
Print a;:Print
'geloest?
Loop While a<>"oooo" 'nein
Print:Print " OK. Fertig. ";ver;" Versuche."
sleep
|
(Hatte ich mal für meinen guten alten Casio FX-880P geschrieben.)
Editiert durch Moderator (Sebastian).
Zuletzt bearbeitet von gripslund am 07.07.2017, 08:41, insgesamt einmal bearbeitet |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 07.07.2017, 08:07 Titel: |
|
|
Sieh mal an, das gute alte Mastermind. Da werden Erinnerungen wach...
Ich hatte mal ein Lösungsschema dafür ausgeknobelt (Lösung in maximal 7 Versuchen, wenn ich mich recht erinnere), aber ich krieg's jetzt auf Anhieb nicht mehr auf die Reihe (ist schon lange her). Mal nachdenken...
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
dreael Administrator
Anmeldungsdatum: 10.09.2004 Beiträge: 2509 Wohnort: Hofen SH (Schweiz)
|
Verfasst am: 07.07.2017, 10:43 Titel: |
|
|
Ohne viel Kommentar:
http://www.dreael.ch/Deutsch/Download/Mastermind-Knacker.html
d.h. ganz früher einmal die Rollen getauscht...
Nebenbei: Mit heutigem 64-Bit und den üppigen RAM-Mengen heutzutage könnte man mittlerweilen schon recht komplexe Spiele damit lösen. Natürlich müsste inzwischen das Ganze noch um Worker-Threads erweitert werden, so dass die Kombinationen-Streichtabelle partitioniert durch verschiedene Threads verarbeitet würde. _________________ Teste die PC-Sicherheit mit www.sec-check.net |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 07.07.2017, 16:00 Titel: |
|
|
Mein Schema ließ sich ganz einfach mit dem Biocomputer zwischen den Ohren bewältigen. Aber wie gesagt...
Ich weiß nur noch, daß ich mit vier unterschiedlichen Farben angefangen und sie bei jedem Zug eine Stelle nach rechts verschoben habe. Für die Farbe, die herausfiel, kam eine neue, noch nicht benutzte herein, und wenn alles einmal rum war, hatte ich die Lösung (zu 100%).
Blöd war nur, daß irgendwann keiner mehr mit mir spielen wollte...
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
dreael Administrator
Anmeldungsdatum: 10.09.2004 Beiträge: 2509 Wohnort: Hofen SH (Schweiz)
|
Verfasst am: 07.07.2017, 21:17 Titel: |
|
|
Beim von mir zuvor genannten Projekt befasste ich mich damals auch mit dem Thema des optimalen Spielweges. Grundprinzip: Array of Boolean für jede mögliche Kombination, bei der ersten GW-BASIC-Version noch als Integer-Array implementiert als einfaches 0/-1 -> entsprechend limitiert beim Spielumfang. Erst bei der C++-Version mit Einzelbits gearbeitet. Weil FreeBasic praktisch auch über das gesamte Repertoire an Bit-Operatoren verfügt, wäre eine entsprechende Portierung kein Problem, so dass mit dem 64-Bit-Compiler das ganze RAM eines üppig ausgestattenen Servers als riesengrosse Streichtabelle genutzt werden könnte.
Grundprinzip ist ein Sieb, also jedesmal wieder die nicht mehr in Frage kommenden Kombinationen laufend streichen. In den ersten Versionen erfolgte die Wahl noch rein zufällig aus den noch in Frage kommenden Farbkombinationen. Später kam dann noch als Optimierung dazu, so zu raten, dass die Durchstreichrate bei falscher Kombination maximal wird => Zufallsgenerator nur noch bei gleichwertig optimalen Farbkombinationen anwenden.
Vorhin mir wieder einmal den Quellcode angeschaut: Im Prinzip könnte beim voll optimierten Raten mit Threads gearbeitet werden, in dem die äussere Schleife noch sequenziell läuft, das Prüfen einer Kombination, wo eine innere Schlaufe nötig ist, jeweils als Arbeitspaket für die Worker-Threads erfolgen könnte. Müsste mit Vorteil als Message Queues erfolgen => Auf diese Weise würde eine moderne Mehrkern-CPU mit voller Leistung arbeiten.
Für die Interessierten noch eine Berechnung, wie komplex ein Mastermind bei heutiger moderner Hardware sein dürfte:
http://beilagen.dreael.ch/QB/Mastermind_Streichtabelle_Server.xls
Das Ganze soll wie folgt interpretiert werden: Als Beispiel ein PC (z.B. 19-Zoll-x86-Server) mit 256 GB RAM. Davon nimmt das Windows-Betriebssystem mit all seinen Diensten + der Code-Teil vom 64-Bit-FreeBasic z.B. ingesamt 3 GB weg -> dem Freebasic-Programm-Prozess und damit dem Streichtabellen-Array stehen somit 253 GB zur Verfügung.
=> Damit wäre es beispielsweise möglich, ein Spiel mit einer Kombination von 12 Stiften, jeder 10 verschiedenen Farben durchzurechnen. Allerdings dürfte die CPU-Rechenzeit schneller zum begrenzenden Faktor werden. _________________ Teste die PC-Sicherheit mit www.sec-check.net |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 08.07.2017, 13:24 Titel: |
|
|
Na gut, ich hatte es immer nur mit der Sandardversion mit 4 Stiften und 6 Farben zu tun.
So wie du deinen Algorithmus beschreibst, sieht es für mich sehr nach brute force aus. Das müsste doch eigentlich auch eleganter gehen...
Deine Berechnung kann ich allerdings nicht ganz nachvollziehen: Bei 12 Stiften und 10 Farben gibt es 10^12 = 1 Billion mögliche Kombinationen. Um 10 Farben darzustellen, werden 4 Bits benötigt, für 1 Billion Kombinationen also 500 Milliarden Bytes. Das sind nach meiner Berechnung ca. 466 GB. Dein Server braucht also ein Speicherupgrade .
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
dreael Administrator
Anmeldungsdatum: 10.09.2004 Beiträge: 2509 Wohnort: Hofen SH (Schweiz)
|
Verfasst am: 08.07.2017, 15:21 Titel: |
|
|
Also ich hatte es damals bereits speicheroptimiert implementiert. Das bedeutet, dass jede mögliche Steckkombination einer Speicheradresse entspricht. Bei GW-BASIC noch ein Array-Index -> auf die berühmten 32767 Möglichkeiten (bzw. weniger, weil ja kein 64k-Speichersegment komplett verfügbar war) beschränkt, später bei der C++-Version dann echt ein Bit im RAM. Mein damaliger 60-MHz-Pentium hatte 16 GB RAM -> wenn ich z.B. 2 MB RAM für MS-DOS, HIMEM.SYS/EMM386, DJGPP-Laufzeitumgebung usw. wegrechne, konnte ich bereits 14 MB nutzen, was dann bereits Spiele mit rund 117 Millionen Kombinationsmöglichkeiten zuliess.
Das kleine Array mit der Farbkombination existiert nur als Laufvariable, weil immer ein Kombinationengenerator (im Prinzip nur verschachtelte FOR-Schleifen - das Ganze aber mit Rekursion, damit die Zahl der Stifte flexibel bleibt. Damals noch aus Performancegründen gar in ein GOTO-Konstrukt umgebaut), der dann schön sequenziell Bit für Bit anfasste (aus Performancegründen natürlich auch immer ein 32-Bit-Wert in eine CPU-Registervariable geholt, dort verarbeitet, zurückgeschrieben, nächste geholt).
Somit hat also bei Deinem 6 Farben/4 Stifte-Spiel (Wiederholungen erlaubt) diese Tabelle auch tatsächlich nur diese 162 Bytes RAM (mit 4-Byte-Alignment 164 Byte) belegt. Nimmt man Dein Spiel mit jede Farbe höchstens einmal möglich (=6*5*4*3 = 360 Möglichkeiten), dann wäre dieses Array sogar nur 45 Bytes (48 Bytes mit 4-Byte-Alignmet) im RAM dimensioniert worden.
Bei der ursprünglichen Version wurde einfach eine beliebige noch freie Kombination gewählt. Bei der optimierten Version wurde der Rateversuch so gewählt, dass die Tabellenstreichrate im Falle eines Fehlversuches statistisch maximal wird. Oder anders gesagt: Wenn der Rateversuch noch nicht der Lösungskombination entspricht, soll wenigstens so viel wie nur möglich ausgeschlossen werden können. _________________ Teste die PC-Sicherheit mit www.sec-check.net |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 10.07.2017, 16:06 Titel: |
|
|
Es hat mir doch keine Ruhe gelassen, die verschütteten Erinnerungen wieder auszugraben .
Dazu habe ich gripslunds Programm so umgeschrieben, daß es dem "normalen" Mastermind entspricht (und es dabei auch gleich ein bisschen lesbarer gemacht). Dann habe ich damit gespie... ähm, ich meine, eine umfangreiche Testreihe durchgeführt. Tatsächlich reichen in 90% aller Fälle 7 Versuche aus, das Maximum waren 10. Die Sache hat allerdings einen Haken: Informationen aus der Stiftematrix herauszulesen ist das eine, das Ganze in einen programmierbaren Algorithmus zu packen, etwas ganz anderes. Außerdem funktioniert das Schema nur, wenn jede Farbe nur einmal vorkommt, die Kombination darf also nicht aus mehr Stiften bestehen, als Farben vorhanden sind.
Daher bin ich auf einen anderen Lösungsansatz gekommen. Dazu habe ich das Programm für eine variable Zahl von Farben (na gut, momentan Zahlen von 0 bis maximal 9, es muß ja einstellig bleiben; wenn mehr gewünscht wird, kann man ja Buchstaben nehmen) und Stiften erweitert und einen Lösungsgenerator dazuprogrammiert.
Den Algorithmus brauche ich nicht groß zu erklären, der dürfte beim Betrachten der Lösungstabelle deutlich werden. Für die erwähnten 12 Stifte bei 10 Farben benötigt mein betagter Rechenknecht (Pentium IV / 3 GHz / 1 GB RAM) etwa 0,2 bis maximal 0,3 Sekunden.
Wenn man den Wert von auto auf 0 setzt, wird der Lösungsgenerator abgeschaltet und man kann die Lösungen von Hand eingeben. Code: | Cls:Randomize 'Timer
Dim As Integer ll, versuchNr, zahlen, spalten, auto, treffer, treffervor, autoStelle
zahlen = 10
spalten = 12
auto = 1
Dim As Integer x(spalten)
Dim As String loesung(spalten), versuch(spalten), loesungKopie(spalten), versuchKopie(spalten), _
versuchAuto(spalten)
Dim As String a
Dim As Double timerem
Do
Cls
Print "Kombinationsspiel V1.0 (0-";Str(zahlen - 1);")":Print
'gesuchte kombination ermitteln
For ll = 1 To spalten
x(ll) = Int(Rnd * zahlen)
'x(ll) = 9
If auto Then
versuchAuto(ll) = "0"
EndIf
Next
'kontrollausgabe
For ll = 1 To spalten
Print x(ll);
Next
Print
loesung(0) = ""
For ll = 1 To spalten
loesung(ll) = Right(Str(x(ll)), 1)
loesung(0) += loesung(ll)
Next
Print " ";loesung(0) 'Kontrollausgabe
versuchNr = 0
timerem = Timer
Do
versuchNr += 1
Print versuchNr;".";Tab(7);"Versuch: ";
For ll = 1 To spalten
versuch(ll) = ""
Next
'Eingabe
For ll = 1 To spalten
Do
If auto Then
versuch(ll) = versuchAuto(ll)
Else
versuch(ll) = InKey
EndIf
Loop While versuch(ll) < "0" Or versuch(ll) > Str(zahlen - 1)
Print versuch(ll);
Next
Print " ";
a = ""
'vergleichskopie erstellen
For ll = 1 To spalten
loesungKopie(ll) = loesung(ll) 'kopie der lösung
versuchKopie(ll) = versuch(ll) 'kopie des versuchs
Next
'richtige Position
For ll = 1 To spalten
If versuch(ll) = loesung(ll) Then
a += "o"
loesungKopie(ll) = "" 'alle korrekten positionen löschen
versuchKopie(ll) = "" 'alle korrekten positionen löschen
EndIf
Next
'richtige Zahl
For x As Integer = 1 To spalten 'lösung durchgehen
If loesungKopie(x) <> "" Then 'keine korrekte position
For y As Integer = 1 To spalten
If versuchKopie(y) = loesungKopie(x) Then 'korrekte zahl
a += "x"
versuchKopie(y) = "" 'zahl auf ""
loesungKopie(x) = "" 'zahl auf ""
Exit For
EndIf
Next
EndIf
Next
Print a;" ";':Print
If auto Then
treffer = 0
For ll = 1 To Len(a)
If Mid(a, ll, 1) = "o" Then
treffer += 1
EndIf
Next
If versuchNr = 1 Then
autoStelle = 1
treffervor = treffer
versuchAuto(autoStelle) = "1"
Else
If treffer = trefferVor Then
versuchAuto(autoStelle) = Chr(Asc(versuchAuto(autoStelle)) + 1) 'nächste zahl
ElseIf (treffer > treffervor) And (treffer < spalten) Then
autoStelle += 1
versuchAuto(autoStelle) = "1"
trefferVor = treffer
Else
versuchAuto(autoStelle) = "0"
autoStelle += 1
versuchAuto(autoStelle) = "1"
EndIf
EndIf
Print 'autoStelle
EndIf
'Sleep 1000
Loop Until a = String(spalten, "o") 'nein
Print " Loesung: ";loesung(0) 'Kontrollausgabe
Print:Print " OK. Fertig. ";versuchNr;" Versuche.";Timer - timerem;" Sekunden."
Sleep
Loop Until Inkey = Chr(27) 'esc |
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
dreael Administrator
Anmeldungsdatum: 10.09.2004 Beiträge: 2509 Wohnort: Hofen SH (Schweiz)
|
Verfasst am: 10.07.2017, 19:34 Titel: |
|
|
Den alten C++-Code auch wieder einmal hervorgekramt; für den aktuellen GCC müsste ich direkt einiges portieren (bereits 20 Jahre her!), daher aus Bequemlichkeit aufs damals genererte Binary vom DJGPP (DOS-GNU-Compiler) zurückgegriffen und in der MS-DOS 6.22-VMware laufen gelassen:
http://beilagen.dreael.ch/QB/MasterMind_Selbstspiel.png
Quellcode zum Ganzen:
http://beilagen.dreael.ch/QB/K_S_SPIE.CPP
Dort liess ich auch den Computer gegen sich selbst spielen.
Beispiel 6 Farben/4 Stifte/Farbwiederholung erlaubt/vorkommend, aber falsch platziert auch angegeben:
Mit herkömmlichem Lösung probieren sind durchschnittliche 3,75 Danebenrate-Versuche nötig. Mit der optimierten Methode nur 3,41 Versuche.
Beispiel 8 Farben/5 Stifte/Farbwiederholung erlaubt/vorkommend, aber falsch platziert auch angegeben:
Herkömmlich: 4.89 Fehlversuche nötig
Optimiert: 4.45 Fehlversuche
Als Anregung für ein "normales" Mastermind-Spiel (klassich wie aus dem BASIC-Büchlein aus den 80er-Jahren): Spezialvariante, wo sich der Computer die Kombination in Wirklichkeit gar nicht zu Beginn ausdenkt, sondern stets so antwortet, dass das Spiel zwar immer korrekt lösbar bleibt, aber die Streichtabelle sich nur minimal reduziert, so dass der Ratende möglichst viele Versuche zum Herausfinden benötigt. => Meldung "Bravo! Du hast es herausgefunden" immer erst dann, wenn die Streichtabelle auf exakt 1 Eintrag reduziert wurde.
Modellbeispiel mit 3 Farben, 2 Stifte / Wiederholung möglich: Benutzer gibt "CA" ein.
Antwort 0/0 (Lösung BB) würde Streichtabelle um 8 reduzieren
Antwort 1 weiss/0 schwarz: würde AB, BC erlauben -> um 7 red. (=schon besser als Antwort!)
2 weiss/0 schwarz (Lösung AC) -> um 8 reduziert (schlechtere Antwort!)
0 weiss/1 schwarz: CB, BA, CC, AA kommen noch in Frage -> nur 5 Streichungen -> noch besser!
1 weiss/1 schwarz: logischerweise unmöglich (würde die Routine daran erkennen, dass anschliessend alles durchgestrichen wäre!)
2 schwarz: = Lösung selber
=> In diesem Beispiel wäre die Antwort 1x schwarz + 1x leer am optimalsten, damit noch möglichst viele weitere Rateversuche vom Spieler benötigt werden. _________________ Teste die PC-Sicherheit mit www.sec-check.net |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 11.07.2017, 06:36 Titel: |
|
|
Du scheinst dich ja intensiver damit befasst zu haben. Ich habe dieses Spiel seinerzeit nur "analog" gespielt, auf dem Spielbrett gegen einen menschlichen Gegner. Über eine Optimierung der Versuchsanzahl habe ich mir nie Gedanken gemacht, es ging nur darum, innerhalb der erlaubten 10 Versuche zu bleiben, und das habe ich mit "meinem" Schema IMMER geschafft.
Neugierig wäre ich allerdings schon, welches Potential darin steckt. Daß der 7. Versuch fast immer erfolgreich ist, legt die Vermutung nahe, daß in den ersten 6 Versuchen redundante Informatioen stecken, die man zur Optimierung nutzen könnte. Mal sehen, ob ich einen passenden Lösungsgenerator hinkriege .
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|