Które kolekcje dzieł są legalne?
Zbiór szachów (białych i czarnych) nazwij legalnym, jeśli ma miejsce w legalnej partii szachów. Na przykład KQRRBBNNPPPPPPPPkqrrbbnnppppppppto zbiór na początku gry. Wydaje się, że jakikolwiek podzbiór tego (wciąż zawierający dwóch królów) jest również możliwy. Ale czasami możesz mieć wiele awansów, więc na przykład Kkqqqqqqqqjest to możliwe, jeśli czarne promują wszystkie osiem pionów na damy, podczas gdy wszystkie inne figury są zbite.
Które kolekcje dzieł są legalne?
Ta odpowiedź na przypuszczenia / stany MathOverflow bez dowodu, że zbiory prawne to te, które można uzyskać z kolekcji początkowej za pomocą następujących dwóch operacji:
Usuń dowolną figurę (niebędącą królem) i promuj co najwyżej jednego białego i co najwyżej jednego czarnego pionka.
Usuń pionka i awansuj najwyżej jednego pionka tego samego koloru i najwyżej dwa pionki przeciwnego koloru.
Czy ta charakterystyka jest poprawna?
Odpowiedzi
Tak, charakterystyka jest prawidłowa i łącznie jest 58 084 310 zbiorów prawnych.
Aby osiągnąć postęp, potrzebujemy odpowiedniego poziomu dyskursu, unikając utraty dokładności, unikając jednocześnie zagłębiania się w błahostki.
Konieczność i wystarczalność ruchów kasujących
Sugerowano, że konieczne i wystarczające są dwa rodzaje operacji, aby dotrzeć do wszystkich zbiorów prawnych:
(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.
Po pierwsze, te dwa kryteria są konieczne. Aby odblokować plik, musi nastąpić przechwytywanie. Schwytanie oficera pozwoli obu pionkom z pliku na awans. Pionek zbijający pionka z sąsiedniego pliku jest bardziej efektywny, ponieważ pozwala trzem pionkom na awans.
Warunek jest również wystarczający, co widać po podzieleniu planszy na 4 pary teczek. Musimy przyjąć założenie, że królowie mogą trzymać się z dala od akcji. Zobacz później przykład, który bada słuszność tego założenia.
"Prośba o zaopatrzenie"
Może warto przejść do pytania, które kolekcje można osiągnąć w ten sposób:
- Policz liczbę widocznych „nie startujących oficerów” po każdej stronie (królowe poza pierwszą; pozostali oficerowie poza drugą tego typu): N_w i N_b
- Policz liczbę "pionków awol" po każdej stronie: (pionki przekształcone w NSO nie są liczone): A_w & A_b
- Policz liczbę „brakujących oficerów” z każdej strony (brakująca królowa lub innych oficerów mniej niż drugiego tego typu): M_w & M_b
Zatem następujące eleganckie nierówności „podaży i popytu” są niezbędnymi i wystarczającymi kryteriami dla legalnego zbioru:
M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b
Grupując terminy według White & Black, lewa strona to „podaż”, a prawa strona to „popyt”. Podaż jest zawsze nieujemna, więc jeśli popyt wynosi zero lub mniej, jest zawsze zaspokojony. Podobnie podaż 8+ zaspokoi każdy popyt, jaki może się pojawić.
Oto przykład. Czy na szachownicy możemy mieć 18 dam? Tak!
N_w = N_b = 8
(because 8 promoted pawns on each side)
A_w = A_b = 0
(every missing pawn was promoted)
M_w = M_b = 6
(all Rs, Bs & Ns were captured)
M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2
Więc to jest legalne. Podobnie jest z podażą Białych na popyt na Czarnych. Nawet gdybyśmy mieli skoczków na planszy, więc M_b = M_w = 4, nierówność wynosiłaby 4> = 4, więc nadal jest legalna.
Pomijając mat / pat
Niektórzy zastanawiają się, czy taką pozycję można osiągnąć bez mata lub impasu, co jest słusznym pytaniem. Odpowiedź brzmi tak. To jak prośba o udowodnienie, że 450g płatków kukurydzianych zmieści się w pudełku. Powszechnie wiadomo, że wystarczy potrząsnąć opakowaniem, a płatki się uspokoją. W pudełku nie ma zbyt wielu płatków kukurydzianych. Chociaż jest to oczywiście nielegalne, możliwe jest umieszczenie na planszy królów i do 34 (!) Białych królowych bez mata lub impasu. Przy tej gęstości robi się trochę ciasno, ale ten eksperyment myślowy pokazuje, że kiedy mamy do czynienia z zaledwie 18 hetmanami, gdzie ponadto przyjazne matki mogą osłonić się przed wrogimi, istnieje ogromny luz i nie trzeba się martwić o przymusowe partnerki. czy patowa sytuacja. Nawet przy 18 damach szachownica jest bardzo pustym pudełkiem płatków kukurydzianych :-)
Liczenie zbiorów
Skupmy się najpierw tylko na białych jednostkach. Ile jest legalnych białych kolekcji? 8,694. Oto szybki dowód.
Niech k będzie liczbą widocznych awansów na wieżę, skoczka lub gońca (tj. Oficerów poza oryginalnym uzupełnieniem 2 dla dowolnego z tych typów). (Ze względu na symetrię królowe są omówione w kilku akapitach).
Niech v (k) będzie liczbą różnych kombinacji R, N, B, które to osiągają.
v(0) = 27:
because there may be 0-2 remaining of each of R,N,B.
For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:
v(1) = again 27:
3 ways to pick one of R,N,B to be 3;
& 0-2 possible for each of the other two types.
v(2) = 36:
27 ways to have 4,0-2,0-2;
& 9 ways to have 3,3,0-2.
Wtedy pozostałe pionki 8-k mogą nadal być Ps, zamienione w Q lub zbite.
Niech q będzie liczbą widocznych promocji hetmańskich (tj. Hetmanów poza oryginalnym uzupełnieniem 1).
Niech u_k (q) będzie liczbą różnych kombinatorycznych sposobów, w jakie możemy to osiągnąć (w kategoriach przetrwania pionków, królowych i zbitych pionków)
u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.
For q>0, u_k(q) = (9-k-q)
s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.
Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1
So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694
Wszystkie te białe kolekcje są rzeczywiście osiągalne, np. Jeśli Black ma tylko gołego króla, ale w rzeczywistości także w wielu innych sytuacjach: nierówności podaży / popytu nie są zbyt wymagające.
Następne ćwiczenie polega na zliczaniu dla każdej kombinacji N_w, M_w, A_w, ile istnieje białych kolekcji.
Obliczyłem następującą tabelę numerów kolekcji, posortowanych według całkowitej liczby elementów na planszy, jak pokazano w tej tabeli:
To pokazuje dla każdej liczby jednostek od 2 do 32
- v_0: liczba podstawowych kandydatów bez obawy o popyt-podaż,
- v_1: liczba osób, które miały jedną porażkę w porównaniu z popytem na podaż,
- v_2: liczba, która ma podwójny błąd w porównaniu z popytem na podaż.
Aby uniknąć podwójnego liczenia, liczba pozycji prawnych jest obliczana jako v_1 - 2 * v_2 + v_3. Moje obliczenia dokładnie pasują do wcześniejszych wyników Kryukova .
Zauważ, że nie ma porażek, dopóki nie osiągniesz 25 jednostek. Dzieje się tak, ponieważ przy 8 ujęciach można zdobyć wszystkie kolekcje promocyjne kandydatów.
Pytanie otwarte o „dodatkowy kredyt” (praca w toku)
Entuzjaści retro dalej rozróżniają kolor kwadratów, na których są biskupi, ponieważ jest to niezmienne. Ma to duży, widoczny wpływ na potencjalną legalność, jest częścią zasadniczej klasyfikacji podstaw szachowych, a także estetycznym problemem w kompozycji. Odpowiedni termin to „niestandardowi oficerowie” (królowe lub „przyciemniani” biskupi poza pierwszym; wieże lub rycerze poza drugim). Liczba zaginionych funkcjonariuszy opiera się na tych samych 5 typach. Określenie, które dodatkowe nierówności są konieczne i wystarczające do scharakteryzowania zbiorów prawnych, jest obecnie znacznie bardziej skomplikowane.
Najlepszym podejściem może być zastosowanie najpierw dostosowanych nierówności podaży / popytu. Następnie możesz zapytać, ile dodatkowych bić pionków jest wymaganych, aby „popchnąć” niektórych gońców do właściwego odcienia?
Bicie pionka oficera / pionka spowoduje, że partia odpowiednio 2/3 pionków awansuje na tych samych polach tinta, ale wydaje się, że dla każdej takiej partii możemy niezależnie wybrać barwę.