To co? Bawimy się? :D

[mariotti]

Hej

Przygotowałem wersję programu do przeszukiwania drzewa gry w szachach. Zadaniem
program jest zliczenie ile jest liści w pełnym drzewku na określoną głębokość Program
został wyposażony w 4 różne algorytmy. Piąta wersja będzie zoptymalizowana, szósta
wersja będzie na BOINC - ale to pod warunkiem że ktoś baaaaardzo mi pomoże
przedrzeć się przez konfigurację.

Program można uruchomić tak po prostu i sprawdzić ile jest węzłów w drzewku - to
pierwszy algorytm.

Drugi algorytm umożliwia wykorzystanie ogromnej pamięci - można zobaczyć
jakie uzyskuje się dzięki temu przyspieszenie.

Trzeci algorytm uruchamia się w wątkach - ilość wątków podaje się jako parametr.

Czwarty algorytm nie dość że uruchamia się w wątkach, to jeszcze umie wykorzystać
ogromną ilość pamięci.

Program przez długi czas będzie w wersji tylko na linux64 bity, potem może będzie
na inne systemy. W początkowym okresie będzie udostępniany tylko w wersji
binarnej, za dłuższy czas udostępnię także źródła.

Do wątków została użyta biblioteka boost::thread - można przypuszczać, że ta
biblioteka korzysta z tych samych mechanizmów na poziomie systemu co OpenMP.

Pierwsze pytanie do Was, ilu jest chętnych do przetestowania programu tak
po prostu na jednym komputerze, a ilu jest chętnych do odpalenia go na
jakimś klastrze? Program na razie nie wspomaga żadnego MPI ani BOINC, ale
podobno można tak skonfigurować klaster, żeby wykonał się na wielu
maszynach. Ciekawy jestem jakie byłyby wyniki na klastrze.

W drugim kroku, jeśli będą chętni do pomocy przy konfigurowaniu BOINC,
przejdziemy do obliczeń w tej sieci. Problem przeszukiwania drzewa gry
jest wykładniczy. Na moim kompie (6 rdzeni) najlepszy algorytm z
najlepszymi parametrami potrzebował 2315 sekund aby przejrzeć drzewko
na głębokość 9 ruchów. Znalazł w nim 2439530234167 liści.  Pewnie w
przeciągu doby zejdzie do 10 ruchów, a w miesiąc do 11 ruchów. Po
optymalizacji, w jeden miesiąc może będzie dochodził do 12 ruchów.
Jakbyśmy użyli 30 komputerów to po miesiącu osiągniemy 13 ruchów - tak
można przypuszczać :)

Jak widać na tej stronice:
http://oeis.org/A048987/list

Ktoś do 13 ruchów już doszedł :) Więc jakbyśmy chcieli bić rekord, to
byśmy musieli zejść do 15-16 ruchów :) Ciekawy jestem czy będą
zainteresowani, zwłaszcza że są poważne rzeczy do obliczenia, a to
tylko zabawa.

Jak będą zainteresowani, to w następnym poście opiszę jak używać
programu :)


Pozdrawiam!

[krzyszp]

Próbowałem odpalić, ale na moim ubu woła o bibliotekę  libboost_thread.so.1.46.1... Doinstalowanie libboost-thread-dev nie pomogło, a chętnie bym potestował na 4 rdzeniach (niestety, RAMu tylko 4GB).

Edit:
Mogę też w wirtualce spróbować na 8 wątkach (Xeon e-3 1230)

[Karlik]

Z tego co napisał krzyszp wynika, że kompilowałeś dynamicznie a nie statycznie. Proponuję albo wrzucić źródła (z makefile'm) albo skompilować statycznie ;)

[RAD-Poland]

dlaczego libboost_thread.so.1.46.1
to stara wersja z 2011 i jeśli akurat jej potrzebujesz skompiluj statycznie

w systemie mam domyślnie 1.52 i 1.53
ale doinstalowałem 1.46.1

po uruchomieniu ./perft nic nie robi, nie obciąża CPU mimo wolnych rdzeni (Xeon E3 1230), nic nie wypisuje w konsoli, nie reaguje też na parametr --help
opisz jak powinna się zachowywać app i ewentualnie z jakimi parametrami uruchamiać

Edit:
po uwzględnieniu n/w komend app działa :)

Kod [Zaznacz] Rozwiń

perft 1
nodes:20 time:0
perft 2
nodes:400 time:0
perft 3
nodes:8902 time:0
perft 4
nodes:197281 time:0
perft 5
nodes:4865609 time:0
perft 6
nodes:119060324 time:20
6 już chwilkę trwało

[Troll81]

projekt ciekawy o ile stanie na nogi :D

[mariotti]

Próbowałem odpalić, ale na moim ubu woła o bibliotekę  libboost_thread.so.1.46.1... Doinstalowanie libboost-thread-dev nie pomogło, a chętnie bym potestował na 4 rdzeniach (niestety, RAMu tylko 4GB).

Dzięki za zainteresowanie !
Na swoich komputerach kopiuję po prostu do /usr/lib/ i działa.
Załączam do posta moją bibliotekę i lekko ulepszony program.
Mam nadzieje że tym razem zadziała, a jak nie, to problem jakoś
się rozwiąże.


A skoro są zainteresowani, to opiszę niektóre komendy:

Uruchamiamy z linii polecenia z bieżącego katalogu bez żadnych
parametrów:
./perft


podstawowe polecenie jest takie samo jak nazwa programu:
perft depth
gdzie depth to głębokość przeszukiwania.
Przykład:
./perft
perft 1         
nodes:20 time:0
perf 2
unknown command: perf
perft 3
nodes:8902 time:0
perft 4
nodes:197281 time:0
perft 5
pnodes:4865609 time:1
perft 6
nodes:119060324 time:20
quit
----------------------------------------------------------------
kolejne polecenie umie wykorzystać dodatkową pamięć:
memPerft depth mem_size mem_probe
depth - głębokość przeszukiwania
mem_size - ilość spamiętanych układów, jeden układ wymaga około 20bajtów pamięci
mem_probe - parametr do zarządzania pamięcią, optymalna wartość zwykle mieści się w przedziale od 2 do 16

Przykład:
./perft
memperft
using: memPerft depth mem_size mem_probe
memPerft 1 100000 4
nodes:20 time:0
memPerft 2 10000 4
nodes:400 time:0
memPerft 3 100000 4
nodes:8902 time:0
memPerft 4 100000 4
nodes:197281 time:0
memPerft 5 100000 4
nodes:4865609 time:0
memPerft 6 100000 4
nodes:119060324 time:6
memPerft 6 100000 8
nodes:119060324 time:6
quit

----------------------------------------------------------------
Kolejne polecenie działa na wątkach:
threadPerft depth max_thread
depth - tak samo jak poprzednio: głębokość przeszukiwania
max_thread - maksymalna ilość wątków

Przykład:
./perft
threadPerft
using: threadPerft depth max_thread
threadPerft 1 4
nodes:20 time:0
threadPerft 2 4
nodes:400 time:0
threadPerft 3 4
nodes:8902 time:0
threadPerft 4 4
nodes:197281 time:0
threadPerft 5 4
nodes:4865609 time:0
threadPerft 6 4
nodes:119060324 time:12
quit

----------------------------------------------------------------
Ostatnie polecenie z tej serii wykorzystuje wątki i pamięć.
threadMemPerft depth max_thread mem_size mem_probe forget
depth - głębokość przeszukiwania
max_thread - maksymalna ilość wątków
mem_size - ilość zapamiętanych układów (jeden układ około 20bajtów)
mem_probe - zarządzanie pamięcią, najlepsza wartość zwykle w przedziale od 2 do 16.
forget - dodatkowy parametr do zarządzania pamięcią, dobra wartość zwykle mieści się w przedziale od tysiąca do miliona.

Przykład użycia
./perft
threadMemPerft
using: threadMemPerft depth max_thread mem_size mem_probe forget
threadMemPerft 1 2 100000 4 0
nodes:20 time:0
threadMemPerft 2 2 100000 4 0
nodes:400 time:0
threadMemPerft 3 2 100000 4 0
nodes:8902 time:0
threadMemPerft 4 2 100000 4 0
nodes:197281 time:0
threadMemPerft 5 2 100000 4 0
nodes:4865609 time:1
threadMemPerft 6 2 100000 4 0
nodes:119060324 time:4
threadMemPerft 7 2 100000 4 0
nodes:3195901860 time:115
threadMemPerft 7 2 1000000 4 0
nodes:3195901860 time:58
threadMemPerft 7 2 10000000 4 0
nodes:3195901860 time:36
threadMemPerft 7 3 10000000 4 0
nodes:3195901860 time:31
threadMemPerft 7 4 10000000 4 0
nodes:3195901860 time:28
quit

------------------------------------------------------------------
Program ma dodatkową komendę setboard. Aby jej używać, najpierw
najlepiej zainstalować program xboard. Xboard to środowisko graficzne
w którym możemy na planszy szachowej poukładać figury. Następnie
układ z szachownicy można przekopiować do schowka i wkleić go
do konsoli programu perft. Tym samym można przeszukać drzewko
dla dowolnego (poprawnego) układu, a nie tylko dla układu startowego.

Przykład użycia:
./perft
setBoard rn3rk1/ppp3pp/4bq2/2b1Np2/2B2P2/8/PPP1Q1PP/R1B1K2R w KQ - 0 1
perft 1
nodes:40 time:0
perft 2
nodes:1480 time:0
perft 3
nodes:56293 time:0
perft 4
nodes:2141911 time:0
memPerft
using: memPerft depth mem_size mem_probe
memPerft 4 10000 4
nodes:2141911 time:1
quit

------------------------------------------------------------------
Program ma wkompilowne 1001 układów. Można go hurtowo
przetestować na tym całym zestawie. Aby to zrobić, przed
komendami trzeba wpisać przedrostek multi, a potem
składnia poleceń jest taka sama.

Przykład:
./perft
multiPerft 2
quit

Jak coś niezrozumiałe, to piszcie.
Pozdrawiam

[mariotti]

projekt ciekawy o ile stanie na nogi :D

To tylko zliczanie węzłów, to (być może) przedsmak czegoś znacznie lepszego.
Niemniej pobawić się można tym programem.  Jak będzie zainteresowanie, to z Waszym wsparciem
może stanąć na nogi :)
Pozdrawiam

[patyczak]

U mnie program działa na Ubuntu 12.XX 64bit po zainstalowaniu biblioteki  :) Muszę tylko jeszcze rozszyfrować co on dokładnie robi i jakie dane zwraca  :D

[mariotti]

U mnie program działa na Ubuntu 12.XX 64bit po zainstalowaniu biblioteki  :) Muszę tylko jeszcze rozszyfrować co on dokładnie robi i jakie dane zwraca  :D

Program bada "złożoność szachów". Umie przyspieszyć obliczenia dzięki użyciu wielu
rdzeni i/albo dużej pamięci. Można wpisać np.:

./perft
perft 6
nodes:119060324 time:19
threadPerft 6 4
nodes:119060324 time:10
quit

I widać że w 4 wątkach (na kompie który ma 2 fizyczne rdzenie) program działa
dwa razy szybciej, a podaje taki sam wynik: nodes: 119060324

Przy pomyślnych wiatrach przerobimy go tak, aby umiał jeszcze wykorzystać BOINC ;-)

Pozdrawiam

[patyczak]

To wyjaśnij jeszcze laikowi szachowemu co to jest "złożoność szachów"? Ilość możliwych rozgrywek od określonego ustawienia figur?

[mariotti]

To wyjaśnij jeszcze laikowi szachowemu co to jest "złożoność szachów"? Ilość możliwych rozgrywek od określonego ustawienia figur?

Raczej nie ma takiego pojęcia, napisałem je tak sobie, żeby właśnie nie wdawać się w szczegóły :)

Ściśle chodzi o procedurę która ma nazwę perft. Etymologia to: perfection test.

Bardzo trudno jest napisać program szachowy. Programiści szukając ułatwienia wymyślili właśnie
perft. Perft polega na przeszukaniu drzewa gry na zadaną głębokość i policzeniu ile drzewo ma
liści. Perft szuka prawie zgodnie z zasadami szachowymi - nie wiem czemu nie robi tego zgodnie w
100%.  Perft nie uwzględnia reguły 50ciu posunięć i reguły trzykrotnego powtórzenia - nie pytajcie
mnie dlaczego tak jest - tak się z jakiś powodów przyjęło, a ja nie chciałem się wyłamywać.

No... to chyba wszystko :)

Pozdrawiam

[Rysiu]

Niestety. Mam problem z bibliotekami. Dasz radę skompilować z opcją -static ?

[mariotti]

Niestety. Mam problem z bibliotekami. Dasz radę skompilować z opcją -static ?

Może się udało, trzeba sprawdzić. Program jest większy, więc na pewno coś dodał :D
U mnie działa na dwóch różnych kompach, mam nadzieję że u Was też zadziała.
Pozdrawiam

[krzyszp]

Niestety. Mam problem z bibliotekami. Dasz radę skompilować z opcją -static ?

Rysiu, przekopiuj tę bibliotekę do /usr/lib i działa :)
Odpaliłem "threadperft 16 4" - zobaczymy, ile zejdzie :)

[mariotti]

Odpaliłem "threadperft 16 4" - zobaczymy, ile zejdzie :)

depth = 16 to dużo za dużo :)

Na początek lepiej spróbować:
threadPerft 8 4

Karkołomne może już być
threadPerft 10 4

Ta druga liczba (tutaj 4) to ilość wątków. Zwykle najlepiej jest dać 1-2 wątki więcej niż
ilość fizycznych rdzeni.

Pozdrawiam

[Rysiu]

Może się udało,

Udało się  :p_arr:

threadperft 2 8
nodes:400 time:0
threadperft 3 8
nodes:8902 time:0
threadperft 4 8
nodes:197281 time:0
threadperft 5 8
nodes:4865609 time:0
threadperft 6 8
nodes:119060324 time:3
threadperft 7 8
nodes:3195901860 time:91
threadMemPerft 7 8 10000000 4 0   
nodes:3195901860 time:9

Rysiu, przekopiuj tę bibliotekę do /usr/lib i działa :)

Próbowałem ale brakowało innej biblioteki niż ta załączona.

Odpaliłem "threadperft 16 4" - zobaczymy, ile zejdzie :)

Setki jak nie tysiące lat  :ph34r:

[krzyszp]

Odpaliłem to na serwerze z Q6600, więc mam 4 fizyczne rdzenie, a że komp nigdy nie wyłączany/resetowany - to niech pracuje :) (chyba, że ma to rok potrwać...)

[Rysiu]

Krzyszp to może zająć nawet dziesiątki tysięcy lat. Do tego czasu nie jest pewne czy gatunek ludzki przetrwa, a Ty piszesz, że komputer nie jest restartowany  :deadman:

[krzyszp]

Krzyszp to może zająć nawet dziesiątki tysięcy lat. Do tego czasu nie jest pewne czy gatunek ludzki przetrwa, a Ty piszesz, że komputer nie jest restartowany  :deadman:

Uuuups, liczyłem na max kilka miesięcy :)
No, to jednak przerywam :)

[mariotti]

Odpaliłem to na serwerze z Q6600, więc mam 4 fizyczne rdzenie, a że komp nigdy nie wyłączany/resetowany - to niech pracuje :) (chyba, że ma to rok potrwać...)

Raczej 100 milionów lat :)

Odpal na głębokość 10 wersję z pamięcią :) Wersja z pamięcią baaardzo przyspiesza, może 100-1000 razy.
Właśnie u siebie sprawdzam ile będzie się to liczyło.

Składnia polecenia:
threadMemPerft depth max_thread mem_size mem_probe forget

Przykład dla 2GB ram i 5-ciu wątków (5 wątków działa szybciej niż 4, nawet gdy są 4 rdzenie)
threadMemPerft 10 5 100000000 4 0

Przykład dla 1GB ram:
threadMemPerft 10 5 50000000 4 0

To powinno się policzyć w jakieś... nie wiem... 12-72h, strzelam że w 20h się policzy.

Pozdrawiam

[Rysiu]

To powinno się policzyć w jakieś... nie wiem... 12-72h, strzelam że w 20h się policzy.

W 20h to nie bo Krzyszp pewnie dodaje dane klimatyczne na serwerze i jakiś dodatkowy load ma  %)

@Mariotti te 100 milionów lat to jakoś oszacowałeś czy z głowy?

[mariotti]

@Mariotti te 100 milionów lat to jakoś oszacowałeś czy z głowy?

Jeśli komputer Q6600 jest dwa razy szybszy od mojego i współczynnik rozgałęzienia
wynosi 30 to 73mln lat. Jeśli Q6600 jest tak samo szybki jak mój i w.r. wynosi 25 to
28mln lat.

Moze 50mln jest dokładniejszym oszacowaniem niż 100mln :)

Natomiast wersja z pamięcią (mogę się bardzo mylić, tutaj szacowanie jest dużo trudniejsze)
w jakieś 500-1000 lat by dała radę, czyli rok na 1tys maszyn. Z tego co pobieżnie
zdążyłem się zorientować, obecny rekord wynosi 13, czyli 16 by przełamało tę barierę aż o 3 poziomy!

Pozdrawiam

[krzyszp]

Czyli generalnie, walka toczy się o "14"???
Bo jeśli tak, i jeżeli możesz zrównoleglić aplikację, to BOINC aż się prosi o to :)

Edit:
Odpaliłem  threadMemPerft 10 5 100000000 4 0, zobaczymy, jaki będzie czas...

[mariotti]

Czyli generalnie, walka toczy się o "14"???

O ile się nie mylę, to tak. Wdziałem z wielu źródeł wyniki dla depth=12. Z raptem dwóch
źródeł dla depth=13. Dla 14 nie widziałem, ale nie powiedziane, że widziałem wszystko :)

Bo jeśli tak, i jeżeli możesz zrównoleglić aplikację, to BOINC aż się prosi o to :)

Spróbujemy. Jeśli rzucać się na BOINC, to wersja z pamięcią i od razu można
na kilka głębokości, np. na wszystkie od 10 do 20. Pytanie dlaczego rzucać się na
głębokości powyżej 16, jeśli to wymaga tak ogromnej mocy obliczeniowej? Odpowiedź
jest taka, że poza dokładnym obliczeniem, robi się także oszacowania. Zanim policzymy
dokładnie dla depth>15, to będziemy mieli policzone częściowo,  np. 0.1% całości.  Wtedy
można to co już policzone wymnożyć razy 1000 i podawać z dania na dzień dokładniejsze
oszacowania. Dla mniejszych głębokości (może dla depth<=16) w końcu się uzyska dokładny
wynik, a dla większych oszacowania też będą cieszyły. Koncepcyjnie jest to proste, w
realizacji... no cóż... wymaga dużo czasu.


Projekt jest prosty i zabawowy, ale w środowisku szachowym może wywoływać emocje :)

Odpaliłem  threadMemPerft 10 5 100000000 4 0, zobaczymy, jaki będzie czas...

Ja odpaliłem na Phenom II 6 rdzeni:
threadMemPerft 10 8 250000000 8 1000000
Porównamy jutro(?) wyniki :D

Pozdrawiam

[krzyszp]

Wszystko pięknie, ale nie uwzględniłem jednego drobiazgu...

Otóż program odpaliłem w konsoli SSH, ale z powodu Einsteina musiałem swojego hosta zrestartować (ale Twój program na serwerze cały czas działa)... Pytanie - czy on zapisuje gdzieś wyniki? Jak nie, to ubiję go i odpalę normalnie (tzn, podczepię monitor i klawiaturę i odpalę lokalnie).

Edit:

Ok, odpaliłem jeszcze raz...

[mariotti]

Ok, odpaliłem jeszcze raz...

Jedyny sposób na zapisywanie to dodatkowy skrypt, np. taki:

#!/bin/sh
(
echo threadMemPerft 1  5 100000000 4 0
echo threadMemPerft 2  5 100000000 4 0
echo threadMemPerft 3  5 100000000 4 0
echo threadMemPerft 4  5 100000000 4 0
echo threadMemPerft 5  5 100000000 4 0
echo threadMemPerft 6  5 100000000 4 0
echo threadMemPerft 7  5 100000000 4 0
echo threadMemPerft 8  5 100000000 4 0
echo threadMemPerft 9  5 100000000 4 0
echo threadMemPerft 10 5 100000000 4 0
echo quit
) | ./perft >> out.txt

[Argento]

A ja po ./perft otrzymuję komunikat <i>command not found</i>...  :o

[mariotti]

Ok, odpaliłem jeszcze raz...

Ciekawy jestem jaki masz wynik i czy program się już zakończył :)
U mnie się zakończył, ale podał błędny wynik :)

Poprawny wynik dla głębokości 10 to 69352859712417
U mnie jest: 69352859710032 i czas 63547 sekund.

Program ma dwie heurystyki, czyli coś co zwykle działa, ale nie gwarantuje
poprawnego wyniku. Muszę sprawdzić czy błędny wynik jest zwyczajnie z
powodu błędu w programie, czy te heurystyki zbyt szybko zawiodły.

Jeśli u Ciebie będzie inny wynik niż u mnie, to mamy prawie pewność, że
heurystyki nie zadziałały. Będę musiał je jakoś "wzmocnić".

Pozdrawiam

[mariotti]

A ja po ./perft otrzymuję komunikat <i>command not found</i>...  :o

Trzeba zrobić dwie rzeczy:
1) zmienić katalog bieżący na ten do którego się przekopiowało program
2) wydać komendę chmod 500 perft
potem powinno działać.

Pozdrawiam

[krzyszp]

U mnie nadal chodzi, ale jak Rysiu zauważył, komp jest dość mocno obciążony zazwyczaj, więc wynik może być później.

[Argento]

wydać komendę chmod 500 perft

Zapomniałem... :bad:
A teraz sytuacja jak u RAD-Poland, czyli żadnej reakcji na ./perft. Tak z paramterami jak i bez...

[Dario666]

Na podstawie waszych wyników zbudowałem prostą funkcję aproksymującą i takie są wyniki:

(pierwsza kolumna to głąbokość analizy, 4 kolejne to średni czas obliczeń dla trybu najprostszego, kolumna mem_mod to czas obliczeń dla trybu z pamięcią)

Kod [Zaznacz] Rozwiń

1          sek                      godz                 dni                lat              (mem mod) lat
2         0                          0                    0                  0                      0
3         0                          0                    0                  0                      0
4         0                          0                    0                  0                      0
5         1                          0                    0                  0                      0
6         20                         0                    0                  0                      0
7         529                        0                    0                  0                      0
8         14 285                     4                    0                  0                      0
9         399 975                    111                  5                  0                      0
10        11 599 272                 3 222                134                0                      0
11        347 978 166                96 661               4 028              11                     0
12        10 787 323 140             2 996 479            124 853            342                    9
13        345 194 340 466            95 887 317           3 995 305          10 939               273
14        11 391 413 235 378         3 164 281 454        131 845 061        360 972            9 024
15        387 308 050 002 837        107 585 569 445      4 482 732 060      12 273 051       306 826
16        13 555 781 750 099 300     3 765 494 930 583    156 895 622 108    429 556 802   10 738 920

Teraz widać dlaczego nikt nie policzył do 16  ;D.

Ostatnia kolumna jest prostym założeniem, wynikającym z podanych przez was wyników, że w trybie z pamięcią obliczenia są wykonywane 40 razy szybciej (patrząc na 1 wątek)

Przy "13" jeszcze idzie policzyć w realnym czasie, ale już "14" to niezła orka.

Przyjmijmy, że wydajność jednego rdzenia to średnio 6000 MIPSów, więc by przeliczyć "14" trzeba wykonać około 1700 kwintylionów FLOPów (licząc jednostki jak amerykanie). To jest, tak dla porównania, około 2 miliardów kredytów w PrimeGrid'zie. Cały zespół B@P ma mniej więcej tyle, a pewnie lwia część tego to projekty liczone na GPU.

[mariotti]

wydać komendę chmod 500 perft

Zapomniałem... :bad:
A teraz sytuacja jak u RAD-Poland, czyli żadnej reakcji na ./perft. Tak z paramterami jak i bez...

Instrukcja i przykłady w moim drugim poście tego wątku :)
Uruchamiamy program i potem wpisujemy komendy.

-------------------------------------------------------------------------------------------------------------------------
Jeśli możesz obliczenia zostawić na dłuży czas ( rzędu 20-60h - zależnie od
szybkości komputera ) to teraz najbardziej potrzebny jest jeden określony
test. A mianowicie trzeba wpisać taki skrypt:

#!/bin/sh
(
echo threadMemPerft 1  5 100000000 4 0
echo threadMemPerft 2  5 100000000 4 0
echo threadMemPerft 3  5 100000000 4 0
echo threadMemPerft 4  5 100000000 4 0
echo threadMemPerft 5  5 100000000 4 0
echo threadMemPerft 6  5 100000000 4 0
echo threadMemPerft 7  5 100000000 4 0
echo threadMemPerft 8  5 100000000 4 0
echo threadMemPerft 9  5 100000000 4 0
echo threadMemPerft 10 5 100000000 4 0
echo quit
) | ./perft >> out.txt

Skrypt można nazwać go.sh. Skryptowi też nadajemy:

chmod 500 go.sh

i uruchamiamy
./go.sh

Potem wynik będą w pliku out.txt


--------------------------------------------------------------------------------------------------------------
Tuning

Jeśli komputer ma 6 rdzeni, to warto jako drugi parametr podać
liczbę 8 (zamiast 5).

Jeśli komputer ma 1GB wolnej pamięci to jak trzeci parametr podajemy
liczbę 50000000 (50 milionów).

Jeśli komputer ma 2GB wolnej pamięci to jak trzeci parametr podajemy
liczbę 100000000 (100 milionów).

Jeśli komputer ma 4GB wolnej pamięci to jak trzeci parametr podajemy
liczbę 200000000 (200 milionów).


---------------------------------------------------------------------------------------------------
PS.

Na moim komputerze program podał wynik z małym błędem. Muszę znaleźć
przyczynę. Potencjalnie są...  cztery przyczyny:
1) błąd sprzętu - wczoraj rano komputer włączył się i nie widział jednej kości ram, musiałem
    wyjąć kości i włożyć na nowo.
2) zwyczajny błąd w kodzie
3) zbyt mała losowość funkcji skrótu (w celu przyspieszenia zapamiętuję tylko funkcję  skrótu a nie cały układ)
4) za słaba CRC - nie używam blokad na dostęp do pamięci, gdyż to bardzo spowalnia. zamiast
   blokad używam crc - jeśli jeden wątek popsuje dane drugiemu wątkowi, to crc powinna się nie zgadzać.

Wyniki na Waszych komputerach trochę pomogą mi ustalić co jest przyczyną błędu. Jeśli wszędzie
będzie dobry wynik, a u mnie zły to będzie wskazywało że mój komputer się rozwalił. Jeśli wszędzie
będą inne wyniki, to będzie wskazywało że mam za słabą funkcję skrótu albo za słaby crc. Jeśli wszędzie
będą takie same (ale błędne) wyniki, to prawdopodobnie mam błąd w kodzie.

Pozdrawiam

[mariotti]

Ostatnia kolumna jest prostym założeniem, wynikającym z podanych przez was wyników, że w trybie z pamięcią obliczenia są wykonywane 40 razy szybciej (patrząc na 1 wątek)

Wyedtyowałem ten post, bo w świetle nowych wyników nie miał on najmniejszego sensu.
Całkiem przyzwoita funkcja aproksymująca to:
time = 400 * A ^ (depth-2)
Dla algorytmu bez pamięci A wynosi prawdopodobnie 25
Dla algorytmu z pamięcią A wynosi prawdopodobnie 11
Gdy pamięci jest mało, to A przyjmuje wartość z przedziału 11-25.
Pozdrawiam

[Rysiu]

Ja liczę do 10 na Core i7 950 i 24 GB RAM. Program zaalokował ponad 22 GB pamięci.

Głębokość 8 obliczył w 106 sekund. Całkiem niezły wynik mi się wydaje. Wszystkie dotychczasowe wyniki zgadzają się z tymi w bazie oeis.org.

---- EDIT:

Obliczył właśnie do głębokości 9. Trwało to 1160 sekund. Wynik zgodny z oeis.org.

[mariotti]

Ja liczę do 10 na Core i7 950 i 24 GB RAM. Program zaalokował ponad 22 GB pamięci.
Głębokość 8 obliczył w 106 sekund. Całkiem niezły wynik mi się wydaje. Wszystkie dotychczasowe wyniki zgadzają się z tymi w bazie oeis.org.
Obliczył właśnie do głębokości 9. Trwało to 1160 sekund. Wynik zgodny z oeis.org.

Zbadamy za jakiś czas jaki wpływ mają dwa ostatnie parametry. U mnie na i3 (laptop) takie
mam wyniki dla depth=8:
./perft
threadMemPerft 8 4 220000000 4 0
nodes:84998978956 time:260
threaMemPerft 8 4 220000000 4 1
unknown command: threamemperft
threadMemPerft 8 4 220000000 4 1
nodes:84998978956 time:277
threadMemPerft 8 4 220000000 4 1000
nodes:84998978956 time:275
threadMemPerft 8 4 220000000 4 1000000
nodes:84998978956 time:247
threadMemPerft 8 4 220000000 8 0
nodes:84998978956 time:246
threadMemPerft 8 4 220000000 8 1000000
nodes:84998978956 time:250
threadMemPerft 8 4 220000000 12 0
nodes:84998978956 time:268
threadMemPerft 8 4 220000000 12 1000000
quit

Najlepszy wynik 246 sekund, najgorszy 277 - czyli trochę można zyskać. Dla
większych głębokości zysk może być znacznie większy.

Pozdrawiam

[Karlik]

Jesteś pewien, że zapamiętywanie funkcji skrótu zamiast całego układu tak istotne? O ile dobrze liczę to całą planszę można zapisać na 24-32 bajtach (w zależności od tego jak zakodujemy planszę). Nie znam algorytmu, więc ciężko mi mówić jaki to miałoby wpływ na wydajność (bo może kodowanie/dekodowanie tego by było zbyt czasochłonne).

[mariotti]

Jesteś pewien, że zapamiętywanie funkcji skrótu zamiast całego układu tak istotne?

Na pewno jest istotne. Jak bardzo istotne, to nie sprawdzałem. Możliwe że to
przyspiesza nawet 2-3 razy. Na pewno da się w ten sposób zapamiętać dwa
razy więcej układów, a to istotnie przyspiesza.

O ile dobrze liczę to całą planszę można zapisać na 24-32 bajtach (w zależności od tego jak zakodujemy planszę).

w 32 bajtach na pewno można, w 20tu może też by się dało. Ale takie zapamiętanie to
nie byłoby szybkie memcpy i potem porównanie przez memcmp. Jak się zrobi planszę
jako liniowe 64/32 bajty, to z kolei wolno działają inne operacje :)

Nie znam algorytmu, więc ciężko mi mówić jaki to miałoby wpływ na wydajność (bo może kodowanie/dekodowanie tego by było zbyt czasochłonne).

Mnie też jest trudno powiedzieć, myślę że z tą techniką działa 2-3 razy szybciej.

Pozdrawiam

[mariotti]

Teraz widać dlaczego nikt nie policzył do 16  ;D.
Ostatnia kolumna jest prostym założeniem, wynikającym z podanych przez was wyników, że w trybie z pamięcią obliczenia są wykonywane 40 razy szybciej (patrząc na 1 wątek)
Przy "13" jeszcze idzie policzyć w realnym czasie, ale już "14" to niezła orka.
Przyjmijmy, że wydajność jednego rdzenia to średnio 6000 MIPSów, więc by przeliczyć "14" trzeba wykonać około 1700 kwintylionów FLOPów (licząc jednostki jak amerykanie). To jest, tak dla porównania, około 2 miliardów kredytów w PrimeGrid'zie. Cały zespół B@P ma mniej więcej tyle, a pewnie lwia część tego to projekty liczone na GPU.

Przychodzi mi do głowy tylko jedyny sensowny sposób na dokładnie oszacowanie czasu
dla algorytmu z pamięcią.

Najpierw trzeba policzyć na jakąś głębokość i zapamiętać wszystkie układy. Potem układy
powtarzające się trzeba wyrzucić, a z każdym układem zapamiętać ilość jego wystąpień. W
ten sposób otrzymamy ilość różnych układów. Różne układy mogłyby leżeć w bazie
na jakimś serwerze. Klient może pytać o układ, wykonywać dla niego obliczenia i odsyłać
wynik z powrotem na serwer. Czyli łączny czas obliczeń będzie wynosił A*N, gdzie
A to średni czas liczenia jednego układu, a N to ilość różnych układów.


Sensowna głębokość dla klienta jest w granicach 8-10. Przy głębokości 8, mogą zapchać
serwer. Przy głębokości 10 na serwerze będzie mało układów, a więc gorzej zadziała algorytm
odrzucania powtarzających się. Powiedzmy że klient będzie liczył na głębokość 9. Czyli
serwer musi sam przeszukać na głębokość 5 aby łącznie uzyskać 14.  Drzewko ma 4865609  liści
przy głębokości 5 ruchów. Widzieliśmy że na głębokość 9 da się policzyć w 1160s. Powiedzmy
że program po zoptymalizowaniu policzy na głębokość 9 w 10-20sekund (kurcze, 20 sekund
nadal może zapchać serwer). Czyli 4865609*10-20s=15-30 lat - całkiem szybko, a do tego
wiele układów będzie się powtarzało.


Nie wiem ile układów będzie się powtarzało, myślę że bardzo dużo odpadnie. Strzelam że
zostanie tylko 10% układów. Czyli 10% * 4865609 * 10-20s = 1.5 - 3 lat - Na boinc to bułka
z masłem.


Jeśli przyjmiemy podstawę potęgi równą 25, to by znaczyło, że z tymi technikami w nie więcej
niż 3tys lat dojdziemy do głębokości 16 ruchów.


Obawa pozostaje jedna, czy naprawdę pozostanie tylko 10% układów po odrzuceniu powtórzeń?

To oszacowanie na pewno jest znacznie bardziej optymistyczne niż Twoje 10 738 920 lat :D

Pozdrawiam

[Szopler]

Kod [Zaznacz] Rozwiń

nie można uruchomić pliku binarnego

1. chmod +x ./perft poszło
2. apt-get install ia32-lib-i386 poszło
3. apt-get libboost-thread-dev poszło
4. ściągnięcie preft + lib w wersji wymaganej poszło

i dalej nie działa :/ (debian 7 no gui)