Współczynnik rozgałęzienia & liczba węzłów
Drzewo gry modeluje każdą możliwą sekwencję ruchów z pozycji początkowej. Każdy węzeł reprezentuje stan planszy. Każda krawędź reprezentuje jeden legalny ruch. Struktura drzewa określa, czy wyszukiwanie pozostaje wykonalne.
Kluczowe parametry
Współczynnik rozgałęzienia b: liczba legalnych ruchów dostępnych w typowej pozycji.
Głębokość d: liczba półruchów do przeszukania do przodu.
Liczba węzłów na głębokości d: b^d
Całkowita liczba węzłów na wszystkich głębokościach: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Dla dużych b i d, suma ≈ b^d (zdominowana przez poziom liści).
Kółko i krzyżyk 4×4×4
Pełne drzewo gry: b ≈ 64 (pola legalne), d = 64 (całkowita liczba ruchów). Pełna liczba węzłów ≈ 64^64 ≈ 10^115. Obserwowany wszechświat zawiera mniej więcej 10^80 atomów. Wyszukiwanie brute-force jest fizycznie niemożliwe.
Obliczanie rozmiaru drzewa
Szachy dostarczają bardziej realistycznych liczb. Średni współczynnik rozgałęzienia b ≈ 35. Wyszukiwanie 6-półruchowe (3 ruchy każdej strony) wymaga około 35^6 węzłów.
Przycinanie alfa-beta: zmniejszanie wykładnika
Przycinanie alfa-beta eliminuje poddrzewa, które nie mogą wpłynąć na wynik minimax. Kluczowe spostrzeżenie: jeśli już wiesz, że jedna gałąź daje wartość V, możesz przyciąć każdą gałąź siostrę, której wartość dowodnie spada poniżej V (dla gracza maksymalizującego) lub powyżej V (dla gracza minimalizującego).
Geometria najlepszego przypadku
Przy optymalnym porządkowaniu ruchów (najlepsze ruchy przeszukane pierwsze), przycinanie alfa-beta zmniejsza efektywny współczynnik rozgałęzienia z b na √b. Głębokość wyszukiwania skutecznie się podwaja dla tego samego budżetu węzłów:
Pełne wyszukiwanie: b^d węzłów
Przycinanie alfa-beta najlepszy przypadek: b^(d/2) węzłów
Przykład: b=35, d=6. Pełne: 35^6 ≈ 1,84 × 10^9. Przycinanie alfa-beta: 35^3 = 42 875. Współczynnik redukcji: ~43 000.
W praktyce porządkowanie ruchów jest niedoskonałe. Typowa redukcja: b^(d×0,75) — równoważny współczynnik rozgałęzienia ≈ b^0,75.
Dualność środka-rogu
Hamming zauważa dualność geometryczną w sześcianie 4×4×4: istnieje inwersja wysyłająca 8 pozycji narożnika do 8 pozycji środka (wewnętrzny sześcian 2×2×2) & na odwrót, zachowując wszystkie 76 linii zwycięstwa.
Liczenie linii przechodzących przez pozycję
W sześcianie 4×4×4 pozycje różnią się tym, ile linii zwycięstwa przechodzi przez nie:
Pozycje narożnika: 7 linii każda (4 przekątne twarzy, 2 linie krawędzi, 1 przekątna przestrzeni)
Pozycje centrum krawędzi: 4 linie każda
Pozycje centrum twarzy: 6 linii każda
Pozycje centrum ciała (wewnętrzne 2×2×2): 7 linii każda
Dualność mapuje narożniki (7 linii) na centra ciała (7 linii). Oba zestawy tworzą 'gorące punkty'.
Dlaczego gorące punkty mają znaczenie geometryczne
Gracz kontrolujący więcej pozycji z wysoką liczbą linii kontroluje więcej potencjalnych linii zwycięstwa. To jest bezpośredni argument geometryczny: maksymalizacja pokrycia linii przewodniczy wyborowi ruchu bez jakichkolwiek poszukiwań.
Funkcje oceny
Każdy program grający w grę potrzebuje funkcji oceny: funkcji mapującej stany planszy na wartości numeryczne (dodatnie = dobre dla gracza maksymalizującego, ujemne = dobre dla gracza minimalizującego). Funkcja oceny zapewnia warunek brzegowy na liściach drzewa wyszukiwania.
Liniowe funkcje oceny
Liniowa funkcja oceny przypisuje wagę w_i każdej cesze f_i pozycji:
E(pozycja) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Dla kółka i krzyżyka 4×4×4: cechy mogą zawierać kontrolowane otwarte linie, pozycje w polach o wysokiej liczbie linii, zagrożone rozwidlenia. Dla szachów: liczba materiału, kontrola środka, bezpieczeństwo króla, struktura pionów.
To jest funkcja liniowa w przestrzeni cech — hiperpłaszczyzna w ℝ^n. Dwie pozycje o tych samych wartościach cech otrzymują tę samą ocenę, niezależnie od wszystkich innych różnic. Geometria funkcji oceny określa, co program 'widzi'.
Program szachowy Samuela poprawiał się poprzez dostosowanie wektora wagi w — zejście gradientowe w przestrzeni liniowych funkcji oceny.
Geometria & granica formalizacji
Drzewo gry ma czystą strukturę geometryczną: wzrost wykładniczy na głębokości d, redukowalny do b^(d/2) przez alfa-beta, dodatkowo redukowalny przez ograniczenie do pozycji wysokiej wartości (gorące punkty zmniejszają efektywne b). Funkcja oceny definiuje hiperpłaszczyznę w przestrzeni cech.
Wszystko to jest czyste, precyzyjne, formalnie kompletne. To opisuje centrum problemu gry — region gdzie struktura matematyczna daje jasne wskazówki.
Granica — gdzie przejść od aplikacji reguł do eksploracji, kiedy handlować przewagą pozycyjną dla okazji taktycznej, jak rozpoznać wyłaniające się wzorce poza funkcją oceny — opiera się tej formalizacji. Ukryta wiedza Hamminga żyje na tej granicy.
Geometria pozwala ci obliczyć ile wyszukiwania możesz sobie pozwolić. To nie mówi ci co szukać.