On Saturday, April 9, 2016 at 8:47:35 PM UTC+2, mk wrote:
> 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ć :-)

Z tego co sobie przypominam, też miałem wątpliwości co do tego, czy
ten algorytm (albo ten zaproponowany przez Bruce Moreland) musi
dać dokładnie taki sam wynik. Intuicyjnie wydaje się że tak,
nawet że oczywiście tak. Jenak ja osobiście dowodu nie umiem
przeprowadzić. Kiedyś napisałem program, który generował losowe
drzewo, a potem je przeszukiwał różnymi algorytmami. Wszystkie algorytmy,
także i ten z wiki, dawały ten sam wynik. W szachach na pewno miałem z
tym problemy i nie potrafię już sobie przypomnieć, czy ostatecznie
na wszystkich testach był ten sam wynik.


>
> >> 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...
Ok, to już nie będę zadawał niestosownych pytań. A jaki problem
chcesz rozwiązać ? ;-)



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

>
> >> 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.
To podpowiem dwie optymalizacje.

1) Wraz z wpisem przechowujemy jego wiek i głębokość. Wpisy dzielmy na pary,
albo na czwórki, albo generalnie na paczki o rozmiarze N wpisów. Zanim dodamy
wpis, ustalamy wpis najmniej ważny z paczki. Ważność wyliczamy z wieku i
głębokości, im głębszy i młodszy tym lepiej. Z funkcji hash liczymy adres paczki,
a
nie pojedynczego wpisu.

2) Liczymy dwie funkcje hash. Jedna funkcja tylko ustala adres paczki, a drugą
przechowujemy we wpisie. Dwie funkcje hash, można rozumieć jako jedną na
typie np. dwa razy większym.


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

>
> >> 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.
Jest możliwe w każdej tego typu grze. Można w każdej grze choćby zapamiętać
stany na N ruchów przed końcem gry, tzw baza końcówek. Niestety w takich
grach jak 'go' lub reversi baza końcówek byłaby ogromna. Ale jakieś reguły
dla każdej gry można podać, jakieś znamiona że zaraz się wygra/przegra zawsze
są. Bez tego szacowania nie zadziała nie zadziała sortowanie ruchów i
iteracyjne pogłębianie.


>
> >> 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.
Coś chyba jest nie tak...


> >> -- 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.
Ok, po prostu koniec gry. Transpozycja ma trochę inną etymologię,
chodził o oto, że w niektórych grach kolejność ruchów A B C
prowadzi do tego samego stanu gry co C B A.


> >> 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.
Warto warto 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).
Chyba nie zrozumiałem, może jest odwrotnie niż piszesz. Tak czy inaczej,
nie jest to ważne, nigdy jeszcze nie słyszałem o grze, w której nie
byłoby warto zapamiętać ruchu i potem zacząć przeszukiwanie od tego ruchu.

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


>
> >> 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...
Ale nie usuwaj tego. Gdy program wyposażysz w heurystyki, to w końcu
zadziała. Zgaduję, że Twój program w końcu dzięki temu przyspieszy
np. 5 albo 20 razy.

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


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



>
> >>> 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...
Są nowe odmiany, programy samouczące, turnieje programów.


> >> 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.
Ależ nie. Ruchy sortuje się na podstawie jakiś wartości. Im lepszy ruch,
tym jakaś funkcja przypisze mu większą liczbę i zostaną posortowane wg
tych liczb. Jeśli uda Ci się przypisać takie liczby, które spowolnią
program, to wystarczy że potem te liczby weźmiesz ze znakiem ujemnym i
już przyspieszy :)


>
> >>>> 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.
Ok, wyjaśniło się.


Pozdrawiam



>
> pzdr
> mk