To co? Bawimy się? :D

[mariotti]

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)

Program na razie nie będzie działał na linuxie 32 bitowym.
Pozdrawiam

[Karlik]

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 :)

Akurat dowolną strukturę można spokojnie w ten sposób porównywać ;] Nie wiem jak masz to do innych operacji przedstawione, ale jak dla mnie to może być coś typu:

Kod [Zaznacz] Rozwiń

struct plansza{
unsigned char white[16];
unsigned char black[16];
};
Gdzie spokojnie możesz zapisać na starszych 4 bitach X, na młodszych Y, same zera dają pionek poza planszą. Wtedy masz 32 bajty, które swobodnie możesz porównać przez memcmp. Jedyny ew. mankament to pionki, które musiałbyś osobno sprawdzać, bo są traktowane indywidualnie. Inne podejście może być takie:

Kod [Zaznacz] Rozwiń

struct plansza{
unsigned char field[4][8];
};
wtedy masz w jednym bajcie dwa pola (możesz je traktować liniowo) - wtedy reprezentujesz sobie najstarszy bit zapisu jako kolor, pozostałe 3 jako rodzaj figury (król, królowa, goniec, koń, wieża, pion) - jedna wartość niewykorzystana. Wtedy masz bardzo wygodne porównywanie przez memcmp.
To masz wersje 32 bajtowe. Z mniejszych, gdzie ma się pełną informację na pewno wykonalna jest 28 bajtowa jeszcze.
Wydaje mi się, że koszt operowania na tak przygotowanej planszy jest mniejszy niż liczenie funkcji skrótu. W sumie to takie gdybanie, bo jak się nie widzi kodu to ciężko cokolwiek doradzić.

To teraz tak, hash ma 20 bajtów z tego co zrozumiałem. Możesz spróbować jakoś ponumerować układy po prostu. Masz maksymalnie zajęte 32 pola z 64, to masz 64 po 32 = 1,8e+18 układów zajętych pól. Masz 13 rodzajów figur (6*2+1 -> jedynka, bo może pole być puste). Więc masz 13^32 *  1,8e+18, z tego logarytm dwójkowy wychodzi ~179, więc musisz poświęcić co najmniej 23 bajty na każdy układ. Można teoretycznie zbić jeszcze to trochę, bo król może występować tylko raz, królowa tylko raz, więc zamiast 13^32 wyjdzie jakieś 13*12*11*10 (króle i królowe), dalej *9*9*8*8 (gońce), *7*7*6*6 (konie), *5*5*4*4 (wieże), *3^8 * 2^8 (pionki) * 2^30 (bo każdy może występować lub nie z wyjątkiem króli), wtedy masz te swoje upragnione 20 bajtów (158 bitów). W rzeczywistej grze liczba układów jeszcze jest mniejsza, bo niektóre sytuacje nigdy nie zajdą, ale liczenie tego to... Tak więc teoretycznie te 20 bajtów może Ci wystarczyć, ale nie zdziwiłbym się, gdyby Twoja funkcja skrótu dawała tę samą wartość dla dwóch różnych układów (zrobienie takiej idealnej nie jest wbrew pozorom takie proste).

[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)

Program na razie nie będzie działał na linuxie 32 bitowym.
Pozdrawiam

Ale kwas :/ przez pomyłkę ściągnąłem i zainstalowałem i386 zamiast amd64... :facepalm2:

Edit: Dobra odpaliłem go.sh...

[Rysiu]

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

Ale 32 czy 64bit?

//Edit: Nie zauważyłem drugiej strony z odpowiedziami  %)

[krzyszp]

Za to u mnie po prawie dobie wyskoczyło "Killed"...  :(

Zakładam, że to z powodu braku wolnej pamięci (serwer wszedł mi ostro na swap'a).

Edit:
Spróbowałem odpalić na Virtualbox'ie skrytp, ale niestety wysypał się z komunikatem (z VB) "Guru meditation" ;)

[Dario666]

Ciekawe jak chcesz zoptymalizować obliczenia z 1160 sekund do średnio 15 sekund, czyli przyspieszyć go 77 razy. To chyba zbytni optymizm.

Znalazłem na stronach szachowych dość obszery wywód z szacowaniem ilości możliwych rozstawień figur i wynik brzmiał 10⁴⁰.

Patrząc na to, że funkcja haszująca 160-bitowa ma 1,46*10⁴⁸ różnych wyników, to może się okazać zbyt mało i kolega Karlik może mieć rację, że hasze będą się powtarzać dla rózych ustawień.

Zasadnicze pytanie jest takie: po co to w ogóle mamy liczyć? Dla samego przeliczenia? Jakie jest cel i jakie dane chcemy zgromadzić, aby można je było wykorzystać do dalszych badań. Według mnie metoda z haszami nie jest trafiona, bo nie możemy z niej odczytać jakie jest rzeczywiste ustawienie figur na szachownicy.

[mariotti]

> Akurat dowolną strukturę można spokojnie w ten sposób porównywać ;]
Nie chodzi o to że nie można, tylko oto, że dane sekwencyjne porównuje się szybciej.



> Nie wiem jak masz to do innych operacji przedstawione, ale jak dla mnie to może być coś typu:
> struct plansza{
> unsigned char white[16];
> unsigned char black[16];
> ;[/code]
> Gdzie spokojnie możesz zapisać na starszych 4 bitach X, na młodszych Y, same zera dają pionek poza planszą.
Nie chodzi o to że nie można spokojnie trzymać :) Chodzi o to, że na reprezentacji planszy trzeba wykonywać
wiele różnych operacji. Jeśli strukturę dopasujemy do jednej operacji, to będzie gorzej dopasowana do drugiej.
Poza tym ta wersja którą teraz robię, docelowo ma efektywnie działać na szachach samouczących, a nie
na teście perft. Test perft to takie zadanie epizodyczne przy okazji :)


> Wtedy masz 32 bajty, które swobodnie możesz porównać przez memcmp.
Ale np. testowanie szacha i znajdowanie ruchów trwa wolniej niż na strukturze którą
mam obecnie - tu przyspieszysz, a tam zwolni.


> Jedyny ew. mankament to pionki, które musiałbyś osobno sprawdzać, bo są traktowane indywidualnie. Inne podejście może być takie:
>

Kod [Zaznacz] Rozwiń

struct plansza{
> unsigned char field[4][8];
> };
> wtedy masz w jednym bajcie dwa pola (możesz je traktować liniowo) - wtedy reprezentujesz sobie najstarszy bit zapisu jako
> kolor, pozostałe 3 jako rodzaj figury (król, królowa, goniec, koń, wieża, pion) - jedna wartość niewykorzystana.
> Wtedy masz bardzo wygodne porównywanie przez memcmp.
No tak, ale jak efektywnie na tym wykonywać wszystkie pozostałe operacje? Operacji jest sporo: sprawdzanie
czy jest szach, sprawdzanie czy ruch jest legalny (po ruchu nie może być szacha), sprawdzanie czy nie próbuje
się bić króla, wyszukiwanie gdzie stoi król, zliczenie ile jest w sumie figur, posortowanie ruchów począwszy
od bić, sprawdzenie czy pozycja na planszy nie powtórzyła się trzy razy, sprawdzenie czy jest remis po wykonaniu
50 ruchów bez bicia, promocji i roszady...


> To masz wersje 32 bajtowe. Z mniejszych, gdzie ma się pełną informację na pewno wykonalna jest 28 bajtowa jeszcze.
Pewnie da się jeszcze mniejszą zrobić niż 28 bajtów, ale to się nie opłaci.


> Wydaje mi się, że koszt operowania na tak przygotowanej planszy jest mniejszy niż liczenie funkcji skrótu.
Mam specjalną funkcję skrótu, jej koszt jej obliczenia to... nie wiem ile... może 1% wykonania całego programu.
Używam kluczy zobrosta, można je obliczać "przyrostowo".


> W sumie to takie gdybanie, bo jak się nie widzi kodu to ciężko cokolwiek doradzić.
A jak się widzi kod, to można jedną rzecz przyspieszyć, a 10 innych spowolni :D



> To teraz tak, hash ma 20 bajtów z tego co zrozumiałem.
Hash ma 8 bajtów. Dodatkowo jest 8 bajtów na ilość węzłów i był 1
bajt na crc. Teraz mam 8 bajtów na crc. Czyli jeden wpis to w
nowej wersji 24 bajty.


> Możesz spróbować jakoś ponumerować układy po prostu. Masz maksymalnie zajęte 32 pola z 64, to masz 64 po 32 = 1,8e+18 układów zajętych pól.
> Masz 13 rodzajów figur (6*2+1 -> jedynka, bo może pole być puste). Więc masz 13^32 *  1,8e+18, z tego logarytm dwójkowy wychodzi ~179, więc
> musisz poświęcić co najmniej 23 bajty na każdy układ. Można teoretycznie zbić jeszcze to trochę, bo król może występować tylko raz, królowa tylko raz,
> więc zamiast 13^32 wyjdzie jakieś 13*12*11*10 (króle i królowe), dalej *9*9*8*8 (gońce), *7*7*6*6 (konie), *5*5*4*4 (wieże), *3^8 * 2^8 (pionki) * 2^30 (bo każdy
> może występować lub nie z wyjątkiem króli), wtedy masz te swoje upragnione 20 bajtów (158 bitów). W rzeczywistej grze liczba układów jeszcze jest mniejsza, bo
> niektóre sytuacje nigdy nie zajdą, ale liczenie tego to... Tak więc teoretycznie te 20 bajtów może Ci wystarczyć, ale nie zdziwiłbym się, gdyby Twoja funkcja skrótu
> dawała tę samą wartość dla dwóch różnych układów (zrobienie takiej idealnej nie jest wbrew pozorom takie proste).
Najprościej i najefektywniej z wszystkich znanych mi sposób działają klucze zobrista. Używam 64bitowej funkcji skrótu, to kolosalna ilość 2^64 różnych
wartości, ale być może okaże się za mało. Mój program właśnie dał złą wartość - może to z powodu zbyt krótkiej funkcji skrótu. Jeśli okaże się za mało, to dam 128 bitów.
Wpis w hash-table z rozmiaru 24bajtów zwiększy się do 32 bajtów - czyli da się zapamiętać o 25% układów mniej - to poważny mankament, bo pamięć jest ważna, ale być
może nie ma innego wyjścia. Natomiast z powodu dłuższych kluczy zobrista program nie spowolni prawdopodobnie nawet o 1% - to naprawdę efektywna metoda.

Pozdrawiam serdecznie

[mariotti]

Za to u mnie po prawie dobie wyskoczyło "Killed"...  :(
Zakładam, że to z powodu braku wolnej pamięci (serwer wszedł mi ostro na swap'a).
Edit:
Spróbowałem odpalić na Virtualbox'ie skrytp, ale niestety wysypał się z komunikatem (z VB) "Guru meditation" ;)

Masakra, czyli program cały czas jest niestabilny. Jutro zapodam nową wersję.
Dzięki i pozdrawiam.

[mariotti]

Ciekawe jak chcesz zoptymalizować obliczenia z 1160 sekund do średnio 15 sekund, czyli przyspieszyć go 77 razy. To chyba zbytni optymizm.

Otóż obecnie mój program wykonuje tyle ruchów ile... jakby to zgrabnie napisać... no tyle ile jest do wykonania w
danym poddrzewie - w programie szachowym tak właśnie trzeba. Ale w procedurze perft na jedną głębokość przed
liściem, czyli tam gdzie jest najwięcej obliczeń, nie trzeba wykonać ani jednego ruchu - wystarczy zliczyć ile ruchów
jest tam dozwolonych i zrobić return ilość_ruchów; - może się mylę, ale szacuję to na przyspieszenie
rzędu 20-40 razy. Do tego dochodzi zarządzanie pamięcią, po tej optymalizacji na ostatnim poziomie, może program tak
mocno przyspieszyć, że nie będzie sensu zapamiętywanie przedostatniego poziomu w wynikach częściowych - a więc
pamięć zostanie wolna dla większych głębokości - a podanie wyniku bez obliczeń na większych głębokościach
daje większe przyspieszenie niż podanie go na głębokościach mniejszych. Do tego mój program ma parametry
probe i forget - na razie nie wiem jakie są ich optymalne wartości. Do tego można ruchy na jednym poziomie wykonać
nie jeden raz, ale dwa razy. Po co dwa razy wykonywać to samo? Ano po to, żeby sprawdzić dla których ruchów jest
zapamiętany wynik i je od razu podać, bo jak się wykona najpierw inne, to zapamiętany wynik może zostać zamazany....

Niby takie sobie proste przeszukiwanie drzewa gry... ale technik jest dużo i każda może coś przyspieszyć.  Jak mi tylko czas
pozwoli to myślę że jest realne przyspieszenie nawet do 200 razy. No i czasy do szacowań wziąłem z laptopa i3 - a to nie
jest zbyt mocny komputer :)


> Znalazłem na stronach szachowych dość obszery wywód z szacowaniem ilości możliwych rozstawień figur i wynik brzmiał 10⁴⁰.
> Patrząc na to, że funkcja haszująca 160-bitowa ma 1,46*10⁴⁸ różnych wyników, to może się okazać zbyt mało i kolega Karlik może
> mieć rację, że hasze będą się powtarzać dla rózych ustawień.
Niewykluczone że ma rację. Do tej pory nigdy się nie spotkałem z taką sytuacją, aby klucz 64bitowy był za krótki. Być może przy obliczeniach
rozproszonych będzie potrzebny klucz 128 bitowy, a może jeszcze większy - na razie tego nie wiem. Natomiast jestem pewny, że mogę
długość klucza zwiększać aż wystarczy.


> Zasadnicze pytanie jest takie: po co to w ogóle mamy liczyć? Dla samego przeliczenia?
Nie rozumiem. To czyli co? W ogóle całe zadanie? Byłem zachęcany/ponaglany żeby zrobić
jakiś projekt do obliczeń rozproszonych.  Na szybko nic lepszego nie mogę zaoferować niż
to zadanie - więc głównie po to.

Taki projekt jest w jakimś małym stopniu prestiżowy, od dawna pasjonaci szachów zastanawiają
się ile jest możliwych układów. Nie da się odpowiedzieć na to pytanie w ogóle, ale można podać
ile jest układów do określonej głębokości. Wielu ludzi liczyło to do 12 ruchów i się chwaliło że
się udało. Nikt dzięki temu projektowi zdrowszy lub bogatszy nie będzie, ale szczęśliwszy może tak :)


> Jakie jest cel
Np. taki może być cel:
Podać dokładnie jaką wartość zwraca funkcja perft dla głębokości do 16 ruchów włącznie.
Podać bardzo dobre oszacowania funkcji perft do 24 ruchów włącznie.

> i jakie dane chcemy zgromadzić, aby można je było wykorzystać do dalszych badań.
Danych raczej nie chcemy gromadzić. Chcemy znać rozwiązanie i chcemy dojść do
niego w najszybszym czasie.


> Według mnie metoda z haszami nie jest trafiona, bo nie możemy z niej odczytać jakie jest rzeczywiste ustawienie figur na szachownicy.
Nie potrzeba odczytywać rzeczywistego układu, przynajmniej teraz program działa i nie odczytuje tego.

Pozdrawiam

[Rysiu]

Ja widzę dość zaawansowany problem z funkcją skrótu. Przecież nawet dając hash o długości 128 bitów lub więcej i tak masz teoretyczną szansę, że coś się powtórzy. Prawdopodobieństwo tego być może jest skrajnie niskie ale jednak jest.

Do takiego zliczania potrzebna jest aplikacja zwracająca zawsze w 100% poprawny wynik.

[Dario666]

Chodziło mi o to, żeby można było wykorzystać w przyszłości uzyskane wyniki do obliczeń na większą głębokość, a nie liczyć znowu od początku.

Druga sprawa dotyczy hashy. NIe wiem czy spotkałeś się kiedyś z "paradoxem urodzin"... Po krótce chodzi o to, że prawdopodobieństwo znalezienia 2 osób urodzonych tego samego dnia wśród grupy 366 osób jest równe 100%. Wydawałoby się, że aby uzyskać prawdopodobieństwo równe 50% potrzeba grupy 183 osób. Nic bardziej błędnego. Do tego wystarczy grupa jedynie 23 osób!
Ten problem wykorzystywany jest do oszacowania ile można wykonać hashy kluczem o określonej długości, aby wystąpiła kolizja (ten sam hash). Przyjmuje się, że prawdopodobieństo 10^-15 jest najwyższym jakie można zaakceptować, aby być pewnym, że kolizja nie wystąpi - notabene na tym bazują funkcje korekcji błędów dysków HDD, CD i DVD. Przy funkcji mieszającej 64-bitowej wystarczy wyznaczyć tylko 190 hashy, aby przekroczyć to prawdopodobieństwo!!! Przy funkcji 128-bitowej jest to 820*10⁹, a przy 256-bitowej to 15*10³⁰. Dlatego właśnie teraz do podpisu elektronicznego stosuje się hashe conajmniej 256-bitowe.

Myślę, że powinieneś zastanowić się na zastosowaniem hashy 256-bitowych, żeby nikt nie podważył wyniku obliczeń. Lecz to już 32 bajty i nie wiem czy nie lepiej byłoby zakodować każdą figuę (jest ich przecież tylko 6) na 3 bitach i pamiętać 64 pola po 3 bity, co daje tylko 24 bajty. Porówanie takiej struktury wymaga w SIMD tylko kilku instrukcji maszynowych.

[mariotti]

Ja widzę dość zaawansowany problem z funkcją skrótu. Przecież nawet dając hash o długości 128 bitów lub więcej i tak masz teoretyczną szansę, że coś się powtórzy. Prawdopodobieństwo tego być może jest skrajnie niskie ale jednak jest.
Do takiego zliczania potrzebna jest aplikacja zwracająca zawsze w 100% poprawny wynik.

Z tego co wiem, wszyscy liczą takie zadania na funkcji skrótu. Ale skoro mnie uczulacie, to:

Po pierwsze przebadamy sprawę. Dam 40 bitów, potem 41, 42 itd. Zobaczymy jaka długość
wystarcza do jakiej głębokości. Z tego co pamiętam, 56bitów do jedno-komputerowych
zastosowań wystarczało w zupełności, ale sprawdzimy to porządnie jeszcze raz.

Po drugie zawsze może znaleźć się ktoś nieuczciwy i podesłać nam błędny wynik, więc
obliczenia trzeba weryfikować. Więc z każdym podzadaniem będziemy wysyłać inną
funkcję skrótu. Wydaje się skrajnie mało prawdopodobne, żeby na dwóch-trzech błędnych
funkcjach skrótu uzyskać dwa-trzy razy takie same wyniki.


------------------------------------------------------------------------------------------------------------------------------
Sprawdzam wpływ parametrów probe i forget na szybkość obliczeń.
Wyniki na laptopie i3:

Kod [Zaznacz] Rozwiń


threadMemPerft 9 4 200000000 1 0 nodes:2439530234167 time:3264
threadMemPerft 9 4 200000000 2 0 nodes:2439530234167 time:2789
threadMemPerft 9 4 200000000 3 0 nodes:2439530234167 time:2647
threadMemPerft 9 4 200000000 4 0 nodes:2439530234167 time:2598
threadMemPerft 9 4 200000000 5 0 nodes:2439530234167 time:2575
threadMemPerft 9 4 200000000 6 0 nodes:2439530234167 time:2566
threadMemPerft 9 4 200000000 7 0 nodes:2439530234167 time:2564
threadMemPerft 9 4 200000000 8 0 nodes:2439530234167 time:2564


Widzę że kombinując z tymi parametrami można uzyskać spory zysk.
Na innych platformach sprzętowych może być inny koszt odstępu do
pamięci, więc ciekawy jestem czy będzie powtarzalność wyników.

Jakby ktoś chciał pomóc, to przesyłam przykładowy skrypt. Parametry:
mem  - pamięć
thr     -  ilość wątków
depth - głębokość przeszukiwania
Jak je ustawiać, chyba już wiadomo, jak nie, to pytajcie.

Natomiast dwa ostatnie parametry (probe i forget) trzeba
wpisać w każdym poleceniu inne. Najlepiej gdy jeden
z tych dwóch parametrów wpisujemy na stałe, a drugi
zmieniamy z jakimś skokiem.

Parametr drugi od końca ma sensowne wartości w przedziale
od 1 do około 20-30. Przyjmuje tylko wartości całkowite.
Parametr drugi może przyjmować dowolne wartości
całkowite z przedziału od 0 aż do 2^64-1.

Można np. parametr pierwszy wpisać na stałe, może równać się
powiedzmy 4, a pod parametr drugi można podstawić jakieś
mocno rozrzucone liczby.

Np.

4 0
4 1
4 5
4 25
4 125
4 625
4 10000
4 100000
4 1000000
4 10000000

Można zrobić odwrotnie, można drugi parametr pozostawić stały, a zmieniać
tylko pierwszy, np. tak:

1 1000000
2 1000000
3 1000000
4 1000000
5 1000000
6 1000000
7 1000000
8 1000000


Poniżej kod którego ja użyłem. Wyniki trafią do pliku out.txt

Kod [Zaznacz] Rozwiń


#!/bin/sh
mem=200000000
thr=4
depth=9


(
echo threadMemPerft $depth $thr $mem 1 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 2 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 3 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 4 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 5 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 6 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 7 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 8 0
echo quit
) | ./perft >> out.txt


------------------------------------------------------------------------------------------------------------------------------

W załączniku najnowsza wersja programu.

[mariotti]

Chodziło mi o to, żeby można było wykorzystać w przyszłości uzyskane wyniki do obliczeń na większą głębokość, a nie liczyć znowu od początku.

Teraz rozumiem. Myślałem nad tym kiedyś przez pewien czas i szukałem jakieś metody/algorytmu. Nawet znalazłem taką możliwość, ale
doszedłem do wniosku, że to się nie opłaci. Wątpię aby to było możliwe, ale jakby ktoś mi podsunął taki algorytm, to oczywiście spróbujemy.

Druga sprawa dotyczy hashy. NIe wiem czy spotkałeś się kiedyś z "paradoxem urodzin"...

Tak, znam termin paradoksu dnia urodzin. Pomimo tego paradoksu do tej pory nigdy nie spotkałem się z
taką sytuacją, aby klucze 64-bitowe nie zadziałały w zastosowaniach jedno-komputerowych. Nawet przy
liczeniu przez 2 tygodnie na 6 rdzeniach równolegle.

Po krótce chodzi o to, że prawdopodobieństwo znalezienia 2 osób urodzonych tego samego dnia wśród grupy 366 osób jest równe 100%.

Przy założeniu że do grupy trafiły losowe osoby :)

Wydawałoby się, że aby uzyskać prawdopodobieństwo równe 50% potrzeba grupy 183 osób. Nic bardziej błędnego. Do tego wystarczy grupa jedynie 23 osób!

No tak, ale ilość różnych wartości funkcji skrótu też rośnie wykładniczo z każdym bitem.

Może spróbujesz oszacować teoretyczną ilość bitów?
Klient musi przeszukać na głębokość powiedzmy 9 ruchów. Powiedzmy że
unikalnych węzłów jest 28*28*16^7 (wszystkich jest 210453397504). Klient może w RAM
przechować około 200mln kluczy. Ja bym to oszacował jako paradoks dnia
urodzin dla roku który ma 2^64 albo 2^128 dni, dla grupy która ma 200 mln
osób a potem w grupie jedna osoba zmienia się 28*28*16^7 razy.
Uzyskamy prawdopodobieństwo błędnego wyniku dla jednego klienta.

Ten problem wykorzystywany jest do oszacowania ile można wykonać hashy kluczem o określonej długości, aby wystąpiła kolizja (ten sam hash). Przyjmuje się, że prawdopodobieństo 10^-15 jest najwyższym jakie można zaakceptować, aby być pewnym, że kolizja nie wystąpi - notabene na tym bazują funkcje korekcji błędów dysków HDD, CD i DVD. Przy funkcji mieszającej 64-bitowej wystarczy wyznaczyć tylko 190 hashy, aby przekroczyć to prawdopodobieństwo!!! Przy funkcji 128-bitowej jest to 820*10⁹, a przy 256-bitowej to 15*10³⁰. Dlatego właśnie teraz do podpisu elektronicznego stosuje się hashe conajmniej 256-bitowe.

Programy szachowe (wszystkie) działają na funkcji 64bitowej.  Mój program też podaje wyniki dla głębokości 9
(powiedzmy że to 28*28*16^7 unikalnych węzłów) przy funkcji 64 bitowej.

Myślę, że powinieneś zastanowić się na zastosowaniem hashy 256-bitowych, żeby nikt nie podważył wyniku obliczeń.

Na pewno wezmę to pod uwagę. W poście powyżej już opisałem dokładnie jak zbadamy sprawę. Wyniki
obliczeń i tak będziemy musieli zweryfikować. Więc można dać każde zadanie do liczenia na dwóch
różnych funkcjach 128 bitowych. Jeśli wyniki będą różne, to się policzy na  trzeciej funkcji skrótu. Jeśli
nadal będą różne, to się zastosuje funkcje 192 bitowe.

Lecz to już 32 bajty i nie wiem czy nie lepiej byłoby zakodować każdą figuę (jest ich przecież tylko 6) na 3 bitach i pamiętać 64 pola po 3 bity, co daje tylko 24 bajty. Porówanie takiej struktury wymaga w SIMD tylko kilku instrukcji maszynowych.

Instrukcji SIMD nie ma na każdej maszynie i mogą być różnice pomiędzy AMD i Intelem. Zamiana mojej szachownicy na
liniowe dane to dość skomplikowana procedura. Mniej/więcej coś takiego:

i=0;
for( j=2 ; j<10 ; j++ )
for( k=3 ; k<11 ; k++ )
lin[i++] = board[j*10+k];
lin[i++] = czy_jest_przyzwolenie_na_bicie_w_przelocie;
for( j=0 ; j<4 ; j++ )
lin[i++] = przyzwolenia_roszad[ idx[j] ];
lin[i++] = która_strona_ma_ruch

Czyli do każdego węzła dojdzie 70 pętli. Jak dane skompresujemy, to jeszcze
dojdą operację bitowe and i or. Spowolni to całość z 10-30 razy.

Istnieje jeszcze inne rozwiązanie... można trzymać dwie reprezentacje
(a właściwie trzy, bo drugą wyspecjalizowaną trzymam już w celu przyspieszenia
testów szacha) jednocześnie i aktualizować ją po każdym ruchu...

Tak czy inaczej, na pewno starannie podejdę do sprawy zapamiętywania
danych częściowych - nie możemy ryzykować błędnych wyników.

Pozdrawiam

[Szopler]

U mnie program po kilkunastu godzinach się zakończył... przedwcześnie

Kod [Zaznacz] Rozwiń

#!/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

Wyniki:

Kod [Zaznacz] Rozwiń

nodes:20 time:2
nodes:400 time:0
nodes:8902 time:1
nodes:197281 time:1
nodes:4865609 time:1
nodes:119060324 time:2
nodes:3195901860 time:10
nodes:84998978956 time:111
nodes:2439530234167 time:2489

[mariotti]

U mnie program po kilkunastu godzinach się zakończył... przedwcześnie

Czyli program ma jakiś dziwny błąd, który uaktywnia się dopiero przy
głębokości 10 ruchów i to tylko na niektórych komputerach :/
Cóż, najwyraźniej czeka mnie żmudny proces debugowania.

Moja kolejna prośba odnośnie testów jest kilka postów wyżej:
http://www.boincatpoland.org/smf/przetwarzanie-rozproszone/to-co-bawimy-sie-d/msg225243/#msg225243

Jakby nie chciało Ci się czytać całego posta, to prośba zaczyna
się tam od słów: "Jakby ktoś chciał pomóc" :D

Pozdrawiam i dziękuję.

[mariotti]

U mnie program po kilkunastu godzinach się zakończył... przedwcześnie

Czyli program ma jakiś dziwny błąd, który uaktywnia się dopiero przy
głębokości 10 ruchów i to tylko na niektórych komputerach :/
Cóż, najwyraźniej czeka mnie żmudny proces debugowania.

Moja kolejna prośba odnośnie testów jest kilka postów wyżej:
http://www.boincatpoland.org/smf/przetwarzanie-rozproszone/to-co-bawimy-sie-d/msg225243/#msg225243

Jakby nie chciało Ci się czytać całego posta, to prośba zaczyna
się tam od słów: "Jakby ktoś chciał pomóc" :D

Pozdrawiam i dziękuję.

P.S.
Oczywiście testujemy tylko najnowszej wersji :)

[Karlik]

Tak, znam termin paradoksu dnia urodzin. Pomimo tego paradoksu do tej pory nigdy nie spotkałem się z
taką sytuacją, aby klucze 64-bitowe nie zadziałały w zastosowaniach jedno-komputerowych. Nawet przy liczeniu przez 2 tygodnie na 6 rdzeniach równolegle.

Zauważ, że jak na razie mówisz, że tak robią programy szachowe i może to być racja, nawet do głębokości tych 9 czy nawet 13 ruchów tak funkcja skrótu może wystarczyć (chociaż ciężko to zwryfikować). Jednak nawet sam wspomniałeś o tym, że to jest drzewo i liczba węzłów rośnie wykładniczo i to bardzo szybko. Nawet jeśli na każdym kolejnym poziomie będzie 20 razy więcej węzłów to samo zapisanie tego wymaga o 5 bitów więcej, nie wspominając w ogóle o prawdopodobieństwie. Tak więc do 12 poziomu spokojnie może Ci wystarczyć 64 bity na samo zapisanie numeru układu, a gdzie tu mówić o jakimkolwiek porównywaniu? Poza tym komputer do grania nie potrzebuje wiedzy pewnej, jak przeoczy któreś ustawienie to praktycznie nic się nie dzieje, co najwyżej lekko mu spadnie możliwość wygranej, Ty bierzesz się za coś co ma być wiedzą pewną/naukową, tutaj naprawdę każda pojedyncza wartość ma znaczenie jeśli chcesz być brany poważnie (albo inaczej: żeby wyniki ciężko było podważyć).

No tak, ale jak efektywnie na tym wykonywać wszystkie pozostałe operacje? Operacji jest sporo: sprawdzanie czy jest szach, sprawdzanie czy ruch jest legalny (po ruchu nie może być szacha), sprawdzanie czy nie próbuje się bić króla, wyszukiwanie gdzie stoi król, zliczenie ile jest w sumie figur, posortowanie ruchów począwszy od bić, sprawdzenie czy pozycja na planszy nie powtórzyła się trzy razy, sprawdzenie czy jest remis po wykonaniu 50 ruchów bez bicia, promocji i roszady...

Do samych obliczeń spokojnie możesz mieć równolegle obie wersje. Zauważ, że w tej chwili bierzesz pod uwagę konieczność wydłużania funkcji hashującej w nieskończoność, więc chyba prościej zapamiętywać cały układ. Co do ostatniego to jak dla mnie zupełnie bezsensowne sprawdzenie. Żeby było 50 ruchów to musiałbyś mieć drzewko na głębokość 50, jak na razie widzę rozważamy max. 20 ruchów do przodu. Poza tym ja to proponuję jako sposób zapisu układu na potrzeby porównań (już do samego drzewka zamiast hasha - w samym hashu też przecież nie sprawdzasz położenia króla ani nic podobnego), i tak musisz docelowo tę zmianę wprowadzić w funkcji skrótu (zrobić dwa xory przykładowo), tutaj masz nawet łatwiej, bo tylko robisz proste przypisanie albo nowej wartości pola do figury (lub dwóch przy biciu lub roszadzie) albo nowej figury do dwóch pól. Uwzględnienie promocji figury w wersji black/white to może być po prostu najstarszy bit.

Lecz to już 32 bajty i nie wiem czy nie lepiej byłoby zakodować każdą figuę (jest ich przecież tylko 6) na 3 bitach i pamiętać 64 pola po 3 bity, co daje tylko 24 bajty.

Nie do końca, masz 12 figur (musisz osobno traktować białe i czarne), więc masz 4 bity na pole, czyli łącznie 32 bajty ;)

[mariotti]

Zauważ, że jak na razie mówisz, że tak robią programy szachowe i może to być racja, nawet do głębokości tych 9 czy nawet 13 ruchów tak funkcja skrótu może wystarczyć (chociaż ciężko to zwryfikować).

Wszystko się zgadza, ale żeby nasze wyniki były poważnie traktowane, to też musimy się zabezpieczyć
przed osobami, które złośliwie podeślą błędne wyniki. Więc można raz policzyć na funkcji 128
bitowej i drugi raz na zupełnie (naprawdę zupełnie) innej funkcji też o długości 128 bitów. Jeśli
wynik będzie błędny, to jest skrajnie mało prawdopodobne, że błąd na dwóch zupełnie różnych
funkcjach skrótu będzie taki sam. Z tą techniką (chyba) upieczemy pięć pieczeni na jednym ogniu:
1) szybkie porównywanie
2) oszczędność pamięci
3) zabezpieczenie przed nieuczciwymi osobami
4) błąd ram, błąd transferu sieci
5) jest już gotowy program, nie trzeba nic dopisywać.

Jednak nawet sam wspomniałeś o tym, że to jest drzewo i liczba węzłów rośnie wykładniczo i to bardzo szybko.
Nawet jeśli na każdym kolejnym poziomie będzie 20 razy więcej węzłów to samo zapisanie tego wymaga o 5 bitów więcej, nie wspominając w ogóle o prawdopodobieństwie.

Jak poprawnie oszacować to prawdopodobieństwo...

Przypuśćmy że na depth=16  jest 1E+19 różnych układów, czyli 2^63.
Użyjemy 128 bitów. Czyli jeden układ przypada na 2^65 wartości
funkcji skrótu... niestety w tej chwili nie wiem jak dalej pójść tą drogą, może
ktoś dokończy?

Może inaczej: W komputerze jest zapamiętanych około 10^8 = 2^27 układów. Funkcja
skrótu ma 2^128 wartości. Czyli na jeden wpis w pamięci przypada 2^101 wartości
funkcji skrótu. Czyli prawdopodobieństwo kolizji wynosi 1 / 2^101. Prawdopodobieństwo
braku kolizji to 1 - 1 / 2^101. Chcemy znać prawdopodobieństwo braku kolizji w 2^65
prób. Czyli mamy ( 1 - 1 / 2^101 ) ^ ( 2^65 )
Wolfram twierdzi, że to dziesięć dziewiątek po przecinku.
http://www.wolframalpha.com/input/?i=%281+-+1+%2F+2^101%29^%282^65%29

Do tego każde obliczenia przeprowadzimy dwa razy na zupełnie innych funkcjach skrótu.

Proszę prześledź moje rachunki, może się gdzieś pomyliłem. Ale jak nie znajdziesz
błędu, to znaczy, że tak właśnie zrobimy i każdy będzie nas traktował poważnie.

Tak więc do 12 poziomu spokojnie może Ci wystarczyć 64 bity na samo zapisanie numeru układu, a gdzie tu mówić o jakimkolwiek porównywaniu? Poza tym komputer do grania nie potrzebuje wiedzy pewnej, jak przeoczy któreś ustawienie to praktycznie nic się nie dzieje, co najwyżej lekko mu spadnie możliwość wygranej, Ty bierzesz się za coś co ma być wiedzą pewną/naukową, tutaj naprawdę każda pojedyncza wartość ma znaczenie jeśli chcesz być brany poważnie (albo inaczej: żeby wyniki ciężko było podważyć).

Jest jeszcze jeden powód z którego będą nas traktowali poważnie. Jeśli 128 bitów okaże się
za mało, to szybko będą wychodziły różne wyniki dla tych samych układów przy użyciu różnych
funkcji skrótu. Od razu wyjdzie że 128 bitów to za mało i zwiększymy do 196 lub 256.

Do samych obliczeń spokojnie możesz mieć równolegle obie wersje. Zauważ, że w tej chwili bierzesz pod uwagę konieczność wydłużania funkcji hashującej w nieskończoność, więc chyba prościej zapamiętywać cały układ.

Oj nie w nieskończoność. Jeśli dobrze oszacowałem, to 128 bitów da prawdopodobieństwo 99.99999999%, że
wynik będzie poprawny. A my policzymy każdy układ na dwóch różnych funkcjach skrótu.

Co do ostatniego to jak dla mnie zupełnie bezsensowne sprawdzenie. Żeby było 50 ruchów to musiałbyś mieć drzewko
na głębokość 50, jak na razie widzę rozważamy max. 20 ruchów do przodu.

Tak, ale mój program docelowo jest stworzony do innego zadania niż test perft. Test perft to
coś co robię tylko przy okazji, więc musi mieć zaimplementowaną (właściwie to już ma) regułę
50 ruchów. Oczywiście po ostatnich optymalizacjach zakomentuję regułę 50 posunięć i potrójne
powtórzenie. Ale struktury danych nie napiszę od nowa, tak żeby nie uwzględniała tej reguły -
po prostu nie mam na to tyle czasu.

Poza tym ja to proponuję jako sposób zapisu układu na potrzeby porównań (już do samego drzewka
zamiast hasha - w samym hashu też przecież nie sprawdzasz położenia króla ani nic podobnego), i tak
musisz docelowo tę zmianę wprowadzić w funkcji skrótu (zrobić dwa xory przykładowo), tutaj masz
nawet łatwiej, bo tylko robisz proste przypisanie albo nowej wartości pola do figury
(lub dwóch przy biciu lub roszadzie) albo nowej figury do dwóch pól. Uwzględnienie promocji figury w
wersji black/white to może być po prostu najstarszy bit.

Zgadza się, można wprowadzić dodatkową reprezentacje specjalnie na potrzeby hash i powinno działać
szybko. Jednak wersja z xor-ową funkcją skrótu jest już gotowa - nic nie muszę robić, ewentualnie
zwiększę jej długość. Program będzie szybciej gotowy.

Lecz to już 32 bajty i nie wiem czy nie lepiej byłoby zakodować każdą figuę (jest ich przecież tylko 6) na 3 bitach i pamiętać 64 pola po 3 bity, co daje tylko 24 bajty.Nie do końca, masz 12 figur (musisz osobno traktować białe i czarne), więc masz 4 bity na pole, czyli łącznie 32 bajty ;)

Czyli o 16 bajtów więcej niż klucz 128 bitowy ;)
16 bajtów to  niby mało... ale widzę że program działa
wyraźnie szybciej z każdym, nawet małym zwiększeniem
pamięci. A weryfikować i tak i tak trzeba.

Pozdrawiam

[mariotti]

Wcześniej odpaliłem:
threadMemPerft 10 8 250000000 8 1000000
Uzyskałem błędny wynik 69352859710032  w czasie 63547 sekund.


Do programu dodałem (chyba) lepszą funkcję skrótu (nadal 64bity) i
lepszą sumę crc (tą do sprawdzania czy wątki nie zepsuły danych).
Wydałem komendę
threadMemPerft 10 8 250000000 1 0
i uzyskałem tym razem poprawny wynik 69352859712417 w znacznie
szybszym czasie 41515 sekund.

Program u mnie nigdy się nie wywalił, zagadką jest dla mnie, dlaczego
wywala się u Was :/ Myślę że wkrótce się wyjaśni wszystko.

Teraz odpalę takie polecenie:
threadMemPerft 10 8 250000000 8 0
Zobaczymy czy wynik będzie dobry i czy coś przyspieszy

Zachęcam, odpalcie nową wersję u siebie jeszcze raz :)

Pozdrawiam

[edit]
Rozejrzałem się po sieci i widzę że ktoś to zadanie liczył na 4 komputerach w 85h,
ktoś inny w 17 dni. Mój program policzył w 12h, a jest jeszcze przed optymalizacją.

[krzyszp]

Program odpalony za pomocą Twojego skryptu wywala u mnie std:bad_alloc. Po zmniejszeniu przydzielonej pamięci (do 50000000) wystartował, aczkolwiek zakładam znaczne wydłużenie operacji.
Komputer mocno obciążony (akurat wildlife dał próbki), dodatkowo podsystem mocno obciążony operacjami dyskowymi MySQL. Przypominam, że procesor to q6600 na standardowych taktowaniach i Ubuntu64 bit.

[mariotti]

Program odpalony za pomocą Twojego skryptu wywala u mnie std:bad_alloc. Po zmniejszeniu przydzielonej pamięci (do 50000000) wystartował, aczkolwiek zakładam znaczne wydłużenie operacji.
Komputer mocno obciążony (akurat wildlife dał próbki), dodatkowo podsystem mocno obciążony operacjami dyskowymi MySQL. Przypominam, że procesor to q6600 na standardowych taktowaniach i Ubuntu64 bit.

Dzięki, zobaczymy czy tym razem obejdzie się bez błędów.
Pozdrawiam

[Karlik]

Przypuśćmy że na depth=16  jest 1E+19 różnych układów, czyli 2^63.
Użyjemy 128 bitów. Czyli jeden układ przypada na 2^65 wartości
funkcji skrótu... niestety w tej chwili nie wiem jak dalej pójść tą drogą, może
ktoś dokończy?

Ogólnie paradoks urodzin. Nie weryfikowałem obliczeń z wikipedii (nie mam tyle czasu i chęci), ale po podstawieniu do wzoru to żeby prawdopodobieństwo powtórzenia przekroczyło 50% to dla 128-bitowej funkcji skrótu potrzeba 2e+19 układów.

[mariotti]

Ogólnie paradoks urodzin. Nie weryfikowałem obliczeń z wikipedii (nie mam tyle czasu i chęci), ale po podstawieniu do wzoru to żeby prawdopodobieństwo powtórzenia przekroczyło 50% to dla 128-bitowej funkcji skrótu potrzeba 2e+19 układów.

W pamięci komputera mamy jednorazowo małą pulę układów, wynosi ona np. 1E+8.
Nie może być konfliktu w ramach puli, we wszystkich mogą zdarzać się konflikty bez
szkody dla wyniku.
Pozdrawiam

[mariotti]

Spiszmy postępy w pracach dotyczących wydajności :)

Kod [Zaznacz] Rozwiń


----------------------------------------------------------------------------------------
Procesor        | polecenie                                 | wynik            | czas
----------------------------------------------------------------------------------------
Phenom II       | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s
Phenom II       | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s
----------------------------------------------------------------------------------------


Tak więc mamy trzeci wynik dla głębokości 10 ruchów i rekordowy czas 21tys sekund.
Zważywszy że ktoś to liczył przez kilkanaście dni, to chyba niezły wynik ;-)
Program się nie wywalił, zakończył się normalnie.

Pozdrawiam

[Dario666]

A możesz zdradzić jakie były , a jakie są teraz funkcje skrótu i CRC  ;D

[krzyszp]

Wynik dla:

Kod [Zaznacz] Rozwiń

#!/bin/sh
mem=50000000
thr=4
depth=9


(
echo threadMemPerft $depth $thr $mem 1 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 2 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 3 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 4 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 5 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 6 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 7 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 8 0
echo quit
) | ./perft >> out.txt


z Q6600:

Kod [Zaznacz] Rozwiń


nodes:2439530234167 time:6921
nodes:2439530234167 time:5976
nodes:2439530234167 time:5691
nodes:2439530234167 time:5633
nodes:2439530234167 time:5512
nodes:2439530234167 time:5551
nodes:2439530234167 time:5546
nodes:2439530234167 time:5560


[mariotti]

z Q6600:

Kod [Zaznacz] Rozwiń


threadMemPerft $depth $thr $mem 4 0
nodes:2439530234167 time:5512


Dzięki za kolejny test :D
Czyli optymalna wartość drugiego parametru w tym teście wynosiła 4. Widzę że często najlepszą
wartością jest 4 lub 8. Mam nadzieję że to nie z powodu obciążenia komputera :)
Czy mógłbyś odpalić ten sam skrypt, ale ostatnie zera w komendzie zastąpić np. wartością 10000000 - siedem zer?

A możesz zdradzić jakie były , a jakie są teraz funkcje skrótu i CRC

Używam kluczy zobrista, ale wcześniej były mniej starannie generowane. Teraz
wygenerowałem całą pulę kluczy kluczy. Każdemu kluczowi dałem wartość 0x555... Czyli
w kluczach jest taka sama ilość zer i jedynek. Potem 10^7 raz zamieniałem z
sobą losowe bity (tzn losowy bit z puli a nie z jednego klucza). Mam dzięki temu
gwarancję idealnego rozkładu równomiernego - właściwie z pewnym małym wyjątkiem,
ale chyba nie ma sensu wdawać się aż w takie szczegóły. Mam pomysł jak zapewnić
aby klucze były jeszcze lepsze, ale to się sprawdzi za jakiś czas.

Funkcja do sprawdzania czy wątki nie psują sobie danych to zwykły xor (czyli tak naprawdę
nie jest to CRC, a tylko pełni taką samą rolę).  Tutaj też jest lepsze rozwiązanie. Zabrzmi to
jak nonsens, ale wartość CRC (tzn jej odpowiednik) może mieć dlugość zero bitów.
Istnieje na to pewien sposób, za jakiś czas będę go też testował i opiszę wyniki.

Dzięki i pozdrawiam

[krzyszp]

Czy mógłbyś odpalić ten sam skrypt, ale ostatnie zera w komendzie zastąpić np. wartością 10000000 - siedem zer?

Odpaliłem, zobaczymy efekty.

[mariotti]

Są kolejne wyniki

Kod [Zaznacz] Rozwiń


----------------------------------------------------------------------------------------
Procesor        | polecenie                                 | wynik            | czas
----------------------------------------------------------------------------------------
Phenom II       | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s
Phenom II       | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s
Phenom II       | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s
----------------------------------------------------------------------------------------


Niby jest nowy rekord - 12tys sekund. Ciekawy jestem jaka jest losowość tych wyników.
Wątki pracują konkurencyjnie i jeden wątek czasami może zamazać ważne dane dla
drugiego wątku - ale na to też jest pewien sposób, będą kolejne benchmarki :)

Pozdrawiam

[Dario666]

Według mnie optymalną wartością jest 5, bo pierwszy test był wykonywany dla 1, a nie dla 0.  ;D

[mariotti]

Według mnie optymalną wartością jest 5, bo pierwszy test był wykonywany dla 1, a nie dla 0.  ;D

Racja!

[mariotti]

Jest kolejna wersja programu. Zrobiłem eksperyment z innym algorytmem zarządzającym
pamięcią. Niestety... jak na razie nie widzę wyraźnego przyspieszenia ani spowolnienia, ale
może na większych głębokościach da się dobrać tak parametry aby lepiej działało.

Opis polecenia
Wpisujemy threadMemPerft2 i program wyświetli podpowiedź:

using: threadMemPerft2 depth max_thread cnt_packages pack_size best_size
where:
best_size<pack_size

Znaczenie parametrów:
depth - standardowo głębokość przeszukiwania
max_thread - ilość wątków
cnt_packages - ilość paczek z układami
pack_size - ilość układów w jednej paczce
best_size - ilość układów priorytetowych

Przykłady warte przetestowania dla
głębokości 9, czterech wątków i 1GB ram:

threadMemPerft2 9 4 5400000 8 1
threadMemPerft2 9 4 5400000 8 2
threadMemPerft2 9 4 5400000 8 3
threadMemPerft2 9 4 5400000 8 4
threadMemPerft2 9 4 5400000 8 5
threadMemPerft2 9 4 5400000 8 6
threadMemPerft2 9 4 5400000 8 7

threadMemPerft2 9 4 10800000 4 1
threadMemPerft2 9 4 10800000 4 2
threadMemPerft2 9 4 10800000 4 3

Dla 0.5 GB RAM można trzeci parametr zmniejszyć o połowę.

Pozdrawiam

[Karlik]

Tak mi się teraz nasunęło: jak przechowujesz przeliczone hashe? Masz własne drzewo avl lub czerwono-czarne czy korzystasz np. z STLowego?

[sknd]

zapodałem na próbę na e3-1230 v2 3.3ghz:

threadMemPerft2 10 6 32400000 8 7

niech mieli...

[mariotti]

Tak mi się teraz nasunęło: jak przechowujesz przeliczone hashe? Masz własne drzewo avl lub czerwono-czarne czy korzystasz np. z STLowego?

Przechowywanie układów to kluczowa rzecz dla wydajności (tej liniowej, implementacyjnej).
Jest to bardzo ważne zarówno w tym programie (perft), jak i w docelowym, czyli w szachach
samouczących. Więc nie korzystam z żadnego gotowego rozwiązania - wszystko wyrzeźbiłem
ręcznie sam :D

Generalnie mam ciągłą tablicę układów. Następnie liczę adres w tej tablicy:
adres = hash % (size-probe);
Potem przeszukuję mniej/więcej tak:
for( i=0 ; i<probe ; i++ ) {
  if( tablica[adres+i].key == key )
     return tablica[adres+i].nodes;

Kosz tej operacji to pewnie wczytanie tego kawałka do cache, a czas pętli jest
pewnie pomijalny.

To tak w dużym uproszczeniu, bo opis ze szczegółami zająłby ze 4 strony :D
---------------------------------------------------------------------------------------------------------


W kolejnej wersji będą trzy takie tablice i w każdej inna strategia zarządzania
danymi. Strategia - czyli heurystyczne ocenienie tego, co warto pamiętać, a co
można z pamięci już usunąć.

Z niektórych oszacowań wynika, że dobra strategia zarządzania danymi dla
głębokości 16 może przyspieszyć cały proces nawet milion razy. To by znaczyło
że zadanie da się policzyć w 1 rok na 20-100 nowych komputerach. Oczywiście
mogę się mocno mylić... ale jak się nie mylę, to zaliczymy 3 rekordy pod rząd :D


Pozdrawiam

[mariotti]

zapodałem na próbę na e3-1230 v2 3.3ghz:
threadMemPerft2 10 6 32400000 8 7
niech mieli...

Dzięki wielkie! To będzie pierwszy głęboki test nowego algorytmu :D
Pozdrawiam

[krzyszp]

U mnie też mieli.

Ciekawi mnie, że zmieniasz ilość pamięci w przedostatnim poście? Przerobiłem go.sh podając "z palca" 10800000 dla 3 dodatkowych prób...

[mariotti]

Doszedł nowy benchmark z phenoma. Wynik poprawny, czas rekordowy jak na ten procesor.
Pomiary czasu są obarczone dużą losowością (algorytm nie jest deterministyczny), ale
raczje już widać, że korzystne wartości dla ostatniego parametru to bardzo duże liczby,
powyżej 1mln.

Kod [Zaznacz] Rozwiń


----------------------------------------------------------------------------------------
Procesor        | polecenie                                 | wynik            | czas
----------------------------------------------------------------------------------------
Phenom II       | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s
Phenom II       | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s
Phenom II       | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s
Phenom II       | threadMemPerft 10 8 250000000 8 10000000  | 69352859712417ok | 17768s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 10000000  | 69352859712417ok | 12092s
----------------------------------------------------------------------------------------


Pozdrawiam

P.S.
Gdy linux w poleceniu cat /proc/cpuinfo wyświetla że procesor ma 2400MHz, to co to oznacza?
Że w danej chwili procesor ma taką częstotliwość? Czy że w pełnym stresie ma tyle? Mój
Phenom był przetaktowany w dół, bo na pełnej prędkości pobierał nawet 300Wat mocy. Nie
pamiętam już, o ile go spowolniłem. Czy mogę polegać na tych 2400MHz z cpuinfo?

[mariotti]

Ciekawi mnie, że zmieniasz ilość pamięci w przedostatnim poście? Przerobiłem go.sh podając "z palca" 10800000 dla 3 dodatkowych prób...

Ale kto i gdzie zmienia?

Ja mam dwa komputery, jeden mój, a drugi udostępnił mi Rysiu.
Na moim jest mniej ramu, o wpisuję 250mln układów. Na tym od Rysia jest
więcej, to wpisuję 450mln.

Są dwa algorytmy. Był threadMemPerft, a doszedł threadMemPerft2 (dwójka na końcu nazwy).
W drugim algorytmie łączna ilość układów to ilość_paczek * ilosc_układów_w_jednej_paczce.

Przykładowo:
threadMemPerft2 9 4 5400000 8 4
oznacza 5400000 * 8 = 43200000 układów = 1036800000 bajtów ram


threadMemPerft2 9 4 10800000 4 2
oznacza 10800000 * 4 =  43200000 układów = 1036800000 bajtów ram <-- tyle samo


W jednym i  drugim poleceniu jest w pamięci tyle samo układów, ale mocno
zmienia się sposób zarządzania pamięcią. Chodzi o to żeby sprawdzić, czy
lepsza jest większa ilość małych paczek, czy mniejsza większych :D


Parametr ostatni decyduje o zarządzaniu w ramach jednej paczki :)


Pozdrawiam

[krzyszp]

Rozumiem. Po prostu pomyślałem, że chcesz jednym skryptem shella sprawdzić więcej parametrów na tej samej maszynie ;)

No cóż, zobaczymy, czy nie wywali się na mojej maszynie (przypominam, 4GB RAM + trochę roboty w tle).

Próbowałem jeszcze raz odpalić na wirtualce, dając 8 wątków do dyspozycji, niesety, VB się wywala... (Prawdopodobnie mam za mało pamięci, aby to sprawnie obsłużyć i jeszcze pracować na kompie).