| OldComp.cz https://oldcomp.cz/ |
|
| Algoritmus pro míchání karet https://oldcomp.cz/viewtopic.php?f=113&t=6617 |
Stránka 2 z 2 |
| Autor: | Panda38 [ 27.08.2018, 09:50 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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í. |
|
| Autor: | Busy [ 27.08.2018, 13:16 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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 
|
|
| Autor: | faraon [ 27.08.2018, 13:32 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
Nebo naopak, určitá (malá) část se podle zákona musí vrátit na výhrách, a zbytek shrábne majitel  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. |
|
| Autor: | Panda38 [ 27.08.2018, 13:41 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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. |
|
| Autor: | faraon [ 27.08.2018, 22:10 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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 [ 20.51 KiB | Zobrazeno 9517 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 [ 17.26 KiB | Zobrazeno 9517 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. |
|
| Autor: | Panda38 [ 27.08.2018, 22:29 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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é.  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í. |
|
| Autor: | faraon [ 27.08.2018, 23:10 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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... |
|
| Autor: | Panda38 [ 27.08.2018, 23:21 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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.
|
|
| Autor: | faraon [ 28.08.2018, 00:39 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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 [ 1.41 KiB | Zobrazeno 9504 krát ] Když ty hromádky mají omezenou velikost, vnese to do toho ještě další bordel: Příloha: 2o.png [ 1.37 KiB | Zobrazeno 9504 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. |
|
| Autor: | Panda38 [ 28.08.2018, 02:03 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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. |
|
| Autor: | Panda38 [ 30.08.2018, 19:22 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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 [ 45.43 KiB | Zobrazeno 9443 krát ] |
|
| Autor: | faraon [ 30.08.2018, 19:42 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
To už vypadá skoro snesitelně. Ale nebylo by jednodušší mít tabulku 20000 správně předmíchaných balíčků?
|
|
| Autor: | Panda38 [ 30.08.2018, 19:52 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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á. |
|
| Autor: | lukz [ 13.01.2019, 22:45 ] | ||
| Předmět příspěvku: | Re: Algoritmus pro míchání karet | ||
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 [ 13.92 KiB | Zobrazeno 8887 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:
|
|||
| Autor: | Panda38 [ 13.01.2019, 23:11 ] |
| Předmět příspěvku: | Re: Algoritmus pro míchání karet |
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. |
|
| Stránka 2 z 2 | Všechny časy jsou v UTC + 1 hodina [ Letní čas ] |
| Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |
|