un — Geometri för maskininlärning: I

un

gäst

1 / ?

Förgreningsfaktor & nodräkning

Ett sökträd modellerar varje möjlig sekvens av drag från en startposition. Varje nod representerar ett brädtillstånd. Varje kant representerar ett lagligt drag. Träets struktur avgör om sökning förblir genomförbar.

Nyckelparametrar

Förgreningsfaktor b: antalet lagliga drag tillgängliga på en typisk position.

Djup d: antalet halfdrag (plies) att söka framåt.

Nodräkning vid djup d: b^d

Totalt antal noder över alla djup: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

För stort b och d domineras totalen av bladnivån ≈ b^d.

4×4×4 Tre-i-rad

Det fullständiga sökträdet: b ≈ 64 (lagliga rutor), d = 64 (totala drag). Fullständig nodräkning ≈ 64^64 ≈ 10^115. Det observerbara universum innehåller ungefär 10^80 atomer. Brute-force-sökning är fysiskt omöjlig.

Sökträd & Alfa-betabeskärning

Beräkna trädstorlek

Schack ger mer realistiska tal. Genomsnittlig förgreningsfaktor b ≈ 35. En 6-plies-sökning (3 drag varje sida) kräver ungefär 35^6 noder.

Beräkna antalet bladnoder för en schacksökning vid djup d = 6 plies med förgreningsfaktor b = 35. Beräkna sedan samma för d = 10 plies. Visa båda beräkningarna uttryckligen.

Alfa-betabeskärning: Minska exponenten

Alfa-betabeskärning eliminerar underträd som inte kan påverka minimax-resultatet. Nyckelintentet: om du redan vet att en gren ger värdet V, kan du beskära någon syskongren vars värde bevisligen faller under V (för den maximerande spelaren) eller över V (för den minimedrande spelaren).

Bästa-fallsgeometri

Under optimal dragordning (bästa drag sökta först) minskar alfa-beta den effektiva förgreningsfaktorn från b till √b. Sökdjupet fördubblas effektivt för samma nodbudget:

Fullständig sökning: b^d noder

Alfa-beta bästa fall: b^(d/2) noder

Exempel: b=35, d=6. Fullständig: 35^6 ≈ 1,84 × 10^9. Alfa-beta: 35^3 = 42 875. Minskningsfaktor: ~43 000.

I praktiken är dragordningen ofullständig. Typisk minskning: b^(d×0,75) — motsvarande förgreningsfaktor ≈ b^0,75.

För en schackmotor med b = 35 och d = 8 plies, beräkna nodräkningen under: (1) fullständig minimax-sökning, (2) perfekt alfa-betabeskärning (bästa fall). Vad är minskningsfaktorn? Visa alla beräkningar.

Center-hörnsdualitet

Hamming noterar en geometrisk dualitet i 4×4×4-kuben: det finns en inversion som skickar de 8 hörnpositionerna till de 8 mittenpositionerna (den inre 2×2×2-kuben) & vice versa, samtidigt som alla 76 vinnande linjer bevaras.

Räkna linjer genom en position

I en 4×4×4-kub skiljer sig positioner i hur många vinnande linjer som går genom dem:

Hörnpositioner: 7 linjer varje (4 ansiktsdiagonaler, 2 kantlinjer, 1 rymddiagonal)

Kantmittenpositioner: 4 linjer varje

Ansiktesmittenpositioner: 6 linjer varje

Kroppsmittenpositioner (inre 2×2×2): 7 linjer varje

Dualiteten mappar hörnpositioner (7 linjer) till kroppsmittenpositioner (7 linjer). Båda uppsättningarna bildar 'heta ställen.'

Varför heta ställen spelar roll geometriskt

En spelare som kontrollerar fler högt-linje-räknings-positioner kontrollerar fler potentiella vinnande linjer. Detta är ett direkt geometriskt argument: linjekoverageökning maximering vägleder dragval utan någon sökning.

4×4×4-kuben har 76 totala vinnande linjer och 64 positioner. De 8 hörnen ligger varje på 7 linjer, de 8 kroppsmittenpositionerna ligger varje på 7 linjer, de 24 ansiktesmittenpositionerna ligger varje på 6 linjer, och de 24 kantpositionerna ligger varje på 4 linjer. Verifiera: adderas dessa räkningar konsekvent? Beräkna den totala räkningen av (position, linje) incidenser från båda sidor: genom att summera över positioner, och separat genom att räkna 4 ändpunkter per linje. Överensstämmer de två totalerna?

Utvärderingsfunktioner

Varje spelprogrammet behöver en utvärderingsfunktion: en funktion som mappar brädtillstånd till numeriska värden (positiv = bra för den maximerande spelaren, negativ = bra för den minimedrande spelaren). Utvärderingsfunktionen tillhandahåller gränsvillkoret vid bladen i sökträdet.

Linjära utvärderingsfunktioner

En linjär utvärderingsfunktion tilldelar en vikt w_i till varje egenskap f_i av positionen:

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

För 4×4×4 tre-i-rad: egenskaper kan inkludera öppna linjer kontrollerade, positioner i höga-linje-räkningsrutor, hotade gafflar. För schack: materiellräkning, centerregel, kungesäkerhet, bonderstruktur.

Detta är en linjär funktion i egenskapsrymden — ett hyperplan i ℝ^n. Två positioner med samma egenskapsvärden får samma utvärdering oavsett alla andra skillnader. Utvärderingsfunktionens geometri bestämmer vad programmet 'ser.'

Samuels checkers-program förbättrades genom att justera viktvektorn w — gradientnedstigning i utrymmet av linjära utvärderingsfunktioner.

En enkel 4×4×4 tre-i-rad-utvärderingsfunktion använder två egenskaper: (1) f_1 = antalet dina öppna linjer (linjer där du har brickor och motståndaren inte har några), (2) f_2 = antalet motståndares öppna linjer. Utvärderingen: E = w_1 × f_1 − w_2 × f_2. Om w_1 = 2 och w_2 = 3, beräkna E för en position där du har 12 öppna linjer och din motståndare har 8. Sedan: om E > 0 betyder att positionen gynnar dig, vad säger detta resultat om positionen?

Geometri & gränsen för formalisering

Sökträdet har en ren geometrisk struktur: exponentiell tillväxt vid djup d, reducerbar till b^(d/2) genom alfa-beta, ytterligare reducerbar genom begränsning till högt värderade positioner (heta ställen minskar effektiv b). Utvärderingsfunktionen definierar ett hyperplan i egenskapsrymden.

Allt detta är rent, precist, formellt komplett. Det beskriver centret av spelprogramsproblemen — regionen där matematisk struktur ger tydlig vägledning.

Gränsen — när man ska växla från regelbruk till utforskning, när man ska handla positionell fördel för taktisk möjlighet, hur man känner igen framväxande mönster bortom utvärderingsfunktionen — motstår denna formalisering. Hammings tystnade kunskap lever vid den gränsen.

Geometrin låter dig beräkna hur mycket sökning du kan tillåta dig. Den säger inte vad du ska söka efter.

Reflektera över geometrin som omfattas i denna lektion. Sökträdsformalism (b^d noder, alfa-betaminskning till b^(d/2), linjära utvärderingsfunktioner) ger en precis beskrivning av de *tillgängliga* delarna av spelprogrammering. Var bryter geometrin ner — och vilken egenskap av spelprogrammeringsintelligens ligger bortom den geometriska modellen? Ge ett specifikt svar, inte en allmän observation.