On Monday, April 4, 2016 at 9:51:13 PM UTC+2, mk wrote:
> 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.
Mnie też jest miło że poruszyłeś ten ciekawy temat, jednocześnie
przepraszam że odpisuję tylko z pamięci.



> W moim problemie chciałbym uzyskiwać wartości dokładne, a nie
> heurystyczne. Przeszukuję pełne drzewo gry (tj. aż nastąpi koniec gry).
Rozumiem, nie wiem czemu pomyślałem, że to gra w szachy :D


>
> > 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.
W szachach to zależało od innych zastosowanych heurystyk. Jeśli
nie stosuje się heurystyk wpływających na wartość evala, to zastosowanie
tablicy transpozycji nie powinno wpływać na rezultat. Ale przypominam sobie,
że w szachach miałem z tym problem. Czy ostatecznie uzyskałem takie same
wartości i ruchy z tablicą transpozycji - nie pamiętam, ale chyba tak.

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



> Swoją drogą jednak nie rozumiem dlaczego *nie* można skorzystać z
> tablicy transpozycji na płytszych poziomach...
Nie można tylko wtedy, gdy chce się uzyskać takie same wyniki jak w
testach bez TT, no i gdy transpozycje mogą występować między
poziomami. Gdy w szachach odzyskuje się gdy
if( curr_depth <= transposition_depth )
to uzyskuje się znacznie silniejszy program.


> 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.
Ok, to mamy z głowy.


>
> > 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...
Tak się nie robi. Zapamiętuje się tylko jeden (potencjalnie) najlepszy
ruch. Nie jest to kosztowne, a przyspieszenie jest ogromne.
To przyspieszenie widać gdy najpierw przeszukuje się na głębokość 1 ruchu,
potem 2 ruchów, itd. Czasami, w niektórych grach, w niektórych programach,
lepszy efekt jest gdy pogłębianie jest o dwa ruchy a nie o jeden.




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



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


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


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


> 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


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


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


> i gracze dowiadują się o wyniku gry, który jest liczbą.
> Celem jednego gracza jest maksymalizacja tej liczby, a drugiego
> minimalizacja.
Hmmmm



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



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


> 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.
Metakod alpha bety ze spamiętywaniem podpowiada że należy to zrobić inaczej.


> 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.
Nie wiem co to za gra, ale raczej należy zastosować pogłębianie, zapamiętać
najlepszy ruch i napisać zgodnie z metacodem.



> 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.
A czas spada?


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



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



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



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

> 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.
Tak, w grze to nie ma sensu, ale w testach mam ogromny sens :)




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




> 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!
Tak to jest z ryzykownymi heurystykami. 100 razy pomagają, a za 101 razem
powodują 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ę.
Właśnie kłopot z tym pewien mam, a w niecie już nie widać tego
pięknego tutoriala :/


> 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.
Powinien działać. Dużo programistów z którymi rozmawiałem, właśnie
przeklepało ten kod. Ja też nie umiem rzucić z rękawa dowodem, że
tamten kod da taki sam wynik jak bez tablicy transpozycji.


> Z drugiej
> strony nie mam dowodu na to, że algorytm z Wiki jest niepoprawny..., ale
> aktualnie bardziej gotowy jestem iść w tą stronę :-)
Porównaj z tą pracą:
http://people.csail.mit.edu/plaat/mtdf.html

Od razu uprzedzam, jakbyś chciał całą teorię zastosować w praktyce, to
okna zerowe rzadko działają i robi sie to inaczej. Bruce to też opisywał
przejrzyściej, mniej teoretycznie, bardziej praktycznie.


>
> > 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.
Były tam kiedyś linki do TT, do okien, null-move, itd. Niestety teraz
to wszystko nie działa, a przejrzystszego opisu nie widziałem.


>
> >> 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. Polecam test z
ilością węzłów w TT - dobry test poprawności TT.


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


Pozdrawiam