Poradíte s implementací Provably Fair?

[Filip Jirsák]

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 10¹⁰⁰⁰ číslic, to ještě budete vzpomínat na 10 miliard náhodných losování.

[Reklama]

[Mirek Prýmek]

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íš.

[Filip Jirsák]

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).

[Jenda]

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í…

[Mirek Prýmek]

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!

[Reklama]

[Filip Jirsák]

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 :-)

[Mirek Prýmek]

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

[OliverGGGGG]

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 ;-)

[Mirek Prýmek]

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.

[Mirek Prýmek]

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.

[Mirek Prýmek]

A ještě jedna poznámka: počet prodaných lístků nemusíš průběžně zveřejňovat.

[Filip Jirsák]

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.

[Jenda]

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č?

[JSH]

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.

[OliverGGGGG]

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?

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 :-)