Nie mogę mówić za algorytmem zastosowanym w Deep Blue, ale spróbuję wyjaśnić ulepszenia w programowaniu szachowym. Szybkość to największa poprawa. Deep Blue używało wieloprocesorowych komputerów dedykowanych, więc porównanie nie jest tak naprawdę możliwe.
https://chessprogramming.wikispaces.com/ jest doskonałym źródłem, ale nawigacja jest trudna.
Istnieją 3 główne funkcje, które zostały ulepszone w celu ulepszenia silnika szachowego: funkcje oceny, generowania ruchów i wyszukiwania.
Ocena jest najtrudniejsza do zaprogramowania, ponieważ istnieje wiele wyjątków od zasad. Ponieważ miejsce na dysku twardym staje się coraz tańsze, funkcja eval pozwala na ocenę większej liczby wyjątków.
Generowanie ruchów, a także wykonywanie i cofanie ruchów, pochłania dużo pamięci, ponieważ trzeba je wykonać wiele razy. Najczęstsze funkcje generowania to skrzynka pocztowa, płyta główna, 0x88, 8x8, rozszerzone płyty (10x10, 10x12) i z góry określona tablica / tabela ruchów (* Używam indeksowanej tabeli ruchów). Obecna opinia jest taka, że bitboardy są szybsze, a używanie magicznych bitboardów przyspiesza to nawet o 30%. Dr Robert Hyatt, profesor i twórca cratfy silnika szachowego, twierdzi, że nie ma znaczącego wzrostu prędkości.
Funkcja wczesnego wyszukiwania była pierwotną funkcją min-max. Zasadniczo próbowałeś zmaksymalizować wynik strony, aby się poruszyć i zminimalizować wynik przeciwnika. Alpha-Beta była pierwszą poprawą. Zmniejszyli liczbę przeszukiwanych ruchów według tabeli transpozycji, wartości odcięcia, okien aspiracji i heurystyki historii. Są to wyszukiwania w pierwszej kolejności. Istnieje również wewnętrzne iteracyjne wyszukiwanie pogłębiające, które próbuje wyszukać „najlepszy” ruch (y) najgłębiej mając nadzieję, że wyszukiwanie innych ruchów okaże się bezowocne.
UWAGA: Moja tabela indeksu. GNUChess i Jester używają tablicy indeksów do generowania swoich ruchów. Inicjują silnik, wypełniając tablicę możliwymi ruchami. Weź sześć elementów i oblicz legalne ruchy dostępne z każdego kwadratu. Więc każdy kawałek miał tablicę [64] [8]. Wziąłem ten pomysł i skompresowałem go do dwóch indeksów i tabeli. Tabela zawiera wartość, która mówi, czy 16 ruchów jest możliwych, jeden indeks przechowuje przesunięcie, a drugi maskę.
offset [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};
maska [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};
Następnie wygenerowanie ruchu przesuwnego jest tak proste, jak sprawdzenie ważności maski w dopuszczalnych przesunięciach względem tabeli ruchów.