Vangin pasianssin todennäköisyydet

Vangin pasianssissa 52 kortin sekoitetusta korttipakasta ladotaan pöydälle 13 ja nämä yhdistetään saman arvoisiksi pinoiksi. Tämän jälkeen loput kortit käydään läpi kolme kerrallaan siten, että vain joka kolmas otetaan huomioon (eli sama asia kun otettaisiin pakasta vain 13 seuraavaa korttia). Jos pakasta nostettu kortti on arvoltaan sama kuin pöydällä oleva pino, niin tämän pinon saa poistaa.

Mikä on todennäköisyys, että pöydälle jää lopuksi k korttia, k=0, 1, 2, ... 13?

Tein tällaisen, missä peliä voi testata (klikkaa pakkaa (vihreä ylä-vasemmalla) pelataksesi kortti/tripletti kerrallaan tai nopeuta peliä ja klikkaa alemmista napeista.

https://prisoners-solitaire--minkkilaukku2.repl.co/
Ilmoita


18 Vastausta

Ketjusta on poistettu 1 sääntöjenvastaista viestiä.


Hankala löytää eksaktia tapaa. Tein simulaation, 100000 ajoa. todennäköisyydet k:lle kortille, k=0,...,13 olivat
2e-05
0.00113
0.00905
0.04398
0.12532
0.22919
0.27041
0.20021
0.09166
0.02523
0.00351
0.00028
1e-05
4 VASTAUSTA:
Hmmm.. Itse saan vähän eri tulokset:

P(X=0) = 0.003702
P(X=1) = 0.019696
P(X=2) = 0.057118
P(X=3) = 0.113366
P(X=4) = 0.1673
P(X=5) = 0.192721
P(X=6) = 0.178426
P(X=7) = 0.13303
P(X=8) = 0.078939
P(X=9) = 0.03777
P(X=10) = 0.013507
P(X=11) = 0.00377
P(X=12) = 0.000607
P(X=13) = 0.000048

(Jäikö sinulta yksi pois, kun niitähän pitäisi olla 14?)
Tein simulaation uudestaan kolmella eri kielellä ja koitin aina unohtaa entisen, mutta sehän saattaa olla, että itse minulla tuli sitten kaikissa sama ajatusvirhe. Täältä löytyy tekeleitäni (C++ ja Python-versiot): https://github.com/minkkilaukku/prisoners-solitaire ja JS on täällä: https://repl.it/@minkkilaukku2/Prisoners-Solitaire

Siellä Python-tiedostossa on myös yritystä laskea tarkasti, laitan ehkä toiseen viestiin niitä pohdelmiani, ettei tästä nyt tule niin pitkä.

Jos tuo tarina, että 5000 kertaa piti vangin koittaa ennen kuin onnistui on totta (tai vaikka olisi keksittykin, mutta luvut laitettu todennäköisiksi), niin tuo minun vastaus 0.0037 on kyllä liian iso, sillä todennäköisyys, että vie vähintään 5000 yritystä on tällöin

(1-0.0037)^5000 = 0.9e-9

eli erittäin pieni.
Arvolla p = 2e-05, se että vie korkeintaan 5000 yritystä olisi

1 - (1-2e-05)^5000 = 0.095

eli vähän järkevämpi.
En tiedä simuloinko väärin. Tässä koodini:

from random import shuffle
tulos = [0]* 13
kertoja = 100000
for kerta in range(kertoja):
x = [i for i in range(52)]
shuffle(x)
y = x[0:13]
z = x[13:26]
A = []
B = []

for i in range(13):
A.append(y[i] % 13)
B.append(z[i] % 13)
yhteiset = set(A) & set(B)
tulos[len(yhteiset)] += 1
for i in range(13):
print(tulos[i]/kertoja)
print(summa)
Anonyymi kirjoitti:
En tiedä simuloinko väärin. Tässä koodini:

from random import shuffle
tulos = [0]* 13
kertoja = 100000
for kerta in range(kertoja):
x = [i for i in range(52)]
shuffle(x)
y = x[0:13]
z = x[13:26]
A = []
B = []

for i in range(13):
A.append(y[i] % 13)
B.append(z[i] % 13)
yhteiset = set(A) & set(B)
tulos[len(yhteiset)] += 1
for i in range(13):
print(tulos[i]/kertoja)
print(summa)
Hmmm.. Siinä taitaa käydä niin, että kun sä otat nuo yhteiset joukkona, niin se ei huomioi sitä kuinka monta A:sta poistuu (eli pinon kokoa). Minä muutin koodia näin (
ja nyt se antaa samanlaisen tuloksen kuin itselläni)

tulos = [0]* 14
.
.
.
#yhteiset = set(A) & set(B)
..for u in B:
....while u in A: A.remove(u)
..tulos[len(A)] += 1
.
.
Tai miksei jopa kirjoittaisi tuota A:n ja B:n täyttöä suoraan:
A = [u for u in y]
B = [u for u in z]

PS. Tuota että Pythonissa joukot voi &-operaattorilla leikata, ja näköjään myös |-operaattorilla yhdistää) en tiennytkään. Kätevä!
minkkilaukku kirjoitti:
Hmmm.. Siinä taitaa käydä niin, että kun sä otat nuo yhteiset joukkona, niin se ei huomioi sitä kuinka monta A:sta poistuu (eli pinon kokoa). Minä muutin koodia näin (
ja nyt se antaa samanlaisen tuloksen kuin itselläni)

tulos = [0]* 14
.
.
.
#yhteiset = set(A) & set(B)
..for u in B:
....while u in A: A.remove(u)
..tulos[len(A)] += 1
.
.
Tai miksei jopa kirjoittaisi tuota A:n ja B:n täyttöä suoraan:
A = [u for u in y]
B = [u for u in z]

PS. Tuota että Pythonissa joukot voi &-operaattorilla leikata, ja näköjään myös |-operaattorilla yhdistää) en tiennytkään. Kätevä!
Prosentit näköjään muuttui joksikin, (taisvat jäähä kiinni u:hun), kokeillaas uudestaan:

A = [u % 13 for u in y]
B = [u % 13 for u in z]
+Lisää kommentti
Tarinan mukaan vankilan johtaja sovelsi peliä elinkautisvankiin. Sai joka päivä pelata yhden pelin ja pääsi vapaaksi, jos sai kaikki kortit poistettua pöydältä. Ja tarinan mukaan pääsi vapaaksi 13 vuoden päästä eli noin 5000 pelin jälkeen. Oli onnekas, jos tn on tosiaan tuo 2*10^(-5).
1
Ilmoita
Tässä hieman pohdelmiani:

Kun valitaan 13 korttia pöydälle ja ne jakautuvat pinoihin, niin kutsutaan näitten pinojen kokojen järjestettyä vektoria tämän valinnan tyypiksi.
On 39 erilaista tyyppiä (laskin Pythonilla: https://github.com/minkkilaukku/prisoners-solitaire/blob/master/prisoners.py ):

[4, 4, 4, 1], [4, 4, 3, 2], [4, 4, 3, 1, 1], ..., [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Löysin mielestäni kaavan sen laskemiseksi, kuinka monta pakan 13-kombinaatiota on tyyppiä (t1, t2,..., tr) tuolla tiedostossa on se kaava funktiona calcTypeOccurs(t, suits, vals). Se on tulo tyypin yli termistä
(vals-i)*binomial(suits, ti)
ja sitten vielä jaetaan koko tulo sillä kuinka monella tavalla tyypissä olevat samat luvut voivat keskenään permutoida, se on getTypeInnerPermuFactor(t).

Sitten pitäisi vielä laskea sellaiset luvut, että kun pakasta on poistettu kortteja tyypin t mukaisesti, niin kuinka monta 13-kombinaatiota jäljellä olevista on sellaisia, että niissä on ainakin 1 jokaista t:n korttia (mielestäni se voidaan WLOG olettaa että ne t:n kortit ovat 0, 1, 2,.., r). Tein jo sen bruteforcen, mutta mitenkäs se kaavan keksiminen. Tuo ensimmäisen valinnan laskuhan on sama kuin tämäkin, mutta siinä ei olla poistettu mitään vaan jokaista korttia on 4 (=suits) kappaletta, joten se oli siten yksinkertaisempi.
4 VASTAUSTA:
""Tuo ensimmäisen valinnan laskuhan on sama kuin tämäkin, mutta...""

Tai siis, nythän lasketaan eri asiaa: sillä toisen valinnan tyypillä ei ole väliä vaan siinä pitää olla vähintään 1 jokaista jotain kiinitettyä lukua, joten ei se lasku ole sama, mutta jotain saman tyyppistä pohdintaa siinä pitää varmaan harjoittaa(?)
Niin ja tämä on siis vain tuon X=0 tapauksen laskemista kohden tämä jälkimmäisen valinnan lasku. Sehän menee erittäin monimutkaiseksi se, että monta sitten lopulta jää.

Minä aloitan nyt pohdinnan uudesta kulmasta.
Kun se pöydän tyyppi on tullut, niin lähdetään yksi kerrallaan ottamaan pakasta niitä testauskortteja (nythän on helppo laskea tn. siirtyä toiseen tyyppiin ja siihen mitä pakassa on jäljellä (jos tulee tyhjä kortti, niin pöydän tyyppi ei muutu, mutta pakassa on yksi kortti vähemmän, voisiko se olla niin, että se ei riipu mikä kortti sieltä 'tyhjänä' heitetään pois vaikka tyyppi muuttuisikin sitten jatkossa eli siihen tulisi eri edustajat niille tyypin luvuille??
Silloinhan sen saisi melko helposti luultavasti dynaamisella ohjelmoinnilla laskettua. Pitäisi koittaa...
Funktio
calculateProb(suits, vals, handLen, pickN)
näyttäisi toimivan, mutta ne jälkimmäiset luvut lasketaan yhä brute-forcena. Kokeilin pienillä arvoilla ja vertasin simuloituun arvoon.
"Toisten lukujen" laskemiseksi:

Olkoon M = {nj * j} multijoukko (alkiota j nj kappaletta, j=1..m). Sen k-kombinaatioiden lukumäärä saadaan polynomin

(1+z+..z^n1) * ... * (1+z+...z^nm)

termin z^k kertoimesta. Ja sellaisten kombinaatioiden, joissa alkioita j, j=1..p, on ainakin yksi saadaan, kun jätetään ykkönen pois näistä polynomeista tuossa yllä olevassa tulossa. (Tai yleisemmin: otetaan vain ne termit kuhunkin polynomiin mitkä lukumäärät tälle alkiolle kombinaatioon sallitaan).
Muistatteko sen lotto-tehtävän, tämähän on samanlainen! Mutta nyt tuloon tulee monen tyyppisiä termejä, riippuen millainen tyyppi pakasta on otettu pois. Mathematica osaisi varmaan tehokkaasti laskea nuo kertoimet. Löytyisiköhän Python-koodia mistä?

Vastaus siis saadaan, kun otetaan summa jokaisen tyypin yli (niitä oli ne 39) termeistä

P(pöydälle tulee tämä tyyppi t) * P(jäljellä olevasta pakasta (josta siis poistettu tyypin t mukaan) tulee sellainen 13-kombinaatio, että siinä on vähintään 1 jokaista tyypin korttia).

Nämä jälkimmäiset todennäköisyydethän voisi laskea jopa siten, että ajattelee pakkaa multijoukkona {(4-t1)*1, (4-t2)*2, ..., (4-tr)*r, (loput)*(r+1)}, eli emäfunktion viimeinen polynomi olisi (1+z+...+z^loput). Osoittajaan kerroin siitä missä ykköset jätetty 1..r:stä pois ja nimittäjään siitä missä ne mukana.
+Lisää kommentti
Haa, tein Sage-koodin:

R.<z> = QQ['z']

vals = 5 #13
k = 7 #13
t = [3,2,1] #[3, 2, 2, 2, 1, 1, 1, 1]
njs = [4- (t[i] if i<len(t) else 0) for i in range(vals)]

g = 1 #the generating polynomial for suotuisat
gAll = 1 #for all
#it is the product
for i in range(len(njs)):
giCoeffs = [1]*(njs[i]+1)
gAll *= R(giCoeffs[:])
if i<len(t):
giCoeffs[0] = 0
g *= R(giCoeffs)

#print g
#print gAll

print "suotuisat"
print g[k]
print "kaikki"
print gAll[k]

Osoitteessa https://sagecell.sagemath.org/ voi suorittaa. Nyt kun jaksaisi vielä siirtää muut laskelmat tuohon ikkunaan, niin saisi ehkä vastauksen P(X=0):lle.
1 VASTAUS:
Tein sen noin mutta antoi väärän tuloksen. Mutta nyt taidan ymmärtää mistä se johtuu:
Tuo antaa ne multijoukon kombinaatiot ihan oikein, mutta ongelma on siinä, että näiden todennäköisyydet tulla on erilaisia. Esim jos pakassa on 2 nollaa, 2 ykköstä ja 4 kakkosta, niin kombinaation '0,0,1' saaminen on pienempi kuin '0,0,2':n.
Korjaisikohan asian, jos mietittäisiinkin permutaatioita ja käytettäisiin eksponentiaalisia emäfunktioita?

Ei kyllä näyttäisi ihan suoraan vaan 1/k!:t polynomeihin polkaisemallakaan toimivan.
+Lisää kommentti
No nyt sain tuloksen

P(X=0) =
964444044208 / 262190765217675
= 0.00367840584853

Tämän näköisellä koodilla: https://github.com/minkkilaukku/prisoners-solitaire/blob/master/prisoners.py
3 VASTAUSTA:
Koodia optimoitu nyt erittäin merkittävästi: siinä kun lasketaan niitä pakasta toisessa vaiheessa tulevia kelpaavia tyyppejä, että monta kutakin sellaista on, niin voidaan rajoittaa ne niin, että sen vektorin summa on korkeintaan se kuinka monta valitaan toisessa vaiheessa (13 tässä perusversiossa). Ne generoidaan siten, että otetaan kaikki lukujen |t|..pickN ositukset ja permutoidaan nämä. Tähän on funktio generateMultipermus -- muuten 13:n pituisten permutaatioiden kanssa olisi ehkä tulla vähän ongelmia (vaikka eihän siellä ole kuin se yksi 13 pituinen, kaikki ykkösiä ja siitä ei sitten tule itseasiassa kuin 1!
minkkilaukku kirjoitti:
Koodia optimoitu nyt erittäin merkittävästi: siinä kun lasketaan niitä pakasta toisessa vaiheessa tulevia kelpaavia tyyppejä, että monta kutakin sellaista on, niin voidaan rajoittaa ne niin, että sen vektorin summa on korkeintaan se kuinka monta valitaan toisessa vaiheessa (13 tässä perusversiossa). Ne generoidaan siten, että otetaan kaikki lukujen |t|..pickN ositukset ja permutoidaan nämä. Tähän on funktio generateMultipermus -- muuten 13:n pituisten permutaatioiden kanssa olisi ehkä tulla vähän ongelmia (vaikka eihän siellä ole kuin se yksi 13 pituinen, kaikki ykkösiä ja siitä ei sitten tule itseasiassa kuin 1!
Jos pakassa olisi 16 korttia kutakin 4 maata, niin voitto-tn. olisi
1354983985597413560192/1457082583811094293369085 = 0.000929929436157

Se on kuitenkin nuo partitio-luvut, jotka tyyppien määrät ovat ja kasvavat eksponentiaalisesti, niin ei tällä menetelmällä kovin pitkälle pötkitä, tuokin vei jo taas 14 sekuntia.
minkkilaukku kirjoitti:
Jos pakassa olisi 16 korttia kutakin 4 maata, niin voitto-tn. olisi
1354983985597413560192/1457082583811094293369085 = 0.000929929436157

Se on kuitenkin nuo partitio-luvut, jotka tyyppien määrät ovat ja kasvavat eksponentiaalisesti, niin ei tällä menetelmällä kovin pitkälle pötkitä, tuokin vei jo taas 14 sekuntia.
Ai niin, ja tuo siis jos lätkittäisiin 16 kolmentoista asemesta myös pöydälle ja sen jälkeen nostettaisiin pakasta, eli 'joka kolmas', niinkuin se alunperin ilmaistiin.

Ne luvuthan (boardN ja pickN) siinä kasvattavat laskentaa. Jos olisi 50*4 korttia, ja boardN = pickN = 13, niin tulos on

1416074149056783184/17785457959223804854010008101 = 7.96197743293e-11

eikä laskenta vie kuin sekunnin.
+Lisää kommentti
No nyt toimii generoivat funktiotkin! Sinne piti laittaa binomikertoimet painottamaan. Koodi (Sagea): https://github.com/minkkilaukku/prisoners-solitaire/blob/master/prisonersSage.py

Tämä jaksaa isompiakin, esim

suits = 4
vals = 40
boardN = vals
pickN = 2*vals

p = calcWinProb(suits, vals, boardN, pickN)
= 2.734e+65 / 4.042e+66
= 0.0676372602897
Ilmoita

Vastaa alkuperäiseen viestiin

Vangin pasianssin todennäköisyydet

Vangin pasianssissa 52 kortin sekoitetusta korttipakasta ladotaan pöydälle 13 ja nämä yhdistetään saman arvoisiksi pinoiksi. Tämän jälkeen loput kortit käydään läpi kolme kerrallaan siten, että vain joka kolmas otetaan huomioon (eli sama asia kun otettaisiin pakasta vain 13 seuraavaa korttia). Jos pakasta nostettu kortti on arvoltaan sama kuin pöydällä oleva pino, niin tämän pinon saa poistaa.

Mikä on todennäköisyys, että pöydälle jää lopuksi k korttia, k=0, 1, 2, ... 13?

Tein tällaisen, missä peliä voi testata (klikkaa pakkaa (vihreä ylä-vasemmalla) pelataksesi kortti/tripletti kerrallaan tai nopeuta peliä ja klikkaa alemmista napeista.

https://prisoners-solitaire--minkkilaukku2.repl.co/

5000 merkkiä jäljellä

Rekisteröidy, jos haluat käyttää nimimerkkiä.

Peruuta