Obliczanie ilości wszytkich możliwych" pozycji" w grach

Obliczanie ilości wszytkich możliwych" pozycji" w grach
0

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?

adf88
  • Rejestracja:ponad 21 lat
  • Ostatnio:prawie 12 lat
0

Wszystko zależy od danej gry. Nie ma ogólnego rozwiązania.

0

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ść.

somekind
Moderator
  • Rejestracja:około 17 lat
  • Ostatnio:około 15 godzin
  • Lokalizacja:Wrocław
0
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.


Po dopracowaniu rozwiązania każdy będzie mógł założyć własny drzewiasty wątek.
adf88
Racja. Jeśli skakać by konikiem w te i wewte to można tak grać do usranej śmierci.
0

To nie ma być wszechwiedzący silnik do gry, tylko jedna liczba więc danych aż tak strasznie dużo nie będzie.

adf88
Aż mi się ciepło zrobiło...
RE
Moderator
  • Rejestracja:około 18 lat
  • Ostatnio:11 miesięcy
1

Chcesz jedną liczbę? Proszę bardzo: ∞.

adf88
  • Rejestracja:ponad 21 lat
  • Ostatnio:prawie 12 lat
0

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

0

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

bogdans
Któryś z graczy musi zgłosić zdarzenie i domagać się remisu. Przy odrobinie złej woli mogą grać w nieskończoność.
somekind
Moderator
  • Rejestracja:około 17 lat
  • Ostatnio:około 15 godzin
  • Lokalizacja:Wrocław
0
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ć.


Po dopracowaniu rozwiązania każdy będzie mógł założyć własny drzewiasty wątek.
bogdans
To o czym pisze @Karton, to są zasady gry. Ilość możliwych partii jest skończona, choć rzeczywiście ogromna.
somekind
Nie jestem pewien w sumie, jak jest z tymi 50 ruchami, coś mi się kojarzy, że w takiej sytuacji zakończenie partii zależy od zgody obu graczy lub decyzji sędziego.
bogdans
W partii towarzyskiej gracze na ogół nie zapisują partii, trudno zatem udowodnić przeciwnikowi, że było już 50 posunięć bez bicia (ruchu pionka) lub że pozycja powtarza się po raz trzeci. A gracz mający przewagę może przeciągać partię licząc na cud lub olśnienie (hetman vs wieża, goniec+skoczek vs nic). 50 ruchów można próbować wyegzekwować, w odpowiednim momencie wyciągamy kartkę, ołówek i stawiamy kreski.
ZJ
  • Rejestracja:około 14 lat
  • Ostatnio:prawie 12 lat
0

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.

Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
2

Ja nie wiem czemu ludzie śpią na zajęciach z Teorii Złożoności Obliczeniowej i na Matematyce Dyskretnej...


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
bogdans
Moderator
  • Rejestracja:ponad 16 lat
  • Ostatnio:prawie 5 lat
0

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.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)