sort_stable und pointer

Michael E.

codecow schrieb:

Ich könnte auch den Source-Code posten falls du misstrauisch bist aber so ist es glaub ich am einfachsten.

... wenn du -static-libgcc benutzt

Aber Faktor 15000 ist schon ne Hausnummer. Hab zwar schon durch ein paar simple Änderungen gute Ergebnisse erzielt, aber natürlich nichts, was für dich zufriedenstellend wäre.

Edit: Wie groß ist HandRanks.dat? Du solltest zumindest Teile cachen und nicht für jeden Aufruf einen neuen Lesevorgang starten. Wenn die Datei nicht zu groß ist (für dich zum Upload, mir ist das egal ), kannst du sie ja mal online stellen.

padreigh

Poker scheint ja recht interessant zu sein. Du gehst von einem 52 Blatt aus zum Simulieren. Laut Wikipedia sind aber eher 6*52 Karten Sledge zum Spielen üblich ... da können in einer Runde also durchaus 8 Asse vertreten sein ... was deine ermittelten Werte (im Sinne einer optimalen Spielstrategie) dann wohl über den Haufen wirft?

Der HandValue von 7/10 Paarungen ist unabhängig von der Kartenfarbe, die ist nur für Flush, Straight Flush und Royal Flush wichtig ... das streicht fast 5/6 oder mehr deiner Riesendbewertungsdatei zusammen ...

Die Datei hat so um die 31MB wenn ich den Code richtig sehe.

SeppJ

padreigh schrieb:

Poker scheint ja recht interessant zu sein. Du gehst von einem 52 Blatt aus zum Simulieren. Laut Wikipedia sind aber eher 6*52 Karten Sledge zum Spielen üblich ... da können in einer Runde also durchaus 8 Asse vertreten sein ... was deine ermittelten Werte (im Sinne einer optimalen Spielstrategie) dann wohl über den Haufen wirft?

Das hat jetzt nichts mit dem Thema zu tun: Das hast du falsch verstanden. Es sind zwar 6 Kartenspiele, aber von denen wird immer nur genau eines verwendet. (edit: Das hat einfache physikalische Gründe: Man kann dann im Hintergrund kräftig mischen, während im Vordergrund mit einem frisch gemischten Deck gespielt wird.)

Michael E.

Meinst du mit 66 Simulationen/Sekunde den zweiten Parameter der Methode, der bei dir auf 10000 steht? Wenn ja, ist der ständige Zugriff auf HandRanks.dat definitiv der Flaschenhals. Ich schaff im Moment ca. 250000 Durchläufe pro Sekunde bei nem Dummy-eval_hand_7. Dann wärs ja doch noch machbar mit Ruby.

Der HandEvaluator nicht meine Arbeit und basiert auf Graphen. Hier ist der Ansatz gut erklärt: http://www.pst.ifi.lmu.de/~hammer/poker/handeval.html
Und hier ist er hauptsächlich entstanden:
http://archives1.twoplustwo.com/showflat.php?Cat=0&Number=8513906&page=0&fpart=1&vc=1
Falls sich jemand dafür interessiert.

Jedenfalls funktoniert er sehr gut und ist absolut optimiert. Mir gehts eigentlich nur um die Simulation.

250k/sek ist schonmal sehr gut. Ich dachte irgendwie ich hätte die Datei schon gecached aber wenn man sich die CPU-Auslastung anguckt ist natürlich alles klar. Werd meine Ruby Version auch mal dementsprechen bearbeiten. Was noch interessant wär hast du 250k Hände oder Simulationen geschafft? Weil man für eine Simulation ja mindestens durch die Anzahl der Spieler rechnen muss.

http://www.megaupload.com/?d=ID3ATVST
Hier hab ich die Datei mal geuploadet. Aber megaupload weigert sich gerade irgendwie sie rauszurücken. Vielleicht gehts nachher.
Aber das einfachste ist wirklich sie sich generieren.

Der Versuch die Datei in einen String zu lesen ist daran gescheitert das String.slice keine Bignum als Parameter akzeptiert und und Fixnum mit 31-Bit nicht in der Lage ist die gesamte Datei zu indexieren. Werd jetzt mal versuchen die Werte als fertige Integer in ein Array zu lesen.

Hm Arrays nehmen auch nur Fixnum Indizes. Wie hast du dass den gelöst?

Michael E.

Oje, ich seh grad, dass ich mich um eine Größenordnung vertan hab Es sind nur ca. 25000 Aufrufe pro Sekunde.

Ich hab HandLookup verkrüppelt zu

class HandLookup
  def eval_hand_7(ary_cards)
    rand(100).to_i
  end
end

MonteCarlo hab ich unverändert gelassen. Meine Version sieht im Moment so aus:

class MonteCarlo2
  def initialize
    @ary_nbr_hand_types = [0, 1277, 4137, 4995, 5853, 5863, 7140, 7296, 7452, 7462]
    @hand_eval = HandLookup.new
  end

  def get_odds(player_count, runs, community_cards_init, player_cards_param)
    random_cards_pool = (1..52).to_a
    random_cards_pool -= community_cards_init
    player_cards_param.each_value do |cards|
      random_cards_pool -= cards
    end

    player_cards_init = Array.new(2 * player_count)
    player_cards_param.each do |key, value|
      unless value.nil? or value.empty?
        player_cards_init[2*key] = value[0]
        player_cards_init[2*key + 1] = value[1] unless value.size < 2
      end
    end

    odds = [0] * player_count

    runs.times do
      community_cards = Array.new(community_cards_init)
      player_cards = Array.new(player_cards_init)
      set_random_card_set(random_cards_pool)

      missing = 5 - community_cards.length
      community_cards += pick_n_random_cards(missing) if missing > 0

      player_cards.map! { |card| card.nil? ? pick_random_card : card }

      ranks = Hash.new

      for i in (0...player_count)
        hand_value = @hand_eval.eval_hand_7([player_cards[2*i], player_cards[2*i+1]] + community_cards)  #TODO: karten einzeln übergeben
        ranks[i] = @ary_nbr_hand_types[(hand_value >> 12)-1] + (hand_value & 0x00000FFF)
      end

      sorted_ranks = ranks.sort { |lhs, rhs| rhs[1] <=> lhs[1] }
      i = 0
      win_score = sorted_ranks[0][1]
      while i < player_count and sorted_ranks[i][1] == win_score do
        odds[sorted_ranks[i][0]] += 1
        i += 1
      end
    end

    puts odds.map { |i| i.to_f / runs * 100 }.inspect
    odds.map { |i| i.to_f / runs * 100 }
  end

  def set_random_card_set(arr)
    @random_card_set = Array.new(arr).shuffle
  end

  def pick_random_card
    @random_card_set.pop
  end

  def pick_n_random_cards(n)
    @random_card_set.slice!(@random_card_set.size - n, n)
  end
end

Aufruf:

foo = MonteCarlo.new
bar = MonteCarlo2.new

Benchmark.bm do |x|
  x.report { foo.get_odds(9, 100000, [], {}) }
  x.report { bar.get_odds(9, 100000, [], {}) }
end

Ausgabe:

user     system      total        real
  4.898000   0.000000   4.898000 (  4.926282)
 14.306000   0.000000  14.306000 ( 14.314818)

Dabei ist ein CPU-Kern vollständig ausgelastet. Am meisten Performancegewinn hat die neue pick_random_card gebracht, weil es einfach deutlich performanter ist, Elemente vom Ende des Arrays wegzunehmen statt mittendrin zu löschen:

Benchmark.bm do |x|
  x.report("pop:    ") { n.times { a = (1..50).to_a; a.shuffle; 10.times { a.pop } } }
  x.report("delete: ") { n.times { a = (1..50).to_a; 10.times { x = a[rand(a.length)]; a.delete(x) } } }
end

Output:
      user     system      total        real
pop:      1.076000   0.000000   1.076000 (  1.087062)
delete:   5.055000   0.000000   5.055000 (  5.046288)

Wenn du das Sortieren in C++ schreibst (z. B. mittels RubyInline) à la

#include <iostream>
#include <algorithm>
using namespace std;

struct Tuple
{
	int first;
	int second;
};

bool pred(const Tuple& lhs, const Tuple& rhs)
{
	return lhs.second < rhs.second;
}

int main()
{
	for(int n = 0; n < 10000000; ++n)
	{
		Tuple foo[10];
		for(int i = 0; i < 10; ++i)
		{
			foo[i].first = i;
			foo[i].second = 1000 - 11 * i;
		}

		sort(foo, foo + 10, pred);
	}
}

sparst du nochmal etwa 0,7 Sekunden IIRC. Außerdem ist das hier ein perfektes Beispiel, bei dem du mehrere Prozesse starten solltest, weil sonst nur ein CPU-Kern ausgelastet wird. Dadurch vervierfacht sich die Geschwindigkeit nahezu bei vier Kernen.

Michael E.

codecow schrieb:

Der Versuch die Datei in einen String zu lesen ist daran gescheitert das String.slice keine Bignum als Parameter akzeptiert und und Fixnum mit 31-Bit nicht in der Lage ist die gesamte Datei zu indexieren.

Eigentlich schon, denn mit 31 Bit kann man 2 GB adressieren.

Michael E.

Deine evil_hand_7 ist fehlerhaft, weil du p ständig verwirfst und somit nur die letzte Karte zur Berechnung einbeziehst. Auch erscheinen mir die Zahlen zur Positionsberechnung viel zu klein für so eine große Datei. Aber ich weiß nicht, wie HandRanks aufgebaut ist, und überlasse das dir.

Hier ist ein Vorschlag für evil_hand_7:

class HandLookup
  def initialize
    @contents = open('d:\handranks.dat', "rb") {|io| io.read };
  end

  def eval_hand_7(ary_cards)
    p = 53
    pos = 0
    ary_cards.each do |pc|
      pos += (pc + p) * 4
    end
    @contents[pos..(pos+3)].unpack("l").first
  end
end

Damit schaff ich noch 60000 statt 100000 Durchläufe in 4,5 Sekunden.

Michael E.

Ne, doch lieber alles direkt in ein Array stopfen:

n = 10000000
pos = 1000
Benchmark.bm do |x|
  x.report { contents = open('d:\handranks.dat', "rb") {|io| io.read }; n.times { contents[pos..(pos+3)].unpack("l").first } }
  x.report { contents = open('d:\handranks.dat', "rb") {|io| io.read }; values = contents.unpack("l*"); n.times { values[pos] } }
end

Output:
      user     system      total        real
 13.572000   0.125000  13.697000 ( 13.724785)
  2.512000   0.202000   2.714000 (  2.890166)

Das ergäbe dann sowas wie

class HandLookup
  def initialize
    @contents = open('d:\handranks.dat', "rb") {|io| io.read };
    @contents = @contents[53..-1].unpack("l*")
  end

  def eval_hand_7(ary_cards)
    @contents[ary_cards.inject(:+)]
  end
end

Das macht dann 5 Sekunden für 100.000 Durchläufe, wenn man die Initialisierung weglässt

Wie funktioniert das eigentlich mit @ary_nbr_hand_types? So wie ich das sehe, kann handvalue deutlich größer sein als 2^12, also wird oft auf einen viel zu großen Index zugegriffen.

Nein die eval_hand_7 funktion ist nicht falsch. So funktionieren direkte, azyklische Graphen. Kann man aber nicht wissen.
http://en.wikipedia.org/wiki/Directed_acyclic_graph

Es wird sich also quasi ein Weg durch den Datensatz gesucht. An jeder Station steht eine neue Addresse wo es hingeht daher brauch man die davor nicht mehr bis am Ende der Handrank steht. Wenn du mehr dazu wissen willst guck dir die beiden Links an die ich vorhin gepostet hab.

Und nope handvalue << 12 kann nicht beliebig groß sein

Das format sieht bit-weise betrachtet so aus:
hhhhrrrrrrrrrrrr
hhhh = 1 high card -> 9 straight flush
r..r = rank within the categorie 1 to max of 2861

So ich hab den Datensatz jetzt auch in ein Array gepackt und krieg damit so 50000 Hände pro Sekunde hin. Das sind bei 9 Spielern aber leider immer noch nur ca. 5000 Simulationen die Sekunde. Wird wohl doch auf C/C++ rauslaufen.

Mein Code sieht übrigens jetzt so aus. Vorhin war es am fehlenden binmode fuer IO::read und der automatischen crlf Konvertierung gescheitert. Darum hatte ich schwachsinnige Werte die wiederum auf ne Stelle im String gezeigt haben die viel zu groß war. Und daher der bignum error.

class HandLookup
  def initialize
    file = File.new(Dir.pwd + "/HandRanks.dat", "rb")
    file.binmode()
    rank_table_string = file.read()
    file.close()
    @rank_table = rank_table_string.unpack("l*")
  end

  def eval_hand_7(ary_cards)
    p = 53
    ary_cards.each do |pc|
      p = pc + p
      p = @rank_table[p]
    end
    return p
  end
end

Die HandRanks.dat kann man jetzt übrigens downloaden. http://www.megaupload.com/?d=ID3ATVST

Hört sich ja alles echt interessant an, haltet uns mal auf dem laufenden

Michael E.

codecow schrieb:

Nein die eval_hand_7 funktion ist nicht falsch.

Sry, hab mich verlesen.

Wenn das so ist, dann geb ichs mit Ruby auf, das in angemessener Zeit zu schaffen Vielleicht mach ich ja noch aus Spaß ne C++-Version...

So nachdem mir heute Nacht einige Lichter aufgegangen sind bezüglich C++ hab ich es jetzt geschafft. Herzlichen Dank dafür an alle insbesondere der Tipp (und der Beispielcode) mit dem struct war zielführend. Und nebenbei noch ein bisschen was über Ruby gelernt. Ich hab jetzt 1 Millionen durchläufe für 3 Spieler in gefühlt einer Sekunde. Das sollte erstmal ausreichen. Bei Bedarf werd ich es noch mit OpenCL erweitern.

Rein interessehalber hät ich allerdings noch zwei Fragen:
1. Was bedeutet dieser gcc output(g++ Evaluator.cpp -o eval.exe):

Info: resolving std::nothrow by linking to __imp___ZSt7nothrow (auto-importc:/mingw/bin/../lib/gcc/mingw32/4.5.0/../../../../mingw32/bin/ld.exe: warning: auto-importing has been activated without --enable-auto-import specified on the command line.
This should work unless it involves constant data structures referencing symbols from auto-imported DLLs.)

2. Warum funktioniert HandLookup als C Version hier nicht:

require 'inline'

class HandLookup
  def initialize
    file = File.new(Dir.pwd + "/HandRanks.dat", "rb")
    file.binmode()
    rank_table_string = file.read()
    file.close()
    @rank_table = rank_table_string.unpack("l*")
  end

  def eval_hand_7(ary_cards)
    p = 53
    ary_cards.each do |pc|
      p = pc + p
      p = @rank_table[p]
    end
    return p
  end
end

class HandLookupC
  inline(:C) do |code|
    code.include '<stdio.h>'
    code.c '
    int HR[32487834];

    int InitTheEvaluator()
    {
        memset(HR, 0, sizeof(HR));
        FILE * fin = fopen("HandRanks.dat", "rb");
        size_t bytesread = fread(HR, sizeof(HR), 1, fin);
        fclose(fin);
    }

    int GetHandValue(int* pCards)
    {
        int p = HR[53 + *pCards++];
        p = HR[p + *pCards++];
        p = HR[p + *pCards++];
        p = HR[p + *pCards++];
        p = HR[p + *pCards++];
        p = HR[p + *pCards++];
        return HR[p + *pCards++];
    }'
  end
end

Hier noch der Code wenns jemanden interessiert:

#include <stdlib.h>
#include <windows.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <time.h>
using namespace std;

struct Tuple 
{
    int first; 
    int second; 
}; 

int HR[32487834];

int randCards[52];

int hand_categories[] = {0, 1277, 4137, 4995, 5853, 5863, 7140, 7296, 7452, 7462};

int InitTheEvaluator()
{
    memset(HR, 0, sizeof(HR));
    FILE * fin = fopen("HandRanks.dat", "rb");
    size_t bytesread = fread(HR, sizeof(HR), 1, fin);
    fclose(fin);
}

int GetHandValue(int* pCards)
{
    int p = HR[53 + *pCards++];
    p = HR[p + *pCards++];
    p = HR[p + *pCards++];
    p = HR[p + *pCards++];
    p = HR[p + *pCards++];
    p = HR[p + *pCards++];
    return HR[p + *pCards++];
}

int PickRandomCard()
{
	int random_card = 0;
	while (random_card == 0) {
		char rand_nbr = rand() % 52;
		random_card = randCards[rand_nbr];
		randCards[rand_nbr] = 0;
	}
	return random_card;
}

bool pred(const Tuple& lhs, const Tuple& rhs) 
{ 
    return lhs.second > rhs.second; 
} 

void MonteCarlo(int rounds, char players, int player_cards[][2], int* com_cards, int* odds)
{
	srand(time(NULL));
	int i;
	int ii;
	int loop;
	int com_cards_t[5];
	int player_cards_t[players][2];
	Tuple ranks[players];
	for (loop = 0; loop < rounds; loop++) {
		for (i = 0; i < 52; i++) {
			randCards[i] = i+1;
		}
		for (i = 0; i < 5; i++) {
			if (com_cards[i] != 0) {
				com_cards_t[i] = com_cards[i];
				randCards[com_cards[i]-1] = 0;
			}
		}
		for (i = 0; i < players; i++) {
			for (ii = 0; ii < 2; ii++) {
				if (player_cards[i][ii] != 0) {
					player_cards_t[i][ii] = player_cards[i][ii];
					randCards[player_cards[i][ii]-1] = 0;
				}
			}
		}
		for (i = 0; i < 5; i++) {
			if (com_cards[i] == 0) {
				com_cards_t[i] = PickRandomCard();
			}
		}
		for (i = 0; i < players; i++) {
			for (ii = 0; ii < 2; ii++) {
				if (player_cards[i][ii] == 0) {
					player_cards_t[i][ii] = PickRandomCard();
				}
			}
		}
		for (i = 0; i < players; i++) {
			int eval_array[] = { player_cards_t[i][0], player_cards_t[i][1], com_cards_t[0], com_cards_t[1], com_cards_t[2], com_cards_t[3], com_cards_t[4] };
			int value_t = GetHandValue(eval_array);
			ranks[i].first = i;
			ranks[i].second = hand_categories[(value_t >> 12)-1] + (value_t & 0x00000FFF);
		}
		stable_sort(ranks, ranks+players, pred);
		odds[ranks[0].first] = odds[ranks[0].first] + 1;
		for (i = 1; i < players; i++) {
			if (ranks[i].second == ranks[i-1].second) {
				odds[ranks[i].first] = odds[ranks[i].first] + 1;
			}
		}
	}
}

int main() {
	InitTheEvaluator();
	int player_cards[][2] = {{2, 35}, {22, 13}, {26, 7}};
	int com_cards[] = {1, 5, 24, 0, 0};
	int odds[] = {0, 0, 0};
	MonteCarlo(1000000, 3, player_cards, com_cards, odds);
	printf("%d %d %d", odds[0], odds[1], odds[2]);
}