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