0%

使用 JavaScript 实现人机对战的井字棋游戏

前言

在今年早些时候,参加了极客时间的前端进阶训练营,接触到了人机对战的井字棋游戏,说要写一篇博客记录一下,今天填坑来了属于是。

井字棋、或者说三子棋相信大家都不陌生,学生时代在本子上画一个“井”字和同学一起下棋,或者直接在带格子的语文作业本上下。

话不多说,我们先来看看,实现的效果:

具体如何实现,主要分为以下几部分:

棋盘绘制

  • 使用 CSS inline-block 实现 3 * 3 布局
  • 定义一维数组 pattern ,模拟 3 * 3 棋盘,记录落子情况
    • 数组元素值定义: 0 表示未落子,1 表示 O 落子,2 表示 X 落子
  • render:遍历一维数组,根据数组元素的值,动态绘制棋盘
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
<!DOCTYPE html>

<style>
#board {
width: 306px;
margin: 0 auto;
}

.cell {
width: 100px;
height: 100px;
color: red;
display: inline-block;
border: 1px solid black;
vertical-align: middle;
line-height: 100px;
font-size: 50px;
text-align: center;
}
</style>

<!-- 可以不写 body 标签 -->
<div id="board"></div>

<!-- 静态 -->
<script>
let pattern = [2, 0, 0, 0, 1, 0, 0, 0, 0];

function render() {
const board = document.getElementById("board");
// 绘制前,清空棋盘
board.innerHTML = "";

for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
const cellValue = pattern[i * 3 + j];
const cell = document.createElement("div");

cell.classList.add("cell");
cell.innerText = cellValue === 2 ? "X" : cellValue === 1 ? "O" : "";

board.appendChild(cell);
}
board.appendChild(document.createElement("br"));
}
}

render();
</script>

用户落子

  • 定义标识变量 color ,记录最近落子一方的元素值
  • render:遍历一维数组,给棋格添加点击事件,将当前棋格的”坐标“作为参数传递
  • setCellValue:定义落子方法,处理一维数组和标识更新、以及棋盘重绘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<!-- 可点击 -->
<script>
let pattern = [2, 0, 0, 0, 1, 0, 0, 0, 0];
let color = 1;

function render() {
// ...
cell.addEventListener("click", () => setCellValue(i, j));
// ...
}

function setCellValue(i, j) {
pattern[i * 3 + j] = color;
color = 3 - color;
render();
}

render();
</script>

检查胜负

  • setCellValue:用户落子后,检查游戏胜负,有一方获胜,游戏结束
  • checkWinOrLose:遍历棋盘,依次检查三纵、三横、两斜的胜负情况
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
<!-- 可点击+可以判定胜负 -->
<script>
let pattern = [0, 0, 0, 0, 0, 0, 0, 0, 0];
let color = 1;

function render() {
//...
}

// 落子
function setCellValue(i, j) {
pattern[i * 3 + j] = color;
render();
if (checkWinOrLose(pattern, color)) {
alert(`${color === 2 ? "X" : color === 1 ? "O" : ""} is winner!`);
// 游戏结束
return;
}
color = 3 - color;
}

// 检查胜负
function checkWinOrLose(pattern, color) {
let win = false;

// 三横
for (let i = 0; i < 3; i++) {
win = true;
for (let j = 0; j < 3; j++) {
if (pattern[i * 3 + j] !== color) {
win = false;
}
}
if (win) {
return win;
}
}

// 三纵
for (let i = 0; i < 3; i++) {
win = true;
for (let j = 0; j < 3; j++) {
if (pattern[j * 3 + i] !== color) {
win = false;
}
}
if (win) {
return win;
}
}

// 两斜
// 正斜线 /
{
win = true;
for (let i = 0; i < 3; i++) {
if (pattern[i * 3 + 2 - i] !== color) {
win = false;
}
}
if (win) {
return win;
}
}

// 反斜线 \
{
win = true;
for (let i = 0; i < 3; i++) {
if (pattern[i * 3 + i] !== color) {
win = false;
}
}
if (win) {
return win;
}
}
return false;
}

render();
</script>

模拟落子(一层)

  • setCellValue:任意一方落子之后,模拟落子(一层),预判胜方
    • predictWin:遍历棋盘,将棋盘数组拷贝,模拟即将落子方落子,得出获胜的落子位置
  • clone:拷贝一维数组
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
<script>
//...
function render() {
//...
}

// 落子
function setCellValue(i, j) {
// ...
if (predictWin(pattern, color)) {
alert(`${color === 2 ? "X" : color === 1 ? "O" : ""} will win!`);
}
}

// 检查胜负
function checkWinOrLose(pattern, color) {
//...
}

// 模拟落子(一层)
function predictWin(pattern, color) {
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// 跳过已经落子的位置
if (pattern[i * 3 + j]) {
continue;
}
let temp = clone(pattern);
temp[i * 3 + j] = color;
if (checkWinOrLose(temp, color)) {
return [i, j];
}
}
}
return null;
}

function clone(value) {
return Object.create(value);
}

render();
</script>

最佳选择(递归)

  • setCellValue: 任意一方落子之后,寻找最佳选择(递归),预判局势
    • bestChoice
      • 执行流程:
        • 调用 predictWin 方法模拟落子(一层),如果返回获胜的落子位置,终止执行,返回结果
        • 遍历棋盘,我方(color)模拟落子后,以对手方((3 - color))视角,代入参数递归调用 bestChoice 方法,得出对手方的最佳结果
        • 对手方的最佳结果取反(-r),即是我方的最差结果,比较后更新对于我方最好的落子位置(point)和结果(result),直到获胜(result = 1),跳出遍历
        • 遍历结束,返回结果
      • 返回值定义:
        • color:落子方
        • point:落子“坐标”
        • result:-2 表示未开始,-1 表示输,0 表示和局,1 表示赢
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
68
69
70
<script>
//...
function render() {
//...
}
// 落子
function setCellValue(i, j) {
//...
let choice = bestChoice(pattern, color);
console.log(
`${
choice.color === 2 ? "X" : choice.color == 1 ? "O" : ""
} best choice: point=${JSON.stringify(choice.point)}, result=${
choice.result
}`
);
}
// 检查胜负
function checkWinOrLose(pattern, color) {
//...
}
// 模拟落子(一层)
function predictWin(pattern, color) {
//...
}

// 最佳选择(递归)
function bestChoice(pattern, color) {
let point = predictWin(pattern, color);
if (point) {
return {
color: color,
point: point,
result: 1,
};
}

// 起步结果
let result = -2;
outer: for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// 跳过已经落子的位置
if (pattern[i * 3 + j]) {
continue;
}
let temp = clone(pattern);
temp[i * 3 + j] = color;
// 根据「对手方」目前情况下未来「最好的结果」,换位得出我方「最差的结果」(-r)
let r = bestChoice(temp, 3 - color).result;
// 比较后更新落子位置和结果
if (-r >= result) {
result = -r;
point = [i, j];
}
// 剪枝
if (result === 1) {
break outer;
}
}
}
return {
color: color,
point: point,
result: point ? result : 0,
};
}
//...

render();
</script>

电脑落子

  • userSetCellValue:用户落子后,电脑落子
    • computerSetCellValue:调用 bestChoice 得到最佳选择(包含落子位置和结果),然后落子
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
<script>
let pattern = [0, 0, 0, 0, 1, 0, 0, 0, 0];
let color = 2;

function render() {
// ...
cell.addEventListener("click", () => userSetCellValue(i, j));
// ...
}

// 用户落子
function userSetCellValue(i, j) {
// ...
computerSetCellValue();
}

// 电脑落子
function computerSetCellValue() {
let choice = bestChoice(pattern, color);
if (choice.point) {
pattern[choice.point[0] * 3 + choice.point[1]] = color;
render();
if (checkWinOrLose(pattern, color)) {
alert(`${color === 2 ? "X" : color === 1 ? "O" : ""} is winner!`);
// 游戏结束
return;
}
color = 3 - color;
}
}

// 检查胜负
function checkWinOrLose(pattern, color) {
//...
}
// 模拟落子(一层)
function predictWin(pattern, color) {
//...
}
// 最佳选择(递归)
function bestChoice(pattern, color) {
//...
}
//...

render();
</script>

总结

回顾一下,在这个人机对战的井字棋游戏中,机器操作的主体逻辑在 bestChoice - 最佳选择 方法中,基于遍历和递归,机器模拟机器下一棋后,再模拟人下一棋,循环往复,直到得出 bestChoice - 最佳选择

说白了就是利用计算机的算力,穷举出所有的可能性,找规则内的最优解。

井字棋还不够计算机算力塞牙缝的,五子棋用穷举法好像会有点小卡,到围棋好像就没法用穷举法应对所有情况了。

欢迎点赞评论,游戏主体部分有了,但是还有诸多不完善的地方,在线链接:

https://codepen.io/lsnsh-the-bashful/full/wvrBpqw