Poradíte s implementací Provably Fair?

Re:Poradíte s implementací Provably Fair?
« Odpověď #30 kdy: 27. 02. 2016, 14:44:58 »
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…


Jenda

Re:Poradíte s implementací Provably Fair?
« Odpověď #31 kdy: 27. 02. 2016, 14:54:28 »
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.

OliverGGGGG

Re:Poradíte s implementací Provably Fair?
« Odpověď #32 kdy: 27. 02. 2016, 14:56:31 »
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?

Re:Poradíte s implementací Provably Fair?
« Odpověď #33 kdy: 27. 02. 2016, 15:03:17 »
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.

Re:Poradíte s implementací Provably Fair?
« Odpověď #34 kdy: 27. 02. 2016, 15:09:38 »
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í.


Re:Poradíte s implementací Provably Fair?
« Odpověď #35 kdy: 27. 02. 2016, 15:31:47 »
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.

Re:Poradíte s implementací Provably Fair?
« Odpověď #36 kdy: 27. 02. 2016, 15:37:33 »
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…

OliverGGGGGG

Re:Poradíte s implementací Provably Fair?
« Odpověď #37 kdy: 27. 02. 2016, 16:21:54 »
@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

Re:Poradíte s implementací Provably Fair?
« Odpověď #38 kdy: 27. 02. 2016, 16:22:22 »
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.

OliverGGGGGG

Re:Poradíte s implementací Provably Fair?
« Odpověď #39 kdy: 27. 02. 2016, 16:23:24 »
*150 ne *500 to som upravil 150 stacilo :)

OliverGGGGGG

Re:Poradíte s implementací Provably Fair?
« Odpověď #40 kdy: 27. 02. 2016, 16:25:41 »
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.

Re:Poradíte s implementací Provably Fair?
« Odpověď #41 kdy: 27. 02. 2016, 17:31:00 »
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.

Re:Poradíte s implementací Provably Fair?
« Odpověď #42 kdy: 27. 02. 2016, 17:42:17 »
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.