atarionline.pl uwarunkowania progr. gen. liczb pseudolosowych - Forum Atarum

Jeśli chcesz wziąć udział w dyskusjach na forum - zaloguj się. Jeżeli nie masz loginu - poproś o członkostwo.

  • :
  • :

Vanilla 1.1.4 jest produktem Lussumo. Więcej informacji: Dokumentacja, Forum.

    • 1: CommentAuthormarok
    • CommentTime18 Jan 2023
     
    Stosunkowo jeszcze proste do wyprowadzenia równanie:
    255!/(256^255)

    daje wynik prawdopodobieństwa rzędu:
    2,65438504251e-110

    (strasznie mały)

    Jeśli się nie mylę (oczywiście mogę), odpowiada to prawdopodobieństwu wszystkich takich zdarzeń spośród kolejnych 255 losowań, które złożą się na wystąpienie dokładnie 1 z 255 wartości, a określona z góry jedna nie wystąpi wcale, z pełnej puli 256 wartości do wylosowania. (Tą jedną z 256, która by miała nie wystąpić byłoby 0.)

    Z pewnością sporo zdarzeń o innej strukturze wyniku (określone liczby powtórzeń) będzie mieć wyższe prawdopodobieństwa wystąpienia (niestety nie jestem tego w stanie policzyć).

    Jeśli więc stwarzana jest tablica liczb pseudolosowych, na zasadzie wartości niepowtarzalnych w innym miejscu tablicy (bo tak się to odbywa), to czytanie liniowe takiej tablicy jest być może jakimś, obawiałbym się, błędem. Zwłaszcza jeśli tablica czytana miałaby być tak "w koło" po wielekroć (licząc już w tysiącach razy).

    Rejest Random w Atari jest dużo bezpieczniejszy, bo nie jest dla naszego użytku liniowy. Nie jest wcale pewne, czy określony wynik pojawi się 1 czy 2 razy (czy więcej razy lub się nie pojawi) w ciągu 255 kolejnych losowań, nawet gdyby jakimś sposobem (zakładając "czarny scenariusz") udało się jednak korzystać z tego rejestru liniowo.


    Słabo się z tym materiałem zdołałem zapoznać na ten moment, ale przypominam o artykule w "Syzygy #7" o generatorze liczb pseudolosowych autorstwa Fox'a.

    Gdyby coś, nadawałby się w całości do przeklejenia w celach edukacyjnych (wcale chętnie bym nawet to zrobił, ale mam problem aby go dobrze przekonwertować do ascii).


    W niedawnej przeszłości w innym wątku na tym forum był link do rozwiązań teoretycznych dla generowania liczb pseudolosowych. Teraz go jednak nie przytoczę (chodzi tylko o hasło w angielsko języcznym wiki).


    Co do samej procedury generującej wartości pseudolosowe, natrafiłem osobiście na tę stronę:

    ->link<-

    Tam znajduje się (jako druga, uproszczona procedura) taki kod (którym można wygenerować pełną tablicę 255 bajtową):
    ; returns pseudo random 8 bit number in A. Affects A. (r_seed) is the
    ; byte from which the number is generated and MUST be initialised to a
    ; non zero value or this function will always return zero. Also r_seed
    ; must be in RAM, you can see why......

    rand_8
    LDA r_seed ; get seed
    ASL ; shift byte
    BCC no_eor ; branch if no carry

    EOR #$CF ; else EOR with $CF
    no_eor
    STA r_seed ; save number as next seed
    RTS ; done

    r_seed
    .byte 1 ; prng seed byte, must not be zero


    Ze swojej strony sprawdziłem, to jeden z głównych powodów mojego pisania tego wątku, że poza wartością #$CF w argumencie, istnieją dodatkowo inne, które spełnić mogą tą samą funkcję (dając inny szyk wartości).
    Natomiast wartość wyjściowa zmiennej r_seed może być dowolna z pominięciem 0 (jak w opisie).

    Więc podaję wszystkie wartości dla których ta procedura generuje tablicę wartości pseudolosowych:

    ; $1D. $2B. $2D. $4D. $5F. $63. $65. $69.
    ; $71. $87. $8D. $A9. $C3. $CF. $E7. $F5.


    Nie było to wydedukowane jakoś (wolałbym), ale wykryte programowo, jeśli chodzi o te wartości.
    • 2: CommentAuthortebe
    • CommentTime18 Jan 2023
     
    na temat radzenia sobie z generowaniem losowych wartości

    ->link<-
    • 3: CommentAuthorilmenit
    • CommentTime18 Jan 2023
     
    zerknij na:
    ->link<-
    oraz:
    ->link<-
    • 4: CommentAuthor0xF
    • CommentTime18 Jan 2023
     
    Nie było to wydedukowane jakoś (wolałbym), ale wykryte programowo, jeśli chodzi o te wartości.


    Jeśli chcesz poczytać o matematycznych podstawach, to ->link<-
    • 5: CommentAuthormarok
    • CommentTime18 Jan 2023
     
    Dziękuję za wszystkie odpowiedzi.

    @0xF: Mono niedawno w innym wątku dotyczącym generowania liczb losowych także dał link do tej strony. O tym próbowałem wpomnieć już poprzednio.


    @ilmenit: Bardzo do rzeczy te linki - dziękuję.
    Przychodzi mi na myśl, aby "zrekonstruować" działanie generatora liczb preudolosowych z Pokeya, które opisał Fox, tym lfsr6502. Tzn. fajnie by było, gdyby to ktoś zrobił, ja się na pewno do tego nie przymierzam.


    @TeBe: Problem trochę od innej strony, ale warte poznania. Muszę to sobie trochę przemyśleć i może coś jeszcze napiszę w luźniejszym nawiązaniu. Dzięki.
    • 6:
       
      CommentAuthorjhusak
    • CommentTime18 Jan 2023
     
    Mam nieodparte wrażenie, że jest to opisane i zakodowane np. w asapconv.
    • 7: CommentAuthortebe
    • CommentTime18 Jan 2023
     
    w grze Arkanoid generatorem liczb pseudolosowych jest rejestr VCOUNT ($D40B) co było przyczyną braku możliwości wylosowania bonusu w postaci 3 piłek.
    • 8: CommentAuthormarok
    • CommentTime19 Jan 2023
     
    @jhusak: mnie trochę bardziej chodziłoby o dołączenie do reszty tych przykładów z lfsr6502.

    @tebe: też ciekawe.


    Taka głupawa może uwaga. Jeśli wynikiem pseudolosowania ma być na wyjściu wartość jedynie podmieniona i z góry ustalona w stosunku do numeru porządkowego wejścia w procedurę (generowania liczby), to jest to po prostu konwersja wartości.
    A konwersja nie nosi z założenia znamion przypadku, a więc nie jest losowaniem (przypadkowej liczby).

    Stąd postulatem jest, aby nie wchodzić w taką procedurę "liniowo" (mam tu na myśli, bez dodatkowej ingerencji w jej, dwie tutaj, zmienne).


    Problem jaki się pojawiał w grze Tetris (jej różnych odmianach) był z goła inny. Przywołam. Chodziło o powtarzalność losowania wciąż tego samego (i/ lub brak przez dłuższy czas gry danego) klocka z zestawu.

    Tutaj mam swoją teorię dlaczego do czegoś podobnego mogło dochodzić.
    Wyobraźmy sobie, że taka gra korzysta z jakiejś procedury lfsr (zupełnie prawdopodobne). Więc działając "liniowo" (autokorekta zmiennych) powinna losować kolejne klocki (ich rodzaj), ("konwersująca") bez powtórzeń, aż do wyczerpania się puli (7-miu). Dopiero po tym fakcie musiałaby zmieniać swoje ustawienia na inne (by przetasować kolejność klocków do nowej puli). Więc w takim przypadku powtórzenia byłyby rzadkie (tylko przy zmianie puli) i tylko na dwa klocki (z gwarancją że 6 kolejnych będzie każdy różny).

    Nie z tym jest problem, więc ja sobie spekuluję że ta procedura może być za każdym użyciem jakby resetowana do stanu wyjściowego, który jest korygowany jeszcze o pewnien czynnik mierzonego czasu. Ale ponieważ czynnik ten ma tendencję do ponownego odmierzania dokładnie tych samych wartości (czasu) co wcześniej (bo np. wykona się w tym czasie "od punktu kontrolnego" ta sama porcja instrukcji), to często nie wpływa na zmianę tej korekty w kolejnych wywołaniach. Więc wynik procedury staje się powtarzalny, w postaci oddawania numeru tego samego klocka.

    To proste wytłumaczenie, zakładające że jest reset procedury lfsr lub zwykły brak autokorekty zmiennych (skoro korekta następuje na podstawie mierzenia upływu czasu).
    • 9: CommentAuthorilmenit
    • CommentTime19 Jan 2023 zmieniony
     
    Powtarzalność sekwencji zawsze trzeba brać do uwagi przy używaniu generatora liczb pseudolosowych. Można na wiele sposobów zmitygować ten problem, np. przeskakiwać stany podczas niedeterministycznych interakcji grającego, używać generatora, który ma długi okres, zanim sekwencja zacznie się powtarzać, generować znacznie większe wartości i je przekształcać do małej (wtedy znając małą wartość nie jest się w stanie powiedzieć jaka będzie kolejna mała wartość, bo może być jedną z wielu).
    • 10: CommentAuthormarok
    • CommentTime20 Jan 2023 zmieniony
     
    Aby uniknąć sekwencji powtarzalnych można
    używać generatora, który ma długi okres, zanim sekwencja zacznie się powtarzać, generować znacznie większe wartości i je przekształcać do małej (wtedy znając małą wartość nie jest się w stanie powiedzieć jaka będzie kolejna mała wartość, bo może być jedną z wielu)


    Przekonuję się, że jest to skuteczne podejście do generowania liczb pseudolosowych w ogóle. Taki "gwóźdź programu".

    W takim razie jednak przydatność procedury, z którą wpierw przyszedłem do tego wątku i która została twórczo rozwinięta w linku do zastosowania wyłonienia liczby losowej, ponieważ daje wynik w tym samym rozmiarze, co wartość przekształcana (generowana), jest wątpliwa. Nie spełnia postulatu ani długiego okresu, ani więc przekształcenia do mniejszej wartości.
    Ten ostatni punkt upoważnia do określenia jej funkcji jako "konwertującej wartość wejścia".

    Owszem, można na jej podstawie prosto jeszcze zadbać o zmniejszenie wartości do wymaganego rozmiaru, ale ponieważ nigdzie o tym nie wpominano przy okazji jej omawiania (jako np. wskazanie), więc potraktuję ją tutaj z całą surowością.

    Te inne wartości zmiennej (przy eor; które sam podawałem i które są w linku) nic w zasadzie poważnego nie wnoszą. Zammienne stosowanie ich nie przynosi niczego "nadzwyczajnego". Określone sekwencje powtarzają się masowo dla każdej z tych wartości, więc podmiana wartości samej tej zmiennej nie daje najmniejszej gwarancji uzyskania innego wyniku.

    Chwila o powtarzających się "masowo" sekwencjach z tej procedury.

    Jest pewnym "masochizmem" czynić podobne wykazy, ale dla zobrazowania "problemu" ma to swój sens:
    01 02 04 08 10 20 40 80
    03 06 0C 18 30 60 C0 XX
    05 0A 14 28 50 A0 XX XX
    07 0E 1C 38 70 E0 XX XX
    09 12 24 48 90 XX XX XX
    0B 16 2C 58 B0 XX XX XX
    0D 1A 34 68 D0 XX XX XX
    0F 1E 3C 78 F0 XX XX XX
    11 22 44 88 XX XX XX XX
    13 26 4C 98 XX XX XX XX
    15 2A 54 A8 XX XX XX XX
    17 2E 5C B8 XX XX XX XX
    19 32 64 C8 XX XX XX XX
    1B 36 6C D8 XX XX XX XX
    1D 3A 74 E8 XX XX XX XX
    1F 3E 7C F8 XX XX XX XX
    21 42 84 XX XX XX XX XX

    Jest to niepełny wykaz.
    Pierwsza kolumna to wartości które mogą następować (ich naturalna kolejność) po różnych wartościach dla każdej z wartości zmiennej (8 wariantów), ale pozostałe kolumny to są wartości, które wynikają z poprzedniej (a wariant zmiennej nie ma tu nic do rzeczy).
    To powinno wyjść jako wniosek z analizy prostego przecież programu, przyznaję że mnie nie wyszło ("przespałem" analizę).

    Pomiędzy $40 a $80 znajduje się $20 wartości nieparzystych, a to oznacza że jest drugie takich $20 wartości, które "muszą" (wariant zmiennej nie ma znaczenia) następować odpowiednio po "swojej" (czyt. poprzedniej) wartości.

    Wygląda więc na to, że ogólna liczba takich "zdeterminowanych" wartości to 64 (1+1+2+4+8+16+32).

    EDIT:
    Pomyłka z tymi ostatnimi obliczeniami.
    Powinni być raczej 127 (1*7+1*6+2*5+4*4+8*3+16*2+32*1)
    • 11: CommentAuthormarok
    • CommentTime20 Jan 2023 zmieniony
     
    Uzupełniając.

    Łatwo dojść do wersji procedury z przekształcaniem wewnątrz wartości bajtu w odwrotnym kierunku.

    rand_8
    LDA r_seed ; get seed
    ; ASL ; shift byte
    lsr ; alt. shift byte
    BCC no_eor ; branch if no carry

    EOR #$C3 ; $C3 or $E7
    no_eor
    STA r_seed ; save number as next seed
    RTS ; done

    r_seed
    .byte 1 ; prng seed byte, must not be zero

    ; asl
    ; $1D. $2B. $2D. $4D. $5F. $63. $65. $69.
    ; $71. $87. $8D. $A9. $C3. $CF. $E7. $F5.

    ; lsr
    ; $B8. $D4. $B4. $B2. $FA. $C6. $A6. $96.
    ; $8E. $E1. $B1. $95. $C3. $F3. $E7. $AF.


    Uzyskany efekt końcowy.

    Zmienia się kolejność "sekwencji deterministycznych"
    80 40 20 10 08 04 02 01
    C0 60 30 18 0C 06 03

    Ich ogólna liczba powinna się zgadzać (zgaduję).

    Wartości zmiennej, które "działają", zmieniają się na inny zestaw (wygląda jakby o 2 pozycje mniejszy, co mnie troszkę zaskakuje - ale ogólnie to mało co rozumiem).
    W obu tych zestawach dwie wartości się powtarzają, więc nabierają charakteru uniwersalności.

    edit:
    Wartości działających jest dokładnie tyle ile było przy obrotach w prawo. (Wiem już jak zgubiłem dwie poprzednio nie przywołane.) Wartości są lustrzanym (bitowo) odbiciem poprzednich, teraz są posegregowane dla lsr aby wizualnie korespondowały z tymi dla asl.
    • 12: CommentAuthor0xF
    • CommentTime20 Jan 2023
     
    8-bitowy generator z "prawidłowym" wielomianem ma okres 255 - bo występują wszystkie wartości oprócz zera. Dla seeda zero utkniesz w zero.
    Te różne "prawidłowe" wielomiany (czyli w praktyce stałe dla EOR) są w praktyce równie dobre - dają wyniki w różnej kolejności, ale chyba nie ma tak, że jedne są lepsze, a drugie gorsze.
    W POKEYu jak wiadomo jest generator 17-bitowy. Jest też o tyle lepszy, że działa z zegarem 1,77 MHz.
    Co do gier to w "Bank Bang!" otwieranie drzwi jest losowane przez odczyt RANDOM w dwóch kolejnych instrukcjach, coś w rodzaju:
    LDA RANDOM
    ORA RANDOM
    AND #$0F
    BEQ OTWORZ

    Atari800 oryginalnie wołało po prostu funkcję C "rand()", co powodowało, że drzwi otwierały się bardzo rzadko.
    • 13: CommentAuthormarok
    • CommentTime21 Jan 2023 zmieniony
     
    W Atariki pod hasłem "RANDOM" w mapie pamięci, znajduje się precyzyjna (pełna?) definicja.

    Liczba pseudolosowa z zakresu od 0 do 255.

    Rejestr zawiera 8 najstarszych bitów 9- lub 17-bitowego rejestru LFSR o wielomianie odpowiednio 1+x^4+x^9 lub 1+x^12+x^17 zależnie od stanu bitu 7 AUDCTL. Zawartość rejestru przesuwana jest w prawo co cykl zegara 1,77 MHz. Przy odczytywaniu serii wartości pseudolosowych dobrze jest więc zadbać, żeby pomiędzy kolejnymi odczytami upłynęło co najmniej 8 cykli pracy zegara 1,77 MHz; w przeciwnym wypadku kolejno odczytane wartości mogą okazać się między sobą zauważalnie skorelowane. Ten efekt da się zauważyć zwłaszcza na akceleratorach.

    Podczas resetowania układu (za pomocą bitów 0 i 1 SKCTL) do rejestru LFSR wsuwane są jedynki.


    Właśnie do niej zajrzałem i przywołuję, bo warto. ;)
    (odpowiedni timing)

    Z informacji, których raczej brakuje, a są w artykule z Syzygy, to nie ma o szczególnym przypadku działania rejestru LFSR w momencie przełączenia zegara z 17 na 9 bitów.

    Postaram się (nieprecyzyjnie) to zreferować:
    zamiast wyniku operacji EOR na bitach 8 i 13 do bitu 16 zawsze wsadzana jest 1-ka;
    ( odczyt z Random przełączonego na 9 bitów Pokeya daje wgląd w bity 16-9 )
    ( odczyt z Random przełączonego na 17 bitów Pokeya daje wgląd w bity 8-1; EOR odbywa się na bitach 0 i 5 )

    Przyczyną tego wyjątku jest to, że LFSR mogłby się "zatrzasnąć na 0".

    Być może to już wszystko, czego nie ma w haśle w Atariki z informacji z artykułu, ale dla mnie wszystko to pozostaje jakby nadal niedopowiedziane (niezrozumiałe najpewnie z przyczyn niedostaktu wiedzy matematycznej).

    Chyba że jeszcze to, że to jest cały czas ten sam rejestr LFSR i on cały czas pracuje (przesuwa wszystkie swoje 17 bitów) mimo przełączenia na 9 bit Pokeya.


    Wychodząc ze wzoru tych wielomianów to nie wiem jak to dokładnie wpasowuje się w opis działania rejestru LFSR Pokeya ("ludzkim językiem" z artykułu). Jak traktować ten X przy wzorze, pisząc kolokwialnie. Czy ten X reprezentuje liczbę 2, czy jest to faktycznie zmienna?

    Korelacja tych wielomianów z opisem działania Pokeya polega na tym, że:
    1+x^[12+5]+x^[17+0] = 1+x^[4+13]+x^[9+8]

    Rozumiem, że wielomian już opisuje działanie szczegółowe LFSR Pokeya (i ten opis z artykułu nic więcej w to nie wnosi), mimo wszystko dobrze że ten artykuł jest i można się z niego dowiedzieć o Random na Atari.

    EDIT:
    poprawiłem to co najważniejsze (całą resztę nie ruszam)
    bit 17 przeflancowałem na 16 (17 bitów: 0-16)
    (mam nadzieję, że ta reszta jest już dobrze przepisana z artka)
    • 14: CommentAuthor0xF
    • CommentTime21 Jan 2023
     
    to jest cały czas ten sam rejestr LFSR i on cały czas pracuje (przesuwa wszystkie swoje 17 bitów) mimo przełączenia na 9 bit Pokeya.

    Tak właśnie jest. Czy to jest niejasne po lekturze mojego starego artykułu w Syzygy?

    Wychodząc ze wzoru tych wielomianów to nie wiem jak to dokładnie wpasowuje się w opis działania rejestru LFSR Pokeya ("ludzkim językiem" z artykułu). Jak traktować ten X przy wzorze, pisząc kolokwialnie. Czy ten X reprezentuje liczbę 2, czy jest to faktycznie zmienna?

    Przeczytałeś ->link<- ?

    LFSR w POKEYu to Fibonacci LFSR a wykładniki w wielomianie mówią, które bity z rejestru bierzemy do XORa. Tyle od strony praktycznej. Jest do tego teoria matematyczna, ale jeśli potrzebujesz zaprogramować lub zbudować sprzętowy LFSR, potrzebujesz tylko wiedzieć, które bity XORować i to właśnie mówią wykładniki wielomianu.

    Programowo mniej kodu jest dla Galois LFSR i to jest właśnie to, co pojawia się w Twoich kawałkach kodu.
    • 15: CommentAuthormarok
    • CommentTime21 Jan 2023
     
    Tak właśnie jest. Czy to jest niejasne po lekturze mojego starego artykułu w Syzygy?

    Dokładnie odwrotenie.
    To wiem z Twojego artykułu, ale prawdopodobnie z hasła na Atariki ciężko o taki jednoznacznie wniosek (pewnie nie napisałem tego w odpowiednim miejscu czy nazbyt zrozumiale).

    Jeśli chodzi o Pokeya i reset to nie zrozumiałem z Twojego artykułu (skoro pytasz o niezrozumienie), czy i jak on może zostać przytrzymany w tym stanie (reset) przez 17 cykli by się "najedynkował" (kolokwializm/ neologizm). Może działa to z automatu (jako reset) albo można to jakoś sprokurować. (Źródeł do artykułu z przykładami jeszcze nie widziałem, tam może znalazłbym wyjaśnienie - przepraszam, ale nie zdołałem jeszcze sobie ich przygotować do wglądu.)
    W Atariki jest "Podczas resetowania układu (za pomocą bitów 0 i 1 SKCTL) do rejestru LFSR wsuwane są jedynki."
    To raczej by znaczyło, że działa tu automat, ale też nie jest to jasne, czy chodzi dokładnie o 17 cykli (może tylko naprowadza na taki wniosek.)


    Przeczytałeś ->link<- ?

    Próbuję, w jakimś tylko stopniu jest to dla mnie przyswajalne.

    LFSR w POKEYu to Fibonacci LFSR

    Tak to kojarzyłem.

    potrzebujesz tylko wiedzieć, które bity XORować i to właśnie mówią wykładniki wielomianu

    Tylko wymagałoby to pewnego jeszcze dopowiedzenia.
    Bity w LFSR są liczone wg kierunku przesuwu nimi (w prawo, z lewa). Nie spotykałem się dotąd z takim określaniem porządkowym bitów.
    To dziwne równanie, które "wysmażyłem" wcześniej, jest właśnie skutkiem braku zauważenia tego elementu (podpowiada ilustracja) i szukaniem mimo wszystko jakieś korelacji (bity się zgodziły - suma ich odwrotnie czytanych pozycji równa się wszystkim bitom, czyli 17).
    • 16: CommentAuthor0xF
    • CommentTime21 Jan 2023 zmieniony
     
    czy i jak on może zostać przytrzymany w tym stanie (reset) przez 17 cykli by się "najedynkował"

    lda #0
    sta SKCTL
    cmp (0,x)
    cmp (0,x)
    lda #3
    sta SKCTL

    Powyższy kod resetuje POKEYa przez 18 cykli, czyli cały rejestr 17-bitowy się najedynkuje.

    Edit:
    Potencjalnie więcej cykli w przypadku wstrzymania CPU przez ANTICa. POKEY działa cały czas.
    • 17: CommentAuthormono
    • CommentTime22 Jan 2023 zmieniony
     
    Nie.
    Poprawny reset POKEY-a nie może bazować na zegarze CPU, bo ten bywa większy niż 1.77, a na zegarze którym taktowany jest hardware:
    lda #0
    sta SKCTL
    sta WSYNC
    sta WSYNC
    lda #3
    sta SKCTL

    Tu masz gwarancję, że niezależnie od tego jakie będzie turbo w komputerze, reset będzie całkowity, bo bazuje na czasie trwania linii skanningowej (114 cykli 1.77 MHz).
    Temat był omawiany przez Draco w wątku o którymś BASIC-u.
    • 18: CommentAuthormarok
    • CommentTime22 Jan 2023 zmieniony
     
    @mono: ok, jeszcze się może delikatnie odniosę, a teraz przeklejam to com se bazgrnął (bardziej w polemice do Fox'a)


    Czy to się zgadza?

    w celu uproszczenia opisu działania,
    jeśli mamy Pokey przełączony na 17 bitów,
    to jest to ".Word" (1-16) + Carry Bit (17) [w nawiasach ponumerowane bity pocz. od najstarszego, jak dla lfsr]

    w następnym cyklu, po
    lfsr do x^1 wpada x^17 po eor z x^12
    rcr do x^1 wpada(-łby) x^17 (po prostu)

    [ RCR Rotate Through Carry Right: 16-bitowy odpowiednik ror.6502 ]

    jeśli mamy Pokey przełączony na 9 bitów
    to jest to ".Byte" (1-8) + Carry Bit (9)

    i po
    lfsr do x^1 wpada x^9 po eor z x^4
    rcr do x^1 wpada(-łby) x^9



    jeśli tak można to zapisać, to nie rozumiem następujących rzeczy:

    co taki zapis mówi?:
    x^17+x^12+1

    przyjmując, że każde x^n niezależnie od pozostałych, reprezentuje swój stan - wartość bitu na pozycji n (z zawartości word / byte)
    (0 lub 1)

    wynik tego działania "na wielomianie" (czy jak je traktować) dać może wartość z przedziału 1-3

    jak rozumiem, dokonuje się następnie na tym wyniku operacja mod(ulo) z 2:
    wynikiem dalej, z tego modulo, może być 1 (1,3) lub 0 (2):
    jeśli x^17 <> x^12 (XOR) to dostajemy na wielomianie [1+0 +1]%2 = 0 , a pasowałoby bardziej odwrotnie, czyli 1,
    jeśli x^17 == x^12 (XOR) to dostajemy na wielomianie [[0|2]+1]%2 = 1 , czyli odwrotnie, niż spodziewałbym się (0).

    wynik spodziwałbym się jest już tym bitem, który ma wejść do x^1 w następnym cyklu lfsr (ale jest jakby odwrotnością)


    Przechodząc teraz do przykładu na stronie wikipedii o lfsr.
    Dodatkowo są tam rzeczy poza analogiami z tym powyżej, których nie rozumiem.

    Przykładowy lfsr jest rozpisany na 16 bitów (nie na 17).

    Tam, gdyby to trzeba przypisywać, rolę Carry Bit mógłby ewentualnie spełniać bit 16.

    Podany jest przykład (z diagramu) LFSR na wielomianie:
    x^16+x^14+x^13+x^11+1

    rezultat na tym wielomiane (po modulo) miałby więc znaleźć się w x^1 w następnym cyklu (najstarszym bicie)

    Jest parę reguł odnośnie tap-ów (pozycji dla wykładników wielomianów).
    The number of taps is even.
    The set of taps is setwise co-prime; i.e., there must be no divisor other than 1 common to all taps.

    The bit positions that affect the next state are called the taps. In the diagram the taps are [16,14,13,11].


    które nie rozumiem, jak spełnia ten wielomian
    gdyż w moim rozumieniu problemem jest to że 16 i 14 mają wspólny dzielnik 2 różny od 1.

    Może, w przypadku gdyby tak interpretować ten wielomian, jak zrobiłem to powyżej, lepszą pomocniczo (lepiej zrozumiałą) konwencją zapisu byłoby:
    x[17]+x[12]+1 ?

    Tylko, zapewne gdzieś tu tkwi błąd.
    • 19: CommentAuthormarok
    • CommentTime22 Jan 2023
     
    @mono: Fox nawiązywał (świadomie / podświadomie) zapewne do swoich źródeł z przeszłości (o których pisałem), a wtedy nie było realnie innego zegara CPU w zastosowaniu. Poza tym, narobiłem takich "byków", że było co poprawiać i chciał to zrobić sprawnie (nie bawiąc się już w didaskalia). Generalnie tamten przykład wyjaśnia sprawę, jak liczyć cykle w odniesieniu do resetu Pokeya (o to mi chodziło).
    Ja ze swojej strony nie doczytałem, że stan resetu utrzymuje się w stanie bitów %00 (bodajże ;) ).
    Czasami czyta się pewne ustępy bez właściwego zrozumienia.
    • 20: CommentAuthormarok
    • CommentTime22 Jan 2023
     
    Chyba jednak liczba tych bitów z przykładu to także 17. Tam jest dodatkowy bit 0 (nie 17). Ma reprezentować tą 1 w działaniu na wielomianie (wciąż nie pojęłem dlaczego to zawsze 1).
    • 21: CommentAuthor0xF
    • CommentTime22 Jan 2023
     
    x^0=1
    • 22: CommentAuthormarok
    • CommentTime22 Jan 2023
     
    Dobrze, ale w praktyce odwraca to wynik całości działania.

    Dla wzoru lsfr Pokeya x^17+x^12+1 ( GF(2) x^17+x^12+1 ?),
    gdy oba bity (.17 i .12) są skasowane (ogólnie: w jednakowym stanie) wyszłoby 1.

    a formalnie, czy x^0 tutaj nie oznaczałby x^17 ? (inne nazewnictwo)
    • 23: CommentAuthormarok
    • CommentTime23 Jan 2023 zmieniony
     
    Programy liczące na podstawie tych wielomianów (z przykładów na stronie wiki) zdają się, jak dla mnie, ignorować to + 1 (od x^0) w obliczeniach.

    Pozostaje to w każdym bądź razie dla mnie wciąż zagadkowe, jakie dokładnie działanie odbywa się z tymi wielomianami.

    To się pewnie do tego nie odnosi, ale wyjaśnienie "inverse modulo" to byłoby to, o co by mogło chodzić… (redukcja + 1 z wyrażenia obliczanego wielomianu):
    Division is multiplication by the inverse modulo p



    W opisie z wikipedii o "Fibonacci LFSRs"…

    The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive over the Galois field GF(2).


    Odszukałem stronę z ich wykazem.
    ->link<-

    Skrócona lista (do której prowadzi link) określona jest jako "primitive irreducible polynomials", rozszerzona (dostępna do zassania) to "primitive polynomials" (co może znaczyć to samo).


    Z listy rozszerzonej, która wydaje się kompletować wszystkie warianty tych "primitive polynomials" do 32 wykładnika przy x (zawiera aż 5372962 wielomianów) wybrałem do "analizy" te pogrupowane wg klucza.

    Pierwsze kryterium, to chyba się określa jako GF(X^9), to wielomiany z najwyższą wartością wykładnika x^9, drugie to liczba "tabs" równa 2. Nasze "x" to raczej 2, więc to byłoby na dobrą sprawę GF(2^9).

    x^9 + x^1 + 1
    x^9 + x^4 + 1
    x^9 + x^5 + 1
    x^9 + x^8 + 1

    Jak można zauważyć tylko część kombinacji jest dopuszczalnych (by było to wyrażenie "primitive").

    Jeszcze jedna grupa, którą wybrałem do analizy.
    Różni się tylko tym (od tej poprzedniej), że drugie kryterium jest obliczone na liczbę "tabs" równą 8.

    x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
    x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^1 + 1

    (Z tej grupy nieaktywnych jest 6 kombinacji. Bez jednego z wykładników: 8,6,5,4,3,1 przy x w wielomianie.)

    LFSR Pokeya to x^9 + x^4 + 1 .

    Analizy w sumie nie będzie. ;)

    (Chodziłoby mi o przypadek drugiego warunku z tych, które określają pozycję tabs dla wielomianów, które działają. We wcześniejszych wpisach pisałem coś, że 16 i 14 jako wykładniki są podzielne przez tą samą wartość, 2, w jednym z takich wielomianów, użytym za przykład na stronie wiki. W każdym razie nie tak należy to rozumieć, jak ja to zrozumiałem. W sensie tego drugiego warunku dla wielomianów, które mogą działać. A rozważania jaki jest na prawdę ten warunek przekraczają moje kompetencje lub w najlepszym razie są przedwczesne.)


    Co jednak teraz zauważam. (!?)

    Nie ma wśród tego wykazu "primitive polynomial" tego od Pokeya przełączonego na 17 bit: x^17 + x^12 + 1 .

    To trochę zastanawia (niepokoi?).
    Nie umiem odpowiedzieć dlaczego, ale temat zamierzam jeszcze podrążyć.
    • 24: CommentAuthorilmenit
    • CommentTime23 Jan 2023
     
    Zapytaj ChatGPT, jest dobry w takich wyjaśnieniach, serio :)
    • 25: CommentAuthormarok
    • CommentTime23 Jan 2023
     
    Zapewne to dobra podpowiedź (trzeba by spróbować, by się o tym przekonać).

    Będąc jednak tradycjonalistą (że się tak określę) i dodatkowo z przyczyn "lingwinistycznych" (musiałbym się poważnie zastanowić nad poprawnym zapisem swojego pytania; angielski nie jest mi specjalnie bliski, z pisaniem poprawnym mam ogromny kłopot) nie spieszno mi do tego. Ponad to czułbym się zapewne onieśmielony jakiś "gadać" z AI (kto wie z czym i kim do końca?? to ostatnie rzucam przed wstępnym nawet jakimś rozpoznaczniem tego czym jest AI w tej odsłonie - zalecana jest może jakaś ostrożność podejścia, tak mi się wydaje).

    W sumie (więc) nie wiem co to jest (specjalnie nawet że jest). Choć wątek o AI jest obecnie na AOL dość mocno zdaje się dyskutowany, to muszę przyznać, że akurat go nie śledzę (z innych źródeł potencjalnej wiedzy na ten temat nie korzystałem).


    Tak przy okazji, znalazłem link do tego (choć to niedostępne dla ogółu):

    ->link<-

    (może dobre by to było dla bardziej wtajemniczonych w tych lfsr -ach)

    coś do liczenia "period" dla Polynomials ograniczonych w GF ? (w zasadzie nie umiem nazwać tego, czego aktualnie szukam)
    • 26: CommentAuthormarok
    • CommentTime24 Jan 2023 zmieniony
     
    2^17+2^12+1 = 135169

    ta liczba nie przechodzi testu na liczbę pierwszą
    ->link<-

    jest to (2) niezbędny warunek dla wielomianu przy GF(2^n) gwarantujący okres 2^n-1

    EDIT:
    czy niezbędny? chyba jednak nie jest to prawidłowe wnioskowanie i rozumienie warunku 2 (sorry)

    przez analogię można to wykluczyć, gdyż za

    ->link<-

    "511 is not prime. It is divisible by 7."
    "135169 is not prime. It is divisible by 29."
    "92161 is not prime. It is divisible by 23."

    to z przykładu wiki dla wielomianu lfsr:
    2^16 + 2^14 + 2^12 +2^11 + 1 = 92161
    • 27: CommentAuthormarok
    • CommentTime24 Jan 2023 zmieniony
     
    This also tells you that product is a bit more complicated, because it requires to do all the shifts but followed by a polynomial long division.


    Znalazłem to (wyrwane tu z kontekstu), co wiąże działanie na wielomianie (takim do lfsr) z dzieleniem (wielomianu? przez wielomian). A więc może wiązać się z tym użycie "inverse modulo" (czyli jak dla mnie ten brak odniesienia + 1 w obliczeniach na wielomianie w kodzie lfsr).

    (To odnośnie odpowiadania sobie na wątpliwości, które wyrażałem tu poprzednio.)
    • 28: CommentAuthormarok
    • CommentTime24 Jan 2023 zmieniony
     
    # Complete list of primitive trinomials over GF(2)
    # up to degree 400

    ->link<-

    jest tam i ten
    17,12,0

    więc nie ma "problemu"
    (okres lfsr na tym "trójmianie" to rzeczywiście 2^17-1)

    trinomials to krótka odmiana polynomials
    akurat taka, jaka jest w użyciu przy Pokeyu

    Poprzednia lista, na której się oparłem, musi być nieco niekompletna

    edit:
    Już chyba rozumiem dlaczego na tamtej liście nie ma wszystkich "wielomianów, które działają".

    przykład:
    na tej liście trójmianów wykładnik 17 jest reprezentowany tak:
    17,3,0
    17,5,0
    17,6,0
    17,11,0
    17,12,0
    17,14,0

    widać, że robią się z tego pary (3+14, 5+12, 6+11) wielomianów, które są względem siebie "symetryczne"


    na pierwszej liście wielomianów wykładnik 17…

    x^17 + x^3 + 1
    x^17 + x^3 + x^2 + x^1 + 1
    x^17 + x^5 + 1
    x^17 + x^6 + 1
    x^17 + x^8 + x^4 + x^3 + 1
    x^17 + x^8 + x^7 + x^6 + x^4 + x^3 + 1
    x^17 + x^10 + x^9 + x^8 + x^6 + x^5 + x^3 + x^2 + 1
    x^17 + x^12 + x^6 + x^3 + x^2 + x^1 + 1
    x^17 + x^12 + x^9 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
    x^17 + x^12 + x^9 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
    x^17 + x^14 + x^11 + x^7 + x^5 + x^3 + x^2 + x^1 + 1
    x^17 + x^15 + x^13 + x^11 + x^9 + x^7 + x^5 + x^3 + 1
    x^17 + x^15 + x^13 + x^11 + x^9 + x^7 + x^6 + x^4 + x^2 + x^1 + 1
    x^17 + x^16 + x^3 + x^1 + 1

    czyli z "trójmianów" są wszystkie (3, 5, 6 ) z par (14, 12, 11)
    symetryczne są "domyślne", więc lista jest też kompletna (źle o niej zdążyłem już napisać)

    dla wielomianów innych niż trójmiany "symetryczność" też musi mieć zastosowanie

    na wiki też coś na ten temat napisano (przypominam sobie hasłowo, choć nie doczytałem w czym rzecz)
    • 29: CommentAuthorilmenit
    • CommentTime24 Jan 2023
     
    Nie do końca rozumiem co próbujesz uzyskać, z czym masz problem, albo czego nie rozumiesz. Czy wkleić kod (najlepiej cały kompilowalny kawałek) i jaki jest z nim problem z punktu widzenia teorii LFSR?
    • 30: CommentAuthormarok
    • CommentTime24 Jan 2023
     
    Próbuję coś odpowiedzieć, trochę mi się to nie klei.

    Ostatnio próbowałem na własną rękę przekonać się (siejąc może wątpliwość) czy okres dla generatora zniekształceń Pokeya przestawiony na 17 bit rzeczywiście działa z tym okresem, o którym "wiadomo" (potwierdzając to sobie).

    Nie mam problemu z kodem, bo nic z tych rzeczy nie piszę. Temat mi się objawił sam, przeglądając stronkę. Dodałem do tam zawartych informacji pewne szczegóły, które okazały się nieznaczące i oczywiście nieodkrywcze.



    Problem jest taki, że często się mylę i zabieram głos przedwcześnie (brakuje mi opanowania), potem się poprawiam i wycofuję z twierdzeń, sugestii, czy wyrażanych wątpliwości. Tworzy się niemiły chaos dla "postronnych".

    Próbowałem coś zrozumieć ogólnie z podstaw matematycznych chwytając się pewnych szczegółów i za ich pomocą starałem się odkryć więcej. Ale mam za duże braki i ogólnie nie tak sprawny umysł, jakbym sobie życzył, żeby się w to bawić (a innych dręczyć) zaczynając od podstaw. No ale, nie zawsze się człowiek kulturalnie umie odnaleźć w towarzystwie.
    • 31: CommentAuthormarok
    • CommentTime27 Jan 2023
     
    Napisałem krótki program symulujący zachowanie lfsr 9/17 bit dla Pokeya (na <300 bajtów).

    Symulacja obejmuje przełączanie szerokości bitów i reset Pokeya (czy działa dobrze?).
    (Uwzględniłem konieczność 18 cykli do skasowania wszystkich bitów, tak jak interpretacyjnie pojąłem, że to działa. Nie jestem też pewien momentu wstawiania bitu po przełączeniu z 17 na 9.)

    Sterowanie to klawisze: lewo / prawo : zmiana tempa następowania kolejnego cyklu przekształceń lfsr,
    lewo / prawo (+ control) : przełączanie się na 9/17 bit,
    R : inicjowanie Reset lub inicjowanie normalnego przekształcania lfsr (po reset).

    Strzałki pomocnicze pokazują skąd pobierana jest informacja dla bitu który nadchodzi i wejdzie na pierwszą pozycję do lfsr w następnym cyklu.

    Są podawane dwie wartości przeliczone na hex z tych bitów / rejestrów lfsr. Odczyt symulowanego $d20a (random) zwracałby tą wartość, która znajduje się bliżej strzałek (otaczają ją). Druga to ta, do której analogicznie nie byłoby sprzętowego dostępu.

    Ostatnia wartość, z drugiej strony ekranu, jakby na uboczu, w hex, to wartość regulowanej prędkości przekształceń lsfr, czas pomiędzy cyklami przekształceń przeliczony na ramki (czyli liczba ramek na cykl).

    Nazwa programiku jest bardzo robocza (coś się może wymyśli, może ktoś podsunie nawet jakiś pomysł).

    Myślałem jeszcze o dodaniu sygnalizacji "BELL" inicjowania Reset, ale nie do końca wiem jak to zrobić w asm.

    Oprócz tego mogłyby się ewentualnie przydać rozkazy zatrzymania i pojedynczego kroku przekształceń.

    Jeśli ktoś miałby pomysł do wykorzystania w związaku z tą emulacją lfsr to oczywiście chętnie przeczytam.

    Przełączanie między 9/17 bit mogłoby może pozwolić na uzyskiwanie okresów o wartości liczby pierwszej (co byłoby może istotne dla generowanych dźwięków). Tutaj teoretycznie można trochę z tym poeksperymentować (tak sobie kombinuję). Natomiast ciężko jest na pewno uzyskać kontrolę nad lfsr w hardware, czyli byłoby to trudne później precyzyjnie odtworzyć (za ew. eksperymentem).
    • 32: CommentAuthormarok
    • CommentTime28 Jan 2023 zmieniony
     
    Przetestowałem procedury Foxa na dostępnych mi emulatorach, dołączone do artykułu w zinie "Syzygy #7", do którego się tu już odnosiłem, i bez którego nie ruszyłbym z miejsca w sprawie rozpoznania działania lfsr na Pokey'u (z pamięci było mi ciężko przywołać wcześniej wszystkie detale, które ten artykuł wnosi ponad to co znaleźć można choćby w Atariki, ale miałem okazję dłużej się nad tym jeszcze zastanowić i sobie to właściwie uświadomić).

    Zrobię taki teraz bilans powodzeń i niepowodzeń tych testów, ponieważ emulacja nie okazała się bezbłędna w tym przypadku (niewątpliwie wymagającego zadania).

    Programów-testów tych są cztery (powiązanych z artykułem). Wszystkie bardzo krótkie i oczywiście sprytne. Jak byłaby potrzeba to je mogę gdzieś dołączyć w załącznikach (albo dodać w tekście).

    Bilans.

    rand9: (prawie) działa na Atari800
    niedokładność polega na: emul. nie zabiera 9 cykli procesorowi i przez to lfsr jest w przebiegu o 9 cykli do przodu w odczycie kontrolnym (z $d20a),
    działa na Atari++

    rand17: działa na Atari800,
    działa na Atari++

    rand9tab: (prawie) działa na Atari800:
    niedokładność polega na odczytach o cykl za wcześnie wartości z lfsr (niedoliczenie 1 cyklu, który miał być a nie został zabrany CPU od początku pomiaru do momentu wypełniania konkretnej pozycji w tabeli)

    tabela ($7E01-$7FFF)
    $00-$71 to w tym obszarze zdarza się że jest do przodu o cykl z odczytem $d20a / lfsr
    $72-$1FE ok (tj. wpisy się zgadzają)

    [pomocnicze zrzuty z porównania z właściwymi wartościami, "dowód w sprawie"]

    (prawie) działa na Atari++
    wszystkie wartości (w stosunku do pierwszej) w tablicy są z odczytu o 1 cykl za wcześnie (niedoliczenie 1 cyklu obciążenia CPU, które się potem już nie wyrównało), lub tylko pierwsza wartość odczytu z lfsr jest o 1 cykl za późno (1 cykl obciążenia CPU nastąpił extra, ale potem się to wyrównuje), a reszta wartości prawidłowa

    rand179: (zupełnie) nie działa na Atari800
    (zupełnie) nie działa na Atari++

    Do tych emulatorów mam dostęp. Do Altirry niestety nie.
    Dlatego jej tu uwzględnić nie mogłem.
    • 33:
       
      CommentAuthorBca
    • CommentTime31 Jan 2023 zmieniony
     
    @all
    to da się przewidzieć totolotka?
    • 34:
       
      CommentAuthortdc
    • CommentTime31 Jan 2023 zmieniony
     
    Skoro wszystko się już parę razy zakręciło, ja powrócę do pierwszego posta - tak na marginesie:

    marok:

    prawdopodobieństwu wszystkich takich zdarzeń spośród kolejnych 255 losowań, które złożą się na wystąpienie dokładnie 1 z 255 wartości, a określona z góry jedna nie wystąpi wcale, z pełnej puli 256 wartości do wylosowania.


    W grze Tomcat mamy losowania dla każdego przeciwnika w jednej ramce* czy wystrzeli.

    W drugim levelu przeciwnicy zaczynają strzelać już dość żwawo, a częstotliwość wystrzałów wzrasta wraz z kolejnymi etapami.

    Ciekawy jest jednak level 1, w którym przeciwnicy nie strzelają. Gdy ktoś się mnie o to pyta od strony technicznej (a rozmawiałem o tym f2f z wieloma osobami), to ja podkreślam, że przeciwnicy co prawda nie strzelają, ale prawdopodobieństwo jest niezerowe.

    Zrealizowane jest to właśnie tak jak opisał marok, czyli przeciwnik wystrzeli jeśli w rejestrze POKEY-a pojawi się wartość 0 (i tylko wtedy). Zero jest tu przykładowe, choć chyba właśnie taka wartość jest w kodzie gry.

    W praktyce oznacza to, że przez cały 1 level żaden przeciwnik nie wystrzeli.

    Jednak gdy uruchomimy grę wiele razy to za którymś razem może jednak wystrzelić. Co nawiasem jest ciekawe, bo zaskoczy to gracza, czyli wywoła emocje;)


    To tylko tak na marginesie jak wygląda w praktyce losowanie z rejestru POKEY-a jednej konkretnej wartości.


    * nie pamiętam, może losowania odbywają się co dwie ramki lub w parzyste i nieparzyste - musiałbym sprawdzić w źródle. Ale teoretycznie dana gra może losować wystrzał raz na ramkę, natomiast co dwie ramki jest to i tak niezauważalne dla gracza.
    • 35: CommentAuthormarok
    • CommentTime31 Jan 2023 zmieniony
     
    Zrealizowane jest to właśnie tak jak opisał marok, czyli przeciwnik wystrzeli jeśli w rejestrze POKEY-a pojawi się wartość 0 (i tylko wtedy). Zero jest tu przykładowe, choć chyba właśnie taka wartość jest w kodzie gry.

    W praktyce oznacza to, że przez cały 1 level żaden przeciwnik nie wystrzeli.

    Jednak gdy uruchomimy grę wiele razy to za którymś razem może jednak wystrzelić.


    Przybliżone prawdopodobieństwo takiego zdarzenia to 1/255 w pierwszej ramce na jednego przeciwnika, gdy już może wystrzelić. Prawodopodobieństwo wystrzelenia raz na cały level 1 od wszystkich przeciwników, to (może) LP*ramki/2/255.
    LP to liczba przeciwników (to jest jednak zmienna, niestała, można przyjąć jakąś wartość średnią niecałkowitą), przyjąłem też że sprawdzana jest wartość 0 z Random (w przeciwnym wypadku trzeba by to równanie wymnożyć przez 2), a możliwość wystrzału jest co drugą ramkę (parzysta/ nieparzysta/ co druga).

    Jeśli przesuw levelu jest ze stałą prędkością (1 punkt na cykl wyświetlania obrazu), a ekran jest na 160 pikseli (czy inaczej), to zależnie od długości levelu liczonego w ekranach można określić prawdopodobieństwo tego samego czyli strzału na level (to zamiast lub przy okazji liczenia ramek ile zajmuje czasu level).

    Historia ciekawa, od strony jak to wygląda z prawdopodobieństwem z Random w praktyce (można to sobie unaocznić).

    @Bca:
    Z dawien dawna słyszało się o "systemach" gry, które miałyby niby szansę się sprawdzić w totka. Więc ludzie próbowali to sobie opracować i przewidzieć przyszłość (cyferki), ale taka idea wydaje się nie mieć racji bytu, gdyż losowania nie zależą od siebie wzajemnie (w przeciwieństwie do Random z lfsr).

    EDIT (korekta obliczeń):

    Wyliczenia prawdopodobieństwa dla levelu 1 są oczywiście błędne.
    Najłatwiej przekonać się o tym, zorientowawszy się, że wartość obliczenia mogłaby przekroczyć granicę 1 (w jakimkolwiek do wyobrażenia scenariuszu, abstrahując od konkretnych uwarunkowań). Prawdopodobieństwo, tak w ogóle, nie może jej przekroczyć, gdyż mieści się w przedziale (0,1), gdzie 0 to zerowe prawdopodobieństwo (coś się nie może wydarzyć), a 1 to 100% pewność że coś zajdzie.
    Prosto rozumując, wychodząc z wartości prawdopodonieństwa dla pierwszej ramki danego zdarzenia (1/255), "policzyłem" że z każdą kolejną ramką będzie ono rosło proporcjonalnie (arytmetycznie). Na to mogłaby wskazywać logika lub tzw. intuicja.

    Lepiej oddaje prawdopodobieństwo przejścia levelu 1 bez wystrzału przeciwnika coś na kształt:

    1 - (254/255) ^ ( ramki/2 * śr. przeciwników na ramkę )

    Dla pierwszej ramki (gdy przeciwnik może już strzelać i powiedzmy dla uproszczenia, że jest jeden), mamy: 1 - (254/255) ^ 1, czyli 1/255 (tu się zgadza, co pisałem).
    Za drugim momentem możliwego wystrzału (może w 3 lub 4 ramce, 1 przeciwnik) wynikiem prawdopodobieństwa byłoby to : 1 - (254/255) ^ 2, czyli 0,0078277585544. Teraz porównajmy oba prawdopodobieństwa, bo to względnie ciekawe:
    (I) 1/255 *2 = 0,00392156862745 *2 = 0,0078431372549 .
    (II) 0,0078277585544/0,0078431372549 = 0,998039215686 .

    Z (II) wynika że prawdopodobieństwo w drugim momencie (po drugim razie, gdzie przeciwnik może strzelać) do wymnożonego przez 2 prawdopodobieństwa w piewszym momencie jest bardzo podobne (I), więc w przybliżeniu jest ono faktycznie 2-krotnie większe (w tym sensie intuicja nie zawodzi tak do końca), ale jednak jest odrobinkę mniejsze niż 2 razy takie (o 2 promile) niż w pierwszym momencie.

    Policzyłem na piechotę (prymitywnie podstawiając do wykładnika różne wartości; nawet nie wiem jak to liczyć "normalnie" uwzględniając odpowiedni zapis matematyczny), że wykładnik o potędze 176 daje już prawdopodobieństwo zbliżone do 50%. Trzeba to rozumieć tak, że jeśli średnio na ekranie mamy 1 samolot przeciwnika to po 352(176*2) ramkach (czyli już po 7 sekundach jest 1 szansa na 2, że przeciwnik strzeli). Może się to nie zgadzać z doświadczeniem z gry, ale różne czynniki mogą jeszcze wpływać na to (nie uwzględnione w obliczeniach).
    • 36: CommentAuthormarok
    • CommentTime31 Jan 2023
     
    Tak przy okazji, bo się trochę nad tym zastanawiałem, czy publicznie w tym wątku nie poprosić, czy dałoby się pod Basic sprawdzić jeden test-program?

    Jest to jeden z tekstów Foxa z pewną modyfikacją, która umożliwia za jednym razem sprawdzenie tego, co test pierwotnie sprawdza ale jednocześnie przejście go nie wyklucza innego wytłumaczenia dla jednostkowego wykonania (ta wersja powtarza badanie w pętli dostatecznie dużo razy, aby wykluczyć przypadkową zbieżność i jedno wykonanie wystarczy).

    Konkretnie to test rand179.asm. Zrobiłem przeróbkę do Basica (funkcja USR), bo brałem pod uwagę samodzielną możliwość sprawdzania tego na real sprzęcie (nie wiem na ile to jednak realne dla mnie).


    Zastanawia mnie też Altirra, ale też pod tym kątem, że pamiętam, że z ekranu można było kopiować tekst, a biorę pod uwagę, że istnieje możliwość odwrotnej operacji (choć to może bardziej problematyczne byłoby dla emulatora w imlementacji). To ułatwiałoby przeniesienia programu w Basic na ekran - paste (potwierdzenie linii returnem) - i odpalenie w prosty sposób.

    Altirra może działać jak real sprzęt, spodziewam się.

    Jest też wersja w asm tego samego tekstu i chyba też ją tu zamieszczę, jeśli komu byłoby łatwiej to sprawdzić (na real sprzęcie lub na Altirra).

    Program w Basic.
    Przejście tekstu to na pewno wartość > 0 (w wersji asm tak samo, ale z akumulatora pod monitorem po brk).

    10 RESTORE 50:FOR I=0 TO 44:READ A:POKE 1152+I,A:NEXT I
    20 A=USR(1152):? :? A=A-(INT(A/1024)*1024)
    50 DATA 104,162,0,160,128,120,238,14,212,238
    60 DATA 0,212,169,0,141,8,210,141,10,212
    70 DATA 140,8,210,173,10,210,157,0,6,232
    80 DATA 208,236,61,0,6,232,208,250,78,14
    90 DATA 212,88,133,212,96


    Jeszcze taka uwaga, że program korzysta z obszaru $480-… (45 bajtów w basic) i 6 strony pamięci (gdyby to z czymś kolidowało).

    Oryginalna wersja (z '99 roku lub wcześniej) procedury Fox'a
    * Program sprawdza,
    * czy podczas przelaczania
    * rejestru 17-bitowego na 9-bitowy
    * do rejestru jest wstawiany bit 1

    ; opt 21
    org $480

    ldx #$00
    ldy #$80
    lda #$40

    sei
    inc $d40e
    inc $d400

    stx $d208
    sta $d40a
    sty $d208
    and $d20a

    lsr $d40e
    cli
    brk
    jmp $480


    Wersja modyfikowana (1 uruchomienie powinno wystarczyć za jednoznaczny dowód). Idea modyfikacji zaczerpnięta z innego programu testu z tego zestawu testów, rand9tab)
    org $480

    ; pla
    ldx #$00
    ldy #$80

    sei
    inc $d40e
    inc $d400

    @ lda #0
    sta $d208
    sta $d40a
    sty $d208
    lda $d20a
    sta $600,x
    inx
    bne @-
    @ and $600,x
    inx
    bne @-

    lsr $d40e
    cli

    brk ; sta $D4
    rts
    • 37: CommentAuthormarok
    • CommentTime6 Feb 2023
     
    (what if) random access by position is needed

    it is (also) possible to compute the shift register's state at any position in O(log² N) time

    (Myślę, że o źródłe tego cytatu nie trzeba nawet wspominać, bo to najwyżej wszem rekomendowana pozycja.)


    z innych źródeł netowych (raczej) wynikło, że:

    log²(n) = log(n) * log(n)

    "Understanding Time Complexity with Simple Examples":
    O(log n): Now I divide the class into two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n). 

    The O(log n) search if all the students knew, but would only tell me if I guessed the right side. 


    Obliczanie "O" ("order") dotyczy chyba ilości powtarzalnych w pętli sekwencji działań (przekształceń), które trzeba przeprowadzić dla uzyskania porządanego wyniku ("shift register's state").

    Nie jest chyba jasne (dla mnie na pewno nie jest), jakie konkretne działania w pętli trzeba przeprowadzić, aby dojść do ostatecznego wyniku (mamy tylko wgląd w szacunek odnoszący się do liczby tych powtarzalnych sekwencji działań).


    Nie wiem czy takie obliczanie tego jest prawidłowe (dla n=511):

    log2(511) = 8.9971794809376 = 9
    log²(511) = 80,9492386122 = 81

    W zależności od skomplikowania sekwencji działań, którą należy powtórzyć w pętli, będzie to (raczej) szybsze od zwykłego przekształcania. Będzie się to uwidaczniać dla coraz większych jednostek czasu. Ten czas, z przykładu, który należy najwyżej do średnio długich (511 cykli) to zejście z 511 przekształceń do 81 (z tym że różniących się na pewno jakoś od poprzednich, niewykłuczone że bardziej złożonych i czasochłonnych).


    To ciekawe zagadnienie, ale sam tego z pewnością nie rozwikłam.

    Natomiast interesuje mnie jeszcze zagadnienie odwrotne - tzn. czy mając odczyt "shift register's state" możemy określić czas jaki był potrzebny do jego osiągnięcia dla Pokeya od stanu przypisanego "czasowi zero".
    • 38: CommentAuthormarok
    • CommentTime14 Feb 2023 zmieniony
     
    Ten mały emulator lfsr Pokeya poprawiłem i dodaję.
    Może tym razem działa poprawnie (poprzedni z pewnością nie działał).

    Operacja na bitach lfsr to teraz XNOR (odwrócone XOR), tak jak to działa w Atari (info z manuala). (Trochę to utrudnia percepcję z ekranu tego co się dzieje.)

    O jedną pozycję przesunąłem obszar bitów (rejestrów) lfsr w odczycie do RANDOM (bity są odwracane).

    Druga wartość w hex jest pomocnicza, pierwsza to odpowiednik rejestru RANDOM (poprzenio błędnie z pewnością założyłem i tak napisałem, że druga może przejąć rolę RANDOM gdy tryb to 17 bit).

    Działają dodatkowo klawisze:
    spacja - zatrzymanie przesuwu lfsr,
    return - przesuw o jedną pozycję .

    Reset zatrzymuje z automatu przesuw, który można wznowić spacją.

    edit: podmieniłem plik