Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: OliverGGGGGG 25. 02. 2016, 18:53:58
-
Zdravim,
podme na problem:
Definicia:
PROVABLY FAIR je mechanizmus ktorym napriklad online kasina "dokazuju" ze nie su rigged. Funguje to pomerne jednoducho. Napriklad pri nejakej hre ma hrac typnut cislo od 1 - 100. System cislo 1-100 vygeneruje este predtym ako hrac typne a nejaku zakodovanu verziu (hash alebo nieco podobne) hracovi ukaze este pred jeho stavkou.
HRAC stavi, a bud vyhra alebo prehra a aby si bol isty moze si overit ze ten 'hash' ktory mu bol rpedom dany je naozaj z cisla ktore bolo neskor ukazane - teda ho nikto neoklamal a cele to bolo len o jeho tipe.
Ok PROBLEM:
Potreboval by som podobny mechanizmus implementovat do hry kde nie je znama vrchna hranica rolovania predom. Teda rolovane cislo je od 0 po X pricom X moze byt kludne 100 alebo 2313216548 ale napriklad nie viac ako 10 na 12tu.
Mate napad ako by to slo?
DOLEZITE: Musi to byt naozaj FER - tzn ziadne zaokruhlovania, alebo "priblizne" proste bud alebo. :-)
PRIKLAD:
Moj napad bol rolovat (X) 0 az Y (pricom Y je obrovske cislo omnohokrat vacsie ako je je pomyselny limit (Z), teda napriklad 0 az 10000000000000 potom urobit
X mod Z a to by bolo moje nahodne cislo z toho pola 0 az Y.
ALE: ukazalo sa ze to nie je vzdy fer a moze casto hracov znevyhodnovat (aj ked malo ale predsa).
Priklad:
3 hraci a roll 1-10
aby vyhral 1 staci rollnut: 1, 4, 7, 10
aby vyhral 2 : 2 5 8
a aby vyhral 3 : 3, 6, 9,
A teda ich sance nie su 33% ale 40, 30, 30 z dovodu ze sa rolovalo 0-10 a nie 0-9
takze riesenie nie je dokonale...
Napady ? :)
Dakujem
-
Co to neřešit a prohlásit, že 10^12 je o 140 řádů menší než výstup SHA512, kterou určitě používáš, a tudíž nerovnoměrnost vnesenou modulením nemá cenu řešit?
Další možnost je třeba:
Server vygeneruje náhodné číslo I a jeho hash pošle hráči.
Následně dojde k určení, že se bude rolovat do M (jestli jsem to dobře pochopil).
Server najde nejbližší mocninu dvojky >= M.
Serve pomocí I naseeduje CSPRNG.
Server počítá T ← M+1; while(T>M) { T ← vezmi M bitů z výstupu CSPRNG }; return T;
T je hodnota, kterou chceš.
-
ugh… Samozřejmě vezmi ceil(log2(M)) bitů z PRNG.
-
@Jenda diki za reakce :-)
Prvni cast: ee nemuzu :-( jak to neni 100% fer tak to nemuzu pouzit :-(
A to druhe... Uh kamo ja mam daleko od matematika :-( ale idem to skusit pochopit ako si to myslel popripade skus vysvetlit 'jednoduchsie' ? :-))
Dakujem
-
> Prvni cast: ee nemuzu :-( jak to neni 100% fer tak to nemuzu pouzit :-(
To musí být zajímavá aplikace, když řeší problém, který nastane s pravděpodobností mnohem nižší, než 1:počet_atomů_ve_vesmíru.
> A to druhe... Uh kamo ja mam daleko od matematika :-( ale idem to skusit pochopit ako si to myslel popripade skus vysvetlit 'jednoduchsie' ? :-))
No prostě tím naseeduješ náhodný generátor a budeš z něj číst čísla. Pokud bude přečtené číslo větší, než potřebuješ, tak ho zahodíš, pokud bude menší, tak ho použiješ. A protože generátor dává bity, budeš zahazovat maximálně polovinu čísel.
-
Ok myslim ze chapem co chces povedat, ale problem je stale v tom ze to nie je 'fer' teda ak to chapem spravne. Aj ked len o MINIMUM no nie je to dokonale.
Proste vygenerujem random velky pocet BITOV ano?
Napriklad
10110101010111110001010
Ok a rolujem
0 -> 14
Teda 0 -> 1110
A teraz budem postupne pridavat bity a ak bude vzniknute cislo vacsie pouzijem predchadzajuce?
1
10
1011
100110 -> !!! Beriem predchadzajuce
Takze 1011 je moje nahodne?
Chapem spravne?
Ale tam su dva problemy, jeden vacsi jeden mensi.
Mensi:
Co ak mi rolovanie zacina '0'?
Vacsi:
Problemom su parne a neparne 'limity' lebo pri jednom sa zahadzuju a pri jednom je to ok. Takze jedno bude mat 'vacsiu' sancu ako druhe nie?
-
> A teraz budem postupne pridavat bity a ak bude vzniknute cislo vacsie pouzijem predchadzajuce?
Ne. Prostě zjistíš, že potřebuješ náhodné číslo od 0 do 93. Spočítáš, že na to je potřeba 7 bitů (horní celá část dvojkového logaritmu 93). A pak vždycky přečteš 7 bitů a podíváš se, jestli je to <= 93. Pokud ne, zahodíš, pokud ano, vracíš to jako výsledek.
-
Chapu okej. Zahodim jako celek. Ok.
Ano to by slo, a myslim ze by to bylo taky fer. Proste Phil s velke - tak zahodit a dalsich 7 bitu. A znova a znova. Ok.
Pri dlouhem retezci 0 a 1 na tom opravdu jako laik nevidim chybu.
Hmmm :-) nice
Dekuju moc! :-)
-
Len to musi mat fixnu dlzku aby napriklad zacinal ten string aj viacerymi 0.
Ine problemy ma fakt nenapadaju..
-
Řešení je jednoduché – nejprve si musíte pořádně ujasnit a popsat zadání. Generovaná náhodná čísla asi nebudou neomezeně velká, už jenom kvůli limitům paměti počítače nebo čase jejich generování. Hráč asi také bude chtít vědět, do jakého limitu se má vejít. Pak tam ale zase píšete, že horní hranice existuje, akorát není známá předem. Před čím? Před okamžikem, než bude hráč tipovat, asi známá být musí. Tak tu náhodnou hodnotu vygenerujte po té, když ta hranice známá je.
Zkrátka z toho vašeho zadání vůbec není jasné, o co se vlastně snažíte a v čem je problém. A je dost pravděpodobné, že až si to sám ujasníte a popíšete, uvidíte, že řešení je triviální.
-
Vrchna hranica losovania zial naozaj nie je jasna az do uplneho konca.
Zadanie:
Sutazi sa o hlavnu cenu. Povedzme tombola. Kazdy si kupi 0 az N listkov. Niekto si kupi 1. Niekto 2 niekto 11252.
Nakoniec musim 'zlosovat' ktory listok vyhrava. A to tak ze random generatorom vygenerujem cislo 1 az P (pocet predanych liatkov v tombole).
Potom zakricim cialo listku a kto ho ma ten vyhrava.
A potrebujem tuto 'nahodou' vylosovat skor ako predam vsetky listky do tomboly aby si sutaziaci vedeli overit ze som im neklamal a od zaciatku bolo jasne ake cislo / cisla budu vylosovane.
Moze byt?
-
Může být. Pak musíte vygenerovat náhodná čísla pro všechny možné počty prodaných lístků. Takže nebude od začátku jasné, jaká čísla budou vylosovaná, ale bude od začátku jasné, že pokud se prodají 2 lístky, bude vylosován lístek A, pokud 3 lístky, bude vylosován lístek B atd.
-
Ale pak může poskytovatel podvádět tak, že se před koncem prodeje podívá, kdo by vyhrál, a může kamarádovi říct "když si koupíš pět lístků, vyhraješ".
-
Ano, to může, ale to pokaždé, když je vylosované číslo známé předem, a teprve pak je možné kupovat další lístky.
-
Tak tu hovorime realne o losovaniach
0 az kludne 10 miliard...
Takze hladam lepsie riesenie ako 10miliard nahodnych losovani a ukladania vysledkov do nejakej tabulky preboha ;-)
Tu to musime skalovat aby to fungovalo aj aj.
Tamto by bolo zverstvo :-)
-
Lepší řešení s generováním diskrétních náhodných čísel neexistuje. Pokud dokážete generovat náhodná čísla ze spojitého intervalu (třeba budete mít generátor, který vygeneruje se stejnou pravděpodobností libovolné reálné číslo z intervalu 0–1), můžete „jednoduše“ vygenerovat takové číslo, zveřejnit třeba hash jeho dekadického zápisu, a až se „prodají všechny lístky do tomboly“, interval 0–1 rozdělíte na N stejných intervalů podle počtu prodaných lístků. Akorát bych nechtěl být ve vaší kůži, až vám ten náhodný generátor vygeneruje náhodné číslo, které má v dekadickém zápisu 101000 číslic, to ještě budete vzpomínat na 10 miliard náhodných losování.
-
Myslím, že Filip dal výbornou radu pořádně si to sepsat a pak teprv řešit. Takže jestli správně chápu, tak postup má být tenhle:
1. získám nějakou náhodnou veličinu R
2. z veličiny R udělám hash a ten zveřejním
3. prodám N lístků
4. Na základě R vyberu algoritmem A výherní lístek tak, že každý z N lístků má stejnou pravděpodobnost být vybrán.
Hledáme algoritmus A.
Je to tak?
Pro začátek bych si ujasnil, jestli doopravdy striktně potřebuješ ten požadavek "každý lístek má stejnou pravděpodobnost být vybrán". Pokud bys totiž použil to modulo, tak sice některé lístky znevýhodníš, ale předem nevíš jaké a je to závislé na počtu prodaných lístků. Takže bych se ptal, jestli ta náhoda může nebo nemůže záviset na počtu prodaných lístků.
Pokud opravdu ne, tak lepší řešení než to, co zaznělo, asi těžko vymyslíš.
-
Pokud opravdu ne, tak lepší řešení než to, co zaznělo, asi těžko vymyslíš.
Ne těžko, prostě to nejde. Když má množina, ze které se vybírá náhodné číslo, N prvků, a prodá se X lístků, bude to spravedlivé jedině tehdy, pokud na každý lístek připadne Y prvků z té množiny náhodných čísel. Nebo-li N = X × Y. N pak tedy musí být (nejmenší) společný násobek všech čísel od 1 do maximálního možného X. Pokud X může být 10 miliard, je jedno, zda spočítá deset miliard náhodných čísle, nebo zda vygeneruje jedno náhodné číslo v rozsahu 1 až NSN(1…10 miliard).
-
Tazatel má nějaký psychický blok modulit třeba 10000bitová čísla, kde je ta odchylka od rovnoměrného rozdělení taková, že ji v tomto a několika příštích vesmírech není potřeba řešit.
Ne těžko, prostě to nejde.
Já jsem navrhoval, jak si generovat ta čísla na přání…
-
Tazatel má nějaký psychický blok modulit třeba 10000bitová čísla, kde je ta odchylka od rovnoměrného rozdělení taková, že ji v tomto a několika příštích vesmírech není potřeba řešit.
Spíš mě teď tak napadá, jestli by se to nedalo řešit tak, že kdyby bylo 250 lístků, tak se použije 8 bitů a těch plonkovních 6 lístků by bylo jako bank a když by to náhodou padlo na ně, tak by nevyhrál nikdo.
Anebo ještě lepší nápad: vyhrál bych já! Zadání by to splnilo: každý z lístků by měl stejnou šanci vyhrát, to nikdo nemůže popřít! :))
-
Já jsem navrhoval, jak si generovat ta čísla na přání…
Jenže to vaše řešení nesplňuje tu podmínku absolutně stejné pravděpodobnosti pro vylosování všech lístků. Ten požadavek je nejspíš úplně zbytečný, ale tazatel musí nejprve pochopit, že problém není v tom, že nikdo neumí navrhnout efektivnější algoritmus, ale v tom, že z matematických zákonů plyne, že uvedený algoritmus je ten nejefektivnější. A že tedy bude muset slevit z některého požadavku.
Spíš mě teď tak napadá, jestli by se to nedalo řešit tak, že kdyby bylo 250 lístků, tak se použije 8 bitů a těch plonkovních 6 lístků by bylo jako bank a když by to náhodou padlo na ně, tak by nevyhrál nikdo.
Že by se jako vzor nepoužila tombola, ale kasino – hrát můžete, jak chcete, ale stejně nakonec vždycky vyhraje pořadatel :-)
-
Spíš mě teď tak napadá, jestli by se to nedalo řešit tak, že kdyby bylo 250 lístků, tak se použije 8 bitů a těch plonkovních 6 lístků by bylo jako bank a když by to náhodou padlo na ně, tak by nevyhrál nikdo.
Že by se jako vzor nepoužila tombola, ale kasino – hrát můžete, jak chcete, ale stejně nakonec vždycky vyhraje pořadatel :-)
Ne! Vyhraju JÁ, ne pořadatel, to je důležitá součást algoritmu,bez toho mu na něj nedám licenci! :))
Ale vážně: zakomponování té možnosti, že nevyhraje nikdo, ten problém docela elegantně řeší, pokud OP opravdu striktně trvá na úplně stejné šanci všech lístků. Nevýherních lístků může být v nejhorším případě n-1, takže ppost nevýhry cca 1/2. Pokud nikdo nevyhraje, může to zopakovat s další předem vygenerovanou posloupností bitů a ppost celkové nevýhry se bude docela rychle blížit k nule. Podle toho, jak velkou ppost celkové nevýhry chce akceptovat, tolik čísel si předem vygeneruje. A bude jich daleko míň než miliardy :)
-
Helou :-)
Dakujem za reakcie a plodne napady :-) pre toto mam rad root.
Tie riesenia s modulom:
- niektore znevyhodnit: no-go: lebo zakladom provably fair je open source algorytmus a ludia by lahko prisli na to ze napriklad par sekund pred koncom limitu na nakup listkov - sa ich kupovat neoplati lebo budu holt znevyhodnene.
(Premiesavat pool nechcem/nemozem/nemam)
-'odstrihnut' prebyvajuce listky pol limit modula a vratit ich zaujemcovi s tym ze : sorry tieto ti uz nepredam lebo tombola konci - no-go lebo chceme predat maximum listkov
- oznacit listky ktore neboli predane ako 'nevyhrava-nikto' vyhravame my - je tiez no-go lebo nasa tombola nesmie byt 'ziskova'
Takze naozaj mi jedine co ostava je 'viacero' losovani ak je treba a ten napad s bitmi sa mi paci najviac. Nemam problem dat vygenerovat dokopy aj pevnu dlzku 500 bitov a jej hash zverejnit. Z tych 500 bitov uz moje cislo trafim :-)
Ouk budem sa s tym hrat a ladit velkost toho nahodneho stringu ;-)
-
Mám pocit, že v tom pořád trochu těkáš a nejseš si úplně jistej, co vlastně děláš :) (bez urážky)
a ludia by lahko prisli na to ze napriklad par sekund pred koncom limitu na nakup listkov - sa ich kupovat neoplati lebo budu holt znevyhodnene.
Je to opačně - zvýhodněné jsou lístky na začátku modulu. Když budeš mít těch zmíněných 250 lístků a 8-mi bitové číslo, tak každý lístek bude mít jednu šanci + prvních 6 lístků bude mít ještě jednu navíc. Čím větší je to R (předem připravené náhodné číslo), tím je to zvýhodnění menší (např. každý má 10^6 šancí a prvních x má jednu navíc -> zanedbatelný rozdíl).
(Premiesavat pool nechcem/nemozem/nemam)
To by ti ani nijak nepomohlo.
- oznacit listky ktore neboli predane ako 'nevyhrava-nikto' vyhravame my - je tiez no-go lebo nasa tombola nesmie byt 'ziskova'
Takze naozaj mi jedine co ostava je 'viacero' losovani ak je treba a ten napad s bitmi sa mi paci najviac. Nemam problem dat vygenerovat dokopy aj pevnu dlzku 500 bitov a jej hash zverejnit. Z tych 500 bitov uz moje cislo trafim :-)
Tomuhle nerozumím. Jestli mluvíš o tom mém návrhu, tak tam nemusí být kasino ziskové - prostě v tom daném kole nevyhrává nikdo. A pokud chceš, můžeš použít dalších m bitů z náhodného řetězce a opět máš nějakou ppost, že nevyhraje nikdo. Ta ppost, že celkově nevyhraje nikdo se s počtem kol rychle snižuje - je přibližně rovná (1/2)^k kde k je počet pokusů -> rychle to konverguje k nule a můžeš si předem zvolit, jak malé pposti celkové nevýhry chceš dosáhnout.
-
je přibližně rovná (1/2)^k kde k je počet pokusů
- teda v nejhorším případě, to jsem zapomněl napsat.
-
A ještě jedna poznámka: počet prodaných lístků nemusíš průběžně zveřejňovat.
-
To předem vygenerované malé číslo ovšem pořád má ten problém, že buď některé lístky vyhrát nemohou, nebo se naopak může stát, že vyhraje neprodaný lístek. Na tom, zda to číslo zapíšete binárně nebo dekadicky přece vůbec nezáleží.
Stačí si to představit na malých číslech. Prodáte 10 lístků. Z toho řetězce bitů tedy použijete buď 3 bity, takže náhodné číslo může ležet v rozsahu 1 až 9, tedy lístek s číslem 10 nemůže vyhrát. Nebo použijete 4 bity, takže náhodné číslo bude ležet v rozsahu 1–17, tím pádem můžou být výherní lístky č. 11–17, které jste neprodal.
Vaše snaha docílit nějakým trikem toho, aby podíl dvou libovolných celých čísel byl vždy celočíselný, je sice zábavná, ale opravdu se vám to žádným trikem nepodaří. Jediný způsob, jak toho docílit, je ten, že dělenec (velikost množiny, ze které vybíráte náhodná čísla) bude celočíselným násobkem nejmenšího společného násobku všech možných dělitelů (možných počtů prodaných lístků).
Pokud jsou počty možných prodaných lístků příliš vysoké, abyste s tím mohl pracovat výše uvedeným způsobem a zajistit absolutní spravedlnost, nezbývá vám, než někde slevit – buď připustit nepatrné rozdíly v pravděpodobnosti výhry, nebo připustit určitou pravděpodobnost, že nevyhraje nikdo. V obou případech si tu pravděpodobnost můžete zvolit, podle toho, s jak velkými náhodnými čísly dokážete pracovat.
-
Já jsem navrhoval, jak si generovat ta čísla na přání…
Jenže to vaše řešení nesplňuje tu podmínku absolutně stejné pravděpodobnosti pro vylosování všech lístků.
Proč?
-
A co takhle použít nejaký standardní dobrý náhodný generátor, před prodejem lístku si nějak vygenerovat seed, zveřejnit jeho hash (+ ten generátor) a vyhrávající lístky ověřit pomocí ověřitelného generátoru s ověřitelným seedem? Vlastní losování sice proběhne až po prodeji, ale výsledek bude jednoznačně určený seedem a počtem prodaných lístků.
Tím, že org ví co padne a může toho zneužít, trpí všechny předgenerované možnosti.
-
Helou :-) opet
Nene ja v tom mam uplne jasno :-) ale porat hledate skulinku jako 'mozne' a sice ne uplne dokonale reseni. Priklad s tombolou je jenom priklad ale hodne hodne pomaha pochopit koncept lebo je to cca 1:1 so mnou.
Pravidla tak jak sem psal sou stejne od zacatku:
- potrebuju spravedlivy (100%, ne 99,99999% ale 100%) system
- musim ukazat jeho prubeh predem
- limit od 1 po N kde 0 < N < 10na15
Jeste info co sem opravdu zapomel: pocet listku zverejnovat musim, zakaznici v case kupovani kuponu potrebuji vedet svoji momentalni sanci (ktera se casem ofc nakupem dalsich listku meni)
Neni to tazkre pochopit co chci ne? :D
A jop tam s tim zvyhodnenim/znevyhodnenim pri modulu sem popletl zacatek a konec - ofc ale vcera sem moc chlastal :-( a psal sem to rano jeste v meh.. Stavu.
Kazdopadne to reseni s retezcem binarek se mi libi. Jaka je tam kritika? Pac nekdo psal ze to neni mozne a toto se me osobne libi a podle mne splnuje co chci ne?
Diki :-)
-
Já jsem navrhoval, jak si generovat ta čísla na přání…
Jenže to vaše řešení nesplňuje tu podmínku absolutně stejné pravděpodobnosti pro vylosování všech lístků.
Proč?
Myslíte to generování náhodného čísla z rozsahu 1 až 2n takového, že 2n bude nejbližší mocnina dvojky větší než počet prodaných lístků? Tam vám pořád zůstávají ta čísla větší než počet prodaných lístků a menší nebo rovna té mocnině dvojky, která buď znamenají, že nevyhrál nikdo, nebo je přidělíte některým lístkům (třeba modulo počet prodaných lístků), čímž ale u daných lístků zdvojnásobíte pravděpodobnost výhry.
To, že podíl dvou libovolných celých čísel nemusí být celé číslo fakt neokecáte…
-
Myslíte to generování náhodného čísla z rozsahu 1 až 2n takového, že 2n bude nejbližší mocnina dvojky větší než počet prodaných lístků? Tam vám pořád zůstávají ta čísla větší než počet prodaných lístků a menší nebo rovna té mocnině dvojky
Samozřejmě. Proto když vygeneruju číslo větší než počet prodaných lístků, tak ho zahodím a generuju nové. Generátor je naseedován pomocí seedu, jehož hash jsem předem zveřejnil.
-
Sak pokial 'nagenerovame' cislo je vacsie ako limit N tak sa cele zahodi a 'losuje' sa znovu.. A znovu a znovu az kym neni < ako N.
To mam ako keby v jednom dlhom stringu 0 a 1 viacero ferovych hodov z ktorych ale niektore holt nemusia vyst.
Ale ak nevysli:
Nebol nikto zvyhodneny ani nezvyhodneny lebo sanca ze to padne na nejaky z predanych listkov je rovnaka.
Ak vysli:
Tak super a tiez bolo losovanie fer lebo kazdy listok mal rovnaku sancu.
Tak ako to chapem vidim jediny problem dlzku retazca 0 a 1 ale ta nech je klidne dlha veeeelmi :-) alebo problemu ze by bola cela rada len 1 a teda 'generovane' cislo by bolo vzdy vacsie ako limit N. Ale to nepredpokladam :-)
Chapem to spravne?
-
ne uplne dokonale reseni
Dokonalé řešení už tu padlo. Pro vás je nerealizovatelné kvůli moc velkým počtům „prodaných lístků“. Zároveň tu už také bylo napsáno, proč žádné efektivnější řešení nemůže existovat. Takže máte tři možnosti – buď si počkat, až budou k dispozici ještě daleko lepší počítače, které ty objemy dat zvládnou, nebo si počkat, až někdo totálně překope takový základ matematiky, jako je násobení přirozených čísel, nebo slevit z požadavků na dokonalé řešení. A nebo ta náhodná čísla generovat analogově, tedy aby se generovala čísla ze spojitého intervalu – ale nevím, jak na takových „analogových“ číslech realizovat jednosměrnou (hashovací) funkci.
Kazdopadne to reseni s retezcem binarek se mi libi. Jaka je tam kritika? Pac nekdo psal ze to neni mozne a toto se me osobne libi a podle mne splnuje co chci ne?
Kritika je pořád stejná. „Řetězec binárek“ znamená, že předem vygenerujete náhodná čísla pro 2n prodaných lístků, kde n jsou přirozená čísla od 1 do vámi zvolené hodnoty (přičemž čísla pro nižší n jsou ve skutečnosti odvozená od čísel s vyšším n, takže to můžete dobře zkomprimovat). Nebo-li budete mít vygenerovaná čísla pro 2 prodané lístky, 4 prodané lístky, 8 lístků, 16, 32, 64 atd. Jenže lístků se nemusí prodat množství odpovídající mocnině dvojky, může se jich prodat 5, 17, 60… Když lístků prodáte 5, použijete náhodné číslo pro 8 lístků, jenže vám tam pořád ty 3 přebývají – buď řeknete, že nevyhrál nikdo (což nechcete), nebo ty tři pozice rozdělíte mezi prodané lístky – jenže 3 pozice nerozdělíte rovnoměrně mezi 5 lístků (pořád je to ten problém s celočíselným dělením), můžete to přidělit jenom třem lístkům, kterým zdvojnásobíte pravděpodobnost výhry (nebo to klidně můžete dát jednomu lístku, kterému pravděpodobnost zečtyřnásobíte). A úplně to samé platí i pro ostatní případy, kdy počet prodaných lístků neodpovídá mocnině dvou.
-
Samozřejmě. Proto když vygeneruju číslo větší než počet prodaných lístků, tak ho zahodím a generuju nové. Generátor je naseedován pomocí seedu, jehož hash jsem předem zveřejnil.
To je to řešení, které tu popsal Mirek Prýmek. Tedy že se losuje opakovaně, přičemž s počtem kol se pravděpodobnost, že se nepodařilo vylosovat platné číslo, limitně blíží nule – ale nuly nikdy nedosáhne.
Není to dokonalé řešení, ale je pravda, že v popisu požadavků dnes ve 14:20 není požadavek na to, aby bylo 100% zaručeno, že se dočkáme konce losování.
-
Samozřejmě. Proto když vygeneruju číslo větší než počet prodaných lístků, tak ho zahodím a generuju nové. Generátor je naseedován pomocí seedu, jehož hash jsem předem zveřejnil.
Ha, taky jsem naletěl – neuvědomil jsem si, že používáte generátor pseudonáhodných čísel, u kterého není zaručeno to 100% spravedlivé rozdělení. To je zaručené jedině u skutečného (hardwarového) generátoru náhodných čísel. To celočíselné dělení fakt nejde obelstít :-) A když se veškerá „náhoda“ musí vygenerovat předem, pořád je tu ta mizivá pravděpodobnost, že vygenerovanou náhodou spotřebujeme a pořád nikdo nevyhrál.
-
Tak ako to chapem vidim jediny problem dlzku retazca 0 a 1 ale ta nech je klidne dlha veeeelmi :-) alebo problemu ze by bola cela rada len 1 a teda 'generovane' cislo by bolo vzdy vacsie ako limit N. Ale to nepredpokladam :-)
Nejen celá řada jedniček, ale prostě čísla, která jsou větší, než počet prodaných lístků. Sice to „nepředpokládáte“, ale to je přesně ta pravděpodobnost, že nikdo nevyhraje, o které psal Mirek Prýmek (a která se s prodlužováním předem vygenerovaného náhodného čísla limitně blíží nule). Takže pokud vám nevadí, že existuje nenulová pravděpodobnost, že nevyhraje nikdo…
-
@Filip a vsechny jeho reakce:
Helou uz myslim ze chapes ja ksem to myslel. Ano pokud by sem vygeneroval na zaklade 0-32 a padlo by mi 31 ale predanych by bylo jenom 30 tak - ja to NEPOUZIJU ale jako celek zahodim a skusim zas.
Takze ano problem je teda jediny : ze ako som pisal ja ako priklad ze same 1. Alebo ako si pisal ty, co je ale to iste :), ze cisla proste vacsie ako mnozstvo predanych listkov.
Takze jedine riziko ktore worst- case sa moze stat je - ze nevylosujem nikoho. Ale AK vylosujem tak JE to fer (nie?).
Pripad NEvylosovania sa da predsa osetrit ale hlavne - je menej problematicky ako "NEFEROVOST".
Priklad:
- Dam si vygenerovat 150 CHAR dlhy string 0 a 1 (1,4 x 10 na 45!)
- Pevna dlzka preto aby zaciatok mohol byt 00001.... a nuly sa mi nestratili
- 500 CHAR 0 a 1 mi pokryje naprikald: 0 az 1000 000 000 000 (bilion) celkovo 1,4 x 10 na 33!
- Ok a teraz ten problem:
Takze vdaka tomuto mozem rolovat extremne vela krat, sanza ze by to stale nepadlo je MINIMALNA a pre mna nedolezita - lebo sa to proste nestane. Mat tak vela '1' vedla seba je nahoda tak mala ze ju mozem zanedbat.
Dolezite pre mna je: Ze zanedbavam naozaj malu sancu na NEVYLOSOVANIE ale v momente ako VYLOSUJEM je to FER. A ako to vidim ja tak 100% fer. A to je to dolezite :-) ze nikoho nepripravim o jeho "sancu", nikomu ju "nepridam" a riskujem len ze nevylosujem ale to sa nestane.
A este dve veci len na okraj len tak :-) :
- nahodny generator cisel pouzivame HW samozrejme
- stale nevidim problem ani v overeni toho stringu nejakym sposobom (napriklad : je tam 0?) a ak nie je tak pevnaDlzka +1 a dam dalsie nahodne cislo, a znova - je tam 0? a Znova a znova? Takze je to nahodna postupnost 0 a 1 ktora ma urctu vlastnost - takze by som mohol dokonca aj ten pripad jednotiek ( 1...11111...1) eliminovat uplne nie?
:)
Dakujem opat za reakcie <3
-
Vaše snaha docílit nějakým trikem toho, aby podíl dvou libovolných celých čísel byl vždy celočíselný, je sice zábavná, ale opravdu se vám to žádným trikem nepodaří.
To je reakce na mě nebo na koho? O nic takového se přece nesnažím. Kdybych se o to snažil, tak bych neřekl, že existuje nenulová ppost, že nevyhraje nikdo. Což jsem řekl.
Jediný způsob, jak toho docílit, je ten, že dělenec (velikost množiny, ze které vybíráte náhodná čísla) bude celočíselným násobkem nejmenšího společného násobku všech možných dělitelů (možných počtů prodaných lístků).
Pokud jsou počty možných prodaných lístků příliš vysoké, abyste s tím mohl pracovat výše uvedeným způsobem a zajistit absolutní spravedlnost, nezbývá vám, než někde slevit – [...] nebo připustit určitou pravděpodobnost, že nevyhraje nikdo. V obou případech si tu pravděpodobnost můžete zvolit, podle toho, s jak velkými náhodnými čísly dokážete pracovat.
Ale vždyť přesně tohle píšu. Když předpokládám maximálně 256 lístků a vygeneruju si 32b náhodné číslo, tak mám dost bitů na 4 pokusy po osmi bitech. V každém pokusu může být maximálně cca 1/2 ppost, že nevyhraje nikdo -> celkově je ppost, že nikdo nevyhraje (1/2)^4. Pokud se mi to zdá moc, použiju místo 32b víc. Nikdy se nedostanu na nulu, ale můžu se dostat na číslo, který jsem ochotnej akceptovat - a akceptuju možnost, že někdo nevyhraje, NEakceptuju nespravedlnost.
-
*150 ne *500 to som upravil 150 stacilo :)
-
Mirku - presne a uplne dokonale.
BTW tvoje prispevky an vsechny moje otazky uz v minulosti (asi 10 temat) jen sem porat linej se registrovat byli vzdy uplne dokonale. Normalne by me zajimalo cim se zivis clovece :D pac jakakoli tema tak ty vis :D
"Nikdy se nedostanu na nulu, ale můžu se dostat na číslo, který jsem ochotnej akceptovat - a akceptuju možnost, že někdo nevyhraje, NEakceptuju nespravedlnost."
- presne.
-
Pripad NEvylosovania sa da predsa osetrit ale hlavne - je menej problematicky ako "NEFEROVOST".
Ošetřit se dá všechno možné. To, jestli je to přijatelné a jestli je to méně problematické, než neférovost, je součást zadání – proto jsem se ptal, jaké přesně je zadání.
- Dam si vygenerovat 150 CHAR dlhy string 0 a 1 (1,4 x 10 na 45!)
- Pevna dlzka preto aby zaciatok mohol byt 00001.... a nuly sa mi nestratili
- 500 CHAR 0 a 1 mi pokryje naprikald: 0 az 1000 000 000 000 (bilion) celkovo 1,4 x 10 na 33!
Teda tohle rozluštit… 45! neznamená 45 faktoriál, ale prostě jen 45, aha. Psal jste o deseti miliardách, pro jejich pokrytí potřebujete 234. Z těch 150 bitů tedy uděláte (150/34=) 4 kola losování.
Takze vdaka tomuto mozem rolovat extremne vela krat, sanza ze by to stale nepadlo je MINIMALNA a pre mna nedolezita - lebo sa to proste nestane. Mat tak vela '1' vedla seba je nahoda tak mala ze ju mozem zanedbat.
4 kola losování, to podle mne není „extrémně vela“. Jak psal Mirek Prýmek, pravděpodobnost, že v jednom kole nikoho nevylosujete, je 1/2. Za čtyři kola tedy ta pravděpodobnost bude 1/24, tedy 1/16. To není minimální pravděpodobnost, to je sakra vysoká pravděpodobnost. Když se to bude hrát 16 hodin denně a každou hodinu se bude jednou losovat, jednou denně nikdo nevyhraje.
- nahodny generator cisel pouzivame HW samozrejme
To je fajn, ale uvědomte si, že budete mít hodně velkou spotřebu náhodných čísel. Abyste měl slušnou pravděpodobnost, že vám ta čísla nedojdou, potřebujete zásobu na desítky opakování, takže nepočítejte se 150 bity, ale s tisíci až desetitisíci bitů.
- stale nevidim problem ani v overeni toho stringu nejakym sposobom (napriklad : je tam 0?) a ak nie je tak pevnaDlzka +1 a dam dalsie nahodne cislo, a znova - je tam 0? a Znova a znova? Takze je to nahodna postupnost 0 a 1 ktora ma urctu vlastnost - takze by som mohol dokonca aj ten pripad jednotiek ( 1...11111...1) eliminovat uplne nie?
To vaše „ověření“ znamená, že byste vyházel hodnoty, které se nemohou použít. Jenže které hodnoty nepřipadají v úvahu víte až v okamžiku, kdy víte, kolik se prodalo lístků. Pokud byste eliminoval třeba ty „samé jedničky“, způsobíte, že při prodeji počtu lístků, který odpovídá mocnině dvou, nemůže ten poslední kupující vyhrát (protože jeho číslo odpovídá právě těm samým jedničkám). To nevypadá moc férově… To, že vám číslo skládající se binárně ze samých jedniček připadá zajímavé, je jenom klam – z hlediska pravděpodobnosti je úplně stejně pravděpodobné, jako kterékoli jiné číslo.
A to je na tom celém to nejdůležitější. Pokud chcete ten systém mít opravdu 100% férový, musíte opravdu dobře vědět, co děláte, jaké jsou charakteristiky komponent, které používáte, jaké mají předpoklady. A všechny ty pravděpodobnosti (např. jak často nikdo nevyhraje) si pak můžete velice snadno spočítat. Pokud to budete brát takhle intuitivně, že čísla 2n jsou nějaká divná a můžete je vyškrtnout, a nějakou pravděpodobnost intuitivně odhadnete na „prostě nestane“ (a ono je to pak 1/16), nebude ten váš systém férový ani omylem.
-
To je reakce na mě nebo na koho? O nic takového se přece nesnažím.
To je reakce na tazatele.
Ale vždyť přesně tohle píšu. Když předpokládám maximálně 256 lístků a vygeneruju si 32b náhodné číslo, tak mám dost bitů na 4 pokusy po osmi bitech. V každém pokusu může být maximálně cca 1/2 ppost, že nevyhraje nikdo -> celkově je ppost, že nikdo nevyhraje (1/2)^4. Pokud se mi to zdá moc, použiju místo 32b víc. Nikdy se nedostanu na nulu, ale můžu se dostat na číslo, který jsem ochotnej akceptovat - a akceptuju možnost, že někdo nevyhraje, NEakceptuju nespravedlnost.
S vámi nepolemizuju, píšeme oba to samé :-) Akorát se snažím to samé popisovat jiným způsobem, protože přesný výpočet pravděpodobnosti je zjevně něco, čím se tazatel nenechá vykolejit ze svých „prostě“. Jinak 32 bitů je hezké číslo, ale podle těch čísel, co tu tazatel píše, se pohybujeme o několik řádů výš. A tam už zase může být problém dostat tolik „náhody“ dostatečně rychle.