Zu großes Array -> Absturz?

hustbaer

Wenn du nicht gross rechnen willst nimm doch einfach so ein Array.
Pack es in eine Struktur, und erzeuge die dann dynamisch:

struct foo
{
short a[13][13][13][13][13][13][13]; // das [1] hinten brauchst du nicht
};

void bar()
{
    std::auto_ptr<foo> f(new foo);
    f->a[1][2][3][4][5][6][7] = 123;
}

Ist nicht ohne Vorteile, da du so die Optimierung der Indexberechnung ganz dem Compiler überlassen kannst.
Und mach dich schonmal auf einige Stunden bis Tage Laufzeit gefasst wenn du da ein paar Milliarden mal zugreifen willst, zumindest wenn die Zugriffe grösstenteils nicht linear (fortlaufend) erfolgen

hustbaer schrieb:

Ist nicht ohne Vorteile, da du so die Optimierung der Indexberechnung ganz dem Compiler überlassen kannst.

meinst du der bekommt das so gut hin?

Kannst du mal verraten, wofür das gebraucht wird? Vielleicht gibts dafür ja ne bessere struktur.

tastenstreichler schrieb:

Kannst du mal verraten, wofür das gebraucht wird? Vielleicht gibts dafür ja ne bessere struktur.

Ja, ich versuche für das Poker spiel Texas Holdem bei zwei vorgegebenen Starthänden die exakte Wahrscheinlichkeit zu berechnen mit der man gewinnt wenn jeder bis zum ende dabei bleibt.
Jeder Mitspieler hat hierbei immer seine zwei eigenen Karten und die fünf Gemeinschaftskarten um das beste Blatt zu bilden.
Aus dem grund nehme ich ein Array welches sieben Dimensionen hat, was die sieben Karten für jeden Spieler darstellen aus denen er sein Blatt bilden kann.

Die Idee wäre nun das ich für alle siebener Kombinationen einen Wert gespeichert habe welcher um so höher ist je besser das Blatt.
Ansonsten müßte ich nämlich bei jedem Blatt immer auf paare, drillinge, straßen usw. überprüfen.

Wie gesagt ist durch die Kombinationsvielfallt die Geschwindigkeit das größte Problem.

pumuckl

Dazu brauchst du aber doch nicht alle Kombinationen zu speichern! Ich wuerds folgendermassen angehn (mehr oder weniger brute force):

- Codiere die Karten mit den Zahlen 1-52
- verteile dein Startblatt
- Ueberlege dir, wie man in einer einfachen Schleife alle Kombinationen von 5 Karten durchlaufen kann. Dabei koennen die 5 Karten geordnet bleiben, das macht die Schleife kleiner und du bearbeitest nicht mehrfach die gleiche kombi.
- ueberpruefe fuer jeden Schleifendurchlauf, ob in der 5er-Kombi die du grade untersuchst eine Karte aus dem Startblatt enthalten ist (wenn ja, ist die kombi nicht moeglich udn wird uebersprungen)
- ueberpruefe, wer die hoechste Hand hat und gib ihm einen "Gewinnpunkt"

wenn du die Schleife einmal komplett durch hast sagt dir die Verteilung der Gewinnpunkte wie die Gewinnchancen fuer die einzelnen Spieler stehen.

An Speicherplatz brauchst du dafuer also
- nSpieler * 2 byte fuer die Starthand
- 5 byte fuer die Schleifenvariablen
- ein paar byte fuer die punkte etc,

aber 130mb soeicher brauchst du nie und nimmer

pumuckl schrieb:

- ueberpruefe fuer jeden Schleifendurchlauf, ob in der 5er-Kombi die du grade untersuchst eine Karte aus dem Startblatt enthalten ist (wenn ja, ist die kombi nicht moeglich udn wird uebersprungen)

Ich bin mir jetzt nicht ganz sicher ob ich das ganze richtig verstanden habe.
Was ich berechnen will ist folgende Situation:
In meinen Händen sind zb Ass-Pik und Ass-Herz. Aus dieser Startsituation, ohne irgend etwas anderes zu kenne, möchte ich nun meine gewinn Chancen berechnen wenn alle bis zum Ende durchspielen. Somit muß ich auch die Karten der Gegner durch alle Möglichkeiten laufen lassen.

pumuckl schrieb:

- ueberpruefe, wer die hoechste Hand hat und gib ihm einen "Gewinnpunkt"

Genau hierfür benötige ich die 130MB "Datenbank" im Speicher. Diese Überprüfung ist nämlich nicht gerade Trivial und erfolgt zb bei 3 Mitspielern pro Kartenvariation viermal. (Die 130 Millionen variationen im speicher stehen in diesem Fall gegen 37 Milliarden Karten variationen welche überprüft werden)

pumuckl

hmm. ok hatte das so verstanden dass du die Karten der anderen auch kennst. dafuer hab ich n kleines Programm geschrieben, wo allerdings noch Kleinigkeiten fehlen:

typedef unsigned char Karte;
typedef unsigned char uchar;

class StartHand
{
  uchar nSp;
  Karte* karten;
public:
  StartHand (uchar nSpieler) : nSp(nspieler), karten(new Karten[2*nSpieler]) {}
  ~StartHand () {delete[] karten;}
  Karte* operator[] (uchar n) {return &karten[2*n];}
  bool Enthaelt(Karte k) const {
    for(uchar i=0; i < 2*nSp; ++i) if(karten[i] == k) return true;
    return false;
  }
  //setze die Karten fuer Spieler (Nr 0 bis nSp-1)
  void Setze(uchar spielerNr, Karte karte1, Karte karte2) { 
    karten[2*spielerNr] = karte1;
    karten[2*spielerNr+1] = karte2;
  }
  uchar NSpieler() const  {return nSp;}
private:
  StartHand& operator=(const StartHand& sh);
};

uchar Spielerzahl() {
  /* z.B. von Konsole einlesen */
}

void Belegestarthand(StartHand& shand) {
  /* z.B ueber Konsole mit shand.setze() */
}

int Bewertekarten(Karte k1, Karte k2, Karte k3, Karte k4, Karte k5, Karte k6, Karte k7) {
  /* gib eine Wertung ab => bessere Karten bessere Wertung */
}

int main() {
  StartHand starthand(Spielerzahl());
  Belegestarthand(starthand);

  Karte karte1, karte2, karte3, karte4, karte5; //5 karten fuer flop, turn und river
  unsigned int punkte[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //laut wikipedia max 11 Spieler
  int bewertung[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

  //jetzt alle kombinationen durchgehn:
  //bei geordneten Karten ist die hoechste kombination 48, 49, 50, 51, 52
  for (karte1 = 1; karte1 < 49; ++karte1) {
    if (starthand.Enthaelt(karte1)) continue; //test ob karte in Starthand vorhanden
    for (karte2 = karte1+1; karte2 < 50; ++karte2) {
      if (starthand.Enthaelt(karte2)) continue;
      for (karte3 = karte2+1; karte3 < 51; ++karte2) {
        if (starthand.Enthaelt(karte3)) continue;
        for (karte4 = karte3+1; karte4 < 52; ++karte4) {
          if (starthand.Enthaelt(karte4)) continue;
          for (karte5 = karte4+1; karte5 < 53; ++karte5) {
            if (starthand.Enthaelt(karte5)) continue;

            for (int i = 0; i < starthand.NSpieler(); ++i) {
              bewertung[i] = Bewertekarten(starthand[i][0], starthand[i][1], 
					   karte1, karte2, karte3, karte4, karte5);
            }
            /* gib dem Spieler der die beste Wertung hat einen Gewinnpunkt*/
          }
        }
      }
    }
  }

  // fuer n Spieler gibt es 
  // (52-2*n)!/[(47-2*n)!*5!] Kombinationen:
  // 2 Spieler: 1712304 Kombinationen
  // 3 Spieler: 1370754 Kombinationen
  // 4 Spieler: 1086008 Kombinationen
  // usw.
  // teile die Punkte durch die Zahl der Kombinationen um die chance herauszufinden

  double gewinnchance[11];
  for (int i = 0; i < starthand.NSpieler(); ++i) {
    gewinnchance[i] = 120.0; //5!
    gewinnchance[i] *= punkte[i];
    for (int j = 0; j <5; ++j) gewinnchance /= (52-j-2*starthand.NSpieler());
  }

  /* gewinnchancen ausgeben */
}

Das programm muesste dann in deinem Fall noch so weit abgeaendert werden, dass du auch noch Schleifen ueber die Anfangskarten der anderen Spieler laufen laesst.

Genau hierfür benötige ich die 130MB "Datenbank" im Speicher. Diese Überprüfung ist nämlich nicht gerade Trivial und erfolgt zb bei 3 Mitspielern pro Kartenvariation viermal. (Die 130 Millionen variationen im speicher stehen in diesem Fall gegen 37 Milliarden Karten variationen welche überprüft werden)

nein, dafuer brauchst du keine riesige Datenbank. Du musst auch nicht alle moeglichen Kartenkombinationen abgespeichert haben. Vergib, wie oben angedeutet, einfach Punkte fuer ein Blatt aus 7 Karten, beispielsweise:

int Bewertekarten(/*karte 1-7*/) {
  int wertung = 0;
  if (werung = royal_flush(/*karten*/) return wertung;
  if wertung = street_flush(/*karten*/) return wertung;
  //...
  return high_card(/*karten*/);
}

int high_card(/*karten*/) {/* gib eine Wertung von 1-13 */}
int one_pair(/*karten*/) {/*wenn ein paar, dann Wertung von 14-26, sonst 0*/}
int two_pair(/*karten*/) {/*hier gibts mehr verschiedene Wertungen*/}
int royal_flush(/*karte 1-7*/) {/*die hoechste Wertung */}

Du reihst die Tests einfach aneinander und kodierst die Wertungen hart rein. Das braucht aber immernoch keine riesen Datenbank...

kleine Anmerkung: deine Datenbank wuerde zum Beispiel alle 4324 Royal-Flush Moeglichkeiten einzeln auflisten (die gibts ja in 4 farben mit hunderten Kombinationen fuer die Karten 6 udn 7), obwohl all diese Kombinationen voellig gleichwertig sind.

pumuckl schrieb:

//jetzt alle kombinationen durchgehn:
  //bei geordneten Karten ist die hoechste kombination 48, 49, 50, 51, 52
  for (karte1 = 1; karte1 < 49; ++karte1) {
    if (starthand.Enthaelt(karte1)) continue; //test ob karte in Starthand vorhanden
    for (karte2 = karte1+1; karte2 < 50; ++karte2) {
      if (starthand.Enthaelt(karte2)) continue;
      for (karte3 = karte2+1; karte3 < 51; ++karte2) {
        if (starthand.Enthaelt(karte3)) continue;
        for (karte4 = karte3+1; karte4 < 52; ++karte4) {
          if (starthand.Enthaelt(karte4)) continue;
          for (karte5 = karte4+1; karte5 < 53; ++karte5) {
            if (starthand.Enthaelt(karte5)) continue;

            for (int i = 0; i < starthand.NSpieler(); ++i) {
              bewertung[i] = Bewertekarten(starthand[i][0], starthand[i][1], 
					   karte1, karte2, karte3, karte4, karte5);
            }
            /* gib dem Spieler der die beste Wertung hat einen Gewinnpunkt*/
          }
        }
      }
    }
  }
  // fuer n Spieler gibt es 
  // (52-2*n)!/[(47-2*n)!*5!] Kombinationen:
  // 2 Spieler: 1712304 Kombinationen
  // 3 Spieler: 1370754 Kombinationen
  // 4 Spieler: 1086008 Kombinationen

Ja, wenn nur die Karten auf dem Tisch sich ändern wäre die Berechnung noch mehr oder minder gut realisierbar. Die for schleifen würde hier bis zur Bewertungs ebene gut 300 Millionen mal aufgerufen (52*51*50*49*48 - pro Spieler!).

pumuckl schrieb:

nein, dafuer brauchst du keine riesige Datenbank. Du musst auch nicht alle moeglichen Kartenkombinationen abgespeichert haben. Vergib, wie oben angedeutet, einfach Punkte fuer ein Blatt aus 7 Karten, beispielsweise:
int Bewertekarten(/*karte 1-7*/) {
  int wertung = 0;
  if (werung = royal_flush(/*karten*/) return wertung;
  if wertung = street_flush(/*karten*/) return wertung;
  //...
  return high_card(/*karten*/);
}

int high_card(/*karten*/) {/* gib eine Wertung von 1-13 */}
int one_pair(/*karten*/) {/*wenn ein paar, dann Wertung von 14-26, sonst 0*/}
int two_pair(/*karten*/) {/*hier gibts mehr verschiedene Wertungen*/}
int royal_flush(/*karte 1-7*/) {/*die hoechste Wertung */}

Ok, bleiben wir einmal bei deiner einfacheren Version. Wenn ich zehn Spieler nehme wären dies bereits 3 Milliarden aufrufe dieser Bewertungsfunktion. Das Hauptproblem weshalb ich aber noch immer glaube das die "Datenbank" notwendig ist:
Du übergibst 7 Karten, die Bewertung in Texas Holdem erfolgt aber nur nach den 5 besten(!) Karten. Das heißt ich bekomme eventuell ein royal flush als Bewertung zurück, obwohl meine 2 Karten die ich in den Händen halte garnicht im Royal Fulsh drin sind. (weil das Flush auf dem Tisch liegt)

pumuckl schrieb:

kleine Anmerkung: deine Datenbank wuerde zum Beispiel alle 4324 Royal-Flush Moeglichkeiten einzeln auflisten (die gibts ja in 4 farben mit hunderten Kombinationen fuer die Karten 6 udn 7), obwohl all diese Kombinationen voellig gleichwertig sind.

Grundlegend richtig, wie oben beschrieben hat dies jedoch mit der Performance zu tun und nach dem was ich bis jetzt gesehen habe scheint es die beste möglichkeit zu sein die mir momentan einfällt. (Die 4324 stimmen übringens nicht ganz. Ich vernachlässige die 4 Farben weil die Datenbank ansonsten astronomische ausmaße annehmen würde.)

pumuckl

shamanu schrieb:

Ja, wenn nur die Karten auf dem Tisch sich ändern wäre die Berechnung noch mehr oder minder gut realisierbar. Die for schleifen würde hier bis zur Bewertungs ebene gut 300 Millionen mal aufgerufen (52*51*50*49*48 - pro Spieler!).

nicht ganz, da die letzten 5 Karten immer geordnet uebergeben werden gibts dafuer maximal 1,7 Mio Aufrufe pro Spieler. Immernoch besser so oft eine Testfunktion aufzurufen als so oft durch deine ganze Datenbank zu krabbeln um die richtige Kombination zu finden.

Du übergibst 7 Karten, die Bewertung in Texas Holdem erfolgt aber nur nach den 5 besten(!) Karten. Das heißt ich bekomme eventuell ein royal flush als Bewertung zurück, obwohl meine 2 Karten die ich in den Händen halte garnicht im Royal Fulsh drin sind. (weil das Flush auf dem Tisch liegt)

Stimmt. aber wenn der Royal flush auf dem Tisch liegt, hat jeder Spieler einen Royal flush. Man muss seine Handkarten nicht einbringen, daher ist das vollkommen richtiges Verhalten.

(Die 4324 stimmen übringens nicht ganz. Ich vernachlässige die 4 Farben weil die Datenbank ansonsten astronomische ausmaße annehmen würde.)

hm. wenn du farben vernachlaessigst dann kannst du einen royal flush von einer normalen strasse nicht unterscheiden...

pumuckl schrieb:

nicht ganz, da die letzten 5 Karten immer geordnet uebergeben werden gibts dafuer maximal 1,7 Mio Aufrufe pro Spieler. Immernoch besser so oft eine Testfunktion aufzurufen als so oft durch deine ganze Datenbank zu krabbeln um die richtige Kombination zu finden.

Das mit den letzten 5 Karten ist mir nicht ganz klar, wie kommst du auf 1,7 Millionen Aufrufe?
Ich will die Datenbank nicht durchsuchen sondern immer gleich an die richtige Position springen.

Stimmt. aber wenn der Royal flush auf dem Tisch liegt, hat jeder Spieler einen Royal flush. Man muss seine Handkarten nicht einbringen, daher ist das vollkommen richtiges Verhalten.

Ok, auf dem Tisch liegt ein drilling. Woher erhalte ich die Information welcher den besten Kicker hat?

hm. wenn du farben vernachlaessigst dann kannst du einen royal flush von einer normalen strasse nicht unterscheiden...

Ja, ich kann generell keinen Flush erkennen. Die "kleinen" probleme kommen aber später...

pumuckl

shamanu schrieb:

Das mit den letzten 5 Karten ist mir nicht ganz klar, wie kommst du auf 1,7 Millionen Aufrufe?

48*47*46*45*44 / 1*2*3*4*5 = ca. 1.7 millionen (genaue Zahl steht in meinem code oben). Denn: dadurch dass fuer die zwei Spieler schon jeweils 2 karten auf der Hand haben kommen fuer den Tisch nichtmehr ganz so viele verschiedene Kombinationen in Frage. und da die Kombination 12345 und 52341 und 31245 usw. alle das selbe ergebnis liefern, habe ich das dadurch ausgeschlossen, dass karte2 groesser ist als karte1 usw. (sieht man auch im code der for-schleifen)
deshalb muss man die Zahl der moeglichen Kombinationen durch die Zahl der moeglichen Permutationen teilen und kommt schon einiges besser bei weg.

Ok, auf dem Tisch liegt ein drilling. Woher erhalte ich die Information welcher den besten Kicker hat?

Gutes Argument. Ich hatte ja angedeutet, dass man schon fuer zwei paare eine groessere Wertungs-range hat. vielleicht gibt man mit der Funktion einfach ein struct aus 3 oder 4 werten wieder. Der erste bezeichnet die Art der Hand (royal flush, full house etc), der zweite die relevante Kartenhoehe (obs jetzt n Koenigsdrilling oder n Damen drilling ist - Kicker beim Drilling brauchts naemlich nicht) und der dritte den kciker z.B. beim Paar. Fuer son ergebnisstruct n vergleichsoperator zu schreiben sollte recht fix gehn.

Ja, ich kann generell keinen Flush erkennen. Die "kleinen" probleme kommen aber später...

Hm. beweise dass das Problem nur ein kleines ist *g* vorher solltest dus nicht vernachlaessigen, sonst raufst du dir hinterher die Haare weil dus etwas gruendlicher nochmal machen musst

pumuckl

Sodele, hab das Ganze mal bissl umgeschrieben, jetzt hast dus wenn du deine karten kennst, die der anderen aber nicht:

typedef unsigned char Karte;
typedef unsigned char uchar;

struct Wertung {
  uchar artderhand;
  uchar k1;
  uchar k2;
  uchar k3;
}

bool operator<(Wertung w1, Werung w2) {
  //da die werte im struct nicht groesser als 50 werden sollten mach ichs mir leicht
  unsigned int i1 = w1.k3 + 50*w1.k2 + 250* w1.k1 + 1250*w1.artderhand;
  unsigned int i2 = w2.k3 + 50*w2.k2 + 250* w2.k1 + 1250*w2.artderhand;
  return i1<i2;
}

//einige globale Variablen (ich weiss, ihhh)
Karte spielerkarten[20] = {0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0};
Karte meinekarten[2];
std::set<Karte> handkarten;
uchar nspieler;
long int meinepunkte, gegenpunkte;

void Lesespielerzahl() {
  /* z.B. von Konsole einlesen */
  nspieler = 4;
}

void Belegestarthand() {
  /* z.B ueber Konsole */
  meinekarten[0] = 13;
  meinekarten[1] = 22;
}

Wertung Bewertekarten(Karte k1, Karte k2, Karte k3, Karte k4, Karte k5, Karte k6, Karte k7) {
  /* gib eine Wertung ab => bessere Karten bessere Wertung */
}

void bigloop(uchar nrecurs, Karte minkarte1) {
  if (nrecurs >= 0) { // es wird 2 for-schleifen pro spieler geben
    ///////////////////////////////////////////// 
    // in spielerkarten werden die Karten der Spieler abgelegt, so dass karten[0] 
    // und karten[1] spieler0 gehoeren usw.
    // Erstens: Die Karten in Spielerhand sind geordnet, also karten[2*n] < karten[2*n+1]
    // Zweitens: permutationen der Spieler sind ohne Belang, daher hat spieler0 eine
    // groessere erste Karte als Spieler1 usw. also karten[2*n] < karten[2*(n-1)]
    // nrecurs gibt die anzahl der rekursionen wieder, bzw die Spielernummer
    for(Karte karte1 = minkarte1; karte1 < 54-(2*nrecurs); ++karte1) {
      if (handkarten.count(karte1) != 0) continue;
      if (!handkarten.insert(karte1).second) throw "?";
      spielerkarten[2*(nrecurs-1)] = karte1;
      for (Karte karte2 = karte1+1; karte2 < 55-(2*nrecurs); ++karte2) {
	if (handkarten.count(karte2) != 0) continue;
	spielerkarten[2*(nrecurs-1)+1] = karte2;
	if (!handkarten.insert(karte2).second) throw "?";

	//schleife fuer den naechsten Spieler bzw. fuer den tisch
	bigloop(nrecurs-1, karte1+1);

	handkarten.erase(karte2);
      }
      handkarten.erase(karte1);
    }
  }
  else { //nrecurs ==0 => tischkarten durchgehn
    Karte karte1, karte2, karte3, karte4, karte5;
    //jetzt alle kombinationen durchgehn:
    //bei geordneten Karten ist die hoechste kombination 48, 49, 50, 51, 52
    for (karte1 = 1; karte1 < 49; ++karte1) {
      if (handkarten.count(karte1) != 0) continue; //test ob karte in spielerhand vorhanden
      for (karte2 = karte1+1; karte2 < 50; ++karte2) {
	if (handkarten.count(karte2) != 0) continue;
	for (karte3 = karte2+1; karte3 < 51; ++karte2) {
	  if (handkarten.count(karte3) != 0) continue;
	  for (karte4 = karte3+1; karte4 < 52; ++karte4) {
	    if (handkarten.count(karte4) != 0) continue;
	    for (karte5 = karte4+1; karte5 < 53; ++karte5) {
	      if (handkarten.count(karte5) != 0) continue;
	      int meinewertung = Bewertekarten(karte1, karte2, karte3, karte4, karte5, meinekarten[0], meinekarten[1]);
	      meinepunkte++; //gehn wir mal davon aus dass wir gewonnen haben
	      for (int i = 0; i < nspieler; ++i) {
		int wertung = Bewertekarten(karte1, karte2, karte3, karte4, karte5, spielerkarten[2*i], spielerkarten[2*i+1]);
		if (wertung > meinewertung) { //war doch einer besser?
		  meinepunkte--;
		  gegenpunkte++;
		  break; //restliche spieler brauchen wir nichtmehr schauen
		}
	      }
	    }
	  }
	}
      }
    }

  }
}

int main() {
  Lesespielerzahl();

  Belegestarthand(meinekarten);
  handkarten.insert(meinekarten[0]);
  handkarten.insert(meinekarten[1]);

  meinepunkte = 0;
  gegenpunkte = 0;

  bigloop(nspieler, 1);

  double meinechance = 1.0*meinepunkte/(meinepunkte+gegenpunkte);
  //man koennte die Anzahl der schleifendurchgaenge auch berechnen, aber das wird haesslich...
}

Die rekursion sieht zwar erstmal etwas dicke aus, aber wenn dus dir Zeile fuer Zeile anschaust, wirds verstaendlich, denk ich mal. Wieviele Schleifendurchlaeufe das werden weiss ich so nicht, aber es sind verdammt viele. Aber immernoch weniger als wenn cih wirklich jede kombination mit allen moeglichen permutationen jeweils durchgehe

pumuckl schrieb:

48*47*46*45*44 / 1*2*3*4*5 = ca. 1.7 millionen (genaue Zahl steht in meinem code oben). Denn: dadurch dass fuer die zwei Spieler schon jeweils 2 karten auf der Hand haben kommen fuer den Tisch nichtmehr ganz so viele verschiedene Kombinationen in Frage. und da die Kombination 12345 und 52341 und 31245 usw. alle das selbe ergebnis liefern, habe ich das dadurch ausgeschlossen, dass karte2 groesser ist als karte1 usw. (sieht man auch im code der for-schleifen)
deshalb muss man die Zahl der moeglichen Kombinationen durch die Zahl der moeglichen Permutationen teilen und kommt schon einiges besser bei weg.

Ach so, Kombination ohne Zurücklegen mit 2 Spielern.
Wenn nun aber nur 2 Karten fix sind und 9 Mitspieler (18 Spielerkarten) sowie 5 Gemeinschaftskarten variabel sind wird auch bei nichtbeachtung der Reihenfolge die anzahl der Möglichkeiten viel zu groß.

Gutes Argument. Ich hatte ja angedeutet, dass man schon fuer zwei paare eine groessere Wertungs-range hat. vielleicht gibt man mit der Funktion einfach ein struct aus 3 oder 4 werten wieder. Der erste bezeichnet die Art der Hand (royal flush, full house etc), der zweite die relevante Kartenhoehe (obs jetzt n Koenigsdrilling oder n Damen drilling ist - Kicker beim Drilling brauchts naemlich nicht) und der dritte den kciker z.B. beim Paar. Fuer son ergebnisstruct n vergleichsoperator zu schreiben sollte recht fix gehn.

Das schreiben selbst schon, die Berechnung wird aber viel zu komplex da jede Wertberechnung einige schritte machen muß.

Hm. beweise dass das Problem nur ein kleines ist *g* vorher solltest dus nicht vernachlaessigen, sonst raufst du dir hinterher die Haare weil dus etwas gruendlicher nochmal machen musst

Ich habe bereits etwas im Hinterkopf das funktionieren könnte. Ich habe es nur noch nicht ganz durchgedacht.

Diese Datenbank geschichte ist ja eigentlich ein Kunstgriff da ich das Problem zuerst ähnlich wie du erklärst lösen wollte, dann jedoch über den enormen Berechnungsaufwand gestolpert bin...

asc

shamanu schrieb:

Ich habe bereits etwas im Hinterkopf das funktionieren könnte. Ich habe es nur noch nicht ganz durchgedacht.

Diese Datenbank geschichte ist ja eigentlich ein Kunstgriff da ich das Problem zuerst ähnlich wie du erklärst lösen wollte, dann jedoch über den enormen Berechnungsaufwand gestolpert bin...

Ich bin mal ganz naiv (das darf ich weil ich kein Mathematiker bin und von Poker, grad von dieser Variante nur eine sehr geringe Ahnung habe ;p):

Wieso sind überhaupt die anderen Spieler interessant? Ihre Hand ist ebenso unbekannt wie die Restkarten. Meines Erachtens ist die Wahrscheinlichkeit genauso hoch eine spezielle Karte aus dem Stapel zu bekommen (Bei 48 Karten und 2 Bekannten wohl um die 1:46).

Und welche Kombinationen noch theoretisch denkbar wären sollte mit deinen Karten doch auch bekannt sein (und endlich).

cu André

@pumuckl: Danke soweit einmal für die Hilfe, ich habe bereits einige Teile deines Codes übernommen und bis jetzt arbeiten sie gut.
Bei den verschachtelten for schleifen werde ich eventuell noch schauen müßen wieviel Performance die ständigen if Abfragen bei vielen Spielern kostet. Aber zuerst einmal schauen wie weit ich mit diesem Setting komme.

asc schrieb:

Wieso sind überhaupt die anderen Spieler interessant? Ihre Hand ist ebenso unbekannt wie die Restkarten. Meines Erachtens ist die Wahrscheinlichkeit genauso hoch eine spezielle Karte aus dem Stapel zu bekommen (Bei 48 Karten und 2 Bekannten wohl um die 1:46).

Bei Holdem erhält man nur 2 Karten zu begin. Es werden später nur noch gemeinschaftskarten auf dem Tisch aufgedeckt. Somit geht es nicht um die Wahrscheinlichkeit eine spezielle Karte zu erhalten.

Als Beispiel:
Ich erhalte zu beginn ein Damen Pärchen. Das einzige was für mich nun im ersten schritt relevant ist ist die Stärke dieser 2 Karten und die Anzahl der Spieler.
Also das Damenpärchen hat zb gegen 4 Spieler eine Grundlegende Gewinnchance von gut 45%, gegen 7 Spieler aber nur noch 28%.
Genau diese Prozentzahlen will ich berechnen und die anderen Spieler haben nur den Einfluß das mehr Gegner die eigenen Chancen verschlechtern. (dafür ist der Pot dann oft größer...)

Und welche Kombinationen noch theoretisch denkbar wären sollte mit deinen Karten doch auch bekannt sein (und endlich).

Die möglichen Kombinationen schon, aber nicht wie gut meine Starthand ist.

Mario Sandler

Vll. solltest du auch einen ganz anderen Ansatz wählen.
Gib deinem Spieler die gewünschte Starthand, und gib
den restlichen Spieler Zufallskarten, und zufällige
Gemeintschaftskarten. Dann schaust du wer gewonnen hat.
Und dass machst du sagen wir 1000 (oder 1.000.000)mal.
Dann siehst du denk ich ziemlich genau mit welcher Wahrscheinlichkeit
du mit dieser Starthand gewinnst.

plizer

Am besten schau mit welche Wahrscheinlichkeitsverteilung das ganze zu lösen ist und suche eine entsprechende Approximationsverteilung für diese. Das Problem sollte doch in die Region der Hypergeometrischen Verteilung einzuordnen sein. Das sollte mind. um den Faktor 100 bis 1000 schneller laufen! Ausserdem würde man das Rad nicht neu erfinden.

pumuckl

@Storm: genau das wirdf ja gemacht. Nur dass ma sich nicht drauf verlaesst, sowas mit statistik zu loesen sondern es genau berechnet. Denn 1000 Durchlaeufe sind definitiv zu wenig statistik, der Fehler waere zu gross um z.B. beim online-Poker Spielgeld zu setzen Und in der groessenordnung von 1.000.000 liegt ja bereits mein Ansatz.
@pilzer: natuerlich ists rechnerisch guenstiger, erst die Verteilungen zu ermitteln und dann im Anwendungsfall damit zu arbeiten. Mein vorgestellter Algorithmus kann genau diese Verteilungen berechnen, so dass man sie tabellieren kann.

Die Anzahl der Kombinationen die man auf der Hand haben kann ist im Uebrigen nicht besonders gross. Da bei dem Problem die eigentliche Farbe der Karten keine Rolle spielt, nur ob das Blatt einfarbig oder mehrfarbig ist, reduzieren sich die Kombinationen auf 13 Paare, 12*13/2 nicht-paare (einfarbig) und 12*13/2 nichtpaare (merhfarbig). Der faktor 1/2 ruehrt daher dass bei 12*13 sowohl die Kombination As-Koenig als auch Koenig-As gezaehlt wird, die nicht unterscheidbar sind. Macht am Ende also 169 Kobinationen fuer jeweils 1-10 Mitspieler also nur 1690 Werte, die zu berechnen sind.

Wenn in meinem obigen Algorithmus die Zahlen 1-13, 14-26 usw, jeweils eine Farbe bezeichnen, kann man weiter ueberlegen, dass es egal ist, in welchem der 13er Abschnitte die zwei Handkarten sind, es ist nur wichtig, ob sie im gleichen oder in zwei unterschiedlichen sind. Daher kann man die von Wert kleinere Karte in den ersten 13er Block verlegen und die zweite je nachdem obs die gleiche oder eine andere Farbe ist, in den ersten bzw. zweiten 13er Block. Damit werden durch die if-abfrage schon frueh die Versuche geblockt, eine der zwei Karten in die Hand der Mitspieler bzw auf den tisch zu packen, die tieferliegenden schleifen werden dafuer garnicht erst aufgerufen. Das ist also nochmal eine Einsparung an Rechenzeit.

Die Anzahl der moeglichen Kombinationen von Tisch- und Handkarten (und damit der Durchlaeufe der innersten Schleife) hab ich nun auch berechnen koennen:
Es sind 50 unbekannte Karten im Spiel, macht 50! kombinationen. Diese muessen geteilt werden durch:
- die Permutationen der 5 Tischkarten, also 1/5! = 1/120
- die Permutationen der Spieler (es ist egal, ob Spieler 2 und 3 ihr Blatt tauschen), also 1/n! fuer n Mitspieler
- die Permutationen der Handkarten jedes einzelnen Spielers, also 1/2! = 1/2 fuer jeden einzelnen Spieler
- die Permutationen der Karten, die im Stapel verbleiben, also 1/(50-5-2*n)!

macht am Ende: $\frac{50!}{(45-2n)!\,2^n\,n!\,120}$
Das ergibt fuer
1 Mitspieler: 2.097.572.400
2 Mitspieler: 947.053.938.600
3 Mitspieler: 2.589e14

Was ne ziemliche Menge wird!
Es muss also evtl. doch ein etwas anders gelagerter Ansatz her, Da auch hier noch viele Situationen mehrfach durchgegangen werden: Wenn ich pik sieben und acht auf der Hand hab ists egal ob der royal flush auf dem Tisch nu in Kreuz, Herz oder Karo liegt.

pumuckl

Args das Problem hat mich jetzt aber gepackt Ist echt mal neherausforderung, da eine Loesung mit moeglichst wenig Durchgaengen zu finden. Ein weiterer Ansatz dem ich gerade nachgehe, um die durchgegangenen Kombinationen zu reduzieren:

Ich ordne die Farben nicht nach den zwei Karten auf der Hand, sondern nach den 5 Karten auf dem Tisch. Fuer 5 Karten auf 4 Farben gibts folgende Schemas:

Es ist also nur zwischen jeweils 2-3 Farben zu unterscheiden und eine jeweilige Gewichtung vorzunehmen. Die Schwierigkeit, wenn man zwei oder drei Farben zu einer zusammenfasst ist, dass auf den Haenden der Spieler dann von dieser zusammengefassten Farbe zwei bzw. drei Karten gleichen Wertes vorkommen koennen.

pumuckl schrieb:

Es ist also nur zwischen jeweils 2-3 Farben zu unterscheiden und eine jeweilige Gewichtung vorzunehmen.

Zwei Farbzustände sollten reichen. Was ich "im hinterkopf hatte" war zwischen Mehrheit und Minderheit zu unterscheiden. Die Farbe ist nur für die Flush's relevant. Und um solch einen zu haben benötigt es mindestens fünf Karten von einer Farbe. In dem Sinne gibt es nur zwei Farbinformationen: Die Farbe welche zu den fünf (oder mehr Karten) gehört und jene welche nicht dazu gehört.

Zu großes Array -&gt; Absturz?

Zu großes Array -> Absturz?