eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingNegamax with alpha beta pruning and transposition tablesRe: Negamax with alpha beta pruning and transposition tables
  • Data: 2016-04-09 20:47:32
    Temat: Re: Negamax with alpha beta pruning and transposition tables
    Od: mk <reverse_lp.pw@myzskm> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    W dniu 2016-04-04 23:51, M.M. pisze:

    Dziś wróciłem do problemu... zacząłem udoskonalać swoje autorskie
    podejście (to z zapamiętywaniem alpha i beta) i... ostatecznie doszedłem
    do algorytmu, który jest w Wikipedii (jest OK!). Rozumiejąc już
    dokładnie co się w nim dzieje przejrzałem jeszcze raz stary kod --
    jednak popełniłem drobny błąd w implementacji tegoż algorytmu skuszony
    drobną fałszywą optymalizacją. Wniosek jest taki, że jak się jak małpa
    implementuje algorytm którego się nie rozumie, to trzeba małpą pozostać
    do końca i nie kombinować :-)

    >> W moim problemie nie używam iteracyjnego pogłębiania, a po postu:
    >> https://en.wikipedia.org/wiki/Depth-first_search
    > Czy mógłbyś zdradzić tajemnicę, do jakiego zadania stosujesz
    > alpha-beta-ze-spamiętywaniem?

    Mam wrodzoną dużą nieśmiałość, a problem który próbuję zaatakować jest
    kompromitująco szalony. Więc nie zdradzę. Po prostu sam nie wierzę w
    pozytywny rezultat, ale uznałem co mi szkodzi spróbować. Powiedzmy taka
    mała wprawka z kryptoanalizy...

    >> Robię tak dlatego z dwóch powodów:
    >> 1. Chcę dokładny wynik więc muszę wykonać pełne przeszukiwanie;
    >> zapamiętanie jednej warstwy w moim problemie w docelowym rozmiarze
    >> wymagałoby grubych dziesiątków GB,
    > Bym musiał wiedzieć co to za problem, to co tutaj napisałeś generalnie
    > nie pasuje mi do moich doświadczeń z grami. Może do Twojego problemu
    > alpha beta ze spamiętywaniem w ogóle nie jest dobrym algorytmem?

    :-)
    Nie dowiem się jak nie sprawdzę.

    >> a może i więcej; na razie pracuję na
    >> problemie o ograniczonym rozmiarze więc mogę sobie pozwolić na pełne
    >> zapamiętanie drzewa gry,
    > Właśnie to co napisałem powyżej, nie ma nic wspólnego z pełnym zapamiętywaniem
    > drzewa gry. Jeśli tak zrozumiałeś, to znaczy, że kompletnie się nie rozumiemy.
    >
    >
    >> ale docelowo chcę jednak użyć tablicy
    >> transpozycji zaimplementowanej jako hash table i ma ona działać jako
    >> rodzaj cache,
    > Dokładnie tak się to robi!
    >
    >> przy czym strategia zwolnienia miejsca na nowy wpis to:
    >> "wybór losowy" (co zapewnia funkcja hashująca).
    > Zwykle stosuje się technikę nie wybór losowy, ale stary zawsze zastępuj
    > nowym. Techniki bardziej zaawansowane dają minimalną poprawę i to tylko w
    > specyficznych warunkach, np. jest mało pamięci i bardzo długi czas
    > przeszukiwania drzewa gry.

    Właśnie o tym pisałem. Obliczam hash bieżącej transpozycji i owy hash
    używam do zaadresowania komórki w której owa transpozycja będzie
    przechowana. Stary wpis jest nadpisywany nowym. Jako że hash ma
    właściwości pseudolosowe to dlatego w metodzie tej uznaję, że
    zastępowaniu ulega losowy wpis.

    >> Mam już to
    >> zaimplementowane i początkowo nawet przypuszczałem, że właśnie owa
    >> "wybiórcza" memoryzacja jest problemem, ale nie...
    > Skąd wniosek że to nie ona jest problemem? Tam jest wiele miejsc w których
    > można się łatwo rąbnąć.

    Bo pomniejszyłem problem i zastosowałem memoryzację pełnego drzewa
    gry... i nie pomogło. I rzeczywiście problem miałem gdzie indziej.

    >> 2. Sortowanie ruchów ma sens tylko jak jesteśmy w stanie dokonać jakieś
    >> heurystyczne oszacowania co do wartości poszczególnych ruchów.
    > Owszem, ale takie oszacowanie zazwyczaj można zrobić i to na kilka sposobów.
    >
    >
    >> W moim
    >> problemie wynik da się prawdopodobnie dopiero obliczyć na końcu "gry".
    > No właśnie, co to za gra? :D

    Jak opisałem wcześniej: gracze znają reguły wykonywania dozwolonych
    ruchów oraz wiedzą w jakiej sytuacji gra się kończy. Wiedzą też jak ze
    stanu końcowego wytworzyć liczbę odzwierciedlającą wynik gry. I na razie
    tylko tyle -- oszacowanie wyniku gry bez dotarcia do węzła końcowego
    wstępnie uznaję za niemożliwe. A jeśli będzie możliwe, to będzie coś
    znaczyło... ale tu tajemnica.

    >> Taka dziwna gra: gracze wiedzą jak wykonywać ruchy, ale raczej nie mają
    >> żadnej wiedzy który ruch jest lepszy, a który gorszy -- dopiero na samym
    >> końcu gry następuje bum!
    > No nie wiedzą dokładnie, ale szacują jakoś prawdopodobieństwo, bo inaczej
    > jakby wykonywali ruchy?

    Patrz wyżej. Osiągnięcie stanu końcowego gry umożliwia dowiedzenie się o
    wyniku gry. Ale po drodze oszacowanie wyniku uznaję za niemożliwe.

    >> -- następują obliczenia oparte o finalną
    >> transpozycję
    > Nie wiem co to jest finalna transpozycja.

    W szachach: mat, pat czy inny stan remisu.
    W grze kółko-krzyżyk: wypełnienie wszystkich pól lub wcześniejsze
    osiągnięcie zwycięstwa zgodnie z regułami tejże gry.
    W grze "czwórki" (connect 4) zużycie przez graczy wszystkich żetonów lub
    wcześniejsza wygrana jednego z graczy zgodnie z regułami gry.

    >> Jak poprzednio pisałem: aktualnie we wpisie tablicy transpozycji
    >> przechowuję:
    >> 1. transpozycję -- klucz,
    >> 2. wynik gry,
    >> 3. wartość alpha przy jakiej obliczono "wynik gry",
    >> 4. wartość beta przy jakiej obliczono "wynik gry".
    > Nie jestem pewny, ale chyba robisz to źle, na 99% powinien być najlepszy ruch.

    Algorytm z Wikipedii nie przechowuje w tablicy transpozycji ruchu
    dającego najlepszy ruch. Nie trzeba, choć być może w pewnych sytuacjach
    warto.

    >> Wpisu używam tylko, gdy bieżące widełki alpha-beta mieszczą się w
    >> całości w widełkach alpha-beta z tablicy transpozycji, to rozumiem i to
    >> działa.
    > Z kolei ja nie rozumiem dlaczego taka wersja u Ciebie działa.

    Alpha i beta określają warunki wycinania. Skoro wartość ruchu
    przechowywana w tablicy transpozycji została obliczona przy liberalnym
    (skromniejszym) warunku wycinania, to tym bardziej będzie poprawna przy
    bardziej rygorystycznym warunku wycinającym (który w pełni pokrywa
    liberalny warunek wycinający).

    >> Wspominając o sortowaniu, podsunąłeś mi myśl, że gdy nie mogę skorzystać
    >> z wartości z tablicy transpozycji ze względu na niezgodność widełek
    >> alpha-beta, to skoro już muszę przeliczać ponownie wartość danej
    >> transpozycji to najlepiej by zacząć analizę od ruchu który poprzednio
    >> dał najlepszą wartość. Ale to wymagało zapamiętania w tablicy
    >> transpozycji jeszcze jednej wartości:
    >> 5. najlepszy ruch
    > Tak, to wymaga zapamiętywania najlepszego ruchu i w sortowaniu ta informacja
    > jest najważniejsza. Jeśli ruch pochodzi z TT to jest wykonywany jako pierwszy,
    > a dopiero potem inne techniki sortowania.

    Algorytm z Wiki tego nie robi (i słusznie żeby nie zaciemniać), ale
    odnośniki z Wikipedii wskazują na dokument:
    http://breukerd.home.xs4all.nl/thesis/

    Rozdział 2 podaje właśnie przykład w którym zapamiętywany jest najlepszy
    ruch.

    >> Co obmyślałem, zakodowałem, a uzyskany wynik... Czas obliczeń zmalał o
    >> około 15% :-)
    >> Niby niewiele, ale ziarnko do ziarnka... No ale kosztem rozmiaru tablicy
    >> transpozycji.
    > 15% gdy jako pierwszy wykonujesz ruch z TT? To zobacz co się będzie działo
    > gdy dasz jeszcze pogłębianie - ale niestety musisz opracować heurystykę
    > oceny gdy nie przeszukałeś do końca.

    No to teraz, dla odmiany, gdy już mam poprawnie działający oryginalny
    algorytm, a nie własną radosną twórczość, dodatkowe zapamiętywanie
    najlepszego ruchu daje baaaardzo niewielki zysk...

    >>> Kolejna propozycja: użyj tablicy transpozycji bez alpha-beta. Sprawdź
    >>> czy ilość węzłów w poddrzewie jest identyczna. Jeśli nie będzie
    >>> identyczna, to masz na 100% błąd.
    >>
    >> Yyyy... tu czegoś nie rozumiem...
    > Przeszukuje się pełne drzew gry algorytmem min-max (albo negamax). Zlicza
    > się ilość węzłów, najlepszy ruch i wartość najlepszego ruchu. Potem
    > dodaje się tablicę transpozycji. W tablicy transpozycji zapamiętuje się
    > ilość ruchów w pod-drzewie. Jeśli odzyskuje się układ z TT, to nie
    > przeszukuje się, ale po prostu pobiera się wartość i ilość ruchów w
    > pod-drzewie. Normalnie masz dwie wartości do testów: najlepszy ruch i jego
    > wartość. Gdy zliczysz jeszcze ilość węzłów, to masz wartość trzecią.
    > Zwykle błędy w TT wychodzą gdy właśnie nie zgadza się ilość węzłów.

    Zastosowałem taki test: uzyskałem zgodne wyniki.

    >> Tablica transpozycji dla algorytmu *bez* alpha-beta jest większa niż ta
    >> przy algorytmie *z* alpha-beta.
    > Nie trzeba zapamiętywać wszystkich węzłów w TT, wystarczy zapamiętać tyle, na
    > ile pozwala pamięć komputera i zaimplementować schemat wymiany.

    Korzystam z tego. Pełne pamiętanie było tylko na czas debuggowania problemu.

    >>> Warto te wyniki porównać z
    >>> innym programem na co najmniej 1000 pozycji.
    >>> Tam kilka moich testów do porównania:
    >>> http://brodacz100.republika.pl/perft.htm
    >>
    >> Chętnie porównam, nie mam tylko zielonego pojęcia czym jest
    >> "brodacz100". ;-)
    > Eh, to program do szachów :D

    O programach szachowych lubię sobie od święta poczytać, ale już samo ich
    tworzenie, mimo że intelektualnie pewnie wciąż atrakcyjne, to jednak, od
    1997, problem stał się jakoś mniej pociągający...

    >> Przy częściowej, wybiórczej analizie drzewa gry wynik analizy oczywiście
    >> może zależeć od wielu szczegółów. Przy pełnej analizie drzewa gry
    >> niezgodne wyniki oznaczają... błąd!
    > Tak to jest z ryzykownymi heurystykami. 100 razy pomagają, a za 101 razem
    > powodują błąd.

    Kwestia agresywności tychże heurystyk... ale jednak przy pełnej analizie
    drzewa gry algorytmem alpha-beta błędne heurystyki spowolnią działanie
    algorytmu, ale ostatecznie wynik musi być poprawny.

    >>>> Cały czas też się zastanawiam, czy faktycznie nie wystarczy
    >>>> wspomniana w Wiki flaga, zamiast pełnej informacji alpha, beta.
    >>>> Różne próby robione "na macanta" dają jednak niepoprawne wyniki...
    >>>Wystarczy.
    >> Hmmm... będę miał to do przemyślenia pewnie na niejedną bezsenną noc.
    > Wystarczy znaczy, że ten algorytm działa, o ile nie ma błędów
    > na wiki w metakodzie, albo innych w Twoim programie.

    I tak się właśnie okazało :-/
    Tj. sama flaga w TT wystarczy, algorytm Wiki jest OK, a błąd w moim
    programie.

    pzdr
    mk

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

  • 09.04.16 23:16 M.M.

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: