Szachy: wysoki współczynnik rozgałęzienia

Question

Próbuję stworzyć prosty silnik szachowy, ale zmagam się z jego wydajnością. Zaimplementowałam Negamax z przycinaniem alfa-beta i iteracyjnym pogłębianiem (bez żadnych dodatkowych heurystyk), ale nie jestem w stanie uzyskać rozsądnego czasu wyszukiwania poza 3-4-tą warstwą. Oto fragment z dziennika mój program od samego początku gry:

2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 
2013-05-11 18:22:06,897 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 
2013-05-11 18:22:08,005 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 
2013-05-11 18:22:10,485 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6 

To pokazuje, że rozgałęzienia współczynnik wynosi około 10. Czytałem, że z właściwego uporządkowania ruchu powinien być coraz coś około 6, więc podejrzewam że moje zamówienie jest złe. Obecnie działa w ten sposób:

1. Węzeł drzewa gry ma powiązaną listę swoich dzieci; początkowo, przechwytuje i promocje są umieszczone przed spokojnych ruchów
2. Podczas poszukiwań, dziecko, które zwiększa alfa lub powoduje odcięcia jest umieszczone na początku listy
3. Na następnej iteracji pogłębienie PV należy szukać najpierw

Czy jest to właściwy sposób zamawiania ruchów i oddziałuję na czynnik, którego się spodziewam? Obecnie używam prostej statycznej funkcji oceny, która bierze pod uwagę tylko istotną różnicę pozycji - czy może być powodem niskiej szybkości odcięcia (jeśli uwzględni się także ruchliwość figur, otrzymam podobne wyniki)? Czy techniki takie jak redukcja ruchów zerowych lub heurystyczna pomoc zabójcy znacząco (nie o 10-15%, ale o rząd wielkości)? Nie oczekuję, że mój silnik będzie mocny, ale chciałbym, aby współczynnik rozgałęzienia wynosił około 6.

Answer 1

Rozwinąłem także silnik szachowy w języku C#, który ma współczynnik rozgałęzienia około 2,5. Z pewnością możliwe jest ulepszenie silnika o wiele rzędów wielkości. W dzisiejszych czasach ogólną strategią jest stosowanie bardzo agresywnego przycinania ruchów w oparciu o porządne porządkowanie ruchów. Poświęcasz trochę poprawności, ponieważ widzisz głębokie linie taktyczne.

Oto przegląd technik, które okazały się najbardziej skuteczne.Zauważ, że niektóre komponenty są uzupełnieniami, a inne są zamiennikami, więc wyniki, które podaję, są ogólnymi wskazówkami. Wielkie zyski na końcu listy nie są możliwe, jeśli nie masz silnego fundamentu.

1. Wystarczy negamax z alpha-beta pruning: głębokości 4 w ciągu 3 sekund.

2. Dodaj iterative deepening i null move heuristic: głębia 5. Pogłębianie iteracyjne tak naprawdę nie pomaga w tym momencie, ale jest łatwe do wdrożenia. Ruch o wartości zerowej polega na pomijaniu swojej tury i sprawdzaniu, czy możesz uzyskać wyłączenie beta z płytkim wyszukiwaniem. Jeśli możesz, prawdopodobnie jest to bezpieczne przycinanie drzewa, ponieważ prawie zawsze jest to korzystne dla ruchu .

3. Killer heuristic: głębokość 6. Wiąże przechowywania ruchy, które powodują odcięcia beta i próbuje je najpierw, czy są one legalne następnym razem jesteś na tej samej głębokości. Wygląda na to, że robisz coś podobnego już .

4. MVV/LVA ordering: głębokość 8. Zasadniczo chcesz umieścić przechwytuje że mają wiele potencjalnych korzyści materialnych netto na szczycie ruchu listy. Jeśli więc pionek zdobędzie królową, powinieneś najpierw go przeszukać.

5. Bitboard representation: głębokość 10. To nie poprawia współczynnika rozgałęzienia , ale to właśnie zrobiłem, gdy dotarłem do tego punktu. Porzuć tablice , użyj zamiast nich opcji UInt64 i użyj polecenia make/unmake zamiast copy-make. Nie musisz używać magicznych bitboardów, jeśli uważasz, że jest to trudne; istnieją prostsze metody, które wciąż są bardzo szybkie. Płyty bitowe znacznie poprawiają wydajność i ułatwiają pisanie komponentów oceny. Poszedłem od perft (6), biorąc minut do podjęcia 3 sekund. (Nawiasem mówiąc, pisząc perft funkcji jest to świetny sposób, aby zapewnić prawidłowość generacji ruchu)

6. Transposition table: głębokość 13. Daje to wielkie korzyści, ale również bardzo trudno uzyskać prawo. Bądź absolutnie pewien, że twoja pozycja hashing jest poprawna przed zaimplementowaniem tabeli. Większość korzyści pochodzi z niesamowitego ruchu, który zamawia stół. Zawsze przechowuj najlepsze ruchy w tabeli, a gdy tylko uzyskasz pasującą pozycję, spróbuj najpierw .

7. Late move reductions: głębokość 16. To znacznie zwiększa głębokość poszukiwań, ale przyrost siły jest bardziej sztuczny niż w przypadku innych technik. Zasadniczo twój ruch zamawiania jest na tyle dobry, że wystarczy przeszukać tylko kilka pierwszych ruchów w węźle, a możesz po prostu sprawdzić inne z płytkimi wyszukiwaniami.

8. Futility pruning: głębokość 17. Liść węzły są przycinane omijając ruchy które mają niewielką szansę na poprawę wartości węzła patrząc na potencjalne korzyści materialnych. Jeśli potencjalny wzrost netto ruchu + statyczna ocena pozycji jest poniżej aktualnej wartości pozycji, pomiń ocenę dla ruchu.

Istnieje wiele innych elementów, które również pomagają, ale większość z nich jest niewielka, a niektóre są zastrzeżone.: D Nie chodzi jednak o wysokie głębokości wyszukiwania i niskie czynniki rozgałęzienia. Rzeczy takie jak quiescence search pogarszają głębokość wyszukiwania, ale są prawie koniecznością dla każdego silnika. Bez tego twój silnik będzie cierpiał z powodu wielkich błędów taktycznych. Możesz również rozważyć check extensions i single reply extensions. Poleciłbym również przynajmniej wprowadzenie piece-square tables do twojej funkcji oceny. Jest to bardzo łatwy sposób na znaczne ulepszenie pozycyjnej znajomości programu; prawdopodobnie zobaczysz, że twój silnik odtwarza więcej popularnych otworów. Programowanie w szachy jest fajnym hobby i mam nadzieję, że ilość informacji nie zniechęci Cię!

Answer 2

Istnieje wiele heurystyk, które można wykorzystać w celu zmniejszenia współczynnika rozgałęzienia.

Najpierw należy użyć transposition table (TT) do przechowywania pozycji wyników, głębokości i najlepszego ruchu. Przed przeszukaniem ruchu najpierw sprawdź, czy został już przeszukany na głębokości> = do głębokości, do której zamierzasz przeszukać. Jeśli tak, możesz po prostu użyć wyniku z tabeli. Jeśli nie, możesz nadal używać przeniesienia w tabeli jako pierwszego ruchu do wyszukiwania.

Jeśli nie ma dopasowania w TT dla pozycji (w wyszukiwaniu), można użyć Iterative Deepening (ID). Zamiast przeszukiwać do głębokości N, najpierw wykonaj wyszukiwanie na głębokość N-2. Będzie to naprawdę szybkie i da ci możliwość wyszukiwania najpierw na głębokości N.

Istnieje również Null Move Pruning. W połączeniu z Alpha-Beta (Negamax jest odmianą Alpha-Beta) znacznie zmniejszy twój czynnik rozgałęziania. Pomysł polega na wyszukaniu pozycji, spróbowaniu ruchu zerowego (nie grając) i wykonaniu poszukiwań zredukowanych (N-2 lub N-3). Ograniczenie wyszukiwania będzie naprawdę szybkie. Jeśli wynik wyszukiwania z przesunięciem zerowym jest nadal wyższy niż beta, oznacza to, że pozycja jest tak zła, że ​​nie musisz już jej przeszukiwać (nie zawsze jest to prawda, ale w większości przypadków).

Oczywiście istnieje wiele innych heurystyk, których możesz użyć do poprawy swojego move ordering, które poprawią twój współczynnik rozgałęziania.