Pytanie:
Czy maszyna skończona to dobry sposób na modelowanie szachów?
A. N. Other
2019-12-16 15:19:05 UTC
view on stackexchange narkive permalink

Bardzo powszechnym modelem w programowaniu jest maszyna skończona (FSM) (zobacz tutaj świetny przykład praktyczny). Czy FSM to dobry sposób na modelowanie szachów? Jakie są najlepsze sposoby, aby to zrobić? Jakie funkcje szachowe można wprowadzić; co należy pominąć?

Nie mam dużej wiedzy z zakresu informatyki ani inżynierii, a nawet programowania szachowego, więc zastanawiałem się nad tym pytaniem.

Co to jest skończona maszyna stanowa?
Jak mówię w pytaniu, mam ograniczoną wiedzę na temat tego pojęcia. Wpis w Wikipedii powinien dać dość dobre wyobrażenie o tym, czym jest maszyna skończona. Pytanie jest oczywiście przeznaczone dla tych, którzy wiedzą, czym jest FSM.
Dlaczego zadajesz pytanie, jeśli nie rozumiesz, co to znaczy? Kontekst tego, co według ciebie oznacza ten termin i dlaczego uważasz, że może on odnosić się do szachów, mógłby pomóc odpowiedzieć.
Nie mogę odpowiedzieć jako naukowiec, ale rozumiem, co inni piszą o skończonej maszynie stanowej. Czy w pełni rozumiesz i wiesz wszystko, o czym mówisz lub o co pytasz? Z mojego doświadczenia wynika, że ​​wiedza poprawia się w ten sposób, zadając pytania, których nie jesteśmy w 100% pewni, a następnie stopniowo, od wnikliwych odpowiedzi, uzyskując lepszy obraz całego pomysłu lub koncepcji.
@Grade'Eh'Bacon Odnoszę się do twojego pragnienia, aby o to zapytać, ale stwierdziłem, że jest bardziej konstruktywne, jeśli po prostu pominiemy uwagi typu: „Dlaczego zadajesz pytanie, jeśli nie rozumiesz, co to znaczy?” I przejdź bezpośrednio do mówiąc to, co powiedziałeś w swoim drugim zdaniu.
To pytanie nie jest odpowiednie dla tej witryny. Jest to pytanie, które znają eksperci informatyki, a nie pytanie, które znają eksperci od szachów, więc należy ono do cs.stackexchange.com
Idąc za twoim rozumowaniem, pytania dotyczące programowania szachowego również nie byłyby odpowiednie dla tej strony, ponieważ tylko programiści mogą na nie odpowiedzieć poprawnie. Ale być może na tej tablicy jest jeden lub więcej informatyków, który jest również ekspertem od szachów. Na razie wydaje mi się, że większość odpowiedzi na moje pytanie jest wnikliwa i adekwatna.
@Grade'Eh'Bacon Dlaczego _ troszczysz się? _ Facet może zadać dowolne pytanie, zostaw go w spokoju.
Pedantycznie nie jestem pewien, czy ma sens zadawać pytanie „Czy X jest maszyną skończoną”. To tak, jakby zapytać „czy moje konto bankowe jest funkcją?” Nie, chyba nie. Jednak ilość pieniędzy w nim może być modelowana za pomocą funkcji. Podobnie, prawdopodobnie niektóre aspekty szachów można by modelować za pomocą FSM, ale sama gra jest grą, a nie konstrukcją matematyczną.
To rodzi interesujące pytanie: czym w ogóle jest gra w szachy? Czy nie jest to zamaskowana konstrukcja matematyczna? Określenie „gra” to coś, co wymyśliliśmy, ponieważ jest zabawne i tak dalej, ale jeśli przeanalizujemy go dogłębnie, czy za tym wszystkim nie stoi matematyka? Dlaczego matematyk, taki jak John Nash, miałby chcieć dogłębnie pisać o teorii gier, skoro pewne gry nie były ostatecznie matematyką?
Ponadto pamiętaj, że komputery mogą grać w szachy. A czy programy komputerowe nie są ostatecznie zbudowane z algorytmów, tj. Matematyki?
@A.N. Inne, Maszyny mogą (w teorii) być zaprojektowane do wykonywania wielu rodzajów zadań związanych z szachami: Powiedz, czy ruch jest legalny, wybierz dobry ruch dla danej pozycji na szachownicy lub historii pozycji, powiedz, czy dana szachownica państwo należy do legalnej gry itd. Ale żadna z tych rzeczy nie jest tym samym, co stwierdzenie, że gra _ jest_ maszyną. Maszyny _ robią_ rzeczy. Gra w szachy nie. Gra nie jest maszyną w mniej więcej taki sam sposób, w jaki lista wskazówek krok po kroku nie jest wycieczką samochodową, albo przepis nie jest posiłkiem.
@Solomon, w takim razie czym jest „gra” w pierwszej kolejności bez dwóch graczy, którzy w nią grają, serii działań lub zadań, które są wykonywane itd. I tak dalej? „Gra w szachy” sama w sobie jest niczym, jest zwykłą abstrakcją. Mówię o całej akcji w moim pytaniu.
Szybkie wyszukiwanie w Google mówi nam tak i ma co najwyżej [7728772977965919677164873487685453137329736522 stany] (https://math.stackexchange.com/a/1407631/2333).
@A.N. Inne, aby komputer mógł grać w szachy i używać do tego matematyki, coś musi przypisać wartość figurom i ich pozycjom. Po przypisaniu wartości łatwo jest dokonać prostego dodawania, aby określić, czy ruch zwiększa, czy zmniejsza wynik w porównaniu z wynikiem przeciwnika. Następnie może wykonać następny ruch, obliczyć wyniki, wykonać następny ruch itp. To, ile ruchów „głęboko” wygląda na komputer, jest podstawowym ustawieniem siły większości komputerowych modeli szachów. Ale prawdziwą inteligencją, która się za nimi kryje, jest tworzenie wartości dla figur i pozycji.
@A.N.Inne, cd. Ale oczywiście jest to o wiele bardziej skomplikowane - model nie jest po prostu ogromną (ale skończoną) tabelą przeglądową liczb (stanów) do zsumowania. Jest to drzewo wyszukiwania, które komputer tworzy i przechodzi (w czasie rzeczywistym), aby obliczyć wyniki. Jak głęboko (i szeroko) komputer może zrobić drzewo, zależy od tego, ile ruchów do przodu może obejrzeć i ocenić.
@A.N.Inne Dobre pytanie, ale proszę zmienić nagłówek, aby pasował do szczegółowego tekstu: „Czy szachy mogą być uważane za maszynę skończoną?”
Dziesięć odpowiedzi:
#1
+22
RemcoGerlich
2019-12-16 15:39:56 UTC
view on stackexchange narkive permalink

Tak, myślę, że tak.

Miałbyś wszystkie możliwe pozycje na zarządach jako stany (wiele stanów, ale skończone). Pozycja wyjściowa jako stan początkowy. Legalne ruchy jako łączniki między stanami (więc „alfabet” składałby się ze wszystkich możliwych ruchów). Pozycje, które kończą grę, takie jak mat, pat i martwe pozycje jako przyjmujące stany.

Ostatecznie otrzymujesz zestaw wszystkich możliwych partii szachowych jako język akceptowany przez maszynę.

Jak można to formalnie rozwiązać z takimi rzeczami, jak nielegalne ruchy, zasady 50 i 75 ruchów, opisujące listę legalnych ruchów, formalnie i tak dalej, pozostawiamy jako ćwiczenia dla czytelnika.

Oferty losowania i gry kończące się w inny sposób, jak np. Awaria telefonu komórkowego, powinny prawdopodobnie zostać pominięte.

Myślę, że nie musisz pomijać ofert remisów i innych czynników zewnętrznych kończących grę. Dodaj stan DrawAccepted i BoardState + DrawOffered dla każdego stanu tablicy. Plus stany BlackLoss i WhiteLoss dla innych czynników zewnętrznych (takich jak rezygnacja), powodując przegraną jednej strony. Każdy stan ma łącze do BlackLoss, WhiteLoss i jego BoardState + DrawOffered, a BoardState + DrawOffered ma łącze do BoardState i DrawAccepted.
Istnieje tylko skończona liczba możliwych stanów tablicy, co z definicji czyni ją FSM. Jednak to tak jakby argumentować, że wszystkie komputery są FSM, ponieważ pamięć jest zawsze ograniczona; chociaż prawda, nie jest to użyteczna abstrakcja. jeśli chcesz FSM, który nie zawiera niemożliwie dużej liczby węzłów, prawdopodobnie odpowiedź brzmi „nie” ze względu na złożoność reguł gry.
Powiedzenie, że maszyna może rozpoznać prawidłową sekwencję ruchów lub prawidłowy stan planszy, nie jest tym samym, co stwierdzenie, że sama gra _ jest_ maszyną.
@SolomonSlow tak, ale oryginalny plakat przyznaje, że używa określeń luźno.
Stanowiska w zarządach nie wystarczą. Potrzebujesz informacji o tym, czy król i wieża się przesunęły, ostatni ruch na półpasant, a aby uzyskać remis po trzykrotnym powtórzeniu pozycji, potrzebujesz ogólnie wszystkich pozycji od ostatniego ruchu pionka.
@M.Herzkamp To łatwe w obsłudze, kosztem wysadzenia rozmiaru zbioru stanów.
#2
+20
John Coleman
2019-12-16 20:00:28 UTC
view on stackexchange narkive permalink

Maszyny skończone można opisać jako rozpoznające języki regularne. Być może mógłbyś zidentyfikować szachy ze zbiorem wszystkich możliwych rekordów gry. Na przykład f3e5g4Qh4 # (partner głupca) jest jednym z krótszych ciągów w tym języku. Ponieważ ten język ma skończony alfabet, a wszystkie słowa mają ograniczoną długość (z górną granicą gdzieś w okolicy 35000, ponieważ maksymalna długość gry wynosi poniżej 6000 ruchów (zakładając zasadę losowania 50 ruchów), a większość ruchów zajmuje 6 liter kodować)). Zatem język szachów jest językiem skończonym, stąd jest trywialnie regularny i dlatego jest rozpoznawany przez FSM.

@Cruncher poważnie, głupcze, [jak możesz pomyśleć, że XML nie może zostać przeanalizowany przez wyrażenie regularne] (https://stackoverflow.com/a/1732454/745903)?
#3
+12
Eric Lippert
2019-12-17 00:46:00 UTC
view on stackexchange narkive permalink

czy grę w szachy można uznać za skończoną machinę stanową?

Tak; to jest dobry wgląd.

FSM jest abstrakcyjnym modelem obliczeń o następujących cechach:

  • Maszyna zaczyna się w znanym „stanie startowym”
  • Maszyna akceptuje sekwencja danych wejściowych
  • Każde wejście jest interpretowane w kontekście bieżącego stanu
  • Każde wejście powoduje aktualizację do bieżącego stanu; aktualizacja zależy tylko od aktualnego stanu gry i danych wejściowych.
  • Niektóre stany to „stany zatrzymania”, które powodują zatrzymanie maszyny.
  • Tam jest ścisłą górną granicą rozmiaru stanu i liczby możliwych wejść.

Jest to ostatnia cecha, która sprawia, że ​​maszyna jest skończoną maszyną stanu. To znaczy, gdybyśmy ponumerowali każdy stan, w którym maszyna mogłaby być znajdować się, byłaby największa taka liczba. Może większa niż liczba atomów we wszechświecie, ale wciąż skończona.

Następnie możemy modelować partię szachów jako FSM. Stan początkowy to tablica startowa. Dane wejściowe to legalne ruchy - w tym ruchy takie jak „Rezygnuję” - i każdy ruch aktualizuje stan planszy. Niektóre stany to „stany zatrzymania” - nazywamy je „białymi ma szachów”, „czarnymi są w patowej sytuacji”, „czarnymi zrezygnowały” i tak dalej.

Ponadto dowolny silny > gra o takich cechach może być modelowana jako FSM; wszystko, czego potrzebujesz, to skończony stan gry i dane wejściowe, które w przewidywalny sposób aktualizują stan gry. Na przykład, jeśli rozważymy wprowadzenie takiego ograniczenia w pokerze, że całkowita liczba żetonów dostępnych dla wszystkich graczy jest mniejsza niż, powiedzmy, sto bilionów - lub jakakolwiek inna skończona liczba - wtedy poker może być również modelowany jako FSM. Mamy stan początkowy: liczbę graczy, liczbę żetonów każdego gracza i potasowaną talię. Mamy zasady, które aktualizują stan - zakłady, sprawdzenia, spasowania i tak dalej - i mamy stany, które zatrzymują grę.

Ale gdybyśmy modelowali pokera w taki sposób, że nie ma ograniczeń co do całkowitej liczby dostępnych żetonów, to technicznie rzecz biorąc, przestałby być FSM; jeśli gracze mogą mieć dowolną liczbę żetonów, wówczas żadna ograniczona ilość informacji nie charakteryzuje każdej gry w pokera.

Warto pomyśleć o grach, które są nie FSM; Już zauważyłem, że gry, w których jest jakaś nieograniczona liczba, nie są FSM. Rozważ grę karcianą, w której gracz może w pewnym momencie wykonać akcję, która powoduje tasowanie talii. W tym przypadku mamy niedeterministyczną zmianę stanu , co sprawiłoby, że technicznie nie byłby to FSM ... ale może jest na to sposób:

A co z kostkami gry oparte na Są one losowe, więc może się wydawać, że nie są FSM, ale możemy sprytnie uczynić ich FSMami, wykonując rzuty każdego gracza jako wejście , tylko takie, które nie jest wybrane przez gracz. I to samo dotyczy innych losowych elementów gry, takich jak tasowanie kart.

Szachy są szczególnie dobrym kandydatem do traktowania jako FSM, ponieważ nie ma przypadkowości i rzeczywiście nie ma stanu ukrytego w wszystko . Obaj gracze przez cały czas znają cały stan gry.

To prawdopodobnie odchodzi od tematu, ale jeśli chodzi o tasowanie talii, czy technicznie mógłbyś sobie z tym poradzić w stanach po tasowaniu „52!”? O ile tasowanie jest niedeterministyczne z punktu widzenia gracza, to jest ostateczne z punktu widzenia automatu skończonego? - pytam szczerze, bo nie jestem do końca pewien.
@Dancrumb brzmi dokładnie tak, jak zamiana niedeterministycznego automatu skończonego na równoważny automat deterministyczny, wraz z możliwą wykładniczą eksplozją stanów. Jednak NFA i DFA mają tę samą moc obliczeniową (oba rozpoznają tylko zwykłe języki).
#4
+9
Laska
2019-12-16 16:46:26 UTC
view on stackexchange narkive permalink

Dla problemistów bardzo przydatne jest myślenie o szachach jako o skończonej maszynie stanowej. Stan może obejmować:

  • jakiego rodzaju figury znajdują się na każdym polu
  • kto ma ruch?
  • prawo do roszady
  • Zdolność en passant

Naprawdę chcesz, żeby był to zakres państwa, głównie dlatego, że jest to zawarte w Prawach w Artykule 9.2 jako podstawa do określenia powtarzalności pozycji!

Jest tu subtelność, ponieważ podczas gdy prawa do roszady zależą tylko od tego, czy K&R się poruszył (lub prawdopodobnie R został schwytany), zdolność przelotowa zależy od tego, czy ep można wykonać. (Może być jakiś szpilka lub czek, który temu zapobiega.) Dlatego potrzebne jest spojrzenie w przyszłość.

Mamy bogate zasoby państw, ale możemy być bardziej oszczędni w definiowaniu alfabetu. Możemy zdefiniować ruch, po prostu wskazując dwa pola, źródło i cel, a następnie możemy zinterpretować to, aby dać unikalny ruch (w tym roszadę i e.p.). Oczywiście w większości przypadków nie ma ruchu między dwoma polami, aw innych przypadkach ruch jest nielegalny z powodu czeku. Jest to w porządku zgodnie z praktyką FSM. Koncepcyjnie możemy uznać, że każda pozycja daje zestaw prawidłowych posunięć.

Naturalne jest, aby układy pionów na szachownicy były stanami, nawet takimi, które reprezentują pozycje nielegalne. Niektóre pozycje wyglądają normalnie, ale w rzeczywistości są nielegalne - w porządku, są w porządku. Pozycje, które mają zero lub jednego króla, lub gracza, który już ruszył, są łatwe. Jednak pozycje, w których jeden gracz ma pionki na pierwszym lub ósmym rzędzie, sugerują, że pionek może zacząć również na innych szeregach, a następnie musielibyśmy śledzić dodatkowy stan dla każdego pionka, aby zobaczyć, czy ma on prawo do podwójnego przeskoku pierwszego ruchu. Pole startowe może również wpływać na to, czy może awansować, gdy osiągnie 8. pozycję. Mamy również pytania dotyczące tego, co się dzieje, gdy gracz ma wielu królów. Ale w zasadzie zdefiniowanie ruchu na nielegalnych stanowiskach jest najlepszym podejściem. Jedyną różnicą między legalną a nielegalną pozycją jest to, czy można ją zakorzenić w początkowej tablicy gry - jest to dość trywialna funkcja, ale czasami bardzo trudna do ustalenia.

Istnieją terminale na pozycjach mata i patowa, ale decyzja, czy pozycja jest martwa, wymaga spojrzenia w przyszłość, więc nie chcemy stracić tego późniejszego drzewka. Nie czyni martwym mniej realnym, gdy powiemy, że się wyłania.

Ruchy 50/75 i rysowanie według reguł powtórzeń są z pewnością poza maszyną stanową. Pierwsza może być osadzona w maszynie stanów, ale druga nie może, więc równie dobrze może po prostu zapisać sekwencję stanów od początku.

W większości przypadków ten początek jest tablicą gier, ale w przypadku złożonych problemów początek jest późniejszym punktem i możemy potrzebować konwencji, aby powiedzieć nam, jak zdecydować o szczegółowym stanie i historii gry.

Jaki jest sens tego wszystkiego? Jednym z problemów związanych z problemami szachowymi (szczególnie bajkowymi) jest to, że zasady i konwencje nie są do końca jasne. Aby wybrać losowy przykład: czy reguła martwej pozycji ma widoczność statusu ruchu 50 ruchu & 75? Świat z problemami nie ma arbitrów, którzy mogliby powiedzieć nam, co być może chcą powiedzieć zasady FIDE. Jeśli powiemy tylko, że cóż, nie ma znaczenia pozostawienie indywidualnych przypadków, wtedy stworzymy mgłę niepewności, która powstrzymuje analizę wsteczną przed osiągnięciem pełnego potencjału.

Tam, gdzie ekspert problematyczny Guus Rol wziąłby teraz Nas polega na rozbiciu każdego przejścia (ruchu) na podróż złożoną z mikro-faz. Pozwala to na bardziej subtelne zarządzanie bajkowymi warunkami. Osobiście uważam, że powinno to być oparte na prostszym modelu, który opisuję tutaj, który jest swego rodzaju bazą dla jego późniejszych eksploracji.

EDYCJA: Inni mogą potwierdzić, czy szachy mogą być reprezentowane w FSM. Unikalny punkt widzenia, który próbuję przyjąć, to jak należy do tego podejść: co ma sens osadzić w maszynie i co powinno być zbudowane na górze. Prawdziwa złożoność, o której nie wspomniałem, polega na zarządzaniu wieloma możliwymi historiami retro, co jest konieczne w przypadku wielu problemów z analizą wsteczną. Jedyną praktyczną drogą do przodu jest stan = pozycja w sensie FIDE. Nie jest to wymagane w przypadku szachów na szachownicy.

Istnieją dwa główne paradygmaty analizy wstecznej: RS & PRA. Każdy z nich może być odpowiednim kandydatem do analizy teorii sieci, która nie została przeprowadzona w systematyczny sposób. Najlepsze wyjaśnienie znajduje się tutaj https://www.janko.at/Retros/Glossary/Castling-and-En-passant.htm. Artykuł Wernera Keyma zawiera kilka klasycznych i trudnych retrospekcji.

Nie myśl o automatyzacji rozwiązywania problemów retro, ale po prostu zdefiniowanie języka, który będzie formalnie reprezentował ich rozwiązanie, byłby świetnym początkiem.

Ignoruję zdarzenia przesadne, takie jak kliknięcie, ruch zapisu, ruch dotykiem, rezygnacja, oferta losowania, roszczenie losowania itp., aby skupić się na stronie kompozycyjnej. Zauważ, że możliwy jest interesujący stan wyścigu, w którym dwóch graczy rezygnuje mniej więcej w tym samym czasie.

Rysowanie z powtórzeniami może być osadzone w FSM, ponieważ istnieje tylko skończona liczba możliwych konfiguracji plansz, a zatem możemy określić, czy ta konfiguracja została osiągnięta w tej grze, czy nie, przy użyciu skończonej liczby bitów. Oczywiście w praktyce nie tak byśmy to zrobili, ale w teorii nie ma zastrzeżeń.
Rzeczywiście lubię problemy retro, ale nie zastanawiałem się zbytnio nad tym, jak można zautomatyzować ich rozwiązanie. Byłoby interesujące zobaczyć, czy istnieje sposób na zastosowanie teorii sieci do problemów retro.
Cześć Eric, dzięki za twój wnikliwy komentarz. Inni mogą potwierdzić, czy szachy mogą być reprezentowane w FSM. Unikalny punkt widzenia, który próbuję przyjąć, to * jak * należy podejść do tego: co ma sens, aby osadzić w maszynie, a co powinno być zbudowane na górze. Prawdziwa złożoność, o której nie wspomniałem, polega na zarządzaniu wieloma możliwymi historiami retro, co jest konieczne w przypadku wielu problemów z analizą wsteczną. Jedyną praktyczną drogą naprzód jest stan = pozycja w sensie FIDE. Nie jest to wymagane w przypadku szachów over-board.
Dodano odpowiedź na główną odpowiedź
#5
+9
Inertial Ignorance
2019-12-16 16:54:52 UTC
view on stackexchange narkive permalink

W pewnym sensie tak bym powiedział. Istnieje niewiarygodnie duża liczba stanów / pozycji, w których mogą się znajdować szachy, ale liczba ta jest ograniczona. Aby przejść z jednego stanu do drugiego, podejmuje się pewne działania. Jeśli jesteś w jednym stanie, możesz wybrać jedną z wielu czynności, aby przejść do innego stanu.

#6
+6
Tertium Quid
2019-12-17 01:49:02 UTC
view on stackexchange narkive permalink

Możesz prawdopodobnie powiązać FSA z uznaniem ważnej partii szachowej (język rozpoznawany przez FSA jest zbiorem wszystkich prawidłowych partii szachowych) przez skojarzenie stanu FSA z parą wartości: (1) możliwą szachownicą konfiguracja oraz (2) wartość określająca następnego gracza, który będzie się poruszał. (Druga wartość może być opcją, biorąc pod uwagę kodowanie kolorów figur). Każda z tych par byłaby połączona z przejściem tylko wtedy, gdyby był dostępny prawidłowy ruch w grze, aby do nich dołączyć. Ważna gra to seria prawidłowych posunięć. Domyślam się, że definicja tego AS jako taka byłaby zbyt duża. Nie jestem pewien, jak wypadłby, powiedzmy, AS dla ruchów kostki Rubika, który wymagałby 43 kwintylionów stanów w swojej definicji (chociaż jest wiele możliwych stanów stwierdzających w tej grze). Maszyna ze stosem byłaby ogromnym ulepszeniem w modelowaniu gry w szachy.

#7
+4
fraxinus
2019-12-17 14:30:14 UTC
view on stackexchange narkive permalink

Gra w szachy jest z definicji maszyną o skończonych stanach.

Z drugiej strony liczba możliwych stanów jest dość duża i istnieje jeszcze większa liczba strategii, które obaj gracze mogą stosować.

Oszczędne dla niektórych końcówek, te liczby generalnie przekraczają współczesne możliwości obliczeniowe, więc gra zwykle NIE jest modelowana jako FSM.

#8
+2
speciesUnknown
2019-12-18 18:38:41 UTC
view on stackexchange narkive permalink

Odpowiedź od programisty

Natknąłem się na to i pomyślałem, że przydałaby się tutaj odpowiedź od programisty.

Chociaż szachownica mogłaby być reprezentowana jako zbiór stanów skończonych, byłoby to niepraktyczne ze względu na samą ich liczbę.

Jednak logika gry zawiera określone kroki - klient gry jest często implementowany przy użyciu FSM. Ponieważ działania podejmowane przez gracza muszą być zgodne z pewnymi regułami, łatwo jest je zaimplementować (w wielu innych grach turowych) za pomocą FSM.

Klient siedzi w określonym stanie, gdy planujesz swój ruch. Moglibyśmy to nazwać „planowaniem”.

Następnie wybierasz kawałek, a klient może podać listę ruchów do wyboru. Stan „Przenoszenie”.

Po wybraniu ruchu klient może go animować.

Następnie przełączasz się na "czekanie", w którym inny klient wykonuje te same kroki.

Gdy dojdzie do mata lub gra nie może być kontynuowana, przechodzimy do stanu "punktacji".

Sama tablica jest definitywnie stanowa i chociaż technicznie skończona, to nie to samo, co FSM, ponieważ nie piszemy z wyprzedzeniem stanów i reguł transferu między stanami.

A co z AI

Chociaż posiadanie wstępnie zakodowanych stanów dla każdej pozycji planszy nie jest możliwe, AI jest w stanie odwzorować wiele tysięcy ruchów z wyprzedzeniem i zbudować duży FSM. W tym przypadku używa właściwości, które każdy stan musi określić, aby określić ruch. Technicznie skończona maszyna stanów, chociaż nie w tej samej definicji.

#9
+2
Christian H. Kuhn
2019-12-21 19:14:12 UTC
view on stackexchange narkive permalink

Ponieważ oznaczyłeś swoje pytanie „regułami”, spróbuję odpowiedzieć.

Nie sądzę, aby FSM był odpowiednim modelem. Oczywiście masz dużą, ale skończoną liczbę stanów. Model ten ma zalety i wady, są lepsi informatycy niż ja, którzy mogą to wyjaśnić. Moja uwaga: liczba przejść może być nieskończona.

Aby to wyjaśnić, musisz zdefiniować „szachy”. Mam nadzieję, że zgodzimy się, że szachy są zdefiniowane w Prawach Szachowych przez FIDE. Składają się one głównie z dwóch części: Podstawowych reguł gry (art. 1 - 5) i reguł zawodów (art. 6 - 12, dodatki i wytyczne).

Aby przejść od pozycji wyjściowej do pozycji po 1.e4 jest kilka przejść. 1. Sf3 Sf6 2. Sg1 Sg8 3.e4 jest jednym z nich. Widzisz problem.

Zgodnie z Regulaminem konkursu, zwł. Art 9.6, liczba przejść jest ograniczona i skończona, ponieważ po piątym zajściu pozycji gra kończy się remisem, a FSM jest dobrym modelem.

Ale jeśli zastosujesz tylko Podstawowe Zasady, wtedy powtórzenie pozycji jest możliwe ad infinitum . A dla nieskończonej liczby przejść skończona maszyna stanowa może z definicji nie być modelem.

#10
+1
user20899
2019-12-18 22:31:47 UTC
view on stackexchange narkive permalink

Tak! Ponieważ istnieje skończona liczba stanów i możesz poruszać się między nimi w oparciu o zasady szachowe. Istnieje zgrabna strona, która wizualizuje możliwe ruchy na połączonym wykresie, więc to już 90% tego, co zrobiłbyś, gdybyś zaprogramował maszynę stanową. graph visualization of opening

https://www.chessroots.com/



To pytanie i odpowiedź zostało automatycznie przetłumaczone z języka angielskiego.Oryginalna treść jest dostępna na stackexchange, za co dziękujemy za licencję cc by-sa 4.0, w ramach której jest rozpowszechniana.
Loading...