표준 모델에서 '돌림 단어 쌍 제거'는 그래프를 단순화하는 매우 강력한 도구였습니다. 그렇다면 이분 유향 그래프에서도 유사한 원리를 적용할 수 있을까요?

단순한 유추의 실패

이분 그래프에서 $a$→$b$, $b$→$a$와 유사한 흐름을 만드는 단어 쌍을 찾아서 제거하면 될 것이라 유추하기 쉽습니다. 하지만 여기서 이전처럼 이 두 단어를 그래프에서 그냥 제거해버리면, 게임의 승패가 바뀌는 심각한 오류가 발생합니다.

예를 들어 '윤축'((첫 음절) 윤 → (끝 음절)축)과 '축세륜'((첫 음절)축 → (끝 음절)륜)이라는 단어 쌍을 생각해 봅시다. 만약 이 두 단어가 없다면 '윤'과 '륜'의 세계는 완전히 단절되어, '윤'을 받은 플레이어가 '륜'으로 갈 방법이 없을 수 있습니다. 하지만 이 두 단어가 존재하면, '윤' → '축' → '륜'으로 이어지는 새로운 다리가 생겨납니다.

만약 '륜'이 강력한 필패 포지션이라면, 이 새로운 경로의 존재만으로도 '윤'의 전략적 가치가 필승에서 필패로 뒤바뀔 수 있습니다. 이처럼 돌림 단어 쌍이 음절 간의 도달 가능성(reachability)을 근본적으로 바꾸는 경우, 함부로 제거할 수 없는 것입니다.

더 엄격한 '돌림 단어 쌍'의 정의

'제거 불변성 원리'가 다시 성립하려면, 돌림 단어 교환이 게임에 어떠한 새로운 변수도 만들지 않는 '완벽하게 중립적인' 교환이어야 합니다. 이를 위해 우리는 돌림 단어 쌍의 조건을 다음과 같이 매우 엄격하게 재정의합니다.

(편의상 ' 따옴표를 붙이면 첫 음절, 붙이지 않으면 끝 음절로 표기합니다: $a$는 끝 음절, $a'$는 첫 음절)

[이분 그래프에서의 돌림 단어 쌍 정의] 두 단어 $a' \rightarrow b$ 와 $b' \rightarrow a$는, 아래의 세 가지 조건을 모두 만족할 경우에만 '제거 가능한 돌림 단어 쌍'이다.

1. 두음 법칙 경로 존재: 두음 법칙 엣지 $a \rightarrow a'$ 와 $b \rightarrow b'$ 가 모두 존재해야 한다.
2. a의 경로 열등성(Path Inferiority): $a'$로 올 수 있는 다른 모든 '끝 음절' $a_{prev}$ 각각은, $a$가 제공하는 모든 두음 법칙 선택지를 포함해야 한다. (즉, $Successors(a) \subseteq Successors(a_{prev})$)
3. b의 경로 열등성(Path Inferiority): $b'$로 올 수 있는 다른 모든 '끝 음절' $b_{prev}$ 각각은, $b$가 제공하는 모든 두음 법칙 선택지를 포함해야 한다. (즉, $Successors(b) \subseteq Successors(b_{prev})$)

2, 3번 조건이 이 정의의 핵심입니다. 이 조건은 두음 법칙 경로 $a \rightarrow a'$ 와 $b \rightarrow b'$ 가 전략적으로 특별한 이점을 제공하지 않는 '열등한' 경로임을 보장합니다. 이로 인해 $a' \rightarrow b, b' \rightarrow a$ 단어 교환은 다른 전략에 영향을 주지 않는 고립된 중립적 행위가 될 수 있습니다.

불변성 원리의 증명 (엄격한 정의 하에서)

이 엄격한 정의하에서, '전략 훔치기' 증명이 다시 성립합니다.

$G' = G - (a' \rightarrow b) - (b' \rightarrow a)$ 라고 할 때, "$v$가 $G'$에서 필패이면, $G$에서도 필패이다" 를 증명해 보겠습니다.

• 가정: 플레이어 B는 $G'$ 게임에 대한 필승 전략 $S'$를 알고 있습니다.
• 상황: $G$에서 게임을 할 때, B는 $S'$를 기반으로 플레이합니다.
• A의 선택:
  1. A가 $G'$에 존재하는 '일반적인 수'를 둔다: B는 전략 $S'$에 따라 응수하여 승리한다.
  2. A가 '특별한 수'인 $a' \rightarrow b$를 둔다: A는 자신의 턴을 소모하여 B를 $b$로 보냈습니다. B는 즉시 $b \rightarrow b'$ 두음 법칙을 적용한 후, $b' \rightarrow a$로 받아쳐 A를 다시 $a$로 보냅니다.
• 결과 분석: '경로 열등성' 조건 때문에, A가 B를 $b$로 보낸 행위는 B에게 어떠한 전략적 손실도 입히지 못했습니다. 결국 A가 한 행동은 자신의 턴을 소모하여 게임판을 $G'$로 만들고, 턴을 다시 자신에게 돌려놓은 것과 같습니다. A는 이제 포지션 ($G'$, $a$)에서 수를 두어야 하지만, B는 $G'$ 게임에 대한 필승 전략 $S'$을 이미 가지고 있으므로 A는 필패하게 됩니다.

따라서 B는 A의 어떤 수에도 대응하여 승리할 수 있으므로, $G'$에서 필패인 포지션은 $G$에서도 필패입니다.

돌림 단어 쌍을 찾는 알고리즘

이 엄격한 조건을 만족하는 돌림 단어 쌍을 찾기 위한 알고리즘은 다음과 같습니다.

1. '중립 두음 법칙' 선별: 모든 두음 법칙 엣지 $x \rightarrow x'$에 대해, 위에서 정의한 '경로 열등성' 조건을 만족하는지 검사합니다.

   즉, $x'$로 이어지는 모든 다른 끝 음절 $x_{prev}$에 대해, $Successors(x) \subseteq Successors(x_{prev})$가 성립하는지 확인합니다. 이 조건을 통과한 두음 법칙 엣지들만 '중립'으로 분류합니다.

2. 돌림 단어 쌍 탐색: '중립'으로 분류된 두음 법칙 엣지 $a \rightarrow a'$ 와 $b \rightarrow b'$ 쌍에 대해서만, 이들을 이어주는 역행 단어 엣지 쌍 $a' \rightarrow b$ 와 $b' \rightarrow a$가 존재하는지 탐색합니다. 만약 존재한다면, 이 두 단어가 바로 '제거 가능한 돌림 단어 쌍'이 됩니다.