# 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)
Sign in with Wallet
Connect another wallet