Kiedy matowanie jest niemożliwe w pozycji


10

Edytuj To pytanie nie jest duplikatem, jak wspomniano w moim komentarzu. Połączone rzekomo zduplikowane pytanie nie dotyczy ani mojego poniższego pytania nr 1, ani pytania nr 3, ani pytania nr 2, z wyjątkiem stycznej wymienionej w odpowiedzi. Powiązane pytanie dotyczy wystarczającego materiału do krycia, podczas gdy moje pytanie dotyczy przypadków, w których materiał może być wystarczający, ale nie jest to możliwe.


Te przepisy szachów powiedzenia

1.5 Jeśli pozycja jest taka, że ​​żaden z graczy nie może matować króla przeciwnika, gra jest remisowana (patrz Artykuł 5.2.2).

5.2.2 Gra jest losowana, gdy pojawi się pozycja, w której żaden z graczy nie może matować króla przeciwnika dowolną serią legalnych ruchów. Mówi się, że gra kończy się w „martwej pozycji”. To natychmiast kończy grę, pod warunkiem, że ruch dający pozycję był zgodny z art. 3 i art. 4.2 - 4.7.

[Artykuły 3, 4.2–4.7 dotyczą w zasadzie wykonywania legalnych ruchów.]

Jest to interesujące, ponieważ wydaje się być może nie oczywiste, czy warunek ten ma zastosowanie (choć przypuszczalnie rzadki w rzeczywistych grach!). Myślę, że to musiało zostać zbadane wcześniej. Zastanawiam się:

(1) Jak trudne jest obliczeniowo ustalenie, że żadna sekwencja legalnych ruchów nie kończy się na matach ? Czy istnieje lepszy algorytm niż brutalna siła?

(2) Czy znasz ciekawe przykłady pozycji, w których trudno jest człowiekowi stwierdzić, czy ten warunek ma zastosowanie?

(3) Czy istnieją przykłady gier historycznych, w których nie przestrzegano tego prawa z powodu niespełnienia przez graczy i urzędników? Szczególnie interesujące, jeśli gra nie zakończyła się remisem z powodu upływu czasu dla jednego gracza.

Inspirowany https://old.reddit.com/r/chess/comments/8ulfrt/using_fide_rules_if_white_runs_out_of_time_in/

(edytuj) Zobacz także to ściśle powiązane pytanie, w którym zaakceptowana odpowiedź zawiera jeszcze kilka przykładów, w których jest wystarczający materiał do skojarzenia, ale z tej pozycji jest to niemożliwe.


Wątpię, by istniały trudne pozycje dla człowieka, aby dowiedzieć się, czy istnieje partnerka, czy nie.
hoacin

2
@BrianTowers, to pytanie jest ściśle powiązane, ale nie jest duplikatem. Samo pytanie dotyczy czegoś zupełnie innego. Akceptowana odpowiedź dotyczy tego tematu, ale tak naprawdę nie odnosi się do żadnego z (1) - (3), z wyjątkiem może trochę (2).
usul

@hoacin, jestem skłonny się zgodzić, ale powinniśmy być w stanie napisać w tym celu szybkie algorytmy, prawda?
usul

1
Istnieje reguła 9.3.2 ostatnich 50 ruchów każdego gracza zostało wykonanych bez ruchu żadnego pionka i bez żadnego przejęcia. który tworzy remis. W myślach pamiętam analizę komputerową, która pokazała przymusowego partnera w większej liczbie ruchów. Taka analiza jest NP kompletna i dlatego żaden algorytm czasu wielomianowego nie mógł jej znaleźć.
MaxW

1
Cześć @fuxia, dziękuję, ale z szacunkiem się nie zgadzam. (a) Połączone pytanie nie jest duplikatem żadnego z moich pytań. (b) Na to pytanie udzielono doskonałej odpowiedzi w krótkiej, spójnej odpowiedzi i wszystko ułożyło się dobrze - lub gdyby nie spóźnione nieprawidłowe oznaczenie jako duplikat. (c) Mam problem z dostrzeżeniem, w jaki sposób te decyzje o moderacji lub próba upomnienia poprawiają ogólnie stronę lub w szczególności to pytanie.
usul

Odpowiedzi:


7

To, o co pytasz, nosi nazwę „Dead Reckoning” w dziedzinie problemów i problemów retro.

(1) Nie znam algorytmu oprócz tego, o którym wspominał Zaifrun: brute force. Powodem jest to, że można znaleźć dość niesamowite pozycje ...

(2) Sprawdź wiele problemów związanych z Dead Reckoning na stronie Andrew Buchanana . Istnieją również bazy danych problemów ( takie jak ta ), w których można uruchomić wyszukiwanie „DR” w zastrzeżeniu.

Konkretny przykład, który pamiętam, to ten , który tutaj odtwarzam. Autor: Andrew Buchanan, w StrateGems 2002. White to move; jaki był ostatni ruch w tej pozycji? (Pozycja jest martwa, ale ostatni wykonany ruch musiał pochodzić z legalnej i rzeczywistej pozycji - więc można ją jednoznacznie ustalić).

NN - NN

(3) Nawet arcymistrzowie technicznie wykonali ruchy w martwej pozycji! Zobacz stronę François labelle za przykłady.


Dlaczego miałoby dziwić, że GM wykonałby ruch w martwej pozycji? Ponieważ ofercie remisowej powinien towarzyszyć ruch, oczekiwałbym, że MG zaoferuje remis, wykonując dowolny ruch. Jeśli gracz zaakceptuje losowanie, ostatni ruch byłby nieistotny. MG może zwrócić się do arbitra, jeśli oferta losowania zostanie odrzucona, ale w przeciwnym razie po co marnować czas arbitra?
supercat

Nie jest to zaskakujące w tym sensie, że w cytowanych grach nie wpływa na wynik gry. Jednak nadal (bardzo technicznie) naruszeniem zasad jest wykonanie dowolnego ruchu (lub oferty remisu) w martwej pozycji, ponieważ gra już się zakończyła. Nawet GM i arbitrzy tego nie egzekwują (chociaż praktycznie nie ma takiej potrzeby).
Remellion

Gdy gra się skończy, sądzę, że wszystko, co się potem wydarzy, będzie nieistotne, co sprawi, że wszelkie pytania dotyczące legalności również będą nieistotne.
supercat

-4

To naprawdę 3 pytania, nie jestem pewien, czy odpowiadam na wszystko tutaj.

Istnieje jednak „algorytm” dla tego problemu, ale jest on kompletny NP, czyli w zasadzie brutalna siła, chociaż można dokonać pewnych optymalizacji. Jest to w zasadzie algorytm generowania bazy tabeli. Oczywiście przy dużej liczbie elementów staje się to trudne do zastosowania, nawet dla pojedynczej pozycji.

Ta Reguła jest w zasadzie dostępna, więc możesz ubiegać się o remis na pozycjach, które są wyraźnie dobrane, takich jak biskup i król kontra samotny król bez pionka i podobnych pozycji.


czy biskupi mają różne kolory, kolega jest możliwy: k1K5 / b7 / 2B5 / 8/8/8/8/8 w - - 0 1, czy chcesz, abym pokazał ci sekwencję legalnych ruchów, które mogą skończyć się w ta pozycja?
lenik

Tak, ale miałem na myśli 1 króla i biskupa kontra 1 króla. Zredagowałem odpowiedź
zaifrun

Dziwne twierdzenie, że NP jest kompletne. Co jest nw tym przypadku? Czy możesz wyjaśnić, w jaki sposób zredukowałbyś do tego inne problemy związane z NP?
RemcoGerlich,

@RemcoGerlich W szczególności wywoływanie algorytmów NP-complete jest błędem kategorii, mogą występować tylko problemy obliczeniowe . Jednak obliczenie optymalnej strategii dla uogólnionych szachów na planszy n × n jest zakończone WYPŁATĄ. (Wikipedia podaje odniesienie Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214). Większość problemów na płycie 8 × 8 jest „trywialna” w kontekście teorii złożoności, ponieważ można je rozwiązać w stałym czasie. (nawet jeśli ta stała jest zbyt duża, aby ją rozwiązać w praktyce)
Dyskretna jaszczurka
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.