Ilość możliwości w szachach.

Leeq3 · Post autor: **Leeq3** » 15 lut 2010, o 22:11

Ile jest możliwych ustawień pionków (wszystkich) w szachach?
Uwzględniając, że na planszy są minimalnie 2 pionki (króle) i wszystkie inne racjonalne sytuacje.
Chodzi o standardową planszę 8x8.

Dudas · Post autor: **Dudas** » 15 lut 2010, o 22:28

Zdecydowanie za dużo żeby to policzyć

Inkwizytor · Post autor: **Inkwizytor** » 15 lut 2010, o 23:45

Oczywiście można spróbować GRUBEGO oszacowania "z góry" ale nie będzie ono spełniać warunku: "racjonalne sytuacje"

Leeq3 · Post autor: **Leeq3** » 16 lut 2010, o 16:20

A czy takie coś ma sens i jest chociaż bliskie pożądanemu wynikowi?
\(\displaystyle{ {64 \choose 32}+{64 \choose 31}+{64 \choose 30} +...+{64 \choose 2}}\)

Chyba można to też tak zapisać:
\(\displaystyle{ \sum_{n=2}^{32} {64 \choose n}}\)

rathaniel · Post autor: **rathaniel** » 16 lut 2010, o 17:15

Z pewnością jest to dalekie od prawdy. Musisz przecież wziąć pod uwagę, że niektóre figury nigdy nie staną na niektórych polach...

Leeq3 · Post autor: **Leeq3** » 16 lut 2010, o 20:53

Tak, ta sprawa tyczy się pionków i gońców.
Zatem, czy da się napisać (nieważne jak długi) wzór na policzenie wszystkich kombinacji (nawet głupich ruchów)?

Post autor: **Dasio11** » 16 lut 2010, o 21:05

Ale sprawa jest dużo bardziej skomplikowana. Na przykład, 6 pionków teoretycznie może stać w jednym rzędzie, ale tylko wtedy, gdy przeciwnikowi brakuje co najmniej 9 bierek. Niemożliwe są też sytuacje, kiedy królowie zadawany jest szach przez trzy różne figury. Wieże nie mogę być poza pierwszą linią, jeśli żaden pionek jeszcze się nie ruszył. Można tak wymyślać...
Ja na razie widzę tylko jedno, informatyczne wyjście: napisać program, który zaczyna od początkowego ustawienia i przeprowadza wszystkie możliwe gry (a tego będzie mnóstwo...), zapisuje sytuacje, porównuje każde dwie i zlicza każdą raz... Ale takie coś pracowałoby godzinami

Leeq3 · Post autor: **Leeq3** » 16 lut 2010, o 21:24

Dasio11 pisze:napisać program, który zaczyna od początkowego ustawienia i przeprowadza wszystkie możliwe gry

Takiego jeszcze nie było

Dasio11 pisze:Ale takie coś pracowałoby godzinami

Albo latami.
Teraz to w ogóle nie wiem co myśleć. Znalazłem w Internecie jakieś 'pogłoski', że kombinacji jest w dużym przybliżeniu \(\displaystyle{ 10^{72}}\), jest to możliwe?

Dudas · Post autor: **Dudas** » 16 lut 2010, o 21:28

Brzmi wystarczająco dużo żeby było rozsądne, pytanie czy jest to wiarygodne źródło.

Post autor: **Dasio11** » 16 lut 2010, o 22:17

Trochę to dziwne, bo \(\displaystyle{ \frac{64!}{32!} \approx 4.82 \cdot 10^{53}}\) i jest to liczba wszystkich możliwości, a przecież jest jeszcze ogromna ilość sytuacji bezsensownych w sensie reguł gry, no i jeszcze powtórzenia pionków lub figur oraz rotacje planszy

Inkwizytor · Post autor: **Inkwizytor** » 16 lut 2010, o 22:42

Leeq3 pisze:A czy takie coś ma sens i jest chociaż bliskie pożądanemu wynikowi?
\(\displaystyle{ {64 \choose 32}+{64 \choose 31}+{64 \choose 30} +...+{64 \choose 2}}\)

Chyba można to też tak zapisać:
\(\displaystyle{ \sum_{n=2}^{32} {64 \choose n}}\)

Niestety nie. Gdy wybierasz 32 pola zajęte nie uwzględniasz róznego rozstawienia figur na tych konkretnych 32 polach. Skorzystałeś ze wzoru na kombinacje, a w zasadzie (z czysto teoretycznego punktu widzenia i przy grubym szacowaniu z góry) trzeba dołożyć kombinacje z powtórzeniami (z powtórzeniami bo piony są nierozróżnialne oraz wieże, skoczki i gońce są parami) a potem powtórzyć rozumowanie dla 31 figur, dla 30 etc. Niestety zmniejszając ilość zajętych pól wzrasta liczba możliwości bo zależy co i jakiego koloru zostaje zdjęte.

silvaran · Post autor: **silvaran** » 16 lut 2010, o 23:24

Heh, takim GRUUUUBYM oszacowaniem z góry byłoby:
\(\displaystyle{ 33^{64}}\), bo do każdego z 64 pól możemy przyporządkować jedną z 32 figur lub jej brak
Tak naprawdę jest to ograniczenie górne, którego nie da się przekroczyć Na pewnoo nie będzie wiecej kombinacji, niż to co ja napisałem, o tak (dlaczego grube oszacowanie? Bo zakłada nawet tak absurdalne sytuacje, jak planszę wypełnioną samymi białymi królami lub czarnymi gońcami )

Problem jest faktycznie ciężki do rozgryzienia i zapewne wielu użytkowników będzie zarywać noce w celu jego rozwiązania

Leeq3 · Post autor: **Leeq3** » 17 lut 2010, o 06:07

Dasio11 pisze:powtórzenia pionków lub figur oraz rotacje planszy

Inkwizytor pisze:trzeba dołożyć kombinacje z powtórzeniami (z powtórzeniami bo piony są nierozróżnialne oraz wieże, skoczki i gońce są parami) a potem powtórzyć rozumowanie dla 31 figur, dla 30 etc. Niestety zmniejszając ilość zajętych pól wzrasta liczba możliwości bo zależy co i jakiego koloru zostaje zdjęte.

silvaran pisze:\(\displaystyle{ 33^{64}}\), bo do każdego z 64 pól możemy przyporządkować jedną z 32 figur lub jej brak
Tak naprawdę jest to ograniczenie górne, którego nie da się przekroczyć

silvaran pisze:Problem jest faktycznie ciężki do rozgryzienia i zapewne wielu użytkowników będzie zarywać noce w celu jego rozwiązania

Ciekawe czy kiedykolwiek komukolwiek się uda
W takim razie bardzo dziękuję za pomoc. Liczba \(\displaystyle{ 33^{64}}\) jako granica nie do przekroczenia mnie satysfakcjonuje Jeszcze raz dziękuję i pozdrawiam.

Inkwizytor · Post autor: **Inkwizytor** » 17 lut 2010, o 08:36

silvaran pisze:Heh, takim GRUUUUBYM oszacowaniem z góry byłoby:
\(\displaystyle{ 33^{64}}\), bo do każdego z 64 pól możemy przyporządkować jedną z 32 figur lub jej brak

To ja trochę obetnę to oszacowanie. Twoje oszacowanie dopuszcza:
- więcej niż jednego piona na tym samym polu
- mniej niż dwie figury
- niepotrzebne szacowanie z pustym polem bo jeśli ustawisz pionki na 32 polach (maksymalnie) to pozostałe siłą rzeczy pozostaną puste.

Trzeba zrobić skorzystać ze wzoru na wariację bez powtórzeń (choć powtórzenia wystąpią ze względu na nirozróżnialność niektórych figur)

- Numerujemy pola szachownicy od 1 do 64.
- Wybieramy 32 pola z 64 i przypisujemy te pola figurom szachowym na wszystkie sposoby czyli silnia z 32.
\(\displaystyle{ {64 \choose 32} \cdot 32! = \frac{64!}{(64-32)!}}\)
Potem rozpatrujemy sytuację z 31 figurami:
\(\displaystyle{ {64 \choose 31} \cdot 31! = \frac{64!}{(64-31)!}}\)
itd. aż do 2 figur (mogą zostać 2 króle)
\(\displaystyle{ {64 \choose 2} \cdot 2! = \frac{64!}{(64-2)!}}\)

No i sumujemy:
\(\displaystyle{ \sum_{i=2}^{32} \frac{64!}{(64-i)!}}\)

Oczywiście nadal jest to dosyć grube szacowanie bo uwzględnia dosyć absurdalne sytuacje typu:
- tylko jeden król na szachownicy albo ich brak,
- króle stojące obok siebie
- obustronny jednoczesny "szach"
- zmultiplikowany "szach" (2 piony, 2 wieże, 2 skoczki, 2 gońce, hetman)
- figury tylko jednego koloru na szachownicy

Tę ostatnią przypadłość można zlikwidować, ale trzeba by zagnieździć sigmy w sigmach, a z tym już trochę roboty.

A jak wspomniałem już wcześniej "trochę" sytuacji się powtarza bo to szacowanie zakłada rozróżnianie tych samych figur w tym samym kolorze.

silvaran · Post autor: **silvaran** » 17 lut 2010, o 11:11

Inkwizytor pisze:
silvaran pisze:Heh, takim GRUUUUBYM oszacowaniem z góry byłoby:
\(\displaystyle{ 33^{64}}\), bo do każdego z 64 pól możemy przyporządkować jedną z 32 figur lub jej brak
To ja trochę obetnę to oszacowanie. Twoje oszacowanie dopuszcza:
- więcej niż jednego piona na tym samym polu
- mniej niż dwie figury
- niepotrzebne szacowanie z pustym polem bo jeśli ustawisz pionki na 32 polach (maksymalnie) to pozostałe siłą rzeczy pozostaną puste.

Co do drugiego i trzeciego zarzutu: przyznaję się, ale sam to napisałem w swoim poście na swoją obronę Ale pierwszy? Wytłumacz czemu, bo nie rozumiem jakim cudem dwa pionki na jednym polu

Albo najlepiej nie wracajmy do tego, zacząłeś zawężać krąg poszukiwań i tego się trzymajmy