Gra Bingo Na Arduino Uno R4 i nie tylko

ethanak · 3 lutego

Jeśli są ograniczenia to nie jest to czysto losowe tasowanie. Poza tym niespecjalnie rozumiem ideę ograniczania do i - przecież wtedy zawsze na najniższej pozycji będziesz miał to co tam siedziało przed tasowaniem.

borabora · 3 lutego

17 minut temu, ethanak napisał:

Jeśli są ograniczenia to nie jest to czysto losowe tasowanie.

To nie są ograniczenia z punktu widzenia kombinatoryki tylko w algorytmie, żeby zachować równomierny rozkład prawdopodobieńśtwa.

Prosto pisząc - na początku jest zbiór A wszystkich liczb od 1 do 76 i pusty ciąg C, do którego wstawiasz kolejno losowane liczby ze zbioru A.
W miarę losowania zbiór A maleje a C rośnie. Na końcu otrzymujesz permutację C i pusty zbiór A.
Algorytm Fishera-Yatesa działa w podobny sposób, tyle że przekształca początkową permutację 1..n do losowej permutacji. Ograniczenie dla randoma wydziela niejako z tej początkowej permutacji zbiór A i ciąg C, gdzie i jest granicą.

ethanak · 4 lutego

Grałeś kiedyś w karty? Bo ja na własne oczy widziałem jak koleś dostał z ręki karetę asów, a drugi małego pokera. O różnych dziwnych rozdaniach w brydżu nie wspomnę...

Pytanie kontrolne: czy projekt ma na celu badanie różnych rozkładów, czy rzeczywistą grę... bo przy rzeczywistej grze jedno do czego bym się doczepił to użycie generatora pseudolosowego zamiast losowego (i wtedy ważna jest wydajność bo losowe działają powoli).

borabora · 4 lutego

10 godzin temu, ethanak napisał:

Grałeś kiedyś w karty? Bo ja na własne oczy widziałem jak koleś dostał z ręki karetę asów, a drugi małego pokera. O różnych dziwnych rozdaniach w brydżu nie wspomnę...

Pytanie kontrolne: czy projekt ma na celu badanie różnych rozkładów, czy rzeczywistą grę... bo przy rzeczywistej grze jedno do czego bym się doczepił to użycie generatora pseudolosowego zamiast losowego (i wtedy ważna jest wydajność bo losowe działają powoli).

Brnąc dalej w analogię do kart, rozwiązanie, które zaprezentowałeś można porównać do tasowania talii kart włączając w to karty już rozdane graczom.
Dokładnie chodzi o tę linię:

for (i=0;i<cnt;i++) swap(t[i],t[random(cnt)]);

W poprawnym algorytmie należy ograniczyć zakres do i. Wydawać by się mogło, że dodatkowe losowanie w losowaniu nie może zaszkodzić, jednak, jak to bywa w probabilistyce, intuicja zawodzi.

Losowanie w zakresie 0...cnt drastycznie psuje rozkład prawdopodobieństwa wystąpienia permutacji. Zauważenie tego podczas kilku czy kilkudziesięciu rozdań jest trudne, ale tworząc tego typu program wypada zrobić to dobrze, tym bardziej, że poprawka jest bardzo prosta. Tym się różni "pisanie kodu" od prawdziwej informatyki (algorytmiki).

Prosty przykład już był, analogia do kart była, pora przejść do rzeczy.

Aby algorytm mieszający był nieobciążony, każda z możliwych permutacji musi mieć dokładnie taką samą szansę na wystąpienie.

Dla tablicy o rozmiarze n, liczba wszystkich możliwych permutacji wynosi n!.
W algorytmie Fishera-Yatesa, w pierwszym kroku mamy n wyborów, w drugim n-1, w trzecim n-2... Łączna liczba dróg, które prowadzą do uzyskania finalnej permutacji, wynosi dokładnie n * (n-1) * ... * 1 = n!. Ponieważ liczba dróg jest równa liczbie permutacji, każda permutacja występuje dokładnie raz.

Co się dzieje przy random(0, n)? Jeśli w każdym z n kroków pętli losujemy jedną z n pozycji, to łączna liczba możliwych "ścieżek" algorytmu wynosi n do potęgi n (n^n).
Aby rozkład był idealnie równy, liczba wszystkich możliwych ścieżek (n^n) musiałaby być wielokrotnością liczby permutacji (n!). Jednak dla każdego n > 2, n^n nie jest podzielne przez n!.
I tutaj znajduje zastosowanie zasada szufladkowa Dirichleta: jeśli spróbujesz rozłożyć n^n wyników do n! "szufladek" (permutacji), a liczba wyników nie jest wielokrotnością liczby szufladek, to niektóre szufladki będą zawierać więcej wyników niż inne. Rozkład staje się nieuchronnie nierównomierny.

Tak wygląda dowód teoretyczny, teraz czas na demonstrację problemu w praktyce - kod źródłowy w C poniżej:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TRIALS 1000000
#define N 3

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int get_permutation_id(int arr[]) {
    if (arr[0]==0 && arr[1]==1 && arr[2]==2) return 0;
    if (arr[0]==0 && arr[1]==2 && arr[2]==1) return 1;
    if (arr[0]==1 && arr[1]==0 && arr[2]==2) return 2;
    if (arr[0]==1 && arr[1]==2 && arr[2]==0) return 3;
    if (arr[0]==2 && arr[1]==0 && arr[2]==1) return 4;
    if (arr[0]==2 && arr[1]==1 && arr[2]==0) return 5;
    return -1;
}

void reset_array(int arr[]) {
    for(int i=0; i<N; i++) arr[i] = i;
}

int main() {
    int counts_correct[6] = {0};
    int counts_naive[6] = {0};
    int arr[N];

    srand(time(NULL));

    // 1. TEST: Poprawny Fisher-Yates (random 0 do i)
    for (int t = 0; t < TRIALS; t++) {
        reset_array(arr);
        for (int i = N - 1; i > 0; i--) {
            int j = rand() % (i + 1); // ZAKRES OGRANICZONY MALEJĄCY 
            swap(&arr[i], &arr[j]);
        }
        counts_correct[get_permutation_id(arr)]++;
    }

    // 2. TEST: Naiwne mieszanie (random 0 do N-1)
    for (int t = 0; t < TRIALS; t++) {
        reset_array(arr);
        for (int i = N - 1; i > 0; i--) {
            int j = rand() % N;       // ZAKRES STAŁY (BŁĄD!)
            swap(&arr[i], &arr[j]);
        }
        counts_naive[get_permutation_id(arr)]++;
    }

    // Wyświetlenie wyników
    const char* labels[] = {"[0,1,2]", "[0,2,1]", "[1,0,2]", "[1,2,0]", "[2,0,1]", "[2,1,0]"};
    printf("Wyniki dla %d powtorzen:\n\n", TRIALS);
    printf("Permutacja | Poprawny F-Y | Naiwny (Bias)\n");
    printf("-----------|--------------|--------------\n");
    for (int i = 0; i < 6; i++) {
        printf("%s    |   %d     |   %d\n", labels[i], counts_correct[i], counts_naive[i]);
    }

    return 0;
}

Wykonywane jest TRIALS losowań (10^6) permutacji ze zbioru 3-elementowego. Liczba permutacji tego zbioru wynosi 6. Program liczy ile razy została wylosowana każda z nich w przypadku propozycji, którą przedstawiłeś i w przypadku poprawnej metody, z ograniczonym zakresem losowań:

int j = rand() % N;       // ZAKRES STAŁY (BŁĄD!)

int j = rand() % (i + 1); // ZAKRES OGRANICZONY MALEJĄCY

Wyniki dla trzech uruchomień:
1)

Wyniki dla 1000000 powtorzen:

Permutacja | Poprawny F-Y | Naiwny (Bias)
-----------|--------------|--------------
[0,1,2]    |   166636     |   222600
[0,2,1]    |   166483     |   221802
[1,0,2]    |   166249     |   110690
[1,2,0]    |   166744     |   111601
[2,0,1]    |   167367     |   222480
[2,1,0]    |   166521     |   110827

2)

Wyniki dla 1000000 powtorzen:

Permutacja | Poprawny F-Y | Naiwny (Bias)
-----------|--------------|--------------
[0,1,2]    |   166619     |   222390
[0,2,1]    |   167068     |   222931
[1,0,2]    |   166483     |   110378
[1,2,0]    |   166450     |   111271
[2,0,1]    |   166168     |   221997
[2,1,0]    |   167212     |   111033

3)

Wyniki dla 1000000 powtorzen:

Permutacja | Poprawny F-Y | Naiwny (Bias)
-----------|--------------|--------------
[0,1,2]    |   166183     |   222543
[0,2,1]    |   166880     |   222302
[1,0,2]    |   167037     |   111300
[1,2,0]    |   166695     |   110445
[2,0,1]    |   166807     |   222153
[2,1,0]    |   166398     |   111257

Wyniki nie pozostawiają złudzeń. Wracając do karcianej analogii - nierówny rozkład losowań to jak znaczone karty. Miejscem zużytych kart jest kosz, program da się poprawić.

Nie generator pseudolosowy jest tutaj problemem lecz rozkład prawdopodobieństwa.
Generator prawdziwie losowy to już "inna bajka". Jego realizacja praktyczna jest bardzo trudna bo używane są do tego izotopy promieniotwórcze. Metoda pośrednia to skorzystanie z serwisu udostępniającego liczby losowe otrzymane z takiego generatora.