---
# System prepended metadata

title: Tic-Tac-Toe (井字棋)

---

# Tic-Tac-Toe (井字棋)

| A        | B        | A     |
| -----    | -----    | ----- |
| B        | C        | B     |
| A        | B        | A     |


## Question

請問先手的勝率/後手的勝率？


## Answer

面談當下沒有得出明確的解答

其實不應往第一手下在哪個位置(A/B/C)去思考

應該先從計算棋局的所有可能性去著手

### 計算出分母後，再從中找出先手勝利的棋局個數

便可求出先手的勝率

### 1. 棋局的所有可能性

設先手為叉叉(X)，後手為圈圈(O)

當任一方勝出後，若玩家仍然會將棋盤填滿(5個X和4個O)，勝出的機率不會因此改變

這C9取5種可能性發生的機率都會一樣：

```
$1 = C(9, 5) = 9! / (4! * 5!) = 126
```

### 2. 先手(X)必勝？

如果直接計算先手(X)勝出的棋局排列，會把先手(X)和後手(O)皆勝出的棋局算入，如下釋例

該類棋局的真實勝負取決於**誰先完成一條線**，需要另外計算

因此需先分別算出：**合局數**、**後手(O)必勝數**、**雙方皆勝數**，才能推出先手必勝(X)的數量

| O        | .        | X     |
| -----    | -----    | ----- |
| O        | .        | X     |
| O        | .        | X     |

### 3. 後手(O)必勝

後手只有4顆棋子

水平/垂直的勝出棋局，剩餘的格子填上先手(X)後，會導致雙方皆勝

斜角的勝出棋局，剩餘的格子填上先手(X)後，仍然只有後手必勝

因此這裡只有斜角勝出棋局為後手(O)必勝：

| O        | .        | .     |
| -----    | -----    | ----- |
| .        | O        | .     |
| .        | .        | O     |


```
$3 = 2 (斜角的兩種可能：正斜角/反斜角) * 6 (後手的第四顆棋子可以填於剩餘的6個位置) = 12
```

### 4. 合局

由於後手(O)棋數較少，易於對排放位置進行列舉

為了方便列舉，依中心位置區分為兩種狀況：

1. C位有後手(O)
    
    先手有四條可勝出的路線(水平*2, 垂直*2)
    
    剩餘的三顆棋子有兩種方式可以堵住先手：
    
    a. 三顆在A位/三顆在B位->後手必勝/雙方皆勝
    
    | O       |         |      |
    | -----   | -----   | -----|
    |         | O       |      |
    | O       |         |  O   |
        
    b. 兩顆放在A位，一顆放在B位->合局 (0度、90度、180度、270度)
    
    | O       |         |      |
    | -----   | -----   | -----|
    |         | O       |   O  |
    | O       |         |      |
    
    c. 兩顆放在B位，一顆放在A位->合局 (0度、90度、180度、270度)
    
    |         | O       |      |
    | -----   | -----   | -----|
    | O       | O       |      |
    |         |         |   O  |
    

2. C位無後手(O)

    a. 四顆在A位/四顆在B位->先手直線勝利/先手斜線勝利
    
    | X      |  O      |      |
    | -----  | -----   | -----|
    | O      |  X      |  O   |
    |        |  O      |  X   |
        
    
    b. 三顆在A位，一顆在B位->先手勝利/雙方皆勝
    
    | O       |         | O    |
    | -----   | -----   | -----|
    | X       |  X      | X    |
    | O       |  O      |      |
    
        
    c. 三顆在B位，一顆在A位 (0度、90度、180度、270度)
    
    |         | O       | O    |
    | -----   | -----   | -----|
    | O       |         |      |
    |         | O       |      |
    
    d. 兩顆在A位，兩顆在B位 (0度、90度、180度、270度)
    
    |         | O       | O    |
    | -----   | -----   | -----|
    | O       |         |      |
    |         |         | O    |



```
$4 = 4 (4種合局狀況) * 4(四種方位) = 16
```

```
合局的機率 = 16/126 = 8/63
```

### 5. 雙方皆勝

斜角不可能雙方皆勝

因此只有直線勝出局，會造成雙方皆勝

1. 水平
    
    | O       | O       | O    |
    | -----   | -----   | -----|
    | .       | .       | .    |
    | .       | .       | .    |
    
```
3 (3條水平線) * 6 (第四顆棋有六種可能擺放的位置) = 18
```
    
2. 垂直
    
    | O       | .       | .    |
    | -----   | -----   | -----|
    | O       | .       | .    |
    | O       | .       | .    |
    
```
3 (3條垂直線) * 6 (第四顆棋有六種可能擺放的位置) = 18
```

```
$5 = 18 + 18 = 36 (雙方皆勝的棋局數量)
```

雙方皆勝的棋局中，**勝利取決於誰先完成一條線**

以步數來計算不同scenario下的可能性

1. 先手(X) 第3步先勝利->此線必由先手的第(1,2,3)步組成
    
    後手有可能在第3或第4(最後一步)步連成一條線：
    
    後手(O) 第3步連成一線->此線必由後手的第(1,2,3)步組成
    | X        | X        | X     |
    | -----    | -----    | ----- |
    | O        | O        | O     |
    | .        | .        | .     |
    
    
    後手(O) 第4步連成一線->此線可能由後手的第(1,2,4) or (1,3,4) or (2,3,4)步組成
    | X        | X        | X     |
    | -----    | -----    | ----- |
    | O        | O        | O     |
    | .        | O        | .     |


```
1(先手連線的可能性) * (1+3)(後手連線的可能性) = 4
```


2. 先手(X) 第4步先勝利->此線可能由先手的第(1,2,4) or (1,3,4) or (2,3,4)步組成

    代表後手(O) 第4步才會連成一條直線->此線可能由後手的第(1,2,4) or (1,3,4) or (2,3,4)步組成

```
3(先手連線的可能性) * 3(後手連線的可能性) = 9
```

3. 後手(O) 第3步先勝利->此線必由後手的第(1,2,3)步組成
    
    先手有可能在第4或第5(最後一步)步連成一條線：
    
    先手(X) 第4步連成一線->此線可能由先手的第(1,2,4) or (1,3,4) or (2,3,4)步組成
    | O        | O        | O     |
    | -----    | -----    | ----- |
    | X        | X        | X     |
    | X        | .        | .     |
    
    先手(X) 第5步連成一線->此線可能由先手的第(1,2,5) or (1,3,5)... (3,4,5)步組成
    | O        | O        | O     |
    | -----    | -----    | ----- |
    | X        | X        | X     |
    | X        | X        | .     |

```
(3+6)(先手連線的可能性) * 1(後手連線的可能性) = 9
```
    

4. 後手(O) 第4步先勝利->此線可能由後手的第(1,2,4) or (1,3,4) or (2,3,4)步組成

    代表先手(X) 第5步才會連成一條直線->此線可能由先手的第(1,2,5) or (1,3,5)... (3,4,5)步組成

```
6(先手連線的可能性) * 3(後手連線的可能性) = 18
```
    
```
3+9+9+18 = 40(所有雙方皆勝的可能性)
3+9 = 13(雙方皆勝下，先手勝利)
9+18 = 27(雙方皆勝下，後手勝利)

Q：為何40比36大？
A：因為這裡多考慮了生成直線的下棋順序
```



```
$5a = 36(真實棋盤數量) * 13/40 = 雙方皆勝下，先手勝利的盤數
$5b = 36(真實棋盤數量) * 27/40 = 雙方皆勝下，後手勝利的盤數
```


### 6. 先手(X)必勝的棋局數

```
$6 = $1 - $3 - $4 - $5 = 126 - 12 - 16 - 36 = 62
```

### 7. 勝率

先手勝率 = (先手必勝數+雙方皆勝下先手勝利)/所有棋局

```
$7a = ($6 + $5a)/($1) = (62 + 36*(13/40))/(126) = 737/1260 = 58.49%
```

後手勝率 = (後手必勝數+雙方皆勝下後手勝利)/所有棋局

```
$7b = ($6 + $5b)/($1) = (12 + 36*(27/40))/(126) = 363/1260 = 28.81%
```

## Reference
[American Mathematical Monthly, June-July 1958, p. 447](https://http://people.missouristate.edu/lesreid/sol10_04.html)