OldComp.cz

Komunitní diskuzní fórum pro fanoušky historických počítačů

Tlsk Mln 2019

Právě je 09 pro 2019, 07:53

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]




Odeslat nové téma Odpovědět na téma  [ Příspěvků: 30 ]  Přejít na stránku Předchozí  1, 2
Autor Zpráva
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 09:50 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Ale o to tady jde - aby se karty dostávaly se stejnou pravděpodobností na všechny možné pozice na výstupu. Je jedno jakým způsobem se toho dosáhne.
1) Musí být rovnoměrná náhodnost, aby se nedalo počítat např. s tím, že první karta má vyšší šanci být opět první kartou.
2) Míchání nesmí být předvídatelné, aby se z jednoho míchání nedalo předpovědět následující míchání.

I u výherních automatů se používá řízená náhodnost, kdy se stanoví co má být výsledkem a náhodnost se upraví.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 13:16 
Offline
Pan Generální

Registrován: 22 kvě 2013, 21:14
Příspěvky: 2346
Bydliště: Bratislava
Has thanked: 259 times
Been thanked: 455 times
Panda38 píše:
I u výherních automatů se používá řízená náhodnost, kdy se stanoví co má být výsledkem a náhodnost se upraví.
Tak to je pravda. Tam je vzdy stanovene ze automat musi majitelom prinasat presne definovany zisk a podla toho sa ta nahoda riadi :)


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 13:32 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 23 bře 2014, 20:13
Příspěvky: 1827
Has thanked: 87 times
Been thanked: 349 times
Nebo naopak, určitá (malá) část se podle zákona musí vrátit na výhrách, a zbytek shrábne majitel :lol:

Jen technický dotaz, do každé z těch šesti přihrádek se vejde 10 karet, co se stane když tam chci hodit jedenáctou? Mám vybrat některou jinou, kde je ještě místo? Už mi jich tam totiž spadlo i 16.

_________________
GOTT is REAL, unless declared INTEGER


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 13:41 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Ano musí se vybrat jiná hromádka.

Jen ještě připomínám, jak jsem se zmínil výše, zřejmě může být těch hromádek i 7 (tolerance je z důvodu přepočtu původních parametrů).

Zkouším teď metodu, která vypadá slibně - při míchání se bude náhodně volit mezi čistě náhodným mícháním (aby se zajistila náhodnost) a předvypočteným korekčním mícháním, které bude dostatečně agresivní, aby křivku vyrovnalo. Korekční míchání se zjistí předem, sledováním ovlivnění histogramu.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 22:10 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 23 bře 2014, 20:13
Příspěvky: 1827
Has thanked: 87 times
Been thanked: 349 times
Panda38 píše:
... ani karty promíchat podruhé.

Fakt by to nešlo? Tím by se to zamíchání dost podstatně vylepšilo, zůstane jen pár menších úletů:
Příloha:
6.gif
6.gif [ 20.51 KiB | Zobrazeno 2864 krát ]

Druhým promícháním se mi poměr mezi nejvyšší a nejnižší četností z víc jak 10000 srazí na méně než 4, při milionu opakování.

Větší počet hromádek to také trochu vyrovná, ale jsou tam velké extrémy u první a poslední karty:
Příloha:
7.gif
7.gif [ 17.26 KiB | Zobrazeno 2864 krát ]


Daly by se spočítat tabulky pro každou kartu zvlášť, na to nepravidelné rozdělení do hromádek, ale bude to strašně komplikované a zůstane tam pořád stejný problém - že ty hromádky jsou setříděné! To by jich muselo být tolik jako karet, nebo aspoň polovina. Při 3 kartách na 25 hromádkách mi spadl poměr na 10, s výkyvy jen na koncích. Ale ani tak to není nic moc.

_________________
GOTT is REAL, unless declared INTEGER


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 22:29 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Jo jasně že druhé míchání by to podstatně spravilo, stejně jako počet hromádek stejný jako počet karet. Ale bohužel to by se pak tento problém neobjevil a řešení by bylo snadné. Není to možné. :cry:

Myslím že ani spočítat tabulky pro každou kartu zvlášť není vhodná cesta. Tady se nedá určovat "tahle karta půjde na tuhle pozici", protože je to závislé i na okolních kartách kam se dostane do hromádky. Zatím vypadá nejschůdnější cesta ze statistiky nechat vybrat několik variant (např. 10 tisíc), které vedou k výsledku, tím se dá podchytit současné působení více karet jako celek. Nejlepší by bylo, kdyby se správné rozložení dalo přímo spočítat, ale zdá se že to asi nikdo nevymyslí.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 23:10 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 23 bře 2014, 20:13
Příspěvky: 1827
Has thanked: 87 times
Been thanked: 349 times
Panda38 píše:
Myslím že ani spočítat tabulky pro každou kartu zvlášť není vhodná cesta.

Není. Například pro 1. kartu - náhodné číslo od 1 do 100:
1 -> 1. hromádka
2..5 -> 2. hromádka
...
65..100 -> 6. hromádka

To by mohlo aspoň trochu zmírnit ty krajní extrémy, nebo je spíš zasunout hlouběji "do davu", ale je to strašně komplikované. A zůstane tam pořád stejný problém - ty seřazené hromádky. Tudy cesta nevede, jenom rozházení jednoho paklu na víc hromádek prostě nestačí :-/

Kdybys ho mohl třeba rozdělit na čtvrtiny, a pak náhodně vybrat některou z nich, ze které hodíš kartu na některou z těch šesti...

_________________
GOTT is REAL, unless declared INTEGER


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27 srp 2018, 23:21 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Ano regulaci náhodnosti rozhození do hromádek jsem zkoušel, což sice vylepšilo ten úvodní "zobák", ale úplně to rozhodilo ostatní charakteristiku, bylo to výsledně ještě víc nerovnoměrné než předtím. Podobného se dá dosáhnout i tím, že se občas první nebo poslední hromádka obsadí jen 1 kartou, což jí dá klasickou lineární náhodnost, ale opět to má katastrofální důsledek na zbytek průběhu.

Co je se seřazenýma hromádkama? Máš na mysli to, že se pak hromádky seskládají v pořadí od 1 do 6? To by přece neměl být problém, protože se hromádky dají zamíchat určováním pořadí při rozhazování.

To zařízení neumí jinak přeskládat vstupní balík. :-) Vloží se do něj balík, ono jej rozhází do přihrádek a vyleze zas balík, víc to neumí udělat.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 28 srp 2018, 00:39 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 23 bře 2014, 20:13
Příspěvky: 1827
Has thanked: 87 times
Been thanked: 349 times
Ne, mám na mysli že v každé hromádce je skupina karet, seřazená od nejmenší po největší.

A když se to složí, nadělá to zuby. Každá karta se kvůli tomu může vzdálit jenom kousek od svojí nejpravděpodobnější pozice. Pro 2 hromádky:
Příloha:
2n.png
2n.png [ 1.41 KiB | Zobrazeno 2851 krát ]

Když ty hromádky mají omezenou velikost, vnese to do toho ještě další bordel:
Příloha:
2o.png
2o.png [ 1.37 KiB | Zobrazeno 2851 krát ]

Ale náhodnost to nezvýší, spíš naopak, protože jsou místa kam se kvůli tomu ty karty nemůžou dostat a vnutí je to jinam.

_________________
GOTT is REAL, unless declared INTEGER


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 28 srp 2018, 02:03 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Jo když se dá přidávat jen na vršek hromádek, jsou vespod karty které byly jako první. Nedá se přidávat doprostřed. Proto je tam rezerva v zaplnění, která s tím umožní hýbat, aby se to dalo vyrovnat.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 30 srp 2018, 19:22 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Uzavřel jsem problém s tímto řešením: Předem jsem vyhledal 20 tisíc zamíchání, která jakž takž kompenzují nelinearitu náhodného míchání. Vyhledával jsem sledováním ovlivnění rozptylu histogramu a výběrem nejlepšího kandidáta 1 z tisíce. Do zařízení jsem přidal tabulku s 20 tisíc seeds pro generátor náhody. Před každým mícháním se náhodně zvolí, zda míchání proběhne buď čistě náhodně, nebo s výchozí hodnotou seeds náhodně vybranou z tabulky. Výsledně statisticky pak dojde k celkem přijatelné linearizaci.

Předal jsem dál "vyšší moci". Když jim to přijde málo lineární, dá se zvyšovat velikost tabulky a přesnost vyhledávání.

Příloha:
test_2.png
test_2.png [ 45.43 KiB | Zobrazeno 2790 krát ]


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 30 srp 2018, 19:42 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 23 bře 2014, 20:13
Příspěvky: 1827
Has thanked: 87 times
Been thanked: 349 times
To už vypadá skoro snesitelně. Ale nebylo by jednodušší mít tabulku 20000 správně předmíchaných balíčků? :lol:

_________________
GOTT is REAL, unless declared INTEGER


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 30 srp 2018, 19:52 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Bylo, o trochu, ale vyžaduje se tam i jakási opravdová náhodnost. 20k je docela malý počet variant (omezený místem v ROM), i proto je to takové zubaté. Uvidí se jak to vyhodnotí Vyšší moc, víc se s tím teď dělat asi nedá.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 13 led 2019, 22:45 
Offline
Kecálek

Registrován: 28 říj 2016, 21:03
Příspěvky: 83
Has thanked: 9 times
Been thanked: 38 times
Ještě jsem se vrátil k tomuhle zajímavému problému. Jak jsem psal výše, když
jsem zkoušel algoritmus míchání vylepšovat, tak se mi zdálo, že víc jak jedna
pozice nejde vylepšit tak, aby byla rovnoměrná pravděpodobnost, která karta na
dané pozici skončí.

No, ale postup Panda38 nakonec fungoval, tak to jsem se tedy spletl, a asi to
jde. I když zas tam byla ta komplikace, že je potřeba mít 20 000
předpřipravených konfigurací. A kde je vzít.

Tak jsem o tom přemýšlel, jestli by šel udělat nějaký algoritmus, který bude
jednoduchý, a i když nezíská ideální rozložení, tak aspoň na začátku balíčku
docílí, že víc než jedna pozice bude vypadat dobře.

A podařilo se mi to vylepšit na prvních 8 pozic zamíchaného balíčku. Pak už se
začínají objevovat určité nerovnoměrnosti, a směrem ke konci balíčku je to čím
dál horší. Ale rozložení pro prvních 20 pozic je, řekl bych, ještě přijatelné.

Kód:
Algoritmus:
  Na začátku zvol číslo C, náhodně z intervalu [1, 50]
  Proměnná slot je pole s počty karet v přihrádkách 1 až 6
    slot = [0, 0, 0, 0, 0, 0]
  rnd() je funkce, která vrátí náhodné číslo z intervalu [0, 1)

  Potom zpracovávej vstupní karty 1 až 50

  Zpracování karty i:
    Opakuj
      Když je i==C, tak o=1
      jinak, když je i>C a rnd()<.18 a slot[0]<9, tak o=1
      jinak zvol o náhodně z intervalu [2, 6]
    dokud slot[o]>9

    slot[o]+=1
    Hoď kartu do přihrádky o

Výsledek, znázorněný graficky, po simulaci 100 000 míchání, je tady.
Příloha:
michani.png
michani.png [ 13.92 KiB | Zobrazeno 2234 krát ]


Každý graf je jedna pozice zamíchaného balíčku. První graf je tedy první karta
zamíchaného balíčku, hodnoty na grafu zleva doprava říkají pravděpodobnost,
že na dané pozici uvidíme tuto konkrétní kartu. Vlevo jsou karty 1, 2, 3, ...
z nezamíchaného balíčku, vpravo jsou karty ..., 48, 49, 50. Šedá čára je
očekávaná hodnota při rovnoměrném rozložení. Na levém a pravém konci graf
začíná z 0, to je jen pro zřetelnost měřítka, není to ještě žádná karta. Pokud
vzdálenost hodnoty pro nějakou kartu od 0 je dvakrát větší než šedá čára od
nuly, znamená to, že daná situace nastává dvakrát častěji, než by měla. A
podobně, pokud hodnota je pod šedou čárou, znamená, že situace nastává méně,
než by měla.


Pro porovnání, simulace prvního algoritmu, s kterým tohle vlákno začalo -
tj. zvolím přihrádku náhodně 1-6, pokud je plná, zvolím náhodně jinou,
dává tento výsledek:


Přílohy:
michani-orig.png
michani-orig.png [ 16.44 KiB | Zobrazeno 2234 krát ]
Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 13 led 2019, 23:11 
Offline
Profík
Uživatelský avatar

Registrován: 24 kvě 2018, 22:32
Příspěvky: 644
Bydliště: Most, Praha
Has thanked: 183 times
Been thanked: 162 times
Sice se dá vylepšit část pozic, ale výrazně se tím rozhodí zbytek. Musí se vylepšovat celý průběh najednou. Vyřešil jsem to statisticky (výše uvedeným způsobem), vyhledáním tabulky možných zamíchání - algoritmus několik týdnů náhodně promíchával karty a nahrazoval hodnoty v tabulce lepšími výsledky, snažil se co nejvíce přiblížit lineárnímu průběhu. Pak už jen stačí náhodně vybírat míchání z tabulky a výsledek může být dostatečně lineární a splňovat obvyklé náhodnostní testy.


Nahoru
 Profil  
 
Zobrazit příspěvky za předchozí:  Seřadit podle  
Odeslat nové téma Odpovědět na téma  [ Příspěvků: 30 ]  Přejít na stránku Předchozí  1, 2

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník


Nemůžete zakládat nová témata v tomto fóru
Nemůžete odpovídat v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete přikládat soubory v tomto fóru

Hledat:
Přejít na:  
Založeno na phpBB® Forum Software © phpBB Group
Český překlad – phpBB.cz