un

guest
1 / ?
back to lessons

Czynnik Rozgałęzienia & Liczba Węzłów

Drzewo gry modeluje każą możliwą sekwencję ruchów od pozycji początkowej. Każdy węzeł reprezentuje stan planszy. Każde koło reprezentuje jeden legalny ruch. Struktura drzewa determinuje, czy wyszukiwanie pozostaje możliwe.

Kluczowe Parametry

Czynnik rozgałęzienia b: liczba dostępnych legalnych ruchów w typowej pozycji.

Głębokość d: liczba pleyów (pół-ruchów) wyszukiwania w przód.

Liczba węzłów na głębokości d: b^d

Razem węzłów na wszystkich głębokościach: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

Dla dużego b i d, łączna liczba ≈ b^d (dominowana przez poziom liści).

4×4×4 Tic-Tac-Toe

Pełne drzewo gry: b ≈ 64 (wolne pola), d = 64 (całkowita liczba ruchów). Pełna liczba węzłów ≈ 64^64 ≈ 10^115. Obserwowany wszechświat zawiera około 10^80 atomów. Brute-force search jest fizycznie niemożliwy.

Game Tree & Alpha-Beta Pruning

Obliczanie Rozmiaru Drzewa

Szachy dostarczają bardziej realistyczne liczby. Średni czynnik rozgałęzienia b ≈ 35. Szósta wysokość wyszukiwania (3 ruchy każda strona) wymaga około 35^6 węzłów.

Oblicz liczbę węzłów liściowych dla wyszukiwania szachowego o głębokości d = 6 pleyów z czynnikiem rozgałęzienia b = 35. Następnie oblicz to samo dla d = 10 pleyów. Pokaż oba obliczenia eksperymentalnie.

Przycinanie Alfa-Beta: Redukcja Wykładni

Szczytowanie 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 obciąć jakąkolwiek siostrzaną gałąź, której wartość nieodwracalnie spada poniżej V (dla gracza maksymalizującego) lub powyżej V (dla gracza minimalizującego).

Optymalna geometria

Pod optymalnym porządkiem ruchów (pierwszy wyszukiwane są najlepsze ruchy), alfa-beta zmniejsza skuteczny czynnik rozgałęzienia z b do √b. Skuteczna głębokość wyszukiwania wzrasta o połowę dla tego samego budżetu węzłów:

Pełne wyszukiwanie: b^d węzłów

Alfa-beta najlepszy przypadek: b^(d/2) węzłów

Przykład: b=35, d=6. Pełne: 35^6 ≈ 1,84 × 10^9. Alfa-beta: 35^3 = 42,875. Współczynnik redukcji: ~43,000.

W praktyce porządek ruchów jest niedoskonały. Typowy współczynnik redukcji: b^(d×0.75) — równoważny czynnik rozgałęzienia ≈ b^0.75.

Dla silnika szachowego z b = 35 i d = 8 posunięć, oblicz liczbę węzłów w przypadku: (1) pełnej wyszukiwania minimax, (2) idealnej ścięcia alfa-beta (najlepszy przypadek). Jakie jest współczynnik redukcji? Pokaż wszystkie obliczenia.

Dwójność Centrum-Krąg

Hamming zauważa dualność geometryczną w klocku 4×4×4: istnieje odwrotność wysyłająca 8 pozycji narożnikowych na 8 pozycji centralnych (wewnętrzny 2×2×2 klocko) oraz odwrotnie, przy czym zachowuje wszystkie 76 linii zwycięstwa.

Liczenie linii przechodzących położenie

W klocku 4×4×4, pozycje różnią się liczbą linii zwycięstwa przechodzących przez nie:

Pozycje narożnikowe: 7 linii każda (4 przekątne twarzy, 2 linie krawędziowe, 1 przekątna przestrzenna)

Pozycje ośrodkowe-krawędziowe: 4 linie każda

Pozycje ośrodkowe-twarz: 6 linii każda

Pozycje ośrodkowe-ciała (wewnętrzny 2×2×2): 7 linii każda

Duality mapa narożników (7 linii) na pozycje centralne ciała (7 linii). Obie serie tworzą 'węzeł gorący'.

Dlaczego węzeł gorący ma znaczenie geometrycznie

Gracz kontrolujący więcej wysokoprocentowych pozycji kontroluje więcej potencjalnych linii zwycięstwa. To bezpośredni argument geometryczny: maksymalizacja pokrycia linii kieruje wyborem ruchów bez jakiegokolwiek wyszukiwania.

Kula 4×4×4 ma 76 łącznych wygrywających linii i 64 pozycji. 8 krawędzi każda leży na 7 liniach, 8 pozycji środkowych ciała każda leży na 7 liniach, 24 pozycji środkowych twarzy każda leży na 6 liniach, a 24 pozycji brzegowych każda leży na 4 liniach. Sprawdź: czy te liczby sumują się zgodnie? Oblicz łączną liczbę incydentów (pozycja, linia) z obu stron: sumując się przez pozycje, a osobno licząc 4 końce na linii. Czy dwa łączne wyniki zgadzają się?

Funkcje ewaluacyjne

Każde programowanie gier potrzebuje funkcji ewaluacyjnej: funkcji przekształcającej stany plansz w wartości liczbowe (pozytywne = dobre dla gracza maksymalizującego, ujemne = dobre dla gracza minimalizującego). Funkcja ewaluacyjna dostarcza warunku granicznego dla liści drzewa wyszukiwania.

Liniowe funkcje ewaluacyjne

Liniowa funkcja ewaluacyjna przypisuje wagę w_i do każdej cechy f_i pozycji:

E(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n

Dla 4×4×4 krzyżówki: cechami mogą być otwarte linie kontrolowane, pozycje w wysokich prostych kwadratów, groźby łańcuchów. Dla szachów: liczba materiału, kontrola centrum, bezpieczeństwo króla, struktura pionów.

To liniowa funkcja w przestrzeni cech — hiperpłaszczyzna w ℝ^n. Dwie pozycje z tymi samymi wartościami cech otrzymują tę samą ocenę niezależnie od wszystkich innych różnic. Geometria funkcji ewaluacyjnej określa, co program 'zauważa'.

Program Samuela do gry w szachy poprawił, dostosowując wektor wag w — spadek gradientowy w przestrzeni liniowych funkcji ewaluacyjnych.

Prosta funkcja ewaluacyjna dla gry w krzyżówkę 4×4×4 używa dwóch cech: (1) f_1 = liczba twoich otwartych linii (linie, w których masz klocki, a przeciwnik nie ma żadnych), (2) f_2 = liczba otwartych linii przeciwnika. Ewaluacja: E = w_1 × f_1 − w_2 × f_2. Jeśli w_1 = 2 i w_2 = 3, oblicz E dla pozycji, w której masz 12 otwartych linii, a przeciwnik 8. Następnie: jeśli E > 0 oznacza to, że pozycja jest w twoim favie, co mówi to wynik o pozycji?

Geometria & Granica Formalizacji

Drzewo gry ma czystą strukturę geometryczną: wykładnicze wzrostu na głębokości d, redukowalne do b^(d/2) przez alfa-beta, dalej redukowalne przez ograniczanie się do wysokiej wartości pozycji (gorące miejsca redukują skuteczne b). Funkcja ewaluacji definiuje hiperpłaszczyznę w przestrzeni cech.

Wszystko to jest czyste, precyzyjne, formalnie kompletnie. Opisuje środek problemu gry - region, gdzie matematyczna struktura dostarcza jasne wskazówki.

Góra - gdzie należy przejść od zastosowania reguł do eksploracji, kiedy należy wymienić korzyści pozycyjne na szanse taktyczne, jak rozpoznawać emergentne wzory poza funkcją ewaluacji - opiera się na tej formalizacji. Wiedza Hamminga żyje na tym krańcu.

Geometria pozwala obliczyć, ile wyszukiwania można sobie pozwolić. Nie mówi ci, czego szukać.

Odzyskaj geometrię pokrytą w tej lekcji. Formalizm drzewa gry (b^d węzłów, redukcja alfa-beta do b^(d/2), liniowe funkcje ewaluacji) dostarcza dokładnego opisu *zatrzymywanych* części gry. Gdzie geometria się rozpada - i jakie właściwości inteligencji gry są poza geometrycznym modelem? Odpowiedz konkretne, nie ogólna obserwacja.