Najlepsze podejście do napisania silnika szachowego? [Zamknięte]

Jestem entuzjastą szachów i programistą. Niedawno postanowiłem zacząć tworzyć silnik szachowy, korzystając z mojej wiedzy szachowej i programistycznej. Oto moje pytanie:

W jakim języku (znam Java, C ++ i Python) i metodologię należy dostosować podczas pisania silnika szachowego?

Byłoby mile widziane trochę wskazówek.

Edytować:

Więc postanowiłem zrobić to w JavaScript. Ściągam ten interfejs gry w szachy z github i teraz jestem gotowy! Moim pierwszym krokiem byłoby napisanie legalnych ruchów. Czy ktoś może skierować mnie w dobrym kierunku? (Jestem nowy w jQuery, ale mam dużo doświadczenia w programowaniu).

PS: Nie próbuję tworzyć bardzo wydajnego silnika (wiem, że jego droga jest zbyt trudna), chcę tylko zapoznać się z procesem i po drodze nauczyć się nowych technik.

Szachista z oceną 2072 tutaj. Zrobiłem tę stronę w czystym JavaScript przez weekend. To nie jest silnik szachowy (zaprojektowałem go tak, by tworzył zabawne pozycje otwarcia jako rodzaj przewrotnego silnika Chess960), ale jest to punkt wyjścia. Kod źródłowy jest tutaj .

Tworzenie funkcjonalnej tablicy wiąże się z wieloma komplikacjami. Obejmują one:

• Po pierwsze, zastanawianie się, jak przedstawić podstawowe legalne działania. Musisz trochę robić matematykę ze współrzędnymi początkowymi i końcowymi. Na przykład w przypadku ruchów wieży jedna ze współrzędnych musi być taka sama przed i po. W przypadku ruchów rycerza suma wartości bezwzględnej zmian współrzędnych musi wynosić 3, a obie współrzędne muszą się zmienić. W przypadku ruchów biskupa albo suma współrzędnych pozostaje taka sama, albo oba zwiększają się o tę samą wartość. Pionki są trudniejsze, ponieważ nie tylko musisz dowiedzieć się, czy można przesunąć dwa kwadraty lub jeden (sprawdź rząd i kolor zamiast przechowywać liczbę wykonanych ruchów), ale także poradzić sobie z całym przechwytywaniem po przekątnej, przesuwać -dobra rzecz.
• Zdobywanie jest wyzwaniem ze względu na pionki i czek. Nie można tak po prostu powiedzieć, że jeśli element przesuwa się na pole innego elementu, to jest to chwytanie. W końcu pionki nie mogą przesuwać się na pole innego pionka, aby je schwytać - mają swój własny sposób chwytania.
• Musisz znaleźć skuteczny sposób, aby sprawdzić, czy pionki przeciwnika stoją na przeszkodzie, aby zdecydować, czy jest to legalne, czy nie.
• Sprawdzenie jest trudne. Po każdym ruchu musisz sprawdzić wszystkie pola, do których mogą dotrzeć pionki wroga, i sprawdzić, czy jeden z nich dotyczy twojego króla, a jeśli tak, to jest to ruch nielegalny.
• Castling, en passant, awans, impas, przymusowe remisy, powtórzenia - żadne z nich nie jest banalne, biorąc pod uwagę skalę problemu.

Wszystkie silniki szachowe działają, patrząc na wszystkie (ewentualnie ustalone heurystycznie podzbiory) legalne ruchy w pozycji i oceniając liczby w celu przedstawienia ich względnych wartości, wykonując te ruchy i rekurencyjnie robiąc to samo dla uzyskanych pozycji. Oto twoje bliźniacze problemy

• Jak skutecznie przechowywać te dane
• Jak kontynuować wyszukiwanie rekurencyjne - w końcu nie możesz pozwolić, aby trwało wiecznie, więc musisz ustalić limit, a następnie wymyślić, jak zaprojektować algorytm, aby przeprowadzał najbardziej optymalne i dokładne wyszukiwanie w tym limicie. Na przykład, chcesz upewnić się, że przynajmniej zawiera ocenę dla każdego możliwego ruchu początkowego, ale możesz również chcieć, aby poświęcił więcej czasu na ocenę bardziej obiecujących ruchów, zamiast dać równą ilość czasu każdemu ruchowi.

To wszystko na samym początku projektowania algorytmu, na temat którego dostępnych jest mnóstwo informacji.

Jeśli chodzi o wybór języka (choć myślę, że już zdecydowałeś się na JavaScript), myślę, że zależy to bardziej od twojego celu niż czegokolwiek innego. Chciałem zrobić mój online (i poprawić się w JavaScript), więc JavaScript był moim wyborem. Zrobi to jednak każdy obiektowy język programowania.

Gdy poczujesz się komfortowo z tym, co robisz, prawdopodobnie pomocne okażą się następujące zasoby:

• Wiki programowania szachowego
• Forum programowania szachów
• StockFish on Github

Powodzenia!

Problem z „programem szachowym” jako koncepcją polega na tym, że istnieje wiele elementów, które mogą pochłonąć dużo czasu i niekoniecznie cię w tej chwili interesują. Możesz spędzić lata po prostu pracując nad grafiką, wyszukiwaniem alfa-beta lub wizualizacją, aby pomóc w opracowaniu wyszukiwarki, lub ... cóż, jest wiele elementów.

Polecam znaleźć program szachowy typu open source (musi być ich wiele) i zająć się ulepszaniem tych części, które najbardziej Cię interesują. Możesz w końcu zastąpić cały program, jedną funkcję na raz, lub możesz nauczyć się wystarczająco dużo i mieć motywację do wyrzucenia go i zaprojektowania własnego programu od zera. W każdym razie kluczem jest uruchomienie „światła” i nauczenie się lin przed próbą zaprojektowania całego programu.

Jeśli znasz zasady gry w szachy, dobrym punktem wyjścia do podstawowych technik jest http://www.frayn.net/beowulf/theory.html Obszerna kolekcja materiałów i linków, które można znaleźć tutaj: http: // chessprogramming .wikispaces.com / Po trzecie: ucz się od kodu innych. Spójrz na źródła Podstępnych . To wiodący silnik open source. Bardzo ważne będzie, aby pomyśleć o przypadkach testowych, aby sprawdzić, czy wprowadzisz ulepszenia: na przykład zacznij od prostych, łatwych pozycji w grze z 3 lub 4 figurkami.

Jak wspomniano, zbudowanie silnika szachowego nie jest strasznie trudne. Być może powinieneś skoncentrować się na tym, jak chcesz używać i (potencjalnie) wdrażać tę aplikację, ponieważ to prawdopodobnie określi twój wybór języka.

Jeśli jest to po prostu fajne ćwiczenie, możesz zakodować je w JavaScript i wdrożyć jako stronę internetową. Jeśli nigdy nie chcesz przerobić go na ekspercką grę w szachy, przynajmniej inni będą mogli grać z nią i jej kodem źródłowym.

Jeśli chcesz nauczyć się konkretnej technologii w tym samym czasie, powiedz WPF, to może być dobry sposób na zabicie dwóch ptaków jednym kamieniem. MVVM może być przesadą w tej aplikacji, ale przynajmniej się tego nauczysz.

Jeśli chcesz kierować reklamy na urządzenia z Androidem, dobrym wyborem będzie Java. Podobnie, Objective-C na urządzenia z systemem iOS.

Długi i krótki wybór języka nie istnieje w próżni.

Zakładam, że już wiesz o koncepcji Min-Max, drzewach i przycinaniu, heurystyce i innych podstawach, a to, co tu piszę, to tylko niektóre szczegóły, które mogły zostać niedocenione.

Ja wraz z przyjacielem czasami pisałem własny silnik szachowy. Dzielę się niektórymi problemami i pomysłami i mam nadzieję, że okażą się one przydatne.

Ponieważ oboje byliśmy programistami Java, nasz język stał się java i zaczęliśmy od podejścia obiektowego. Kawałki były przedmiotami, tablica była przedmiotem, teczki i szeregi (rzędy i kolumny w literaturze szachowej) były przedmiotami. I to było złe. Narzut był ogromny, a program miał trudności z przejściem dalej niż 2 ruchy (4 warstwy) w drzewie wyszukiwania.

Tak więc po kilku poszukiwaniach uzyskaliśmy genialny pomysł (choć nie nasz!): Reprezentowanie elementów i planszy jako Długich liczb całkowitych (64-bitowych). Ma to sens, ponieważ szachownica ma 64 pola. Reszta była nieco mądrzejsza (działała bardzo blisko procesora = bardzo szybko). Rozważmy na przykład binarną 64-bitową liczbę całkowitą, w której te przedstawiają kwadraty na planszy, które twój atak może zaatakować. Teraz, jeśli wykonasz logiczne „I” między dwiema liczbami w ten sposób, niezerowy wynik oznacza, że ​​masz kwadrat z atakującymi. Jest kilka sposobów przedstawienia szachownicy i pionków, więc:

1 - Zdecyduj o swojej prezentacji na forum

Następnie potrzebujesz i otwierasz bazę danych. Otwarcie szachów zostało w jakiś sposób rozwiązane, dlatego zaleca się, aby mieć i otwierać książkę. W tym przypadku masz dużo dodatkowego czasu w grach błyskawicznych.

2 - Znajdź sobie książkę otwierającą.

Zrobiliśmy to, ale wciąż nie byliśmy dobrzy:

3 - Dobry silnik szachowy powinien widzieć przed sobą 6 ruchów (12 warstw).

Więc to, co wtedy zrobiliśmy, polegało na wykorzystaniu czasu martwego (jeśli jest to silnik ludzki kontra komputerowy).

4 - Wykorzystaj czas, kiedy przeciwnik myśli o utworzeniu niektórych poziomów twojego drzewa.

I wciąż byliśmy daleko od 12 warstw. W wyniku dalszych badań odkryjemy kilka sztuczek! Na przykład zasugerowano pominięcie jednej warstwy drzewa i rozpoczęcie od następnej warstwy (jakby nie było przeciwnika). Chodzi o to, że jeśli ruch jest wyjątkowo idiotyczny, to po co marnować czas i zobaczyć, jakie są reakcje przeciwników na ten ruch. Jednak jeden dobry silnik powinien być w stanie rozróżnić ruch idiotyczny i poświęcenie genialnej królowej.

5 - Naucz się programowania sztuczek dla tego konkretnego problemu (szachy).

Ja i mój przyjaciel, w tym stanie, nadal byliśmy źli: / Co mogliśmy zrobić - i częściowo zrobiliśmy - to uratować obliczone pozycje. Jeśli obliczysz pozycję, zachowaj ją na przyszłość! To samo dotyczy pętli w drzewie wyszukiwania. Chodziło o to, aby efektywnie zapisać / odzyskać:

6 - Zapisz wygenerowane dane ... Skutecznie!

i w końcu:

7 - Kod z maksymalną optymalizacją.

Ten problem jest niezwykle drogi zarówno pod względem czasu procesora, jak i pamięci. Bardzo ważne jest bardzo efektywne pisanie kodu. Pamiętaj, że mówimy o współczynniku rozgałęzienia wynoszącym 35. Oznacza to, że bezużyteczne „jeśli” gdzieś w twojej heurystyce, może stać się 3.3792205e+18bezużyteczne „jeśli” jest gdzieś głęboko w twoim drzewie wyszukiwania.

Programowanie w szachy jest bardzo interesującym wyzwaniem i nadszedł czas, abyś mógł przetestować swoje możliwości programowania. Jest jeszcze kilka punktów, które mogę zasugerować, ale jestem pewien, że odkryjesz je sam. Jest wiele innych punktów, których nie znam, ale można je znaleźć w Internecie!

Powodzenia i miłej zabawy!

ps Nie znam zbyt dobrze javascript, ale coś mówi mi na podstawie trudności problemu, być może biorąc pod uwagę wszystko, co może zaoferować C ++, lepiej byłoby porzucić javascript i zrobić to w C ++.

Zgodnie z edycją jesteś na etapie definiowania „legalnych” ruchów.

Istnieją dwa sposoby opisywania ruchów w szachach. Notacja opisowa i notacja algebraiczna . Prawdopodobnie potrzebujesz funkcji, która przyjmuje element, pozycję początkową i pozycję końcową jako parametry. na przykład. Rycerz od QN1 do QB2 jest nieprawidłowy, ale rycerz od QN1 do Q2 jest ważny. Myśląc o tym, notacja algebraiczna może być prostsza ze względu na możliwość łatwego obliczenia pozycjonowania „względnego”.

Aby zapewnić piszesz kwoty minimalnego wymaganego kodu, chciałbym zacząć pisać testy dla tej funkcji pierwszy . Jeśli używasz notacji algebraicznej, prawdopodobnie nie potrzebujesz testu na sztukę / początek / koniec. Spraw, by każdy test działał, i zreformuj duplikację przed przejściem do następnego „ruchu”. Twój kod stanie się czystszy.

Gdy już wystarczająco pokonasz legalne i nielegalne ruchy dla każdego elementu, zacznę dodawać czeki dla innych zmiennych (takich jak przeniesienie króla do warunków „czeku” i „wiązania”).

Polecam qunit do testów jednostkowych i jaśmin do testów behawioralnych w JavaScript.

Właściwie napisałem silnik szachowy. Przygotuj się na smakołyk i koszmar. Kiedy zrobiliśmy to z moimi przyjaciółmi, był to konkurs czasowy, a językiem, w którym zdecydowaliśmy się wybrać, była Java. Uważam, że Java lub C to najlepszy wybór, ale widzę, że zdecydowałeś się na Javascript. Naprawdę nie mogę tego zapukać, ponieważ nie jestem z tym zaznajomiony.

Głównym problemem tutaj będzie to, że istnieje tak wiele scenariuszy przenoszenia / wygrywania z każdym kawałkiem, z którego musisz wziąć pod uwagę, więc zalecam, abyś napisał wszystkie możliwe sytuacje dla każdego kawałka, zanim zaczniesz kodować. Samo wskoczenie bez planowania sprawi, że ten zabawny projekt stanie się powtarzalnym obowiązkiem. Ale to naprawdę najważniejsze. Po prostu najpierw zaplanuj poza kodem i upewnij się, że otrzymujesz każdy scenariusz pojedynczo.

Powodzenia

W części gry polegającej na podejmowaniu decyzji przez graczy komputerowych nie mogę polecić wystarczająco dużo książki „Sztuczna inteligencja: nowoczesne podejście” (strona z książkami http://aima.cs.berkeley.edu/ ). W zależności od twojego doświadczenia w matematyce (teoria grafów pomaga) może to być trochę wysoki poziom, ale jest napisany tak prosto, jak to możliwe, i zawiera bardzo aktualny przegląd (i pewną głębię) technik sprawiają, że programy decydują.

Wskaże ci takie rzeczy, jak określenie celu (tj. Mat lub zero), ocena, jak bliski jest dany stan (układ planszy) od tego celu, jak wygenerować różne możliwe następujące stany, zaczynając od bieżącego, i jak przemierzać ogromną przestrzeń problemową.

Jedną z rzeczy, które mogą pomóc w zaprojektowaniu algorytmu sztucznej inteligencji, jest zastanowienie się, jak zdecydować, który ruch grać dalej, tak jakbyś miał cały czas na świecie, zaczynając od sytuacji bardzo zbliżonej do wygranej. Optymalizujesz go tak, aby znalazł rozwiązanie w rozsądnym czasie (godziny), a następnie znajdziesz sposoby na wybór zwycięskiej ścieżki, nawet jeśli nie zbadałeś jeszcze wszystkich wyników, abyś mógł faktycznie przerwać „myślenie” czas na przełom.

Dopiero wtedy mogłem spojrzeć na optymalizację reprezentacji, aby przyspieszyć poszczególne obliczenia, na przykład używając długich liczb całkowitych, jak sugerowano. Bez względu na to, jak szybko możesz dokonać pojedynczego porównania, jeśli sposób, w jaki przemierzasz przestrzeń problemową, nie ma dobrej heurystyki, zajmie to całe wieki.

Możesz iść naprawdę, jak chcesz, ale oto moje przemyślenia na ten temat:

Użyłbym Java, ponieważ pozwala to być na bardzo wysokim poziomie i mieć do dyspozycji biblioteki interfejsów użytkownika (AWT, Swing). Do modelowania szachownicy i pionków można zastosować podejście obiektowe. Inne przedmioty mogą zastąpić historię ruchu i punktację. Nawet gracze mogą być obiektami, a następnie możesz w przyszłości rozszerzyć swoją Playerklasę o sztuczny, inteligentny odtwarzacz komputerowy.

Możesz rzucić okiem na kontroler widoku modelu (MVC), ponieważ jest to bardzo fajne podejście w tym przypadku, aby powiązać obiekty modelu (model domeny) z interfejsem użytkownika (widok) i umożliwić użytkownikowi manipulowanie model (przez kontroler).

Możesz także zastosować programowanie oparte na testach , które nie tylko zapewnia, że ​​wszystkie metody zachowują się zgodnie z oczekiwaniami, ale także zmusza do napisania testowalnego, modułowego kodu.

Zasady samych szachów są dość proste. Musisz tylko być w stanie stworzyć matrycę (tablica 2-wymiarowa) dla tablicy i znaleźć sposób na zakodowanie pojęć elementów, zasad ruchu dla każdego elementu, potwierdzenia, że ​​ruch jest legalny i warunków, które sygnalizują koniec gry. Nie ma w tym nic szczególnie trudnego. Powinieneś używać języka, który znasz najlepiej.

Teraz, jeśli chcesz stworzyć szachową sztuczną inteligencję, która przyjmie rolę jednego z graczy, tam sprawy stają się trudne. Ale znowu wybór języka nie jest tutaj największym problemem; zrozumienie zasad sztucznej inteligencji jest. To będzie znacznie ważniejszy czynnik.

(Powiedziawszy to, ten rodzaj podejmowania decyzji może być bardzo intensywny obliczeniowo, i prawdopodobnie będziesz chciał użyć czegoś, co kompiluje się do kodu natywnego, a nie języka skryptowego. A C ++ jest bardzo złym wyborem, nie dlatego, że nie jest dobrze - dostosowane do tego problemu, ale po prostu dlatego, że jest to bardzo zły język, a próba zaimplementowania w nim skomplikowanych rzeczy jest dobrym sposobem na samodzielne zakodowanie różnego rodzaju problemów.)