Isté kasíno zaviedlo nasledovnú hru: Krupier postupne hádže mincou, až pokým hráč nepovie "stop!", čím hru ukončí. Hráč však musí hru ukončiť najneskôr po desiatom hode. Akonáhle hráč zahlási "stop!", dostane ako výhru toľko dolárov, v koľkých posledných po sebe nasledujúcich hodoch padol znak. Napríklad: ZHHZZZZ[stop!] = výhra 4 doláre, ZHZHZZ[stop!] = výhra 2 doláre, ZZHZZHZHZ[stop!] = výhra 1 dolár, alebo ZZHZZHZHHH[stop!] = výhra 0 dolárov. Aká je v tejto hre optimálna stratégia hráča, t.j. stratégia, ktorá hráčovi maximalizuje očakávanú výšku výhry?
Poznámka 5.2.: Po rozhovore s kolegom som dospel k názoru, že by som mal uviesť toto upozornenie: Nehľadajte úžasnú a jednoduchú fintu, ako tento príklad plne vyriešiť za päť minút; zdá sa, že najrýchlejšia metóda riešenia si vyžaduje napísať malý programík pre počítač. Takže riešením tohoto príkladu môže byť algoritmus, ako sa pomocou počítača dopracovať k (nejakej) optimálnej stratégii hráča. A čím bude ten algoritmus rýchlejší/jednoduchší, tým lepšie riešenie ste našli.
Poznámky: Obrázky doláru pochádzajú zo stránok random.org, kde si napríklad môžete nechať vygenerovať náhodné hody mincou, alebo kockou, pričom v pozadí stojí generátor "pravej" náhodnosti založený na atmosferickom šume a nie obvykle používané generátory pseudonáhodných čísiel. A samozrejme - spomínané kasíno je len moja fikcia :-)
24 komentárov:
po precitani nadpisu som najprv myslela, ze koncis s blogom! :-)
Vobec ma nenapadlo, ze ten nadpis moze vyvolat takyto dojem.
Samozrejme s blogom nekoncim; stale neprestava prirodzeny prisun novych napadov a drzi ma blogersky optimizmus. Napriklad aj vcera, ked ma nahodou napadla tato uloha, tak som bol velmi rad, ze sa s nou mozem pomocou blogu s niekym podelit. :-)
Zaujimavy hra, budem si ho musiet vyskusat. :-) Mozno budem spat s riesenie.
Nikdy som sa matike nejako extremne nevenoval, takze ak sem napisem dristy, tak sa ospravedlnujem.
Sanca, ze po dvoch hodoch mincou padne dva krat hlava je 1/2 * 1/2, cize 1/4. Z toho vyplyva, ze po 10 hodoch je sanca 10 hlav 1/1024, cize sanca na akukolvek postuponost bezhlavych jazdcov klesa exponencialne s poctom hodov.
Cau tomi. Vobec nepises dristy; to, co si napisal, je pravda. Ale takato uvaha je zatial len maly krocik k rieseniu ulohy, ktorym je popisat, za akych okolnosti (a ci vobec) ma hrac hadzanie mincou predcasne ukoncit a zobrat si svoju vyhru.
Uplne riesenie musi plne zodpovedat na vsetky otazky typu, napriklad: Ak dosial krupierovi padlo HZZ, je pre mna vyhodne povedat "stop!" a zobrat si svoje vyhrate 2 dolare, alebo mam pokracovat a dufat, ze sa mi este vyskytne Znak trikrat za sebou, no sucasne riskovat stratu v pripade, ze vo stvrtom hode padne Hlava a potom sa uz nevyskytne ani len jedna dvojica Znakov za sebou?
Mam taku myslienku. Ist na to odzadu.
Po 10. hode musim zobrat, co je.
Po 9. hode mam moznost vyberu. Pokial je moja doterajsia vyhra x a budem pokracovat, na 50% este ziskam 1, ale na 50% stratim x. Cize urcite sa mi oplati pokracovat len vtedy, pokial x=0, inac je skoncit (pre x=1 neostro) najlepsou strategiou. Ocakavana vyhra v najhorsom pripade je vtedy 1.
Po 8. hode mam tiez moznost vyberu. Pokial je moja doterajsia vyhra y a budem pokracovat, na 50% este ziskam 1, ale na 50% stratim y a moja nova ocakavana vhra uz bude len 0,5 (lebo vtedy x=0). Cize urcite sa mi oplati pokracovat len vtedy, pokial y=0, inac je skoncit (pre y=1 neostro) najlepsou strategiou. Ocakavana vyhra v najhorsom pripade je vtedy 1.
A teraz sa mozem postupne prehryzt (ake levovske) az k pozicii po 1. hode.
Vychadza mi vseobecna strategia: ked ziskam 1, beriem, co mam a koncim.
Teraz, ked tak nad tym uvazujem, mam este jeden mozny pristup: aky je ocakavany vynos z kazdeho jednotliveho dalsieho hodu, ked mam z nahratych? Pre z=0 je to 0,5. Pre z=1 je to 0, pre z>1 je to zaporne. Hm?
Napísal som si program, ktorý ráta očakávanú výšku výhry. Napríklad pre hornú hranicu 3 hody mi vychádza očakávaná výška výhry rovných 1. Pre hornú hranicu 10 hodov mám očakávanú výhru 1.90625. Tento program by vedel aj poradiť, čo spraviť v akej situácií. Otázkou zostáva, či je aj naozaj správny.
Lev: Ist na to odzadu je dobry napad ;-)
Avsak vo svojej uvahe po 8. hode si urobil chybicku: Ak mame prave jeden hodeny znak (t.j. 7. hod bol H a 8.hod bol Z), tak je optimalne hru este neukoncit.
Totiz s pravdepodobnostou 1/2 padne v 9. hode znak a v tom okamihu to s vyhrou $2 ukoncis, s pravdepodobnosotou 1/4 bude 9. a 10. hod ZH, kedy koncis s vyhrou $1 a s pravdepodobnosotu 1/4 to bude HH, kedy koncis s $0. Stredna hodnota je teda (1/2)*2+(1/4)*1+(1/4)*0=$1,25, co je viac ako $1, ktory by si ziskal ukoncenim hned po hode 8.
Nakoniec, takouto uvahou by Ti vyslo, ze aj ak by sa hadzalo milion hodov, tak by bolo optimalne skoncit po prvom znaku, cize s (takmer :-) stopercentnou isotou mas zisk presne $1, ale ak by si zvolil strategiu skoncit povedzme po dvoch naslednych znakoch, tak (tiez takmer) s istotou dosiahnes zisk $2.
Ale ako som napisal, hlavna myslienka je uplne spravna.
Lukas: Zrejme mas na mysli ocakavanu vysku vyhry pri optimalnej strategii hraca. Ano, pre 3 hody to mas spravne; optimalnu strategiu a ocakavanu vysku vyhry som nacrtol na tomto obrazku. A ci je to Tvoje riesenie spravne aj pre 10 hodov a aka je konkretne ta 10 hodova optimalna strategia? To nechajme na dalsich pripadnych zaujemcov, nech sa s tym este trochu popasuju... ;-)
Noooo, ked tak nad tym uvazujem... ked je hodov velmi vela, povedzme vela, vela, vela... tak ked si vopred povieme, ze skoncime, akonahle dosiahneme vyhru x, tak je celkom slusna sanca, ze sa x bodov za sebou podari dostat. Napriklad 10 - to potrebujeme 10 spravnych stran za sebou, cize 1 z 1024 moznosti. Ked takuto seriu 10 hodov nezavisle zopakujeme 1000x (a zanedbame 10-ky presahujuce z jednej serie do druhej), dostaneme aspon raz 10 bodov s pravdepodobnostou 1-(1023/1024)^1000, co je viac ako 62%.
Ked sa vratim k prikladu 10 hodov. Aka je sanca, ze za sebou ani raz nepadnu 2 znaky? Asi dost mala. Myslim, ze sa to da zratat rekurentne. (Preto treba niekde zacat.) Takze sa asi oplati cakat na dva znaky za sebou. Treba este preratat, ze sa neoplati cakat na tri znaky za sebou... a to by asi tak mohlo byt.
Lev: V tom prvom odstavci mas pravdu; ak by bola postupnost hodov velmi dlha, tak by nebolo dobre uspokojit sa len s dvomi-tromi za sebou iducimi znakmi, ale lepsie by bolo cakat na dlhsiu seriu znakov.
Co sa tyka druheho odstavca, tak pravdepodobnost, ze v serii 10 hodov sa niekde vyskytnu 2 znaky za sebou je 55/64, cize priblizne 86% a ze sa vyskytnu niekde 3 znaky za sebou je 65/128, co je priblizne 51%. Cakat na dvojicu znakov by teda urcite bolo lepsie, ako cakat len do prveho znaku.
Avsak optimalna strategia moze byt este komplikovanejsia: moze byt takeho typu, ze sa rozhodujeme nielen na zaklade toho, kolko mame dosial napadanych znakov, ale aj na zaklade toho, ake je cislo momentalneho hodu. Napriklad pri milion hodoch by sme sa na zaciatku neuspokojili len tak s nejakymi par znakmi za sebou, ale ked by sa nam uz pocet hodov chylil ku koncu, tak by bolo optimalne vziat aj skromnejsiu sumu :-)
Skratka tento problem je jeden z najtazsich, ake som tu dosial uviedol...
Odpoved na tvoju matematicku hadanku som ti poslal mailom. Mozes ho aj zverejnit...
Pridavam riesenie od Juraja, ktore mi poslal mailom. Momentalne sa vsak este k tomuto komplexnemu rieseniu neviem podrobnejsie vyjadrit :-) Kazdopadne zda sa, ze by mohlo byt OK.
-------------------------
Ako vyriesit hru:
Budem pocitat pre kazdy krok pravdepodobnost vsetkych moznych vyhier *
ich_hodnota. A vyberiem maximum z nich. Takze:
Zadefinujem f(X)=X, funkcia vynosu z X poslednych vyhernych minci
A ta suma:
P-pocet pokusov (P=10, podla zadania)
p-pocet uz uskutocnenych pokusov
n-pocet poslednych vyhernych minci; n=AKTUALNY_ZISK
P1(k)={1-(1/2)^(k-n))} pravdepodobnost, ze nebude hned nasledovat sekvencia [k*vyhra] (pre k=1..P-p)
P1(k)=1 pravdepodobnost, ze nebude hned nasledovat sekvencia [k*vyhra] (pre k=P-p+1..P-p+n)
P2(k)={[1-(1/2)^(k+1)]^(P-p-k)} pravdepodobnost, ze nebude (pre k=1..P-p+n)
P2(k)=1 pravdepodobnost, ze nebude (pre k=P-p+n+1..P)
sekvencia [prehra, k*vyhra] v dalsich kolach
Celkove mozne vynosy potom
Wi=f(k) * [1-P1(k)*P2(k)]
Sucasny vynos:
V=f(n)
Ak V>max{Wi}, neoplati sa ist dalej, cize zastavujem hru...
......................
package mince;
import java.util.Random;
/**
*
* @author Juraj Vanco
*/
public class Hra {
public double f(double X) { //vyherna suma, vstup: pocet rovnakych minci
return X;
}
public double pow(double zaklad, int mocnitel) {
double vysledok = 1.0;
for (int i = 0; i < mocnitel; i++) {
vysledok = vysledok * zaklad;
}
return vysledok;
}
double Hra(int N) { ////celkovy pocet hodov
int n = 0; //pocet uskutocnenych hodov
int p = 0; //pocet poslednych vyher
boolean HraPokracuje = true;
double Vyhra = 0;
for (n = 1; (n <= N) && HraPokracuje; n++) {
HraPokracuje = false;
Random generator = new Random();
int random = generator.nextInt(2);
if (random == 0) {
p = 0;
// System.out.print(n + ". KOLO: BOLA HODENA 0");
} else {
p++;
// System.out.print(n + ". KOLO: BOLA HODENA 1");
}
Vyhra = f(p);
// System.out.println(", pocet poslednych vyher:" + p + ".
Vyherna suma zatial: " + Vyhra);
for (int i = 1; i <= N; i++) {
double RevPravdepodobnost;
if (N - n - i <= 0) {
RevPravdepodobnost = 1.0;
} else {
RevPravdepodobnost = pow(1 - pow(0.5, i + 1), N - n - i);
}
if ((p < i) && !(N - n - i + p < 0)) {
RevPravdepodobnost = RevPravdepodobnost * (1 - pow(0.5,
i - p));
}
double Pravdepodobnost = 1 - RevPravdepodobnost;
double MoznaVyhra = f(i) * Pravdepodobnost;
// System.out.print("Pravdepodobnost vyhry " + i + " minci je
teraz:" + Pravdepodobnost + ". Mozno vyhrat: " + MoznaVyhra);
if (MoznaVyhra > Vyhra) {
HraPokracuje = true;
// System.out.println(" HRA POKRACUJE!!!");
} else {
// System.out.println();
}
}
System.out.print(p + " ");
}
System.out.println("Tvoja vyhra:" + Vyhra);
return Vyhra;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int N = 1000; //pocet hier
double Vynos = 0;
Hra JednaHra = new Hra();
for (int i = 0; i < N; i++) {
Vynos = Vynos + JednaHra.Hra(10);
}
System.out.println("Tvoj vynos:" + Vynos + ", na jednu hru:" + Vynos
/ N);
}
}
Testoval som Jurajove riešenie a pre 3 hody dávalo priemerný zisk okolo 0.9. Keď už sa sem dáva kód, tak tu je môj. Treba to vhodne odsadiť, lebo je to Python :-)
def max(x, y):
if x > y:
return x;
return y;
n = 100
vyhra = [0]
for i in range(1, n):
q = i
for j in reversed(range(1, i)):
q = max(j, (vyhra[i-1-j] + q) / 2.0);
vyhra.append((vyhra[i-1] + q) / 2.0)
for i in range(0,len(vyhra)):
print i, vyhra[i]
Uvedený program by sa dal upraviť aj na verziu, ktorá reaguje online na padnuté mince.
Zistil som, ze moj algoritmus nie je optimalny...
Uz mam pripraveny novy. Juraj.
OK Juraj. Keď ho budeš mať, skús pomocou neho vypočítať strednú hodnotu zisku pri tom maxime 10 hodov ako je v zadaní, či to bude to isté, čo vyšlo Lukášovi, t.j. 1,906.
Takze:
Lukasovemu algoritmu nerozumiem, mohol by si dat k nemu vysvetlenie?
Program este nie je hotovy, je len myslienka. V prvom kroku som totiz povodny moj algoritmus vylepsil a tento uz dava vysledok 1.906 pri 10 hodoch. Problem je, ze nie je stale optimalny (odskusane pri 100 hodoch). Preco je to tak mi uz je jasne (algoritmus ide do vyssieho rizika ako je potrebne), viem aj preco, len som si to este nenaprogramoval. V tomto tyzdni to vsak (dufam) stihnem.
Skúšal som to spočítať rekurentne (na počítači samozrejme) a vyšlo mi to 1,906250000 a to pri optimálnej stratégii ktorá je asi jasná - zastanem, ak očakávaná hodnota v prípade že budem pokračovať je menšia, ako to čo zatiaľ mám. Takže to už som tretí, asi to bude teda dobrý výsledok.
Teda Michal, vsetko znie ok, az na tu poslednu vetu: "Takže to už som tretí, asi to bude teda dobrý výsledok." Dokaz mnozstvom tych, ktori maju rovnaky nazor? To je nejaka nova metoda dokazu? :-)
Juraj, Michal: OK.
Lev: Samozrejme, hocikolko ludom moze vyjst to iste, a aj tak to moze byt nespravne. Ale Michal netvrdi, ze je to tym definitivne dokazane, len ze je to asi dobre a s takymto sposobom uvazovania sa v principe da suhlasit. Pravda, mohli by sme spisat aj formalny matematicky dokaz, ktorym by sa dane tvrdenie (prakticky) definitivne potvrdilo.
Nic si z toho nerobte, ze vyryvam. Stve ma, ze som na riesenie neprisiel ja a tak hryziem. :-)
OK Lev :) Mozno sa Ti vsak podari rozlusknut deformovanu kocku, ktoru som prave publikoval.
Skusim to zatial aspon slovne popisat, kedze tento tyzden nemam moc casu. Ja pouzivam slovo 'vyhra' ako 'vyherna strana mince' a 'prehra' ako 'nevyherna strana mince'.
Moje rieseni nebralo do uvahy alternativy, t.j. treba zapocitat do pravdepodobnosti toto:
1. P1=pravdepodobnost, ze teraz padne [k*vyhra]
2. P2=pravdepodobnost, ze odteraz na k-tom mieste padne [prehra] a hned alebo niekedy potom padne [prehra, m*vyhra]
Ak spocitame f(k) * P1 + m(k)*P2, dostavame sumu, ktoru porovname s aktualnym ziskom. Ak je aktualny zisk nizsi, pokracujeme.
--------------------------------------
Predchadzajuci algoritmus riesi hlavny problem mojho prveho algoritmu, t.j. ked neskor prehrame, aku mame este sancu ziskat "nieco"...
--------------------------------------
Tento nacrtnuty algoritmus stale nie je v poriadku, pretoze uvazuje napr. aj o moznostiach [prehra, m*vyhra] aj pri konci hry (predstavme si, ze pri konci hry budem uvazovat, ze mi padne 8*vyhra... jednoducho nepadne, pretoze uz predtym moj algoritmus skonci hru). Preto treba vlozit este 2 uvahy, resp. vypocty:
1. P1=pravdepodobnost, ze bude nasledovat hned [k*vyhra], pricom sam algoritmus musi otestovat, ci sa na mieste n+k (n- pocet uskutocnenych hodov) moze nachadzat vyhra p+k (p- aktualny zisk). Ak sa nemoze, P1=0.
2. P2=pravdepodobnost, ze bude nasledovat [prehra, m*vyhra] po tom, co bude hned nasledovat [k-1*vyhra]. Pricom sa musi otestovat, ci sa na mieste, kde testujem [prehra, m*vyhra] moze nachadzat vyhra m. Ak nie, tieto moznosti uz neprinasam do vypoctu pravdepodobnosti.
---------------------------------------
Nacrtnuty algoritmus teda musi ist odzadu a zapisovat si min. mnozstvo bodov, ktore treba pre kazde miesto, ak chceme zastavit hru. Vyuzije na to moj algoritmus, ktory zase vyuziva uz vypocitane min. vyhry potrebne na stopnutie hry (pre miesta, ktore budu este len nasledovat)...
Takuto tabulku potom uz len aplikujem na hody. Hlavny algoritmus teda spociva vo vytvoreni tej tabulky.
--------------------------------------
Neviem, ci tam bolo vsetko jasne, ale snazil som sa :)
Juraj
Ozaj a este...
Testoval som moj program (ten bez implementacii myslienky o niektorych hodoch, ktore neprichadzaju do uvahy) pre 100 hodov a dalo to vysledny zisk:4.275.
Naviac niekto tu spominal, ze pouzije lukasovu tabulku na algoritmus pre hru... Mne to ale nevychadza, s mojim algoritmom casto mam aj vyhru 6, dokonca 7 v hre! I ked som napisal, ze nie je optimalny. Uvidime, co sa stane, ked ho prekopem...
Juraj
Zverejnenie komentára