autorstwa Lauri Hartikka
przyjrzyjmy się kilku podstawowym pojęciom, które pomogą nam stworzyć prostą si w szachach:
- generowanie ruchu
- ocena planszy
- Minimax
- i przycinanie alfa beta.
na każdym kroku udoskonalamy nasz algorytm jedną z tych sprawdzonych technik programowania szachowego. Zademonstruję, jak każdy z nich wpływa na styl gry algorytmu.
możesz zobaczyć ostateczny algorytm AI tutaj na Githubie.
Krok 1: generowanie ruchu i wizualizacja planszy
użyjemy szachów.biblioteka js do generowania ruchu i szachownicy.js do wizualizacji planszy. Biblioteka move generation zasadniczo implementuje wszystkie zasady gry w szachy. Na tej podstawie możemy obliczyć wszystkie ruchy prawne dla danego stanu planszy.
Korzystanie z tych bibliotek pomoże nam skupić się tylko na najciekawszym zadaniu: stworzeniu algorytmu, który znajdzie najlepszy ruch.
zaczniemy od stworzenia funkcji, która po prostu zwraca losowy ruch ze wszystkich możliwych ruchów:
chociaż ten algorytm nie jest zbyt solidnym szachistą, jest dobrym punktem wyjścia, ponieważ możemy grać przeciwko niemu:
Krok 2 : Ocena pozycji
teraz spróbujmy zrozumieć, która strona jest silniejsza w określonej pozycji. Najprostszym sposobem, aby to osiągnąć, jest policzenie względnej siły elementów na planszy za pomocą poniższej tabeli:
dzięki funkcji oceny jesteśmy w stanie stworzyć algorytm, który wybierze ruch, który da najwyższą ocenę:
jedynym namacalnym ulepszeniem jest to, że nasz algorytm będzie teraz przechwytywał kawałek, jeśli będzie mógł.
Krok 3: drzewo wyszukiwania za pomocą Minimax
następnie utworzymy drzewo wyszukiwania, z którego algorytm może wybrać najlepszy ruch. Odbywa się to za pomocą algorytmu Minimax.
w tym algorytmie rekurencyjne drzewo wszystkich możliwych ruchów jest badane na określoną głębokość, a pozycja jest oceniana na końcowych „liściach” drzewa.
następnie zwracamy najmniejszą lub największą wartość potomka do węzła nadrzędnego, w zależności od tego, czy ma się poruszać biała czy czarna. (To znaczy, staramy się albo zminimalizować lub zmaksymalizować wynik na każdym poziomie.)
dzięki Minimax nasz algorytm zaczyna rozumieć podstawowe taktyki szachów:
skuteczność algorytmu minimax jest w dużej mierze oparta na głębokości wyszukiwania, którą możemy osiągnąć. Jest to coś, co poprawimy w następnym kroku.
Krok 4: Przycinanie alfa-beta
przycinanie Alfa-beta jest metodą optymalizacji algorytmu minimax, która pozwala nam pominąć niektóre gałęzie w drzewie wyszukiwania. Pomaga nam to znacznie głębiej ocenić drzewo wyszukiwania minimax przy użyciu tych samych zasobów.
przycinanie alfa-beta opiera się na sytuacji, w której możemy przestać Oceniać część drzewa wyszukiwania, jeśli znajdziemy ruch, który prowadzi do gorszej sytuacji niż wcześniej odkryty ruch.
przycinanie alfa-beta nie wpływa na wynik algorytmu minimax — tylko przyspiesza.
algorytm alfa-beta jest również bardziej wydajny, jeśli zdarzy nam się najpierw odwiedzić te ścieżki, które prowadzą do dobrych ruchów.
z alfa-beta otrzymujemy znaczne wzmocnienie algorytmu minimax, jak pokazano w poniższym przykładzie:
kliknij na ten link, aby wypróbować ulepszoną wersję Alpha-beta szachowej sztucznej inteligencji.
Krok 5: Ulepszona funkcja oceny
funkcja oceny początkowej jest dość naiwna, ponieważ liczymy tylko materiał, który znajduje się na planszy. Aby to poprawić, dodajemy do oceny czynnik uwzględniający pozycję elementów. Na przykład, rycerz na środku planszy jest lepszy (ponieważ ma więcej opcji, a tym samym jest bardziej aktywny) niż rycerz na krawędzi planszy.
użyjemy nieco dostosowanej wersji tabel piece-square, które zostały pierwotnie opisane w CHESS-programming-wiki.
z następującym ulepszeniem, zaczynamy uzyskiwać algorytm, który gra w „przyzwoite” szachy, przynajmniej z punktu widzenia zwykłego gracza:
wnioski
siła nawet prostego algorytmu gry w szachy polega na tym, że nie popełnia on głupich błędów. Mimo to nadal brakuje jej strategicznego zrozumienia.
dzięki metodom, które tu wprowadziłem, udało nam się zaprogramować algorytm gry w szachy, który może grać w podstawowe szachy. „Część AI” (wyłączona z generowania ruchu) końcowego algorytmu to zaledwie 200 linii kodu, co oznacza, że podstawowe pojęcia są dość proste do wdrożenia. Możesz sprawdzić ostateczną wersję na GitHub.
kilka dalszych ulepszeń, które moglibyśmy wprowadzić do algorytmu, to na przykład:
- move-ordering
- szybsze generowanie ruchu
- i ewaluacja specyficzna dla gry.
