<f...@g...SKASUJ-TO.pl> napisał(a):

> M.M. <m...@g...SKASUJ-TO.pl> napisał(a):
>
> > <f...@g...SKASUJ-TO.pl> napisał(a):
> >
> > > no tez w miare ciekawe; czytales to i kojarzysz co to
> > > robi i gdzie? mniejsze od dooma na oko chyba ze dwa razy,
> > > mozesz opowiedziec co tam sie dzieje to tez mozna pogadac
> >
> > Szczegółów nie rozumiem. Ogólnie ten program ma to samo co
> > każdy program do grania w tego typu grę:
> > 1) przeszukiwanie drzewa gry
> > 2) funkcję oceny pozycji
> > 3) książkę debiutową
> > 4) bazę końcówek
> > 5) do tego ma masę technik usprawniających przeszukiwanie drzewa.
> > Pozdrawiam
> >
>
> a wlasnie jak to drzewo jest 'przeszukiwane'?, dla szachow
> to rosnie bardzo szybko nap powiedzmy ze jest 30 mozliwych
> ruchow bialych na to 30 mozliwych ruchow czarnych, po ktorych
> jest 30 mozliwych ruchow bialych (dla dwu tur naprzod robi sie
> ok miliona mozliwosci) ?
>


w szczegolnosci:
- jak daleko siega ksiazka debiutow (ile tur naprzod w calosci
rozpracowane, ile ew sciezek przeliczone i odlozone)
- o ile moge wyobrazic sobie ze program liczy sobie
ta fuukcje oceny pozycji to chyba powinien tez liczyc ja
'w odwrotna strone' z punktu widzenia przeciwnika (i brac
te ruchy przeciwnika jako bardziej prawdopodobne) ?






--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@g...SKASUJ-TO.pl> napisał(a):

> M.M. <m...@g...SKASUJ-TO.pl> napisał(a):
>
> > <f...@g...SKASUJ-TO.pl> napisał(a):
> >
> > > no tez w miare ciekawe; czytales to i kojarzysz co to
> > > robi i gdzie? mniejsze od dooma na oko chyba ze dwa razy,
> > > mozesz opowiedziec co tam sie dzieje to tez mozna pogadac
> >
> > Szczegółów nie rozumiem. Ogólnie ten program ma to samo co
> > każdy program do grania w tego typu grę:
> > 1) przeszukiwanie drzewa gry
> > 2) funkcję oceny pozycji
> > 3) książkę debiutową
> > 4) bazę końcówek
> > 5) do tego ma masę technik usprawniających przeszukiwanie drzewa.
> > Pozdrawiam
> >
>
> a wlasnie jak to drzewo jest 'przeszukiwane'?, dla szachow
> to rosnie bardzo szybko nap powiedzmy ze jest 30 mozliwych
> ruchow bialych na to 30 mozliwych ruchow czarnych, po ktorych
> jest 30 mozliwych ruchow bialych (dla dwu tur naprzod robi sie
> ok miliona mozliwosci) ?

Pełne drzewo właśnie tak ma. Zdaje się że współczynnik rozgałęzienia
dla szachów średnio wynosi 25 ruchów na węzeł.

Dokładne ilości węzłów dla tysiąca pozycji przeszukanych na głębokość
pięciu lub sześciu ruchów zebrałem kiedyś na tej stronie:

http://brodacz100.republika.pl/perft.htm

Tak zwane układy FEN są po prawej stronie tabelki. Układy fen można
przekopiować i wkleić do toola na tej stronie:

http://www.ee.unb.ca/cgi-bin/tervo/fen.pl

Po wklejeniu widać szachownicę z rozstawionymi bierkami szachowymi, jest
czytelniej niż zakodowana postać :)

Na stronie z brodacza są dwie kolumny "mem perft". Są w nich wyniki
przeszukiwania dla algorytmu wyposażonego w pewne usprawnienie. Usprawnienie
to polega na tym, że w hash-table zostaje zapamiętana ilość pod-węzłów dla
danego węzła. Jeśli dany węzeł pojawi się znowu, to zamiast czasochłonnego
przeszukiwania następuje szybki odczyt z hash-table.

Przykładowo dla pierwszej pozycji zwykłe przeszukiwanie na sześć ruchów w
głąb trwało 51.58s, a w poddrzewie było 675053594 węzłów. Przy zastosowaniu
spamiętywania w hash-table czas spadł do 6.5 a ilość węzłów jaką algorytm
obliczył jest identyczna. Tak więc w tym konkretnym przypadku dało się
czas skrócić około 8 razy.

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@g...SKASUJ-TO.pl> napisał(a):

> w szczegolnosci:
> - jak daleko siega ksiazka debiutow (ile tur naprzod w calosci
> rozpracowane, ile ew sciezek przeliczone i odlozone)
W każdym programie książka debiutowa może być budowana innym algorytmem i
w związku z tym w każdym programie może mieć inną głębokość.
Przykładowo można wziąć bazę rozgrywek dobrych graczy i przekopiować z
niej do programu np. pierwsze 12 ruchów. Wtedy książka będzie sięgała do 12
ruchów... Czasami słyszę że niektóre otwarcia w niektórych programach
sięgają do 28-32 ruchów.

Jedna z ciekawych (ale nie bez kontrowersji) metod budowania książki
jest opisana np. tam:
http://www.cis.uab.edu/hyatt/learning.html


> - o ile moge wyobrazic sobie ze program liczy sobie
> ta fuukcje oceny pozycji to chyba powinien tez liczyc ja
> 'w odwrotna strone' z punktu widzenia przeciwnika (i brac
> te ruchy przeciwnika jako bardziej prawdopodobne) ?

Po pierwsze plansza w takich grach jak szachy czy warcaby jest symetryczna.
Jeśli w danym układzie prawem do ruchu dysponują np. czarne, to można
zrobić lustrzane odbicie planszy i policzyć ocenę tak, jakby prawo
do ruchu miały białe.

Po drugie w takich grach wygrana jednej strony oznacza przegraną drugiej.
Więc jeśli ocena dla danego układu dla białych wynosi np. +45 to można
przyjąć że dla czarnych wynosi -45. Tzw gra o sumie zerowej.

Pozdrawiam







--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

M.M. <m...@g...SKASUJ-TO.pl> napisał(a):

> <f...@g...SKASUJ-TO.pl> napisał(a):
>
> > M.M. <m...@g...SKASUJ-TO.pl> napisał(a):
> >
> > > <f...@g...SKASUJ-TO.pl> napisał(a):
> > >
> > > > no tez w miare ciekawe; czytales to i kojarzysz co to
> > > > robi i gdzie? mniejsze od dooma na oko chyba ze dwa razy,
> > > > mozesz opowiedziec co tam sie dzieje to tez mozna pogadac
> > >
> > > Szczegółów nie rozumiem. Ogólnie ten program ma to samo co
> > > każdy program do grania w tego typu grę:
> > > 1) przeszukiwanie drzewa gry
> > > 2) funkcję oceny pozycji
> > > 3) książkę debiutową
> > > 4) bazę końcówek
> > > 5) do tego ma masę technik usprawniających przeszukiwanie drzewa.
> > > Pozdrawiam
> > >
> >
> > a wlasnie jak to drzewo jest 'przeszukiwane'?, dla szachow
> > to rosnie bardzo szybko nap powiedzmy ze jest 30 mozliwych
> > ruchow bialych na to 30 mozliwych ruchow czarnych, po ktorych
> > jest 30 mozliwych ruchow bialych (dla dwu tur naprzod robi sie
> > ok miliona mozliwosci) ?
>
> Pełne drzewo właśnie tak ma. Zdaje się że współczynnik rozgałęzienia
> dla szachów średnio wynosi 25 ruchów na węzeł.
>
> Dokładne ilości węzłów dla tysiąca pozycji przeszukanych na głębokość
> pięciu lub sześciu ruchów zebrałem kiedyś na tej stronie:
>
> http://brodacz100.republika.pl/perft.htm
>
> Tak zwane układy FEN są po prawej stronie tabelki. Układy fen można
> przekopiować i wkleić do toola na tej stronie:
>
> http://www.ee.unb.ca/cgi-bin/tervo/fen.pl
>
> Po wklejeniu widać szachownicę z rozstawionymi bierkami szachowymi, jest
> czytelniej niż zakodowana postać :)
>
> Na stronie z brodacza są dwie kolumny "mem perft". Są w nich wyniki
> przeszukiwania dla algorytmu wyposażonego w pewne usprawnienie. Usprawnienie
> to polega na tym, że w hash-table zostaje zapamiętana ilość pod-węzłów dla
> danego węzła. Jeśli dany węzeł pojawi się znowu, to zamiast czasochłonnego
> przeszukiwania następuje szybki odczyt z hash-table.
>
> Przykładowo dla pierwszej pozycji zwykłe przeszukiwanie na sześć ruchów w
> głąb trwało 51.58s, a w poddrzewie było 675053594 węzłów. Przy zastosowaniu
> spamiętywania w hash-table czas spadł do 6.5 a ilość węzłów jaką algorytm
> obliczył jest identyczna. Tak więc w tym konkretnym przypadku dało się
> czas skrócić około 8 razy.
>

- no ale normalnie pewnie nie przeszukuje sie kompletnie wszerz
tylko wybiorczo w glab, nie?
- tu jest 6 ruchow czy 6 tur ?

nie jest to az takie hiperzlozone, szczerze mowiac, jak sie
ma troche pojecia (i umie programowac wogole), jest tez
dosyc ciekawe

aczkolwiek, sam jak mowielem bardziej interesuje sie grami
'video' z tego chyba przede wszystkim powodu ze mz lepiej sie
w nie gra,

co do szachow to jedyny program szachowy jaki kojarze to
'collosus ches iles tam zero' (2.0? 3.0?) - dolaczany na
cartridge'u do commodore (fajne bylo to ze jak mu sie
ustawilo sekunde czasu max na myslenie to slabo grał (!))








--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

M.M. <m...@g...SKASUJ-TO.pl> napisał(a):

> <f...@g...SKASUJ-TO.pl> napisał(a):
>
> > w szczegolnosci:
> > - jak daleko siega ksiazka debiutow (ile tur naprzod w calosci
> > rozpracowane, ile ew sciezek przeliczone i odlozone)
> W każdym programie książka debiutowa może być budowana innym algorytmem i
> w związku z tym w każdym programie może mieć inną głębokość.
> Przykładowo można wziąć bazę rozgrywek dobrych graczy i przekopiować z
> niej do programu np. pierwsze 12 ruchów. Wtedy książka będzie sięgała do 12
> ruchów... Czasami słyszę że niektóre otwarcia w niektórych programach
> sięgają do 28-32 ruchów.
>
> Jedna z ciekawych (ale nie bez kontrowersji) metod budowania książki
> jest opisana np. tam:
> http://www.cis.uab.edu/hyatt/learning.html
>
>
> > - o ile moge wyobrazic sobie ze program liczy sobie
> > ta fuukcje oceny pozycji to chyba powinien tez liczyc ja
> > 'w odwrotna strone' z punktu widzenia przeciwnika (i brac
> > te ruchy przeciwnika jako bardziej prawdopodobne) ?
>
> Po pierwsze plansza w takich grach jak szachy czy warcaby jest symetryczna.
> Jeśli w danym układzie prawem do ruchu dysponują np. czarne, to można
> zrobić lustrzane odbicie planszy i policzyć ocenę tak, jakby prawo
> do ruchu miały białe.
>
> Po drugie w takich grach wygrana jednej strony oznacza przegraną drugiej.
> Więc jeśli ocena dla danego układu dla białych wynosi np. +45 to można
> przyjąć że dla czarnych wynosi -45. Tzw gra o sumie zerowej.
>

nie o to mi chodzi, chodzi o to czy kojarzysz sam algorytm
'przeszukiwania' drzewa, na pewno trzeba przeszukiwac
jakies prawdopodobne ruchy wiec trzeba miec kryterium
prawdopodobienstwa zarowno swoich posuniec jak i
posuniec przeciwnika - przeszukania latwo mi sobie
wyobrazic ale jak nie bardzo kojarze jak wygladac moze
sam algorytm wyboru










--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@g...SKASUJ-TO.pl> napisał(a):

> M.M. <m...@g...SKASUJ-TO.pl> napisał(a):
>
> > <f...@g...SKASUJ-TO.pl> napisał(a):
> >
> > > w szczegolnosci:
> > > - jak daleko siega ksiazka debiutow (ile tur naprzod w calosci
> > > rozpracowane, ile ew sciezek przeliczone i odlozone)
> > W każdym programie książka debiutowa może być budowana innym algorytmem i
> > w związku z tym w każdym programie może mieć inną głębokość.
> > Przykładowo można wziąć bazę rozgrywek dobrych graczy i przekopiować z
> > niej do programu np. pierwsze 12 ruchów. Wtedy książka będzie sięgała do
12
> > ruchów... Czasami słyszę że niektóre otwarcia w niektórych programach
> > sięgają do 28-32 ruchów.
> >
> > Jedna z ciekawych (ale nie bez kontrowersji) metod budowania książki
> > jest opisana np. tam:
> > http://www.cis.uab.edu/hyatt/learning.html
> >
> >
> > > - o ile moge wyobrazic sobie ze program liczy sobie
> > > ta fuukcje oceny pozycji to chyba powinien tez liczyc ja
> > > 'w odwrotna strone' z punktu widzenia przeciwnika (i brac
> > > te ruchy przeciwnika jako bardziej prawdopodobne) ?
> >
> > Po pierwsze plansza w takich grach jak szachy czy warcaby jest
symetryczna.
> > Jeśli w danym układzie prawem do ruchu dysponują np. czarne, to można
> > zrobić lustrzane odbicie planszy i policzyć ocenę tak, jakby prawo
> > do ruchu miały białe.
> >
> > Po drugie w takich grach wygrana jednej strony oznacza przegraną drugiej.
> > Więc jeśli ocena dla danego układu dla białych wynosi np. +45 to można
> > przyjąć że dla czarnych wynosi -45. Tzw gra o sumie zerowej.
> >
>
> nie o to mi chodzi, chodzi o to czy kojarzysz sam algorytm
> 'przeszukiwania' drzewa, na pewno trzeba przeszukiwac
> jakies prawdopodobne ruchy wiec trzeba miec kryterium
> prawdopodobienstwa zarowno swoich posuniec jak i
> posuniec przeciwnika - przeszukania latwo mi sobie
> wyobrazic ale jak nie bardzo kojarze jak wygladac moze
> sam algorytm wyboru
>

o ile kojarze szachy to to jest gra w ktorej (przynajmniej jak
ja gralem) glownym elementem jest stwarzanie zagrozenia (zwlaszcza
dla nieoslonietych figur) np koniem dla gonca czy wiezy, wiec
pewnie po tych zagrozeniach sie liczy te wybory

- niby umiem grac z tym ze nigdy nie lubilem kombinowac
i zasadniczo z kim nie gralem (troche z ojcem czy pozniej
np w karty czy strategie z kumplami tez troche) to zawsze
przegrywam, a ostatnimi czasy to wogole nie mam checi w to
grac - za to kiedys gralem w pewien ordzaj fajnej karcianki
(na kompie, astral costam) gdzie wystawialo sie np dżiny
przeciw szkieletom, regenaratora kontra zombie itd (parami
po piec w pionowych kolumnach i to byla swietna gra)







--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

> co do szachow to jedyny program szachowy jaki kojarze to
> 'collosus ches iles tam zero' (2.0? 3.0?) - dolaczany na
> cartridge'u do commodore (fajne bylo to ze jak mu sie
> ustawilo sekunde czasu max na myslenie to slabo grał (!))
>

ustalilem ze byl to collosus chess 2.0 razem z nim na
cartridge'u byly international soccer i sylicon syborgs
ta sylicon syborgs to byla dosyc niesamowita gra, nie
za bardzo moglem sie polapac o co w tym chodzi ale
lubilem grac,

http://www.c64.com.pl/index.php/supergames.html

(jakby mi sie udalo w najblizszych latach zrobic jakies
gierki o tak niesamowitym klimacie bylbym zadowolony) :(


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@g...SKASUJ-TO.pl> napisał(a):
> - no ale normalnie pewnie nie przeszukuje sie kompletnie wszerz
> tylko wybiorczo w glab, nie?
> - tu jest 6 ruchow czy 6 tur ?

Jeśli przeszukujemy po to aby wyznaczyć optymalny ruch, a nie po to
aby sprawdzić ile drzewo ma pod-węzłów, to okazuje się że pewnych
gałęzi nie trzeba przeszukiwać. O niektórych gałęziach z jakimś
prawdopodobieństwem można powiedzieć że są 'bezsensowne' bez konieczności
przeszukiwania. Wykorzystuje się do tego tzw techniki przycinania. Różne
techniki mają różną skuteczność. Niektóre techniki dają blisko 100% pewności
że dalsze przeszukiwanie nie ma sensu.

W niektórych grach taką przykładową techniką jest null-move. Wykonujemy
dwa ruchy pod rząd nie dając przeciwnikowi do wykonania ani jednego
ruchu. Jeśli w dwóch ruchach nie udało się nam uzyskać wyraźniej przewagi
to wnioskujemy że gałąź jest tak zła, że nie ma sensu jej analizować.
Zwykle wykonujemy ruchy które poprawiają naszą sytuację, więc jeśli w
dwóch ruchach nie udało się poprawić, to prawdopodobnie trafiliśmy na
przegraną pozycję.

Czasami mówi się że dzisiejsze programy szachowe mają średni poziom
rozgałęzienia cztery ruchy na węzeł. Nie lubię tego oszacowania, ponieważ
moim zdaniem jest zbyt uproszczone.


> nie jest to az takie hiperzlozone, szczerze mowiac, jak sie
> ma troche pojecia (i umie programowac wogole), jest tez
> dosyc ciekawe
Tak się wydaje że to nie jest takie trudne. Np. mój program prawie w
każdej wersji miał jakiś drobny błąd w generatorze ruchów. Jeśli nie
wspomagamy się zewnętrznymi narzędziami, to trzeba napisać 3-4 wersje
najlepiej od zera i sprawdzić czy dają takie same wyniki. A przecież
generator ruchów to jedna z najprostszych rzeczy w programie szachowym :)

Ponadto mój program nie miał nawet szans na dobrą grę, ponieważ nie
wiedziałem o istnieniu choćby takiej techniki jak qsearch. Technika ta polega
na tym, analizuje tylko ważne ruchy plus jeden sztuczny ruch którym
jest pas. W qsearch gracz ma prawo do wykonania ważnego ruchu (np.
bicia, albo promocji pionka na damę) i ma prawo do spasowania.

Takich technik jak qsearch jest więcej. Nie sposób aby jeden programista w
ciągu jednego życia wymyślił je wszystkie sam. Trzeba skądś się dowiedzieć
przynajmniej o najważniejszych technikach. Wtedy się zgodzę że napisanie
podstawowego programu do grania w szachy nie jest takie hipertrudne.

Jednak podstawowy program od dobrego programu dzieli przepaść. Przerobienie
podstawowego programu na bardzo dobry program jest zawsze hipertrudne.
Trudność ma kilka swoich źródeł:
1) Techniki często poprawiają grę minimalnie, jeśli są napisane niezbyt
wydajnie to stosowanie ich się nie opłaci.
2) W związku z pierwszym trzeba napisać 50-100 technik bez błędów przy
zachowaniu bardzo wydajnego kodu, często stosuje się wstawki w asemblerze.
3) Techniki często z sobą nie współpracują, z dodaniem każdej nowej techniki
trzeba przeanalizować wszystkie pozostałe. Jeśli technika w jakiś
etapach gry, albo w jakiś układach, albo w jakiś stanach przeszukiwania
drzewa gry nie działa, to trzeba te sytuacje odfiltrować ifami.
4) Każda technika ma kilka do nawet kilkudziesięciu parametrów. Łącznie
w programie szachowym może być np. 200 bardzo ważnych parametrów i
2tys mniej ważnych. Trzeba ustalić wartości tych parametrów w pobliżu
optimum.

> aczkolwiek, sam jak mowielem bardziej interesuje sie grami
> 'video' z tego chyba przede wszystkim powodu ze mz lepiej sie
> w nie gra,
I lepiej sprzedaje :)

> co do szachow to jedyny program szachowy jaki kojarze to
> 'collosus ches iles tam zero' (2.0? 3.0?) - dolaczany na
> cartridge'u do commodore (fajne bylo to ze jak mu sie
> ustawilo sekunde czasu max na myslenie to slabo grał (!))

Jeśli masz ochotę, to może spróbuj pograć z tym programem:

http://www.tckerrigan.com/Chess/TSCP

To jest podstawowy program szachowy, a właściwie to jest
minimalny program szachowy - ale co ważne poprawny i
kompletny i bez błędów. Jest dostępny z dobrze okomentowanym
źródłem. Można mu regulować głębokość przeszukiwania drzewa gry.
Ustaw np. na jeden ruch i zagraj. Potem na dwa ruchy... :)

Można do tego programu podpiąć GUI, ale ja wolę tekstowy i
na zwykłej planszy przestawiać bierki :)

Pozdrawiam

P.S.
A na stronie brodacza głębokość 6 oznacza że w sumie obie strony zrobiły 6
ruchów, czyli każda ze stron po 3 ruchy.


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

>
> http://www.tckerrigan.com/Chess/TSCP
>

no to jest dosyc ciekawe (ciekawe jest np hall of
shame ) to co by mi sie gigantycznie przydalo to
cos takiego tylko nie dotyczacego programu szachowego
a minimalnego kompilatora c (najlepiej z jakims ciezkim
komentarzem albo wewn tutorialem zeby dalo sie to
jakos latwo przeczytac)






--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@g...SKASUJ-TO.pl> napisał(a):

> >
> > http://www.tckerrigan.com/Chess/TSCP
> >
>
> no to jest dosyc ciekawe (ciekawe jest np hall of
> shame ) to co by mi sie gigantycznie przydalo to
> cos takiego tylko nie dotyczacego programu szachowego
> a minimalnego kompilatora c (najlepiej z jakims ciezkim
> komentarzem albo wewn tutorialem zeby dalo sie to
> jakos latwo przeczytac)

Trudno przecenić wartość edukacyjną minimalnych programów i
prostych przykładów. Osobiście sporo się nauczyłem właśnie
na źródłach TSCP. Dzięki temu mogłem czytać źródła bardziej
zaawansowanych programów. Jeśli chciałbyś się zainteresować
budową kompilatorów to pewnie rozpoczęcie nauki od czytania
najprostszych źródeł byłoby również dobrą lekcją. Ale język
C, nie wspominając o C++ to dość duże bydle. Może warto
poszukać jakiegoś kompilatora/parsera również dla minimalnego
języka?

Pozdrawiam




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry