OldComp.cz

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

DOSDev 2020

Právě je 14.07.2020, 19:13

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.08.2018, 09:50 
Offline
Profík
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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í.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


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

Registrován: 22.05.2013, 21:14
Příspěvky: 2633
Bydliště: Bratislava
Has thanked: 279 times
Been thanked: 504 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.08.2018, 13:32 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2024
Has thanked: 101 times
Been thanked: 388 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.

_________________
"Dokud nebyly počítače, programování nebylo problémem.
Jestliže bylo několik slabých počítačů, bylo programování malým problémem.
Když však programátoři získali počítače na svou dobu ohromné síly, stalo se také programování ohromným problémem."

E. W. Dijkstra, 1972


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

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27.08.2018, 22:10 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2024
Has thanked: 101 times
Been thanked: 388 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 3876 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 3876 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.

_________________
"Dokud nebyly počítače, programování nebylo problémem.
Jestliže bylo několik slabých počítačů, bylo programování malým problémem.
Když však programátoři získali počítače na svou dobu ohromné síly, stalo se také programování ohromným problémem."

E. W. Dijkstra, 1972


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

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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í.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27.08.2018, 23:10 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2024
Has thanked: 101 times
Been thanked: 388 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...

_________________
"Dokud nebyly počítače, programování nebylo problémem.
Jestliže bylo několik slabých počítačů, bylo programování malým problémem.
Když však programátoři získali počítače na svou dobu ohromné síly, stalo se také programování ohromným problémem."

E. W. Dijkstra, 1972


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

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 28.08.2018, 00:39 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2024
Has thanked: 101 times
Been thanked: 388 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 3863 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 3863 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.

_________________
"Dokud nebyly počítače, programování nebylo problémem.
Jestliže bylo několik slabých počítačů, bylo programování malým problémem.
Když však programátoři získali počítače na svou dobu ohromné síly, stalo se také programování ohromným problémem."

E. W. Dijkstra, 1972


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

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


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

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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 3802 krát ]

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 30.08.2018, 19:42 
Offline
Pan Generální
Uživatelský avatar

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

_________________
"Dokud nebyly počítače, programování nebylo problémem.
Jestliže bylo několik slabých počítačů, bylo programování malým problémem.
Když však programátoři získali počítače na svou dobu ohromné síly, stalo se také programování ohromným problémem."

E. W. Dijkstra, 1972


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

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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á.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


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

Registrován: 28.10.2016, 21:03
Příspěvky: 119
Has thanked: 13 times
Been thanked: 48 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 3246 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 3246 krát ]
Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 13.01.2019, 23:11 
Offline
Profík
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 837
Bydliště: Most, Praha
Has thanked: 253 times
Been thanked: 216 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.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


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