Bin zu doof den Unterschied in meinem Code zu finden... Leute mit Informatikerblick gesucht! :D

[hhgtew]

Wenn das Minenfeld genullt ist, versteht sich, ansonsten bleibt er bei dem ersten Minevorkommen natürlich automatisch hängen.

[Tobs40]

Bashar schrieb:

Ganzzahl-Überlauf? Welchen Typ haben n_fail und n_success, wenn du 438 Milliarden Durchläufe hast, kann der Typ überhaupt solche Größen aufnehmen?

Ich verwende unsigned long long, sollte lang genug sein. Das mit 438 war ja der Ansatz,der funktioniert hat

[Tobs40]

Arcoth schrieb:

Könntest du mal ein vollständiges Minimalbeispiel posten? Insbesondere wegen Definition von mines und der anderen Variablen. Man kann sonst nur spekulieren.

Das Problem mit den Summen ist eigentlich meine Umformulierung eines Spiels:

Man hat einen Weg aus Feldern und eine Figur am Anfang. Nun würfelt man immer wieder und zieht so viele Felder (z.B. erster Wurf 1 --> Figur erstes Feld, am Anfang steht die Figur noch nicht auf dem Weg). Betritt die Figur ein vermintes Feld, ist das Spiel verloren. Erreicht sie das Ziel (Erreicht ein theoretisches 50. Feld, muss nicht mit genauer Augenzahl erfolgen) ist das Spiel gewonnen. Der Spieler trifft also keine Entscheidungen, sondern würfelt nur. (Spiel hat sich ein Kind ausgedacht). Ich will wissen, wie wahrscheinlich es ist, das Spiel zu gewinnen (und wie viele Möglichkeiten es gibt)

Das konkrete Beispiel (Zeichnung vom Kind) hat folgenden Weg:
O = normal
X = vermint
Start --> OXOOXOOXOOXOOXOXOOXOOOOXOOOOXOOOXOXXOXOOXOOXOXOOO --> Ziel

49 Felder, 16 verminte, nämlich 2,5,8,11,14,16,19,24,29,33,35,36,38,41,44 und 46

Meintest Du das mit einem konkreten Beispiel?

[Tobs40]

hhgtew schrieb:

for (int i = 1; i < 7; i++) // Weiterwürfeln
{
  solve(sum + i);
}

Warum schreibst du nicht gleich ohne Schleife

solve(sum + 1);

Es kommt doch sowieso dann in beiden Fällen immer sum=50 raus. Vielleicht übersehe ich auch was.

Ich will alle Spielverläufe durchgehen und zählen, welche gewinnen und welche verlieren. Im Prinzip entsteht hier durch solve(int sum) ein Baum der Spielverläufe. Und solang es nicht vorbei ist, geht es nach jedem Zug mit 6 Möglichkeiten weiter. Oder meintest Du etwas anderes?

[Tobs40]

hhgtew schrieb:

Wenn das Minenfeld genullt ist, versteht sich, ansonsten bleibt er bei dem ersten Minevorkommen natürlich automatisch hängen.

Ahhhh... Jetzt verstehe ich. Nein, das geht nicht. Siehe vorherige Nachricht.

[Columbo]

Tobs40 schrieb:

Meintest Du das mit einem konkreten Beispiel?

Nein, ich meinte einen konkreten, kompilierbaren Stück Code.

[tobias.voelk@t-online.de]

main.cpp:

#include <iostream>
#include "PhilGame.h"
using namespace std;

int main()
{
	PhilGame pg = PhilGame();
	int eingabe;
	while (true)
	{
		system("CLS");
		cout << "1 - GOTTA CALCULATE IT ALL!" << endl;
		cout << "2 - PLAYING N HUNDRED MILLION RANDOM GAMES (-1 for endless)" << endl;
		cin >> eingabe;
		system("CLS");
		if (eingabe == 2)
		{
			cout << "How many Hundred Million Games: ";
			cin >> eingabe;
			pg.estimate(eingabe);
		}
		else
		{
			pg.calculate();
		}
	}
	return 0;
}

PhilGame.h:

#include <iostream>
#include <time.h>
using namespace std;

class PhilGame
{
	public:
		void init();
		void calculate();
		void solve(int sum);
		void estimate(unsigned long long n);
	private:
		bool mines[56];
		unsigned long long n_success;
		unsigned long long n_fail;
};

PhilGame.cpp:

#include "PhilGame.h"

void PhilGame::init()
{
	srand(time(NULL));

	for (int i = 0; i < 56; i++)
	{
		mines[i] = false;
	}
	mines[2] = true;
	mines[5] = true;
	mines[8] = true;
	mines[11] = true;
	mines[14] = true;
	mines[16] = true;
	mines[19] = true;
	mines[24] = true;
	mines[29] = true;
	mines[33] = true;
	mines[35] = true;
	mines[36] = true;
	mines[38] = true;
	mines[41] = true;
	mines[44] = true;
	mines[46] = true;

	n_success = 0;
	n_fail = 0;
}

void PhilGame::calculate()
{
	system("CLS");
	cout << "BRUTE FORCE GO!" << endl;
	init();

	solve(0);

	system("CLS");
	cout << "CALCULATED IT ALL!!!" << endl;
	cout << n_fail + n_success << " Games played!" << endl;
	cout << "Success        : " << n_success << endl;
	cout << "Fails          : " << n_fail << endl;
	cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
	cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
	system("PAUSE");
}

void PhilGame::estimate(unsigned long long n)
{
	system("CLS");
	cout << "Guessing the Probability..." << endl;
	init();

	int sum;

	if (n == -1) // FÜR IMMER!!
	{
		int j = 0;
		while (true)
		{
			j++;
			for (int i = 0; i < 100000000; i++)
			{
				sum = 0; // Startfeld
				while (true) // Solange bis Abbruch
				{
					if (mines[sum]) // Ist Minenfeld?
					{
						n_fail++; // Ein gescheitertes Spiel!
						break; // Abbrechen
					}
					else if (sum > 49) // Schon im Ziel?
					{
						n_success++; // Ein erfolgreiches Spiel!
						break; // Abbrechen
					}
					else
					{
						sum += 1 + (rand() % 6); // Sonst Würfelzahl draufaddieren
					}
				}
			}
			system("CLS");
			cout << "Guessing the Probability..." << endl;
			cout << j << " Hundred Million Games played" << endl;
			cout << "Success        : " << n_success << endl;
			cout << "Fails          : " << n_fail << endl;
			cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
			cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
		}
	}

	for (unsigned long long j = 0; j < n; j++)
	{
		for (int i = 0; i < 100000000; i++)
		{
			sum = 0;
			while (true)
			{
				if (mines[sum])
				{
					n_fail++;
					break;
				}
				if (sum > 49)
				{
					n_success++;
					break;
				}
				sum += 1 + rand() % 6; // 1 bis 6
			}
		}
		system("CLS");
		cout << "Guessing the Probability..." << endl;
		cout << j + 1 << " of " << n << " Hundred Million Games played" << endl;
		cout << "Success        : " << n_success << endl;
		cout << "Fails          : " << n_fail << endl;
		cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
		cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
	}

	system("CLS");
	cout << "Done with Guessing!" << endl;
	cout << n << " Hundred Million Games played!" << endl;
	cout << "Success        : " << n_success << endl;
	cout << "Fails          : " << n_fail << endl;
	cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
	cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
	system("PAUSE");
}

void PhilGame::solve(int sum)
{
	if ((n_fail + n_success) % 100000000 == 0)
	{
		system("CLS");
		cout << (n_fail + n_success)/100000000 << " Hundred Million Games played!" << endl;
	}

	//system("CLS");
	//cout << "Stehe auf Feld " << sum << endl;

	if (mines[sum]) // Ist ein Minenfeld?
	{
		//cout << sum << " ist eine Mine!" << endl;
		//system("PAUSE");
		n_fail++; // Ein gescheitertes Spiel!
		return; // Funktion abbrechen
	}
	//cout << sum << " ist KEINE Mine" << endl;

	if (sum > 49) // Schon im Ziel?
	{
		//cout << sum << " ist im Ziel!" << endl;
		//system("PAUSE");
		n_success++; // Ein erfolgreiches Spiel!
		return; // Funktion abbrechen
	}
	//cout << sum << " ist noch nicht im Ziel!" << endl;
	//system("PAUSE");

	for (int i = 1; i < 7; i++) // Ansonsten mit allen Würfelmöglichkeiten weiter probieren
	{
		solve(sum + i);
	}
}

[Bashar]

Der Durchrechnungsansatz generiert, nachdem er eine Mine angetroffen hat, keine weiteren Pfade ab dieser Stelle. Ganz krass deutlich wird das, wenn du ein Minenfeld nimmst, das nur eine Mine, nämlich auf Feld 1 (direkt nach dem Startfeld), enthält. Dann bekommst du 1 Fehlschlag und viele Erfolge. Das zufällige Ausprobieren von Pfaden sollte dagegen ungefähr 1/6 Fehlschläge ergeben, das ist die Wahrscheinlichkeit, beim ersten Würfeln eine 1 zu würfeln.

[tobias.voelk@t-online.de]

Bashar schrieb:

Der Durchrechnungsansatz generiert, nachdem er eine Mine angetroffen hat, keine weiteren Pfade ab dieser Stelle. Ganz krass deutlich wird das, wenn du ein Minenfeld nimmst, das nur eine Mine, nämlich auf Feld 1 (direkt nach dem Startfeld), enthält. Dann bekommst du 1 Fehlschlag und viele Erfolge. Das zufällige Ausprobieren von Pfaden sollte dagegen ungefähr 1/6 Fehlschläge ergeben, das ist die Wahrscheinlichkeit, beim ersten Würfeln eine 1 zu würfeln.

Ach Du... DU HAST RECHT!!! Wie konnte ich SO blöd sein?? xD
WIE KONNTE ICH SO BLÖD SEIN?????
Es war nicht der Code... Es war Mathematik.
Und das von mir mit 14 Punkte Abi und DMV-Preis -,-
Schande über mich!

Danke für eure Hilfe!
Case cleared!

[Tobs40]

Dank euch funktioniert nun alles.

Für das vorhin erwähnte Spiel ergibt sich nun folgendes:
11.305.116.961 mögliche Spielverläufe
davon gewinnen 10767922632 (ca.95,25%)
und verlieren 537194329 (ca. 4,75%)
DAVON DARF MAN ABER KEINEN TRUGSCHLUSS AUF DIE GEWINNCHANCHE ZIEHEN!!!

Gewinnchanchen:
Durch Spielen von 438,4 Milliarden Runden: 0,392822...%
Durch exaktes Ausrechnen: 0,391759...%
--> d.h. bei 1000 Runden, würde man im Schnitt 4 gewinnen.

Idee die Gewinnchanche zu berechnen:
Man stelle sich das Spiel als Baum der Spielverläufe vor. Nun muss man nur an jedem Knoten die Wahrscheinlichkeit ausrechnen, bis zu diesem Knoten und danach auf eine Mine zu kommen. Diese Minenwahrscheinlichkeiten muss man dann nur noch in einer Variable aufsummieren --> Das ist die Chanche zu scheitern
--> 1-Chanche zu Scheitern = Gewinnchanche

Danke für eure Hilfe!

Hier ist das fertige Programm. Wer selbst Varianten des Spiels ausprobieren möchte, kann die Anzahl der Felder durch Änderung der Konstante l anpassen und die Minen in der Funktion init() anders setzen.

main.cpp

#include "PhilGame.hpp"
using namespace std;

int main()
{
	PhilGame pg = PhilGame();
	int eingabe;
	while (true)
	{
		system("CLS");
		cout << "Calculating Phillips Game! Copyright by Tobias Völk :P" << endl;
		cout << "1 - GET HOW MANY WAYS TO PLAY!" << endl;
		cout << "2 - PLAYING N HUNDRED MILLION RANDOM GAMES (-1 for endless)" << endl;
		cout << "3 - CALCULATE CHANCHES!" << endl;
		cin >> eingabe;
		system("CLS");
		if (eingabe == 1)
		{
			pg.getNumberOfPossibleWays();
		}
		else if (eingabe == 2)
		{
			cout << "How many Hundred Million Games: ";
			cin >> eingabe;
			pg.estimate(eingabe);
		}
		else
		{
			pg.calculate();
		}
	}
	return 0;
}

PhilGame.hpp:

#include <iostream>
#include <time.h>
using namespace std;

const int l = 49; // Anzahl Felder = "Länge l"

class PhilGame
{
	public:
		void init();
		void calculate();
		void getNumberOfPossibleWays();
		void solve(int sum, long double prev_prob);
		void getWays(int sum);
		void estimate(unsigned long long n);
	private:
		bool mines[l+7];
		unsigned long long n_success;
		unsigned long long n_fail;
		long double prob;
		unsigned long long n_ways;
};

PhilGame.cpp:

#include "PhilGame.hpp"

void PhilGame::init()
{
	srand(time(NULL));

	for (int i = 0; i < l+7; i++)
	{
		mines[i] = false;
	}

	mines[2] = true;
	mines[5] = true;
	mines[8] = true;
	mines[11] = true;
	mines[14] = true;
	mines[16] = true;
	mines[19] = true;
	mines[24] = true;
	mines[29] = true;
	mines[33] = true;
	mines[35] = true;
	mines[36] = true;
	mines[38] = true;
	mines[41] = true;
	mines[44] = true;
	mines[46] = true;

	n_success = 0;
	n_fail = 0;

	prob = 0.0;
}

void PhilGame::estimate(unsigned long long n)
{
	system("CLS");
	cout << "Guessing the Probability..." << endl;
	init();

	int sum;

	if (n == -1) // FÜR IMMER!!
	{
		int j = 0;
		while (true)
		{
			j++;
			for (int i = 0; i < 100000000; i++)
			{
				sum = 0; // Startfeld
				while (true) // Solange bis Abbruch
				{
					if (mines[sum]) // Ist Minenfeld?
					{
						n_fail++; // Ein gescheitertes Spiel!
						break; // Abbrechen
					}
					else if (sum > l) // Schon im Ziel?
					{
						n_success++; // Ein erfolgreiches Spiel!
						break; // Abbrechen
					}
					else
					{
						sum += 1 + (rand() % 6); // Sonst Würfelzahl draufaddieren
					}
				}
			}
			system("CLS");
			cout << "Guessing the Probability..." << endl;
			cout << j << " Hundred Million Games played" << endl;
			cout << "Success        : " << n_success << endl;
			cout << "Fails          : " << n_fail << endl;
			cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
			cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
		}
	}

	for (unsigned long long j = 0; j < n; j++)
	{
		for (int i = 0; i < 100000000; i++)
		{
			sum = 0;
			while (true)
			{
				if (mines[sum])
				{
					n_fail++;
					break;
				}
				if (sum > l)
				{
					n_success++;
					break;
				}
				sum += 1 + rand() % 6; // 1 bis 6
			}
		}
		system("CLS");
		cout << "Guessing the Probability..." << endl;
		cout << j + 1 << " of " << n << " Hundred Million Games played" << endl;
		cout << "Success        : " << n_success << endl;
		cout << "Fails          : " << n_fail << endl;
		cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
		cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
	}

	system("CLS");
	cout << "Done with Guessing!" << endl;
	cout << n << " Hundred Million Games played!" << endl;
	cout << "Success        : " << n_success << endl;
	cout << "Fails          : " << n_fail << endl;
	cout << "Chanche Winning: " << (float)n_success / (n_fail + n_success) * 100 << "%" << endl;
	cout << "Chanche Losing : " << (float)n_fail / (n_fail + n_success) * 100 << "%" << endl;
	system("PAUSE");
}

void PhilGame::calculate()
{
	system("CLS");
	cout << "Calculating Chanches..." << endl;
	init();

	solve(0, 1.0);

	system("CLS");
	cout << "CALCULATED IT ALL!!!" << endl;
	long double anti_prob = 1.0 - prob;
	cout << "Chanche Winning: " << (long double)anti_prob * 100 << "%" << endl;
	cout << "Chanche Losing : " << (long double)prob * 100.0 << "%" << endl;
	system("PAUSE");
}

void PhilGame::solve(int sum, long double prev_prob)
{
	if (sum > l)
	{
		return;
	}

	// Minen nach diesem Zug zählen
	long double num_mines = 0.0;
	for (int i = 1; i < 7; i++)
	{
		if (mines[sum+i])
		{
			num_mines++;
		}
	}

	long double this_prob = ((long double)num_mines / 6.0)*prev_prob; // Wahrscheinlichkeit jetzt auf Mine zu latschen
	prob += this_prob; // zu Gesamtwahrscheinlichkeit addieren (auf Mine quatschen)

	// weiter
	for (int j = 1; j < 7; j++)
	{
		if (!mines[sum + j])
		{
			solve(sum + j, prev_prob/6.0);
		}
	}
}

void PhilGame::getNumberOfPossibleWays()
{
	system("CLS");
	cout << "Counting possible Ways..." << endl;
	init();

	getWays(0);

	system("CLS");
	cout << "Counting Done!" << endl;
	cout << n_ways << " possible Games" << endl;
	cout << n_fail << " possible failed Games " << (float)n_fail/n_ways*100 << " %" << endl;
	cout << n_ways - n_fail << " possible successful Games " << (float)(n_ways-n_fail) / n_ways * 100 << " %" << endl;
	system("PAUSE");
}

void PhilGame::getWays(int sum)
{
	if (sum > l)
	{
		n_ways++;
		return;
	}
	if (mines[sum])
	{
		n_ways++;
		n_fail++;
		return;
	}
	for (int i = 1; i < 7; i++)
	{
		getWays(sum + i);
	}
}

[Bashar]

Das Minenfeld um 7 größer zu machen ist ein ziemlich übler Hack. Überschreite doch einfach die Arraygrenzen nicht, indem du zuerst prüfst, ob sum >= l ist, und dann erst mine[sum].

[tobias.voelk@t-online.de]

Bashar schrieb:

Das Minenfeld um 7 größer zu machen ist ein ziemlich übler Hack. Überschreite doch einfach die Arraygrenzen nicht, indem du zuerst prüfst, ob sum >= l ist, und dann erst mine[sum].

Danke für den Tipp. So müsste ich am Ende viele Funktionsaufrufe einsparen können. Leider war die Geschwindigkeit nach der Umsetzung nicht großartig besser. Vielleicht hat Visual Studio da schon vorher was optimiert.

Naja, aber danke, das Motiv wird mir sicher noch öfters begegnen

[Tobs40]

Hilfe Leute!

Ich habe den starken Verdacht, dass mein Programm selbst durch die Verwendung des Datentyps "long double" eine große Anzahl extrem kleiner Werte verschluckt und deshalb das Ergebnis leicht verfälscht. Nach dem kläglich gescheiteren Versuch selbst eine Klasse zu schreiben, die Zahlen als Strings speichert und verrechnet, wende ich mich nun an euch.

Ich muss Zahlen speichern, die im Extremfall so klein wie 1/6^50 sind o.O (Das müssten 39 Kommastellen sein)
Brauche also einen Datentyp der solche Zahlen PERFEKT multipliziert und addiert. Der auch Perioden und schräge Brüche zwischendurch nicht vereinfacht. Hat jemand schonmal sowas geschrieben? Oder gibt es das schon?

Im Prinzip muss ich eine MENGE Zahlen die das Produkt aus je bis zu 50 Faktoren von 1/6; 2/6; ...; 6/6 sind, addieren. Dabei darf mir keine einzige Kommastelle verfälscht werden.

Mit freundlichen Grüßen: HELFT MIR!!!

Tobias

[SeppJ]

Da hilft dir auch kein String (außer du rechnest in einem System mit mindestens den Primteilern 2 und 3), dafür hilft aber Denken und Mathematik: Rechne mit Brüchen. Oder gleich mit Sechsteln.

[tobias.voelk@t-online.de]

SeppJ schrieb:

Da hilft dir auch kein String (außer du rechnest in einem System mit mindestens den Primteilern 2 und 3), dafür hilft aber Denken und Mathematik: Rechne mit Brüchen. Oder gleich mit Sechsteln.

Doch, String hätte geholfen. Wollte ja eine Zahlenklasse schreiben, mit der man dann beliebig große/kleine Zahlen speichern und verrechnen kann. Also sowas wie “0,1230000000000000000000003141592...“, das halt nichtmal in long double passt.
Was meinst Du genau mit 2 und 3 als Primteilern? Klingt interessant
Ich habe auch daran gedacht, die Zahlen als großen Bruch zu schreiben, um spätere Ungenauigkeiten einzuschränken. So nach dem Motto: 2x6x3x5x.../6 hoch <Anzahl Faktoren im Nenner> Aber vermeiden lassen sie sich nicht ganz, oder rechnen die Operatoren intern mit beliebiger Genauigkeit? Hab ja zwischendrin wieder falsche Ergebnisse, die ich addiere Die sind so klein, dass sie als 0.0 gezählt werden, aber es sind so viele, dass sie das Ergebnis verfälschen. Hast Du noch Ideen für Mathekniffe?