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

[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?