Gimli wrote:

KosiarZ: to wcale nie jest takie proste jak ci się wydaje, zważ na możliwość bez zbić to jest proste ale tak, to przy trzeciem rucu musisz juz wziac pod uwagę możliwość postawienia kamienia w miejscu, gdzie stał już wcześniej jakiś. Policzenie ile jest możliwości wykonania kolejnego ruchu sprawia trochę trudności, bo trzeba brać pod uwagę ilość możliwych zbić co komplikuje sprawę. A co do ilości możliwych do rozegrania partii przez ludzi, to wszystkie są możliwe. pograj na kurniku to się przekonasz. Czasem trafiają się tam ludzie, którzy wykonują najbardziej nieprawdopodobne ruchy.

Prawda, pamiętam jak ktoś sam sobie oczy zamykał po kolei :>

A jeśli chodzi o możliwości to _teoretycznie_ jest to łatwe. Najprościej jest zrobić symulator który wypróbuje wszystkie możliwości, takie coś chyba sam bym umiał. Potrzebny byłby jedynie mocny komp żeby coś takiego udźwignąć Gdyby zagadnienie uprościć (w tym przypadku po prostu poprawić algorytm), byłoby jeszcze szybciej i jeszcze prościej.

KosiarZ wrote:

Potrzebny byłby jedynie mocny komp żeby coś takiego udźwignąć Gdyby zagadnienie uprościć (w tym przypadku po prostu poprawić algorytm), byłoby jeszcze szybciej i jeszcze prościej.

Mocny komputer chyba nie wystarczy.
znak ^ to oczywiście potęga
Kilka faktów:
- możliwość ustawienia (nic o zasadach go nie wiemy) kamieni na planszy gdzie kolejnośc jest istotna to 381! (silnia) czyli 2*3*4*5*...*380*381
Powiedzmy że gra go ma tylko 2*2*2*2*....2*2 = czylli 2^380
Teraz aby zaobrazować tę liczbę. Ile wynosi połowa 2^380 ?
odpowiedz: 2^379 !!!
Więc jaki procent 2^380 stanowi liczba 2^190 ?
odpowiedz - 0,00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 %
z dokładnością do kilku zer.

Powiedzmy że gra go ma 2^190 wariantów gry - jest to dość sensowne szacowanie. w koncu to MALEŃKI procent wszystkich możliwych układów.

Teraz inne liczby:
liczba atomów we wszechświecie 2^80
liczba gier w szachy 2^50 (niektórzy mówią 2^30 inni 2^60 - malo to istotne)
liczba operacji jakie do tej pory wykonały wszystkie komputery (łącznie z superkomputerami) na świecie 2^45 (około)

kolejne pytanie - jakim procentem liczby 2^180 jest liczba 2^45?
mowiąc inaczej

Silny komputer TO ZA MALO.
Albo inny obraz, powiedzmy, że ze chcesz zapisać każdą możliwą partię. Powiedzmy, że potrafisz to zrobić wykorzystując 1kilobajt pamięci (czyli malutkie sgf). Aby wiec zapisać partie potrzebujesz 2^180 kilobajtów pamięci. Czyli około 2^170 megabajtów, czyli 2^160 gigabajtów czyli 2^150 terabajtów... czyli... duzo.
Powiedzmy jednak, że potrafisz to teoretycznie zrobić za pomocą jednego bajta - potrzebujesz wtedy już tylko 2^140 terabajtów. Prawda że duzo mniej? jakieś tysiąc razy.

Radze nie miec złudzeń. Matematyka oferuje liczby większe niż wszechświat, podobnie gry logiczne.

Na koniec mała zagadka - policzcie ile sekund minęło od stworzenia wszechświata (powiedzmy 16 miliardów lat). Następnie policzcie czy wszystkie wariacje go potrafiłby obliczyć komputer, który od początku stworzenia świata wykonywałby około 4 milionów operacji na sekunde (czyli współczesne komputery). Dla uproszczenia powiedzmy, że nasz algorytm jest idealny i zajmuje jedną operacje na sprawdzenie partii.
Jesli to za mało policzcie ile takich komputerów byśmy potrzebowali.
I jeśli to duża liczba - czy by się zmieściły na ziemi (dla ułatwienia komputer zajmuje metr kwadratowy)

Kto policzy?

Jest jeszcze jeden problem. We wszystkich zalozeniach dotyczących możliwych rozkładów gry nie bierze się pod uwagę zasady, że w miejsce zbitego kamienia można wstawić następny. Przyjęcie takiej możliwości drastycznie zwiększa ilość możliwych wariantów. Kamienie wstawione w miejsce zbitych też mogą być zbite, w to miejsca znowu wstawiane kamienie itd. Zapewne też możliwe są partie nieskończenie długie oparte o wzajemne zbicia inne niż potrójne ko.

dede wrote:

Jest jeszcze jeden problem. We wszystkich zalozeniach dotyczących możliwych rozkładów gry nie bierze się pod uwagę zasady, że w miejsce zbitego kamienia można wstawić następny. Przyjęcie takiej możliwości drastycznie zwiększa ilość możliwych wariantów. Kamienie wstawione w miejsce zbitych też mogą być zbite, w to miejsca znowu wstawiane kamienie itd. Zapewne też możliwe są partie nieskończenie długie oparte o wzajemne zbicia inne niż potrójne ko.

Ja w swoich obliczeniach pokazuję, że nawet dla braku tego założenia (zresztą była o nim mowa we wcześniejszych postach) liczba możliwych partii jest duża.

Natomiast problem czy Go jest grą nieskończoną jest dość ciekawy.
Z informatycznego punktu widzenia gra nieskończona to taka, gdzie istnieje taki punkt w grze, od którego jakiekolwiek ruchy sie nie wykona nie uzyska się końca gry.
Jednak nie wydaje mi się aby Go było grą nieskończoną. Jest zasada ko, która mówi, że układ na planszy nie może się powtórzyć. Tu nazwa tej zasady jest myląca, gdyż nie chodzi tylko o ko w standardowym znaczeniu (czyli niemożliwość natychmiastowego odbicia kamienia), ale o dowolne układy. Tak więc zasada mówiąca, że niedozwolony jest ruch w którym układ na planszy się powtórzy, sprawia że nie można mówić o nieskończonej partii.

Przyznam jednak ze tak detalicznie zasad gry nie przejrzałem, więc mogę się mylić. Zaznaczam jednak że nie chodzi mi o deklarajcę zwycięzcy a jedynie o określenie momentu konca gry.

benerit wrote:

Jednak nie wydaje mi się aby Go było grą nieskończoną. Jest zasada ko, która mówi, że układ na planszy nie może się powtórzyć. Tu nazwa tej zasady jest myląca, gdyż nie chodzi tylko o ko w standardowym znaczeniu (czyli niemożliwość natychmiastowego odbicia kamienia), ale o dowolne układy. Tak więc zasada mówiąca, że niedozwolony jest ruch w którym układ na planszy się powtórzy, sprawia że nie można mówić o nieskończonej partii.

Taka zasada to nie ko, tylko superko. Tej zasady nie ma w japońskich zasadach, czyli chyba jest możliwość nieskończonej gry (np. wspomniane już potrójne ko).

w zasadach chinskich potrojne ko jest rownoznaczne z zakonczeniem gry z wynikiem remisowym (brak zwyciescy) nie dawno taka gra miala miejsce (Lee Changho vs Chang Hao grali na wielkim murze chinskim)