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.
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.
Spędziłem jeszcze trochę czasu na poszukiwaniach innych opisów
alpha-beta prunning with memorization, ale nic lepszego niż to co w
Wikipedii nie znalazłem.

Próbuję więc samodzielnie przemyśleć problem i w pełni go zrozumieć...
W algorytmie z Wiki w tablicy transpozycji dodatkowo zapisywana jest
flaga, która przyjmuje stany: UPPERBOUND, LOWERBOUND, EXACT.
Moim zdaniem to jednak za mało informacji by móc rozstrzygnąć czy można
taki wpis w przyszłości wykorzystać.
Moim zdaniem trzeba zapisać w tablicy transpozycji parametry alpha
(alphaOrig wg algorytmu Wiki) i beta przy jakich został obliczony wynik
gry dla danej transpozycji.

Zapamiętuję więc dla każdej transpozycji parametry alpha i beta (bardzo
niechętnie bo pożerają pamięć).
Gdy natrafię ponownie na daną transpozycję dokonuję sprawdzenia czy
alpha_current >= alpha_memorized oraz czy beta_current <= beta_memorized.
Z obliczonej uprzednio wartości korzystam tylko wtedy, gdy oba powyższe
warunki są spełnione. No i chyba działa... tj. wyniki zgodne oraz
otrzymałem najszybszą wersję algorytmu.

Pozostają jednak wątpliwości czy nie da się tu czasem czegoś ulepszyć:
np. gdy nie da się użyć wartości z tablicy transpozycji to być może da
się jakoś zmodyfikować parametr alpha lub beta by uzyskać lepszą
wydajność. Algorytm z Wiki ma coś takiego:

if ttEntry.Flag = EXACT
return ttEntry.Value
else if ttEntry.Flag = LOWERBOUND
? := max( ?, ttEntry.Value)
else if ttEntry.Flag = UPPERBOUND
? := min( ?, ttEntry.Value)
endif
if ? >= ?
return ttEntry.Value

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

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?

pzdr
mk

do góry

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.

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

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.

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

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




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


> Spędziłem jeszcze trochę czasu na poszukiwaniach innych opisów
> alpha-beta prunning with memorization, ale nic lepszego niż to co w
> Wikipedii nie znalazłem.
>
> Próbuję więc samodzielnie przemyśleć problem i w pełni go zrozumieć...
> W algorytmie z Wiki w tablicy transpozycji dodatkowo zapisywana jest
> flaga, która przyjmuje stany: UPPERBOUND, LOWERBOUND, EXACT.
> Moim zdaniem to jednak za mało informacji by móc rozstrzygnąć czy można
> taki wpis w przyszłości wykorzystać.
> Moim zdaniem trzeba zapisać w tablicy transpozycji parametry alpha
> (alphaOrig wg algorytmu Wiki) i beta przy jakich został obliczony wynik
> gry dla danej transpozycji.
>
> Zapamiętuję więc dla każdej transpozycji parametry alpha i beta (bardzo
> niechętnie bo pożerają pamięć).
> Gdy natrafię ponownie na daną transpozycję dokonuję sprawdzenia czy
> alpha_current >= alpha_memorized oraz czy beta_current <= beta_memorized.
A depth >= curr_depth?
W wiki jest właśie większy równy:
if ttEntry is valid and ttEntry.depth >= dept



> Z obliczonej uprzednio wartości korzystam tylko wtedy, gdy oba powyższe
> warunki są spełnione. No i chyba działa... tj. wyniki zgodne oraz
> otrzymałem najszybszą wersję algorytmu.
>
> Pozostają jednak wątpliwości czy nie da się tu czasem czegoś ulepszyć:
> np. gdy nie da się użyć wartości z tablicy transpozycji to być może da
> się jakoś zmodyfikować parametr alpha lub beta by uzyskać lepszą
> wydajność. Algorytm z Wiki ma coś takiego:
>
> if ttEntry.Flag = EXACT
> return ttEntry.Value
> else if ttEntry.Flag = LOWERBOUND
> ? := max( ?, ttEntry.Value)
> else if ttEntry.Flag = UPPERBOUND
> ? := min( ?, ttEntry.Value)
> endif
> if ? >= ?
> return ttEntry.Value

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

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




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


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


Pozdrawiam

do góry

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

do góry

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

do góry

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

do góry

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

do góry