五子棋，作為一款家喻戶曉的桌上遊戲，
可能是程式新手練習程式、設計遊戲 AI 的好起點。
其實這篇文章是以筆者做的 Python 遊戲為範本；
那時做出了連珠棋（六子棋）的 AI（雖然沒用到 AI 技術）
後來一直想找機會把這個做法記錄下來。
本篇將用 JavaScript 進行說明；其他程式可參考算法。
初始化
初始化階段，我們需要清空棋盤的二維陣列，
除此之外，還需要定義一些基本變數。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| ...
const CONNECT = 5;
const N = 19;
const EMPTY = 0;
const WHITE = 1;
const BLACK = 2;
let board = null;
let player = null;
let computer = null;
let now = null;
let end = null;
...
let other = function(c) {
if(c == WHITE) {
return BLACK;
}
else if(c == BLACK) {
return WHITE;
}
return EMPTY;
};
...
let initialize = function() {
player = BLACK;
computer = other(player);
now = BLACK;
end = false;
board = Array.from({length: N}, ()=>{
return Array.from({length: N}, ()=>{
return EMPTY;
});
});
refresh();
};
...
initialize();
|
玩家不一定要下黑方，
可以設定由玩家選擇顏色，但這裡為了方便就固定下黑子。
接下來就可以撰寫繪製棋盤的 refresh() 函數了。
繪製棋盤
在遊戲可以開始提供給玩家操作前，
我們要先把棋盤繪製出來。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
const canvas = document.getElementsByTagName("canvas")[0];
const context = canvas.getContext("2d");
...
const BLOCK = 24;
const MARGIN = 15;
const TEXT = 12;
const WIDTH = (N - 1) * BLOCK + MARGIN * 2;
const HEIGHT = (N - 1) * BLOCK + MARGIN * 2 + TEXT;
...
canvas.width = WIDTH;
canvas.height = HEIGHT;
let color = function(c) {
if(c == WHITE)
return "#FFFFFF";
else if(c == BLACK)
return "#000000";
return null;
};
let refresh = function() {
let ox, oy, tx, ty, r;
context.clearRect(0, 0, canvas.width, canvas.height);
for(let x = 0; x < N; x++) {
for(let y = 0; y < N; y++) {
context.beginPath();
ox = x * BLOCK + MARGIN;
tx = ox;
oy = MARGIN;
ty = (N - 1) * BLOCK + MARGIN;
context.moveTo(ox, oy);
context.lineTo(tx, ty);
ox = MARGIN;
tx = (N - 1) * BLOCK + MARGIN;
oy = y * BLOCK + MARGIN;
ty = oy;
context.moveTo(ox, oy);
context.lineTo(tx, ty);
context.stroke();
}
}
for(let x = 0; x < N; x++) {
for(let y = 0; y < N; y++) {
context.beginPath();
if(board[x][y] != EMPTY) {
ox = x * BLOCK + MARGIN;
oy = y * BLOCK + MARGIN;
r = BLOCK / 2;
context.arc(ox, oy, r, 0, 2 * Math.PI);
context.fillStyle = color(board[x][y]);
context.fill();
context.strokeStyle = "#000000";
context.stroke();
}
}
}
if(end == true) {
...
}
};
...
|
繪製棋盤雖然比較麻煩，但內容不困難，
座標的暫存變數可以直接寫在繪圖函數的傳入值內也可以。
遊戲進行
遊戲進行是透過玩家按下滑鼠來推動，
這樣處理比起透過 setInterval() 函數重複執行要有效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
let chess = function(x, y) {
if(board[x][y] == EMPTY) {
board[x][y] = now;
if(...) {
end = true;
}
else {
now = other(now);
}
}
refresh();
};
canvas.onmousedown = function() {
if(end == true) {
...
}
else {
let x = Math.round((event.offsetX - MARGIN) / BLOCK);
let y = Math.round((event.offsetY - MARGIN) / BLOCK);
chess(x, y);
if(now == computer) {
...
}
}
};
|
設定 chess() 函數檢查落子規則，使得主函數變得很簡潔。
勝負判斷
這裡開始的設計是五子棋程式冗長與否的關鍵！
由於可能會重複使用「是否超出棋盤」的邏輯，
這裡先寫一個 belong() 函數為之後做準備。
1
2
3
4
5
6
| ...
let belong = function(v, min, max) {
return v >= min && v < max;
};
...
|
接著這邊取得連珠數量的方式是這樣的，
我們先考慮一個方向的情況，在這個方向上，
連珠的數量為：「A 部分的數量 + 1 + B 部分的數量」
數量說明請參考圖 1。
另外觀察所有的方向：
考慮給定一個 (x, y) 加上一個 (dx, dy) 的偏移量，
由於 A 部分跟 B 部分是完全相反的。
也就是說 A = (x + dx, y + dy) 的話，
有 B = (x + (-dx), y + (-dy)) 的關係。
圖 2 使用顏色把原方向及反方向標出來。
這裡列出所有座標變化：
| 方向 |
dx 偏移量範圍 |
dy 偏移量範圍 |
| 左上 → 右下（上圖藍色部分） |
dx = [-1, -2, -3, -4] |
dy = [-1, -2, -3, -4] |
| 左上 → 右下（上圖紅色部分） |
dx = [+1, +2, +3, +4] |
dy = [+1, +2, +3, +4] |
| 直向（上圖藍色部分） |
dx = [-0, -0, -0, -0] |
dy = [-1, -2, -3, -4] |
| 直向（上圖紅色部分） |
dx = [+0, +0, +0, +0] |
dy = [+1, +2, +3, +4] |
| 右上 → 左下（上圖藍色部分） |
dx = [+1, +2, +3, +4] |
dy = [-1, -2, -3, -4] |
| 右上 → 左下（上圖紅色部分） |
dx = [-1, -2, -3, -4] |
dy = [+1, +2, +3, +4] |
| 橫向（上圖藍色部分） |
dx = [-1, -2, -3, -4] |
dy = [-0, -0, -0, -0] |
| 橫向（上圖紅色部分） |
dx = [+1, +2, +3, +4] |
dy = [+0, +0, +0, +0] |
如果令：
| 偏移量代號 |
偏移量範圍 |
| fixed |
[0, 0, 0, 0] |
| forward |
[+1, +2, +3, +4] |
| reverse |
[-1, -2, -3, -4] |
可以把上表化簡成：
| 方向 |
dx 偏移量範圍 |
dy 偏移量範圍 |
| 左上 → 右下（上圖藍色部分） |
reverse |
reverse |
| 左上 → 右下（上圖紅色部分） |
forward |
forward |
| 直向（上圖藍色部分） |
fixed |
reverse |
| 直向（上圖紅色部分） |
fixed |
forward |
| 右上 → 左下（上圖藍色部分） |
forward |
reverse |
| 右上 → 左下（上圖紅色部分） |
reverse |
forward |
| 橫向（上圖藍色部分） |
reverse |
fixed |
| 橫向（上圖紅色部分） |
forward |
fixed |
這樣就可以設計一個函數，
傳入目前座標、棋子顏色及變化量範圍，
回傳有多少連珠：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| ...
let check = function(x, y, c, dx, dy) {
let count = 0;
for(let i = 0; i < CONNECT - 1; i++) {
let tx = x + dx[i];
let ty = y + dy[i];
if(!belong(tx, 0, N) || !belong(ty, 0, N)) {
continue;
}
if(board[tx][ty] == c) {
count++;
}
else {
break;
}
}
return count;
};
...
|
有了這樣的函數後，可以直接調用：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ...
let connect = function(x, y, c) {
let assess = Array.from({length: 4}, (v, i)=>{return 0;});
let fixed = Array.from({length: CONNECT}, (v, i)=>{return 0;});
let forward = Array.from({length: CONNECT}, (v, i)=>{return i;});
let reverse = Array.from({length: CONNECT}, (v, i)=>{return -i;});
fixed.shift();
forward.shift();
reverse.shift();
assess[0] = check(x, y, c, forward, fixed) + check(x, y, c, reverse, fixed) + 1;
assess[1] = check(x, y, c, fixed, forward) + check(x, y, c, fixed, reverse) + 1;
assess[2] = check(x, y, c, reverse, reverse) + check(x, y, c, forward, forward) + 1;
assess[3] = check(x, y, c, reverse, forward) + check(x, y, c, forward, reverse) + 1;
max = assess.reduce((previous, current)=>Math.max(previous, current));
return max;
};
...
|
因為勝出一定是「當前回合落子」造成遊戲結束，
所以勝負條件會寫在 chess() 函數內，
給定座標就是當前落子的位置：
1
2
3
4
5
6
7
8
9
10
11
12
13
| ...
let chess = function(x, y) {
if(...) {
...
if(connect(x, y, now) >= CONNECT) {
end = true;
}
...
}
...
};
...
|
這裡的這個做法還有其他功能。將於 電腦對弈 段落介紹。
結束處理
既然勝負判斷已經完成，就可以順便實作結束處理。
這邊就顯示一行字在底部，然後再次點擊畫面可以重複遊戲這樣。
1
2
3
4
5
6
7
8
9
10
11
| ...
canvas.onmousedown = function() {
if(end == true) {
initialize();
end = false;
}
else {
...
}
};
|
則畫布的更新：
1
2
3
4
5
6
7
8
9
10
11
12
13
| ...
let refresh = function() {
...
if(end == true) {
context.font = "12px Verdana"
context.fillStyle = "#000000";
let winner = (now == BLACK ? "black" : "white");
let text = `${winner} is won!(click screen to play again)`;
context.fillText(text, MARGIN, canvas.height - TEXT);
}
};
...
|
電腦對弈
電腦 AI 其實是最難寫的。
不過我們別有用心的設計了 connect() 函數後，
這裡可以在這裡使用這兩個函數。
由於連珠棋有輪流落子的規則，
所以只要輪到我方時，我盤面上最長的連珠大於對手最大連珠，
我方繼續加子，如果對方不阻擋，則我方就會勝出。
反之，如果對手的最大連珠大於我方，我方應該先阻擋對方。
具體的說，透過我們的 connect() 函數傳入可以落子的座標，
找到「如果這個座標落子的話」這裡會形成的最大連珠。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
let search = function(c) {
let target = {
x: 0,
y: 0,
count: 0
};
for(let x = 0; x < N; x++) {
for(let y = 0; y < N; y++) {
if(board[x][y] == EMPTY) {
let max = connect(x, y, c);
if(target.count < max) {
target.x = x;
target.y = y;
target.count = max;
}
}
}
}
return target;
};
|
電腦 AI 的部分就很簡單了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
canvas.onmousedown = function() {
if(end == true) {
...
}
else {
...
if(now == computer) {
playerTarget = search(player);
computerTarget = search(computer);
if(playerTarget.count > computerTarget.count) {
chess(playerTarget.x, playerTarget.y);
}
else {
chess(computerTarget.x, computerTarget.y);
}
}
}
};
|
雖然這裡稱作電腦「AI」對弈，但實際上是傳統的暴力搜索。
演示
來下棋吧！