W jaki sposób policzyć ile jest wszystkich możliwych "pozycji" w danej grze?
W szachach jest podobno x*10^120 więc bruteforce raczej odpada, szczególnie, że w shogach i go tych "pozycji" będzie znacznie więcej.
Przez pozycję rozumiem nie tylko aktualne rozmieszczenie bierek, ale też to jak do tego doszło, czyli to samo rozmieszczenie przy różnych ruchach wcześniejszych to dwie różne "pozycje".
Czy jest na to lepsza metoda niż bruteforce?
Wszystko zależy od danej gry. Nie ma ogólnego rozwiązania.
W takim razie przyjmijmy, że szukamy tej liczby w szachach.
Dodam, że nie chodzi mi o dokładny algorytm(chociaż byłoby fajnie), ale o jakieś ogólne wskazówki jak do problemu podejść.
Karton_niezalogowany napisał(a)
Przez pozycję rozumiem nie tylko aktualne rozmieszczenie bierek, ale też to jak do tego doszło, czyli to samo rozmieszczenie przy różnych ruchach wcześniejszych to dwie różne "pozycje".
Masz zamiar przechować nieskończoną ilość danych? Zazdroszczę ambicji, ale nie wróżę powodzenia.
Skoro chcesz mieć pełne drzewo gry, to musisz zbudować je w całości. Co innego, gdybyś poszukiwał najlepszego ruchu w danej sytuacji.
To nie ma być wszechwiedzący silnik do gry, tylko jedna liczba więc danych aż tak strasznie dużo nie będzie.
Chcesz jedną liczbę? Proszę bardzo: ∞.
Tak jak somekind zauważył nie możesz brać pod uwagę wszystkim możliwych "dojść" do danej pozycji bo jest ich nieskończenie wiele. Nawet jeśli pominąć by to założenie problem jest baaardzo trudny.
Poszukaj info o liczbie Shannona (Shannon number).
O ile znam szachy to:
3 ruchy w tą i z powrotem to koniec gry
Zdaje się, że 50 ruchów bez bicia piona i koniec gry
Z tego wynika, że liczba musi być skończona.
@adf88
Dzięki
Karton_niezalogowany napisał(a)
O ile znam szachy to:
3 ruchy w tą i z powrotem to koniec gry
Zdaje się, że 50 ruchów bez bicia piona i koniec gry
Z tego wynika, że liczba musi być skończona.
Zasady prowadzenia turniejów szachowych, to nie to samo, co zasady gry (wykonywania ruchów). Owszem, dodając zasadę o braku bicia bierki i ruchu pionem w 50 ruchach, można ograniczyć drzewo gry, ale i tak obawiam się, że jest zbyt wielkie, by je całe wyznaczyć.
Można trochę przyspieszyć, korzystając z już obliczonych wyników dla wszystkich partii do 6 figur, można to ściągnąć stąd: http://kirill-kryukov.com/chess/tablebases-online/ . Przy współczesnych dyskach twardych to może nawet na jednym się zmieści.
Ja nie wiem czemu ludzie śpią na zajęciach z Teorii Złożoności Obliczeniowej i na Matematyce Dyskretnej...
Wycofuję się z tego co napisałem w komentarzach. Przepisy o 50 posunięciach i trzykrotnym powtórzeniu, to fragment zasad gry, ale one nie działają automatycznie. Jeden z graczy musi się domagać uznania partii za remisową (nie jest np. możliwa ingerencja sędziego). Zatem partia może mieć dowolną długość, ilość możliwych partii jest nieskończona.