Gdybym zajął legalną pozycję w szachach, w jakim stopniu silnik mógłby wypracować poprzednie ruchy? [w niektórych innych grach planszowych, takich jak Othello, taką rekonstrukcję gry można łatwo wykonać za pomocą silnika.]
Gdybym zajął legalną pozycję w szachach, w jakim stopniu silnik mógłby wypracować poprzednie ruchy? [w niektórych innych grach planszowych, takich jak Othello, taką rekonstrukcję gry można łatwo wykonać za pomocą silnika.]
Silniki takie jak Stockfish i Komodo nie są w stanie wypracować poprzednich ruchów, ponieważ nie do tego są zaprogramowane.
Jednak jest znikome prawdopodobieństwo, że ktokolwiek może kiedykolwiek zaprogramować działający silnik legalne poprzednie ruchy. Logika ustalenia, czy ewentualny poprzedni ruch jest legalny, czy nie, jest niezwykle trudna.
Na początek jak wypisujemy możliwe poprzednie ruchy?
Ewentualne poprzednie ruchy, zwane cofnięciami (jeśli na sekundę zignorujemy legalność), można łatwo znaleźć algorytmicznie - każda figura cofa się, gdy porusza się w szachach do przodu (z wyjątkiem pionków), a także mogą „odciągnąć” jednostkę wroga - pionka, skoczka goniec, wieża lub królowa. na przykład wBc4 bierze pionka na f7 w odwrotnej kolejności, wygląda jak goniec poruszający się z f7 do c4, z czarnym pionem pojawiającym się na f7.
Piony poruszają się o 1 pole do tyłu i odbijają o jedno pole ukośnie do tyłu. (Możesz dowiedzieć się, jak wygląda podwójny krok.)
W odniesieniu do czeków można wycofać się do czegoś, co wygląda jak „czek” w zwykłych szachach i zawsze należy się wycofać, aby nigdy nie zostawiać przeciwnika w "czek". (Więc jeśli poprzedni przykład wBc4xbPf7 sprawdza czarnego króla na e8, to białe musiały wycofać gońca, aby usunąć „szach”.)
Rozrzucenie roszady jest łatwe do wizualizacji (i dodaje ograniczenie, że lub wieża nie może się ponownie wycofać). Nie-en-passant jest trudny do opisania i stanowi podstawę wielu klasycznych problemów retro. Brak promocji znów jest łatwy do wizualizacji.
Zatem wyliczenie wszystkich potencjalnych wycofań nie jest trudne z programistycznego punktu widzenia. Niezwykle trudną częścią jest określenie, które wycofanie jest legalne. Jest wiele powodów, dla których wycofanie się nie może być legalne, od prostych (na przykład wycofanie niezbicia, aby zostawić 9 czarnych pionków na szachownicy) po bardzo zawiłe (por. większość problemów z analizą wsteczną, patrz róg Retro).
Zobacz na przykład ten problem autorstwa Troitsky'ego na Chess.SE i towarzyszącą mu odpowiedź. Wiele logiki wymaga udowodnienia, że w rzeczywistości istnieje tylko jedno legalne wycofanie się czarnymi, a to nie jest oczywiste, obejmuje liczenie bić pionków, biorąc pod uwagę ich kolejność i ograniczenia tempa.
Aby napisać silnik wykonując takie zadanie, trzeba umieć wyjaśnić ludzką logikę stojącą za tym w taki sposób, aby komputer mógł ją wykonać. Wydaje się to po prostu niemożliwe, biorąc pod uwagę, że „legalność wycofań” jest o wiele bardziej mglista niż „legalność posunięć do przodu w szachach”.
Obecne wyszukiwarki w ogóle tego nie potrafią. Obliczanie wstecz różni się znacznie od obliczania do przodu. Kawałki powstają zamiast zostać zabrane.
Ale z pewnością możesz dostosować silniki, aby móc dobrze wykonywać to zadanie.
Postanowiłem rozszerzyć to na bardziej ogólny przegląd zastosowania silników do różnych podgatunków retro.
Silniki szachowe (np. Stockfish) są dobre w wypróbowywaniu wszystkich ruchów w przyszłości w pozycji, ale słynie z złej abstrakcji ogólnych cech, takich jak fortece.
W ten sam sposób możesz łatwo spróbować cofnąć możliwe najmniejsze ruchy, po prostu zmuszając pionki do ruchu do tyłu, wykluć przeciwne elementy zamiast je przejmować i uciekać z dala od przeciwnych królów, którzy ich „sprawdzają”. Trudność polega na wyodrębnieniu ogólnych cech, aby dowiedzieć się, czy pozycję można wyprowadzić z pozycji wyjściowej. Rozróżnienie między ruchami prawnymi a pozycjami legalnymi jest tutaj kluczem i jest to rozróżnienie również w przepisach FIDE.
Gry sprawdzające Jedna domena retro, która odniosła wielki sukces w zakresie silników to gry dowodowe. Są jak problemy retro, z tym wyjątkiem, że otrzymałeś dodatkowe informacje o spodziewanej liczbie ruchów. To pojęcie zegara ogromnie upraszcza proces retro, w podobny sposób, w jaki można wydedukować gry Othello, ponieważ zna się dokładną liczbę ruchów. Niektórzy uważają je za warunki do przodu, ponieważ zaczynasz od tablicy gry i możesz grać do przodu, ale są one ogólnie postrzegane jako retros. Wiodącymi silnikami w tej przestrzeni są Natch, Euclide, Popeye i Jacobi dla problemów z wróżkami.
Ogólne retros Jest mniej silników do ogólnych problemów retro. Działają one, umożliwiając rozwiązującemu określenie ograniczeń, które są wywnioskowane przez człowieka rozwiązującego. Jacobi robi to w ramach pewnej teoretycznej liczby ruchów, ale najlepsze, co znam, to enigmatyczny Rawbats, narzędzie używane tylko przez jego twórcę Mario Richtera i znane tylko z wyników w zwiększaniu umiejętności programisty.
Retraktory dla współpracowników Dla kogoś, kto potrafi skomputeryzować, istnieje duża szansa na zbudowanie prostego mechanizmu wycofywania, który po prostu próbuje wycofać ostatnie ruchy, nie martwiąc się o globalną legalność, a następnie gra naprzód jak zwykły silnik problemów. Taki silnik, w połączeniu z odrobiną ludzkiego zdrowego rozsądku, byłby w stanie zweryfikować setki kompozycji retraktorów pomocniczych, których obecnie nie można przetestować.
Na koniec chcę wspomnieć o dwóch obszarach retros, które są mniej podatne na silnik napaść.
Problemy oparte na konwencjach Jedna z nich to domena konwencji retro: roszady, en passant i innych pokrewnych zasad. Nie wykonano połączenia logicznego systemu rozumowania z silnikiem szachowym, aw niektórych przypadkach istnieją głębokie niejednoznaczności w samych konwencjach. Ta praca jest zwykle pozostawiona człowiekowi do rozwiązania, ale w zasadzie, jeśli konwencje mogłyby być logicznie ugruntowane, byłby to interesujący temat badawczy.
Retraktory obronne Inny trudny gatunek kompozycji retro zawiera wysoce technicznych przeciwników defensywnych różnego rodzaju. Zasadniczo polegają one na grze w szachy wstecz w konkurencyjny sposób, a kwestie legalności pozycji są zwykle kluczem, bez którego problemy kompozycje nie mają sensu.
Zasadniczo odpowiedź brzmi „nie” i prawdopodobnie nigdy się to nie zmieni.
Mam zamiar porównać to z podstawami tabel, ponieważ wydaje się to istotne ze względu na sposób ich wykonania w porównaniu z pytaniami w Twoje pytanie. Zdaję sobie sprawę, że różnią się pod pewnymi innymi względami.
Podstawy tabel, które są bazami danych idealnej gry końcowej, są obliczane dokładnie w taki sposób, o jaki pytasz: Zaczynają od pozycji końcowej i wracają do możliwa oryginalna pozycja. Oczywiście rozpoczynają się od końca gry, kiedy na planszy pozostaje tylko 7 lub mniej pionów, w tym królów. Możesz zobaczyć, że jest to DUŻO łatwiejsze niż twoje pytanie, ale nadal jest to OGROMNE przedsięwzięcie w zakresie mocy obliczeniowej, jaką obecnie znamy.
Mając tylko 7 elementów, zajmuje to nie tylko niesamowitą ilość czas na rozwiązanie nawet jednej pozycji, a przechowywanie wszystkich 7-osobowych baz tabel zajmuje WYSOKIE 140 terabajtów. To zajęło lata. Możesz zobaczyć, jak dodanie jeszcze kilku kawałków rośnie wykładniczo. Ze względu na ekstremalne koszty mocy obliczeniowej nie jesteśmy nawet blisko uruchomienia 8-osobowych baz tabel, a szacuje się, że przechowywanie ich w całości zajęłoby ponad 10 petabajtów. Nawet jeśli nie próbujesz rozwiązać każdej pozycji z 32 figurami, możesz zobaczyć, jak próba przejścia z końca gry z powrotem do pierwotnej pozycji wyjściowej 32-częściowej jest niewykonalna.
Jedyne pytanie to czy mogliby zaprogramować ludzką skłonność do grania na różne sposoby, aby przyciąć poszukiwania, ale bardzo wątpię, że nawet wtedy liczby są ogromne.
Nie
Przede wszystkim silniki (i wszyscy) grają przeciwko innym (graczowi, innemu silnikowi, a nawet sobie w innym kolorze). Mogą odgadnąć prawdopodobny ruch (y) innego aktora, ale nie posuwają się za daleko. Wybierają dobry ruch, a ruch drugiego aktora pomaga im zawęzić zakres możliwości.
Odwrócenie pozycji w grze to inny problem, ponieważ musisz wiedzieć ruchy obu graczy aby go rozwiązać. Nie wiesz, czy posunięcia były dobre, czy złe, a nawet czy miały sens, wiesz tylko, że były legalne. W tym sensie przebudowa gry byłaby bardziej zbliżona do „rozwiązywania” szachów (uzyskania wszystkich możliwych rozwiązań gry z pozycji startowej).
Dodatkowo, nawet jeśli wzmocnisz wymagania („zgadnijmy, że każdy gracz zawsze wykonywał ruch z najlepszą analizą obecnego silnika ”) masz wiele sytuacji, w których pojawia się kilka możliwych stanów poprzedników. Po prostu zgadnij
rnbqkbnr / pp1p1ppp / 8/8 / 3p / N7 / PPP1PPPP / R1B1KBNR w - - 1 13
Czy to pochodzi z?
[fen ""] 1. d3 c5 2. d4 e5 3. Na3 exd4 4. Hxd4 cxd4
Czy od?
[fen ""] 1. d3 c5 2. d4 e5 3. Na3 cxd4 4. Hxd4 exd4
W obu przypadkach ostatni ruch czarnych jest najsilniejszy, ale nie pozwala ci zdecydować, który był poprzedni sytuacja. W miarę jak analiza sięga wstecz, możliwości mnożą się.
Jak powiedzieli inni, obecne silniki nie są do tego przeznaczone. Ale z teoretycznego punktu widzenia informatyki jest to „możliwe”, chociaż prawdopodobnie niewykonalne.
Tak jak „naprzód” silnik szachowy może przeszukiwać co najwyżej kilka (dziesiątki?) Ruchów w przyszłości (ponieważ możliwości eksplodują wykładniczo), silnik wstecznego silnika cierpiałby z powodu tego samego ograniczenia.
Myślę, że wyliczenie wszystkich legalnych ruchów wstecz z danego stanu tablicy jest stosunkowo proste (w przeciwieństwie do tego, co powiedzieli inni), ale liczba możliwości eksplodują wykładniczo im dalej się cofamy.
W każdym razie, ponieważ liczba stanów tablicy jest skończona, teoretycznie jest "możliwe" napisanie takiego programu: mając wystarczająco dużo czasu, komputer przeanalizuje każdy możliwy stan i ostatecznie kończy się prawidłową grą do tego momentu (nie jest unikalna; wiele gier może prowadzić do tego samego stanu) lub stwierdza, że taka pozycja jest niemożliwa (nawet jeśli uzyskanie tam, stąd cytaty na temat „możliwe”). To właśnie my informatycy nazywamy problemem rozstrzygającym. Takie podejście jest prawdopodobnie niewykonalne (jak z pewnością nie jest wykonalne w przypadku „szachów do przodu”).
Jednak współczesne silniki szachowe nie wyliczają ślepo wszystkich możliwości. Zamiast tego używają bardzo zaawansowanych heurystyk do decydowania o prawdopodobieństwie ruchu i bardzo dobrze radzą sobie przeciwko ludziom. Wydaje mi się, że podobnej heurystyki i technik można użyć do stworzenia gry w szachy wstecz w oprogramowaniu, które przynajmniej czasami działa.
Prawdą jest, że zaczynając od pozycji docelowej, poszukiwanie możliwych poprzednich ruchów będzie prawdopodobnie niewykonalne. Istnieje jednak podejście, które może zapewnić rozsądną grę, która trafia w docelową pozycję.
W normalnych silnikach szachowych komputer ocenia każdą pozycję według pewnych kryteriów, takich jak liczba pozostałych elementów. Celem wyniku jest określenie, jakie jest prawdopodobieństwo wygranej z tej pozycji.
Zamiast tego można użyć innego zestawu kryteriów punktacji, takich jak liczba elementów na właściwych miejscach i czy zestaw pozostałych elementów pasuje do celu.
Umieszczenie dwóch takich silników grających przeciwko sobie w normalnej grze napastników może prawdopodobnie wygenerować grę, która zakończy się w docelowej pozycji.
Dodatkowo: Zabawnym rozszerzeniem byłoby użycie normalnej punktacji do przewidywania ruchów przeciwnika i punktacji celu dla własnych ruchów silnika szachowego. W ten sposób silnik szachowy typu „gra na bramkę” próbowałby zmusić przeciwnika „gra na zwycięstwo”, aby znalazł się na określonej pozycji. Oczywiście byłoby to możliwe tylko w przypadku niewielkiej części pozycji.
Chociaż obecnie może nie być możliwe napisanie sztucznej inteligencji, która działa lepiej niż ludzie, istnieje kilka odpowiednich programów w podtytule „retro, programy, úlohy” tutaj
Z czysto teoretycznego punktu widzenia: Tak, jest to możliwe.
Wystarczy grać do przodu we wszystkie możliwe gry, aż znajdziesz przynajmniej jedną grę, która zawiera aktualną pozycję. Następnie wykorzystujesz ruchy, które wykonał do przodu, aby przeprowadzić analizę retro.
Ale nie możesz tego po prostu zrobić, ponieważ liczba możliwych gier jest ogromna. A więc ten punkt jest tylko dowodem, że w teorii jest to możliwe. W praktyce pytanie brzmi, czy można to wykonać w rozsądnym czasie.
Przypuszczam, że można to wykonać, rozszerzając niektóre z obecnych metod planowania, ale szczegóły nie są proste. Poleciłbym zadać pytanie, czy sztuczna inteligencja może to osiągnąć na https://ai.stackexchange.com, ponieważ jest to interesujące pytanie dotyczące sztucznej inteligencji gier i może wywołać całkiem interesujące odpowiedzi na tej stronie.