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