井字棋是一个规则非常简单的小游戏，应该绝大部分的同学都玩过。就是在一个井字格里面画 X 和 O，谁先在横、竖、斜向上连成了一条线就赢了。
我们今天的要做的就是实现这一个简单的小游戏，然后在游戏的基础上实现一个简单的 AI 跟我们对弈。
1. 画棋盘
既然实现的是棋类游戏，第一步当然是把棋盘画出来了。棋盘部分的代码其实非常简单了，需要考虑的是棋盘数据需要怎么存储，我比较习惯用一维数组来存储，当然你也可以用一个二维数组。不过一维数组对于二维数组来说有很多好处，我们后面会介绍。
<style></style>
<div id="board"></div>
<script>
let pattern = [
2, 0, 0,
0, 1, 0,
0, 0, 0
];
function show(pattern) {
let board = document.getElementById('board');
board.innerHTML = "";
for (let y = 0; y < 3; y++) {
for (let x = 0; x < 3; x++) {
let cell = document.createElement('div');
cell.classList.add("cell")
cell.innerHTML = pattern[y * 3 + x] === 2 ? "❌" :
pattern[y * 3 + x] === 1 ? "⭕️" : "";
board.appendChild(cell);
}
board.appendChild(document.createElement("br"));
}
}
show(pattern);
</script>
我们用 JS 代码来控制棋盘的大小，而不是直接用 HTML 画出来，因为我们后续还需要考虑到落子的问题。
我们使用了正常流来进行布局，这里还要注意的是用 inline-block 来布局，一定要用 vertical-align: middle; 设置基线。如果对正常流不是很熟悉可以看 此处为语雀文档，点击链接查看：https://www.yuque.com/wendraw/fe/css-layout。当让你也可以用 flex、grid 进行布局。
然后用的是一维数组，那么将 x、y 坐标对应到数组的下标还需要进行简单的运算。
最后就能得到棋盘：
image.png
2. 添加落子
添加落子功能也比较简单了，就是给每个格子 cell 加上 click 事件，然后在对应的位置画上对应的棋子即可。
上一步的 pattern 数组还有一个小的编程技巧，就是我们是用 0 来表示没有放置棋子，用 1 来表示 ⭕️ 棋子，用 2 来表示 ❌ 棋子。用 1、2 来表示两种棋子，当需要处理交替落子时，我只需要用 3 -「当前棋子的值」，就得到了对方棋子的值。
<script>
let color = 1;
function show(pattern) {
cell.innerHTML = pattern[y * 3 + x] === 2 ? "❌" :
pattern[y * 3 + x] === 1 ? "⭕️" : "";
cell.addEventListener('click', () => move(x, y));
board.appendChild(cell);
}
function move(x, y) {
if (pattern[y * 3 + x] > 0) return;
pattern[y * + x] = 3 - color;
color = 3 - color;
show(pattern);
}
</script>
3. 判断输赢
我们现在有交替落子的能力了，接下来就需要判断输赢了，对于井字棋来说有 8 种情况可以赢，横向（三种）、纵向（3 种）、正斜向（撇的方向）、反斜向（捺的方向）。理清楚赢的条件就好办了，只需要依次检查整个棋盘在这 4 个方向是否有三个相同的棋子连起来了。
处理这些代码还是需要一点小技巧的，我观察可以知道，对于正斜向来说坐标 x 等于 坐标 y，对于反斜向来说坐标 x 与坐标 y 的和为 2。
<script>
function check(pattern, color) {
for (let y = 0; y < 3; y++) {
let win = true;
for (let x = 0; x < 3; x++) {
if (pattern[y * 3 + x] !== color) {
win = false;
break;
}
}
if (win) return true;
}
for (let y = 0; y < 3; y++) {
let win = true;
for (let x = 0; x < 3; x++) {
if (pattern[x * 3 + y] !== color) {
win = false;
break;
}
}
if (win) return true;
}
{
let win = true;
for (let i = 0; i < 3; i++) {
if (pattern[i * 3 + i] !== color) {
win = false;
break;
}
}
if (win) return true;
}
{
let win = true;
for (let i = 0; i < 3; i++) {
if (pattern[i * 3 + 2 - i] !== color) {
win = false;
break;
}
}
if (win) return true;
}
return false;
}
</script>
然后就是调用 check 函数的时机，其实每次有一方落子时，就要判断是否已经赢了。所以我们只需要在 move 里面添加判断即可。
<script>
function move(x, y) {
if (pattern[y * 3 + x] > 0) return;
pattern[y * 3 + x] = color;
show();
if (check(pattern, color)) {
alert(`${color === 2 ? "❌" : "⭕️"} is winner`);
}
color = 3 - color;
}
</script>
至此，一个简单的井字棋就已经完成了🎉🎉。当然游戏还比较简陋，还可以在这个框架的基础之上增加更复杂的逻辑，如，双人在线玩、可以悔棋、结束后重开等等。
4. AI
我们选择在这个基础之上，加上一个 AI 来陪玩。
Will win
第一步应该是需有能够自动判断，下完这一步之后我们就能赢了。其实也非常简单，只要在所有的空位依次下一个子，然后判断是否能赢就可以了。
这里需要注意的是，我们是模拟落子，不能直接修改棋盘的数据（当然也可以修改、判断之后立马复原）。因此我们需要将原来的棋盘复制一份，再修改、判断。
function willWin(pattern, color) {
for (let y = 0; y < 3; y++) {
for (let x = 0; x < 3; x++) {
// 有棋子就跳过
if (pattern[y * 3 + x] !== 0) continue;
let tmp = clone(pattern);
tmp[y * 3 + x] = color;
if (check(tmp, color)) return true;
}
}
return false;
}
这部分的代码非常简单了，需要考虑的就是 clone() 函数部分的代码，复制数据在 JS 中有非常多的选择。对于一维数组我们可以直接用 slice() 方法。当然如果是多维数组或者树形结构 slice 就搞不定了，不过我们可以借助 JSON 的「序列化」和「反序列化」，如， JSON.parse(JSON.stringify(pattern)) 也能得到一份新的数据 。
不过上面介绍的那些方法都太消耗性能了，由于我们用的是一维数组，所以可以利用 JS 的原型机制。直接以原数组为原型造一个新的对象。这个方法在 copy 的数据量大的时候，性能的优势非常大。这也是我们选择使用一维数组来存储数据的最大因素。
代码非常简单，只有一句：
function clone(pattern) {
return Object.create(pattern);
}
然后我们在有一方落子之后就可以判断另一方是否直接赢了。
function move(x, y) {
if (willWin(pattern, color)) {
console.log(`${color === 2 ? "❌" : "⭕️"} will win!`);
}
}
Best choice
有了 willWin 机制，我们再来考虑一个问题，什么情况下我们一定会输？其实就是当我方没有 willWin，而对方有两个 willWin 的点的情况。
我们转换成具体的代码就是：
function bestChoice(pattern, color) {
let point = willWin(pattern, color);
if (point) {
return {
point: point,
result: 1,
}
}
let result = -1;
for (let y = 0; y < 3; y++) {
for (let x = 0; x < 3; x++) {
if (pattern[y * 3 + x] !== 0) continue;
let tmp = clone(pattern);
tmp[y * 3 + x] = color;
let opp = bestChoice(tmp, 3 - color);
if (-opp.result >= result) {
point = [x, y];
result = -opp.result;
}
}
}
return {
point: point,
result: point ? result : 0,
}
}
算法整体的思想就是，首先检查我方是不是快赢了（willWin），如果是，就直接结束了。如果不是，就再找对方可以赢的点，处理的方式就是遍历所有空位，并填上我方的棋子。然后在这个情况下查看对方的 bestChoice，再将对方的 result 与我们当前的 result 对比，对方最糟糕的选择对于我们来说就是最好的选择。保存当前的 point 和 result，再进行下一轮的寻找，在所有情况中找出最优的选择。
最后就是将找到的最优 point 返回，result 还要看 point，如果不存在就说明是平局的情况。
剪枝
这个地方我们是遍历的所有的情况，所以其实时间复杂的非常的高，大概是 O(2^n)。所以我们还可以加上一些剪枝的操作来降低复杂度，如，输赢剪枝、蒙特卡洛剪枝等等。
我们的井字棋只有 3x3 的棋盘，递归的深度不大，所以我们能够算出精确结果。其实对于 8x8 的黑白棋，15x15 的五子棋，19x19 的围棋都是无法算出精确结果，只能使用估值算法为每一步棋打分。
我们这个稍微修改一下那个双重循环，来加入一个输赢剪枝。
outer:for (let y = 0; y < 3; y++) {
for (let x = 0; x < 3; x++) {
if (pattern[y * 3 + x] !== 0) continue;
let tmp = clone(pattern);
tmp[y * 3 + x] = color;
let opp = bestChoice(tmp, 3 - color);
if (-opp.result >= result) {
point = [x, y];
result = -opp.result;
}
if (result === 1) break outer;
}
}
computerMove 和 userMove
有了上面的 bestChoice 我们就可以让 AI 陪我们玩了（不过我们永远都不赢了了🤣），我们将之前的 move() 函数改名成 userMove，然后再加上一个 computerMove 函数让计算机自动落子。
computerMove 函数的逻辑跟 userMove 一样，只不是坐标 x、y 是由 bestChoice 给我们生成。
function userMove(x, y) {
if (pattern[y * 3 + x] > 0) return;
pattern[y * 3 + x] = color;
show(pattern);
if (check(pattern, color)) {
alert(`${color === 2 ? "❌" : "⭕️"} is winner`);
}
color = 3 - color;
computerMove();
}
function computerMove() {
let choice = bestChoice(pattern, color);
if (choice.point) {
pattern[choice.point[1] * 3 + choice.point[0]] = color;
}
show(pattern);
if (check(pattern, color)) {
alert(`${color === 2 ? "❌" : "⭕️"} is winner`);
}
color = 3 - color;
}
棋谱
到上一步，其实一个简单的陪玩 AI 已经完成了。不过还有一个问题，当我们需要 AI 先落子时，在它看来 9 个位置没有差别，所以最后一个位置的值覆盖前面的情况，最后它一定会会走右下角。
但其实井字棋是有最佳开局点的，就是中心点。处理这个问题棋类游戏常用的技巧就是「棋谱」，弄一个有各种开局的棋谱，碰到对应的棋局情况直接走固定的位置即可。
简单的实现就是：
const openings = new Map();
openings.set(
[0, 0, 0, 0, 0, 0, 0, 0, 0].toString() + "1",
{ point: [1, 1], result: 0 }
);
openings.set(
[0, 0, 0, 0, 1, 0, 0, 0, 0].toString() + "2",
{ point: [0, 0], result: 0 }
);
function bestChoice(pattern, color) {
if (openings.has(pattern.toString() + color)) {
return openings.get(pattern.toString() + color);
}
}
这里的思路比较简单，我们就初始化了两种棋盘的情况，key 部分只要能保证是唯一的情况就可以了。
结束
本篇文章实现了一个简单的井字棋游戏，最后还实现了一个 AI 来陪玩。对于棋类游戏来说整个的架构都是这样，画棋盘 --> 交替落子 --> 判断输赢。有些棋类还存在吃子、有些区域不能落子的情况，如黑白棋、围棋，这些都是落子部分的逻辑更加复杂。然后不同的棋类输赢的方式也不一样，比如象棋只要吃掉对方的将（或者帅）就算赢，这些就是增加判断输赢的逻辑。
最后就是 AI 部分了，对于棋类游戏来说，AI 做的事情就是遍历所有情况，找到对于我方最有利的位置。这里面最复杂的就是 best choice 的功能，对于井字棋来说可以穷尽所有可能找到最终解。但是对于绝大多数棋类游戏来说，递归所有解的复杂度太高了（O(2^n) 复杂度），所以就要引入了「剪枝」、「棋谱」等机制来降低复杂度。
最后完整的代码放在了 GitHub tictactoe 上了。
参考
winter 前端进阶训练营
https://zh.wikipedia.org/wiki/%E4%BA%95%E5%AD%97%E6%A3%8B
评论