• eräänlaisen pasianssin läpipääseminen

    Home Forums Pokeritieto Pokerimatematiikka ja kassavaatimukset eräänlaisen pasianssin läpipääseminen

    Viewing 15 posts - 31 through 45 (of 46 total)
    • Author
      Posts
    • #897852
      Peixinho
      Participant

      En ota asiaan kantaa, mutta…

      Kaikkien ruletinbiittausketjujen lisäksi tällainenkin siis on mahdollista? Usko ihmiskuntaan vahvistui jonkun verran.

      JR on näköjään palaamassa takaisin, koska Dharma permabännissä. Mikäs siinä, tervetuloa vaan takaisin.

      #897882

      http://www.math.dartmouth.edu/~doyle/docs/treize/treize.pdf näppärimmät varmaan löysivätkin jo linkin, mutta laitetaan nyt vielä tänne.

      #897883
      hauturi
      Participant

      @korppuleipa wrote:

      http://www.math.dartmouth.edu/~doyle/docs/treize/treize.pdf näppärimmät varmaan löysivätkin jo linkin, mutta laitetaan nyt vielä tänne.

      “DRAFT” ja “UNDER CONSTRUCTION” ja vaikuttaakin keskeneräiseltä. Onko tuosta joku lopullinen versio jossain?

      (arvasin, että Markovin ketjut liittyy tähän jotenkin, vaikken niistä mitään ymmärräkään)

      #897898
      KunChipitKarkaavat
      Participant

      Alkuperäisen kysyjän täsmälliseen probleemaan liittyvä nimenomainen stokastinen prosessi ei ole Markovin ketju (1-kertaluokan tai edes 2-kertaluokan). Riippuu tietysti vähän, miten määritellään tila. Eli pitää tietää jokaisella stepillä koko tilahistoria – ei vain edeltäjää. Periaatteessa, jos tila määriteltäisiin, parina (X(i), F(i)), jossa X(i) on indikaattorimuuttuja, joka kertoo, onko kosahtanut steppiin i mennessä ja F(i) on tyhjentävä tilasto (sufficient statistics), joka olisi tässä tapauksessa frekvenssijakauma käytetyistä korteista siten, että järjestyksellä ei väliä (ekvivalenssiluokka), niin tällaisella tila-avaruudella, voisi ajatella olevan Markovin ketju, mutta vähemmän konstruktiivisesti mielikuvituksillisilla keinotekoisilla tila-avaruuksilla koko ajan on voimassa ikävä kyllä

      Pr(X(i) ; X(i-1),…,X(1)) != Pr(X(i) ; X(i-1),.., X(i-k)) kaikilla i-1>=k>=1

      eli koko historia (tai tarkemmin sen tyhjentävä tilasto) pitää ottaa huomioon. Mutta kuten taas pari lausetta taaksepäin sanoin, voidaan mielikuvituksella konstruoida tila-avaruus, jossa kyseessä on Markovin ketju.

      #897901

      @KunChipitKarkaavat wrote:

      Alkuperäisen kysyjän täsmälliseen probleemaan liittyvä nimenomainen stokastinen prosessi ei ole Markovin ketju (1-kertaluokan tai edes 2-kertaluokan). Riippuu tietysti vähän, miten määritellään tila. Eli pitää tietää jokaisella stepillä koko tilahistoria – ei vain edeltäjää. Periaatteessa, jos tila määriteltäisiin, parina (X(i), F(i)), jossa X(i) on indikaattorimuuttuja, joka kertoo, onko kosahtanut steppiin i mennessä ja F(i) on tyhjentävä tilasto (sufficient statistics), joka olisi tässä tapauksessa frekvenssijakauma käytetyistä korteista siten, että järjestyksellä ei väliä (ekvivalenssiluokka), niin tällaisella tila-avaruudella, voisi ajatella olevan Markovin ketju, mutta vähemmän konstruktiivisesti mielikuvituksillisilla keinotekoisilla tila-avaruuksilla koko ajan on voimassa ikävä kyllä

      Pr(X(i) ; X(i-1),…,X(1)) != Pr(X(i) ; X(i-1),.., X(i-k)) kaikilla i-1>=k>=1

      eli koko historia (tai tarkemmin sen tyhjentävä tilasto) pitää ottaa huomioon. Mutta kuten taas pari lausetta taaksepäin sanoin, voidaan mielikuvituksella konstruoida tila-avaruus, jossa kyseessä on Markovin ketju.

      Tuossa linkatussa kirjoituksessa olivat pitäneet yhtenä steppinä markovin ketjussa pakkojen sekoittamisen väliä jolloin historialla ei väliä ja -> markovin ketju.

      #897936
      mattile71
      Participant

      Käytiin asiasta 7 vuotta sitten keskustelu tiede-palstalla.

      http://www.tiede.fi/keskustelu/24873/ketju/korttipakkalasku/sivu/1

      Sellainen tekniikka kuin inkluusio-ekskluusio toimisi jos haluaisi ratkaista analyyttisesti.Vaatisi myös jonkun BigInteger -libraryn.

      Ei tuosta parilla päivällä selviäsi. Varmaan menisi viikko. Järkevämpää ajankäyttöä on kehittää softia nettirahapeleihin.
      Pöljän pojan pasianssi.

      #897938
      hauturi
      Participant

      @mattile71 wrote:

      Käytiin asiasta 7 vuotta sitten keskustelu tiede-palstalla.

      http://www.tiede.fi/keskustelu/24873/ketju/korttipakkalasku/sivu/1

      Sellainen tekniikka kuin inkluusio-ekskluusio toimisi jos haluaisi ratkaista analyyttisesti.Vaatisi myös jonkun BigInteger -libraryn.

      Ei tuosta parilla päivällä selviäsi. Varmaan menisi viikko. Järkevämpää ajankäyttöä on kehittää softia nettirahapeleihin.
      Pöljän pojan pasianssi.

      Tuoltahan löytyi linkki paperiin: http://www.math.dartmouth.edu/~doyle/docs/rank/rank.pdf

      Eikös se tuossa ole ratkaistu?

      #897941

      @hauturi wrote:

      Tuoltahan löytyi linkki paperiin: http://www.math.dartmouth.edu/~doyle/docs/rank/rank.pdf

      Eikös se tuossa ole ratkaistu?

      Riordan also showed that Rn approaches 1/e4 as n tends to infinity

      Tämä fiilis oli itselläkin -heitti vain tuosta simulaatiotuloksesta mutta ilmeisesti n ei ollut riittävän iso.

      #897942
      mattile71
      Participant

      @hauturi wrote:

      Tuoltahan löytyi linkki paperiin: http://www.math.dartmouth.edu/~doyle/docs/rank/rank.pdf

      Eikös se tuossa ole ratkaistu?

      Joo, mutta jos yrittäisi itse ratkaista tuon huvin vuoksi, ikäänkuin matemaattisena urheilusuorituksena.
      Tai oppiakseen jotain.
      Tuossa pdf:ssähän se tekniikka mainitaan, rekursiivinen inkluusio -eksluusio.
      Ei taida mennä long double -muuttujalla, tarvitaan BigInteger -tyyppi -library.

      #897946
      JR
      Participant

      @mattile71 wrote:

      Käytiin asiasta 7 vuotta sitten keskustelu tiede-palstalla.

      http://www.tiede.fi/keskustelu/24873/ketju/korttipakkalasku/sivu/1

      Sellainen tekniikka kuin inkluusio-ekskluusio toimisi jos haluaisi ratkaista analyyttisesti.Vaatisi myös jonkun BigInteger -libraryn.

      Ei tuosta parilla päivällä selviäsi. Varmaan menisi viikko. Järkevämpää ajankäyttöä on kehittää softia nettirahapeleihin.
      Pöljän pojan pasianssi.

      Piti kokeilla kun ei toi aikataulu tuntunut uskottavalta… En tosin tiedä teenkö tolla sun tekniikalla, kun ei oo tuttu termi, mutta kuitenkin laskee tarkkaan (floating pointien rajoissa).

      Tähän meni 40 minuuttia:

      public class Patience {

      public final int SUITS;
      public final int RANKS;
      public final int elements;

      private final double odds[];

      public Patience(int suits, int ranks) {
      this.SUITS = suits;
      this.RANKS = ranks;
      this.elements = (int) Math.pow(SUITS + 1, RANKS);
      System.out.println(this.SUITS + " suits, " + this.RANKS + " ranks, "
      + elements + " deck states");
      odds = new double[elements];
      }

      public void calculate() {
      long start = System.currentTimeMillis();
      System.out.println("Mark result for 1 card decks");
      markFinalSituations();
      for (int i = 2; i <= SUITS * RANKS; i++) {
      System.out.println("Calculate odds for " + i + " card decks");
      calculateDeckSizes(i);
      }
      System.out.println("Done in " + (System.currentTimeMillis() - start)
      / 100 / 10.0 + " seconds.");
      int deck[] = new int[RANKS];
      for (int i = 0; i < deck.length; i++)
      deck = SUITS;
      System.out.println("Odds to pass: " + odds[deckToAddress(deck)]);
      }

      private int deckToAddress(int cardsLeft[]) {
      int address = 0;
      for (int c : cardsLeft) {
      address *= (SUITS + 1);
      address += c;
      }
      return (address);
      }

      private int deckSizeCounter;

      private boolean iterate(int cardsLeft[]) {
      int p = 0;
      cardsLeft[p]++;
      deckSizeCounter++;
      while (cardsLeft[p] > SUITS) {
      cardsLeft[p] = 0;
      p++;
      deckSizeCounter -= SUITS;
      if (p >= cardsLeft.length)
      return (false);
      cardsLeft[p]++;
      }
      return (true);
      }

      private void calculateDeckSizes(int size) {
      int cardsLeft[] = new int[RANKS];
      deckSizeCounter = 0;
      int losingCard = RANKS - 1 - ((size - 1) % RANKS);
      do {
      if (deckSizeCounter == size) {
      double situationOdds = 0;
      for (int cardDrawn = 0; cardDrawn < RANKS; cardDrawn++) {
      if (cardsLeft[cardDrawn] > 0 && cardDrawn != losingCard) {
      cardsLeft[cardDrawn]--;
      situationOdds += this.odds[deckToAddress(cardsLeft)]
      * (cardsLeft[cardDrawn] + 1);
      cardsLeft[cardDrawn]++;
      }
      }
      odds[deckToAddress(cardsLeft)] = situationOdds / size;
      }
      } while (iterate(cardsLeft));
      }

      private void markFinalSituations() {
      int cardsLeft[] = new int[RANKS];
      deckSizeCounter = 0;
      do {
      if (deckSizeCounter == 1)
      odds[deckToAddress(cardsLeft)] = cardsLeft[RANKS - 1] == 1 ? 0.0
      : 1.0;
      } while (iterate(cardsLeft));
      }

      public static void main(String args[]) {
      new Patience(4, 13).calculate();
      }
      }

      Ohjelman oikeellisuutta voi testata pienemmällä pakalla, esim 3 suitin ja 13 kortin pakka laskee noin 30 sekunnissa, eikä vaadi hirveästi muistia. Pienet pakat (2-4 korttia) vastasivat kombinatorisia laskuja, ja isommat simulaatioita. Täydellä pakalla runksuttaa muutamia minuutteja, ja suostui pyörimään vasta kun annoin javalle 14M tilaa (-Xmx14000M)

      janne@janne-CM6630-CM6730-CM6830:~/workspace/randomsandbox/bin$ java -Xmx14000M randomsandbox.Patience
      4 suits, 13 ranks, 1220703125 deck states
      Mark result for 1 card decks
      Calculate odds for 2 card decks
      Calculate odds for 3 card decks
      ... snip ...
      Calculate odds for 51 card decks
      Calculate odds for 52 card decks
      Done in 776.7 seconds.
      Odds to pass: 0.016232727467194636

      Palaan töihin hiomisen sijaan, mutta helppoja mahdollisia parannuksia tohon ohjelmaan olis:
      nopeus
      -tehdään iterate luokka, joka osaa hypätä seuraavaan samankokoiseen pakkakompositioon
      -jaetaan yhden pakkakoon sisällä laskenta jotenkin lohkoiksi ja eri threadeihin
      muisti
      -ei numeroida deckToAddressilla kaikkia pakkakompositioita samalle janalle, vaan pakan koon funktiona, silloin vois varata eri pakkakokojen odds-taulukot erillään, ja pitää aina vain kahta peräkkäistä kerralla muistissa

      #897954
      hauturi
      Participant

      JR:llä on ilmeisesti joku ihan oikea tietokone, kun voi antaa 14GB heapin virtuaalimasiinalle (eikös 14000M ole 14G eikä 14M)

      #897955
      JR
      Participant

      @hauturi wrote:

      JR:llä on ilmeisesti joku ihan oikea tietokone, kun voi antaa 14GB heapin virtuaalimasiinalle (eikös 14000M ole 14G eikä 14M)

      Äh siis tietysti 14G.

      Mun työ on sellaista, että koneen tärkeimmät ominaisuudet on paljon nopeeta muistia, ja paljon monitoritilaa.

      #897956
      mattile71
      Participant

      Sairasta, en kyllä uskonut että tuon pystyy analyyttisesti ratkomaan 40 minuutissa.Olet JR ilmeisesti keksinyt jonkun ratkaisun, jota edes kovan luokan yliopistomatemaatikot ole saaneet aikaan.En valitettavasti pysty tuosta koodistasi suoraan lukemaan miten olet ratkaissut sen.
      Voisit antaa pienen selityksen.
      C++ on kätevä rekursiivisiin juttuihin ja samalla saa koko muistiavaruuden käyttöönsä.Mutta tuo algoritmisi ei tainnut olla rekursiivinen.

      #897957
      JR
      Participant

      @mattile71 wrote:

      Sairasta, en kyllä uskonut että tuon pystyy analyyttisesti ratkomaan 40 minuutissa.Olet JR ilmeisesti keksinyt jonkun ratkaisun, jota edes kovan luokan yliopistomatemaatikot ole saaneet aikaan.En valitettavasti pysty tuosta koodistasi suoraan lukemaan miten olet ratkaissut sen.
      Voisit antaa pienen selityksen.
      C++ on kätevä rekursiivisiin juttuihin ja samalla saa koko muistiavaruuden käyttöönsä.Mutta tuo algoritmisi ei tainnut olla rekursiivinen.

      Lasketaan lopusta alkuun, eli aloitetaan mahdollisilla yhden kortin pakoilla.

      -Se pakka jossa on jäljellä ässä, hävitään, muut pakat voitetaan.

      Jatketaan kahden kortin pakoilla.

      -Pakka jossa on ässä ja kuningas
      -50 % nostetaan kuningas ja hävitään
      -50 % nostetaan ässä, ja voitetaan niin usein kuin jäljellä oleva pakka (1 kuningas) voittaa
      jne… mahdolliset kahden kortin pakat

      jatketaan N kortin pakat,
      häviävän kortin nostotodennäköisyydellä hävitään heti
      muilla korteilla voitetaan sillä todennäköisyydellä kuin pakka josta on vähennetty se kortti voittaa

      #897975
      KunChipitKarkaavat
      Participant

      @hauturi wrote:

      Eikös se tuossa ole ratkaistu?

      Näyttäisi olevan. En tosin jaksanut lukea läheskään niin ajatuksella, että spottaisin virheitä, mutta koska helvetillinen summatulo ratkaisussa on oltava ja tuolta se löytyy sekä vastaus lähellä teidän simulaattoritulosta, niin uskotaan 😀

      @punavuoren highroller wrote:

      Riordan also showed that Rn approaches 1/e4 as n tends to infinity

      Tämä fiilis oli itselläkin -heitti vain tuosta simulaatiotuloksesta mutta ilmeisesti n ei ollut riittävän iso.

      Mielenkiinnosta: Mistä sait fiiliksen / hajun asymptoottisen rankin pakan ratkaisusta?!

      @matille71 wrote:

      Sairasta, en kyllä uskonut että tuon pystyy analyyttisesti ratkomaan 40 minuutissa.Olet JR ilmeisesti keksinyt jonkun ratkaisun, jota edes kovan luokan yliopistomatemaatikot ole saaneet aikaan.En valitettavasti pysty tuosta koodistasi suoraan lukemaan miten olet ratkaissut sen.
      Voisit antaa pienen selityksen.
      C++ on kätevä rekursiivisiin juttuihin ja samalla saa koko muistiavaruuden käyttöönsä.Mutta tuo algoritmisi ei tainnut olla rekursiivinen.

      JRn koodi näyttäisi olevan ammattiohjelmoijan käsialaa, joka on toteuttanut ennenkin isoja hakuavaruuksia läpikäyviä algoritmeja. Ihan eleganttia ja esteettistä koodia vielä, kun otetaan huomioon, että se kirjoitettiin 40 minuutissa 🙂

      Btw: “Rekursiivisiin juttuihin” esteettisimpiä ovat funktionaaliset kielet kuten esim Lisp ja Python. Rekursiivisesti voi ohjelmoida myös ilman eksplisiittistä rekursiota. Algoritmiikan tutkijat puhuvat yleensä “dynaamisesta ohjelmoinnista”, kun konstruoivat rekursiiviset palautuskaavat, jotka antavat ratkaisun haku/optimointiongelmaan. Esim lyhimmän polun etsiminen painotetussa verkossa (Floyd-Warshall algoritmi) on yksi hyvä esimerkki, jota voi googlailla, jos aihepiiri kiinnostaa.

      @JR wrote:

      Täydellä pakalla runksuttaa muutamia minuutteja, ja suostui pyörimään vasta kun annoin javalle 14M tilaa

      Jotain kuvaa laskennan hidastumisesta rankin kasvamisen funktiona saisi, kun piirtäisi kuvan, jossa x-akselilla on korttipakan rank ja y-akselilla laskenta-aika minuutteina (maiden lukumäärän voi kiinnittää neljään).

    Viewing 15 posts - 31 through 45 (of 46 total)
    • The forum ‘Pokerimatematiikka ja kassavaatimukset’ is closed to new topics and replies.