编程能力 —— TicTacToe(井字棋)

发布于: 2020 年 07 月 09 日

井字棋是一个规则非常简单的小游戏,应该绝大部分的同学都玩过。就是在一个井字格里面画 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;
}
// 利用 JS 中的 label 标签来跳出外层循环
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

发布于: 2020 年 07 月 09 日 阅读数: 75
用户头像

wendraw

关注

还未添加个人签名 2018.05.07 加入

还未添加个人简介

评论

发布
暂无评论
编程能力 —— TicTacToe(井字棋)