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-04 21:51:11
    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 14:50, M.M. pisze:
    > On Monday, April 4, 2016 at 2:05:24 PM UTC+2, mk wrote:
    >> Próbuję zaimplementować możliwie efektywnie algorytm rozwiązujący pewien
    >> problem sprowadzający się do gry o sumie stałej pomiędzy dwoma
    >> przeciwnikami.
    >>
    >> W pierwszym kroku zaimplementowałem algorytm min-max (w postaci negamax).
    >>
    >> W moim problemie do danego stanu gry (transpozycji) można dojść czasami
    >> na wiele różnych sposobów więc by przyśpieszyć działanie algorytmu
    >> zastosowałem "memoryzację" czyli zapamiętuję już przeanalizowane stany
    >> gry (transpozycje) i wykorzystuję taki wpis jeśli ponownie natrafię na
    >> wcześniej przeanalizowaną transpozycję. Obliczenia znacząco
    >> przyśpieszyły, wyniki zgodne, jak dotąd dobrze...
    >>
    >> Obok, wzbogaciłem też algorytm negamax (bez memoryzacji) o alpha-beta
    >> prunning. No i też OK: obliczenia przyśpieszyły, wyniki zgodne, jak
    >> dotąd dobrze...
    >>
    >> Dalej, chcę połączyć alpha-beta prunning z memoryzacją... Zaświtało mi w
    >> głowie, że to będzie bardziej skomplikowane niż na początku by się mogło
    >> wydawać... ale od czego Internet, poszukajmy jak zrobili to inni i
    >> natrafiłem na artykuł Wikipedii:
    >> https://en.wikipedia.org/wiki/Negamax#Negamax_with_a
    lpha_beta_pruning_and_transposition_tables
    >>
    >> Zaimplementowałem u siebie algorytm przedstawiony w Wikipedii i niestety
    >> zacząłem otrzymywać wyniki niezgodne z trzema uprzednio przedstawionymi
    >> metodami.
    >
    > Też z tym miałem problemy. Nie pamiętam już czy dla wszystkich pozycji
    > otrzymałem ten sam wynik. U mnie czasami wersja z błędem grała lepiej, więc
    > się aż tak bardzo nie przejmowałem.

    Zacznę od podziękowania za zainteresowanie moim tematem i poświęcony czas.

    W moim problemie chciałbym uzyskiwać wartości dokładne, a nie
    heurystyczne. Przeszukuję pełne drzewo gry (tj. aż nastąpi koniec gry).

    > Najpierw zwróć uwagę na to co jest niezgodne: najlepszy ruch, wartość dla
    najlepszego ruchu, czy jeszcze coś innego?

    W ogólności niezgodne są najlepszy ruch oraz wartość najlepszego ruchu.
    Nie są to wartości odległe, czasami się nawet zgadzają, ale to raczej
    kwestia przypadku.

    >
    > Jak odzyskujesz układy z tablicy transpozycji? Czy wtedy gdy depth>=curr_depth,
    > czy wtedy gdy depgh==curr_depth ? Wartość zgodna z poprzednimi testami
    > może być tylko dla drugiej wersji.

    Akurat w moim problemie takie same transpozycje mogą wystąpić tylko na
    tej samej głębokości, więc nie sprawdzam wcale warunku głębokości.
    Sytuacja podobna jak w grze "kółko i krzyżyk".

    Swoją drogą jednak nie rozumiem dlaczego *nie* można skorzystać z
    tablicy transpozycji na płytszych poziomach... muszę też to przemyśleć
    (mam pewne intuicje dlaczego), chętnie zapoznałbym się z wyjaśnieniem,
    ale jak napisałem: warunek głębokości nie dotyczy mojego problemu.

    > Mogę zaproponować jeszcze jeden pośredni test, który mi pomagał. Otóż,
    > w pierwszych próbach, można użyć tablicy transpozycji tylko do
    > sortowania ruchów. W zależności od tego jak (poza tą techniką)
    > sortujesz ruchy i czy używasz iteracyjnego pogłębiania, powinno
    > znacznie albo bardzo znacznie przyspieszyć.

    Ale musiałbym w każdym wpisie tablicy transpozycji przechowywać
    kolejność ruchów jakie mam wykonać... trochę kosztowne...

    W moim problemie nie używam iteracyjnego pogłębiania, a po postu:
    https://en.wikipedia.org/wiki/Depth-first_search

    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, 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, ale docelowo chcę jednak użyć tablicy
    transpozycji zaimplementowanej jako hash table i ma ona działać jako
    rodzaj cache, przy czym strategia zwolnienia miejsca na nowy wpis to:
    "wybór losowy" (co zapewnia funkcja hashująca). Mam już to
    zaimplementowane i początkowo nawet przypuszczałem, że właśnie owa
    "wybiórcza" memoryzacja jest problemem, ale nie...
    2. Sortowanie ruchów ma sens tylko jak jesteśmy w stanie dokonać jakieś
    heurystyczne oszacowania co do wartości poszczególnych ruchów. W moim
    problemie wynik da się prawdopodobnie dopiero obliczyć na końcu "gry".
    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! -- następują obliczenia oparte o finalną
    transpozycję i gracze dowiadują się o wyniku gry, który jest liczbą.
    Celem jednego gracza jest maksymalizacja tej liczby, a drugiego
    minimalizacja.

    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".

    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.
    Jestem również przekonany, że jeśli bieżące widełki alpha-beta obejmują
    w całości widełki alpha-beta z tablicy transpozycji to obliczenia trzeba
    wykonać ponownie. Zastanawiam się tylko nad sytuacją gdy widełki bieżące
    i te z tablicy transpozycji częściowo się pokrywają -- czy nie da się tu
    czegoś poczarować... teraz odrzucam taki wpis jako nienadający się do
    użycia.

    Jeszcze wrócę do sortowania ruchów. Użycie tablicy transpozycji tylko do
    posortowania ruchów pewnie by i u mnie bez problemu działało. Wykonałem
    sobie taki test, że analizuję ruchy w losowej kolejności i algorytm
    alpha-beta (bez tablicy transpozycji) daje mi zawsze jednakowy i
    poprawny wynik.

    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

    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.

    > 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...
    Tablica transpozycji dla algorytmu *bez* alpha-beta jest większa niż ta
    przy algorytmie *z* alpha-beta. Wcale się temu nie dziwię i tego
    oczekuję po "przycinaniu" alpha-beta: wszak przerywamy analizę, gdy
    bieżący gracz osiąga wynik na który nie zgodzi się przeciwnik (gdyż ma w
    dyspozycji lepszy ruch na którymś z wyższych poziomów) tj. gdy alpha >=
    beta.

    > 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". ;-)

    U mnie (zmniejszona do testów) gra ma < 10 mln transpozycji.

    >> W dyskusji dotyczącej artykułu jedna z osób narzeka, że i u niej
    >> algorytm z Wikipedii nie działa, inna osoba jednak kontruje, że algorytm
    >> jest na pewno poprawny, a wina jest po stronie niewłaściwego
    >> zaimplementowania tegoż algorytmu.
    > Wszystko zależy od pozostałych algorytmów. Inaczej będzie z pogłębieniami,
    > inaczej z qsearch, a już zupełna masakra z null-move...

    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!

    > Używam ciut innej implementacji i ciut innego algorytmu niż na wiki.
    > Moja działała minimalnie szybciej i przeszukiwała minimalnie mniej węzłów
    > (lepiej obcinała). Niestety nie mam pod ręką metakodu, jeśli znajdę,
    > to podrzucę.

    Jeśli bez zbędnego kłopotu się znajdzie, to chętnie wypróbuję.

    Nie ukrywam, że i chciałbym rozumieć jak to działa, np. ten z Wiki.
    Póki rozumiem co się dzieje w moim programie, to wyniki mam poprawne.
    Ten z Wiki przeklepałem trochę jak małpa... i nie działa. Z drugiej
    strony nie mam dowodu na to, że algorytm z Wiki jest niepoprawny..., ale
    aktualnie bardziej gotowy jestem iść w tą stronę :-)

    > Opieram się na metakodzie który udostępnił kiedyś w sieci ten autor:
    > https://chessprogramming.wikispaces.com/Bruce+Morela
    nd
    > Niestety samego metakodu już nie mogę znaleźć.
    >
    > Widać tylko kod samej alpha-bety:
    > https://cs.marlboro.edu/code/perl/TicTacToe/bruce-mo
    reland/alphabeta.html

    Z czystą alpha-beta nie mam problemów.
    Ale dzięki za link, może coś na tej stronie wygrzebię dla siebie.

    >> 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.

    >> Jak powinien wyglądać algorytm alpha beta prunning z memoryzacją?
    >> Może jednak ten z Wiki jest dobry, a ja popełniam błąd w implementacji?
    > Ten na wiki (chyba) jest poprawny, aczkolwiek Bruce Moreland podał
    > znacznie bardziej zwartą i czytelną wersję, a poza tym, u mnie
    > obcinała ona więcej węzłów.

    Dziękuję za namiary -- spróbuję pogooglać.

    pzdr
    mk

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

  • 04.04.16 23:51 M.M.
  • 09.04.16 20:47 mk
  • 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: