un — 기계 추론의 기하학: I

un

게스트

1 / ?

수업 목록으로

분기 계수 & 노드 개수

게임 트리는 시작 위치에서 가능한 모든 수의 수열을 모델링합니다. 각 노드는 보드 상태를 나타냅니다. 각 엣지는 하나의 합법적 수를 나타냅니다. 트리의 구조는 탐색이 가능한지를 결정합니다.

주요 매개변수

분기 계수 b: 일반적인 위치에서 사용 가능한 합법적 수의 개수.

깊이 d: 앞을 내다보며 탐색할 플라이(반-이동)의 개수.

깊이 d에서의 노드 개수: b^d

모든 깊이에 걸친 총 노드: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

큰 b와 d에 대해, 총합 ≈ b^d (엽 수준이 지배적입니다).

4×4×4 틱택토

전체 게임 트리: b ≈ 64 (합법적 사각형), d = 64 (총 이동). 전체 노드 개수 ≈ 64^64 ≈ 10^115. 관찰 가능한 우주는 대략 10^80개의 원자를 포함합니다. 무차별 탐색은 물리적으로 불가능합니다.

게임 트리 & 알파-베타 가지치기

트리 크기 계산

체스는 더 현실적인 숫자를 제공합니다. 평균 분기 계수 b ≈ 35. 6-플라이 탐색(각 측면에서 3수)에는 대략 35^6개의 노드가 필요합니다.

분기 계수 b = 35인 깊이 d = 6 플라이의 체스 탐색에서 엽 노드의 개수를 계산하세요. 그 다음 d = 10 플라이에 대해 같은 계산을 하세요. 두 계산 모두 명시적으로 보여주세요.

알파-베타 가지치기: 지수 줄이기

알파-베타 가지치기는 미니맥스 결과에 영향을 줄 수 없는 부분 트리를 제거합니다. 핵심 통찰력: 한 분기가 값 V를 준다면, 그 값이 입증 가능하게 V보다 아래인 형제 분기(극대화 플레이어의 경우) 또는 V보다 위인 형제 분기(극소화 플레이어의 경우)를 가지칠 수 있습니다.

최선의 경우 기하학

최적 수 순서(최선의 수가 먼저 탐색됨) 하에서, 알파-베타는 유효한 분기 계수를 b에서 √b로 줄입니다. 같은 노드 예산에 대해 탐색 깊이가 효과적으로 두 배가 됩니다:

전체 탐색: b^d 노드

알파-베타 최선의 경우: b^(d/2) 노드

예: b=35, d=6. 전체: 35^6 ≈ 1.84 × 10^9. 알파-베타: 35^3 = 42,875. 감소 계수: ~43,000.

실제로는 수 순서가 불완전합니다. 일반적인 감소: b^(d×0.75) — 동등 분기 계수 ≈ b^0.75.

b = 35, d = 8 플라이인 체스 엔진에 대해, 다음 하에서 노드 개수를 계산하세요: (1) 전체 미니맥스 탐색, (2) 완벽한 알파-베타 가지치기(최선의 경우). 감소 계수는 무엇입니까? 모든 계산을 보여주세요.

중심-코너 이중성

해밍은 4×4×4 큐브에서 기하학적 이중성을 주목합니다: 8개의 코너 위치를 8개의 중심 위치(내부 2×2×2 큐브)로, 그리고 그 반대로 보내는 반전이 존재합니다, 모든 76개의 승리 선을 유지하면서.

위치를 통과하는 선 세기

4×4×4 큐브에서, 위치는 그들을 통과하는 승리 선의 개수가 다릅니다:

코너 위치: 각각 7개의 선 (4개의 면 대각선, 2개의 엣지 선, 1개의 공간 대각선)

엣지-중심 위치: 각각 4개의 선

면-중심 위치: 각각 6개의 선

몸-중심 위치 (내부 2×2×2): 각각 7개의 선

이중성은 코너(7개의 선)를 몸-중심(7개의 선)으로 매핑합니다. 두 세트 모두 '핫 스팟'을 형성합니다.

왜 핫 스팟이 기하학적으로 중요한가

높은-선-개수 위치를 더 많이 제어하는 플레이어는 더 많은 잠재적 승리 선을 제어합니다. 이것은 직접적인 기하학적 논증입니다: 선 커버리지 최대화는 어떤 탐색 없이 수 선택을 안내합니다.

4×4×4 큐브는 76개의 총 승리 선과 64개의 위치를 갖습니다. 8개의 코너는 각각 7개의 선 위에 있고, 8개의 몸-중심 위치는 각각 7개의 선 위에 있고, 24개의 면-중심 위치는 각각 6개의 선 위에 있고, 24개의 엣지 위치는 각각 4개의 선 위에 있습니다. 확인하세요: 이 개수들이 일관되게 합산됩니까? 양쪽에서 (위치, 선) 접속의 총 개수를 계산하세요: 위치에 대해 합산하고, 선당 4개의 끝점을 세어서 분리하여. 두 합계가 동의합니까?

평가 함수

모든 게임 플레이 프로그램에는 평가 함수가 필요합니다: 보드 상태를 숫자 값에 매핑하는 함수 (양수 = 극대화 플레이어에게 좋음, 음수 = 극소화 플레이어에게 좋음). 평가 함수는 탐색 트리의 엽에서 경계 조건을 제공합니다.

선형 평가 함수

선형 평가 함수는 위치의 각 특징 f_i에 가중치 w_i를 할당합니다:

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

4×4×4 틱택토의 경우: 특징에는 제어되는 열린 선, 높은-선-개수 사각형의 위치, 위협받는 포크가 포함될 수 있습니다. 체스의 경우: 물질 개수, 중심 제어, 왕 안전, 폰 구조.

이것은 특징 공간의 선형 함수입니다 — ℝ^n의 초평면. 같은 특징 값을 가진 두 위치는 다른 모든 차이와 상관없이 같은 평가를 얻습니다. 평가 함수의 기하학은 프로그램이 '본다'는 것을 결정합니다.

Samuel의 체커 프로그램은 가중치 벡터 w를 조정하여 개선되었습니다 — 선형 평가 함수의 공간에서의 경사 하강.

간단한 4×4×4 틱택토 평가 함수는 두 특징을 사용합니다: (1) f_1 = 당신의 열린 선의 개수 (당신이 폰을 가지고 상대방이 없는 선), (2) f_2 = 상대방의 열린 선의 개수. 평가: E = w_1 × f_1 − w_2 × f_2. w_1 = 2, w_2 = 3일 때, 당신이 12개의 열린 선을 가지고 상대방이 8개를 가진 위치에 대해 E를 계산하세요. 그 다음: E > 0이 위치가 당신을 선호한다는 뜻이면, 이 결과는 위치에 대해 무엇을 말합니까?

기하학 & 정식화의 경계

게임 트리는 깔끔한 기하학적 구조를 가집니다: 깊이 d에서의 지수적 성장, 알파-베타에 의해 b^(d/2)로 축소 가능, 높은 값 위치로 제한함으로써 추가로 축소 가능 (핫 스팟은 유효 b를 축소합니다). 평가 함수는 특징 공간에서 초평면을 정의합니다.

이 모든 것은 깔끔하고, 정확하고, 형식적으로 완전합니다. 게임 플레이 문제의 중심을 설명합니다 — 수학적 구조가 명확한 지침을 제공하는 지역.

경계 — 규칙 적용에서 탐색으로 전환할 위치, 위치적 이점을 전술적 기회와 교환할 시점, 평가 함수 너머의 새로 생긴 패턴을 인식하는 방법 — 이 정식화에 저항합니다. 해밍의 암묵적 지식은 그 경계에 있습니다.

기하학은 당신이 얼마나 많은 탐색을 할 수 있는지 계산하도록 하게 합니다. 그것은 당신이 무엇을 찾아야 할지를 말하지 않습니다.

이 수업에서 다룬 기하학을 생각해 보세요. 게임 트리 형식주의 (b^d 노드, 알파-베타 감소 b^(d/2), 선형 평가 함수)는 게임 플레이의 *다루기 쉬운* 부분의 정확한 설명을 제공합니다. 기하학은 어디서 전함되는가 — 그리고 게임 플레이 지능의 어떤 속성이 기하학적 모델 너머에 있는가? 일반적인 관찰이 아니라 구체적인 답을 주세요.