Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

Kombinationsspiel

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Projektvorstellungen
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
gripslund



Anmeldungsdatum: 09.03.2006
Beiträge: 10
Wohnort: Zeckerin

BeitragVerfasst am: 06.07.2017, 22:02    Titel: Kombinationsspiel Antworten mit Zitat

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 zwinkern

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
Benutzer-Profile anzeigen Private Nachricht senden
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 836
Wohnort: Ruhrpott

BeitragVerfasst am: 07.07.2017, 08:07    Titel: Antworten mit Zitat

Sieh mal an, das gute alte Mastermind. Da werden Erinnerungen wach... lächeln

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

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2457
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 07.07.2017, 10:43    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 836
Wohnort: Ruhrpott

BeitragVerfasst am: 07.07.2017, 16:00    Titel: Antworten mit Zitat

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

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2457
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 07.07.2017, 21:17    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 836
Wohnort: Ruhrpott

BeitragVerfasst am: 08.07.2017, 13:24    Titel: Antworten mit Zitat

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

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2457
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 08.07.2017, 15:21    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 836
Wohnort: Ruhrpott

BeitragVerfasst am: 10.07.2017, 16:06    Titel: Antworten mit Zitat

Es hat mir doch keine Ruhe gelassen, die verschütteten Erinnerungen wieder auszugraben grinsen .

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
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2457
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 10.07.2017, 19:34    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 836
Wohnort: Ruhrpott

BeitragVerfasst am: 11.07.2017, 06:36    Titel: Antworten mit Zitat

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 lächeln .

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Projektvorstellungen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
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.

 Impressum :: Datenschutz