[教你做小游戏]|[教你做小游戏] 《五子棋》怎么判断输赢(你能5分钟交出代码吗?)

我是HullQin,公众号线下聚会游戏的作者(欢迎关注公众号,发送加微信,交个朋友),转发本文前需获得作者HullQin授权。我独立开发了《联机桌游合集》,是个网页,可以很方便的跟朋友联机玩斗地主、五子棋等游戏,不收费没广告。还开发了《Dice Crush》参加Game Jam 2022。喜欢可以关注我 HullQin 噢~我有空了会分享做游戏的相关技术。
1. 问题描述 《五子棋》游戏,如何判断输赢呢?
这个问题是不是很简单?适合给代码初学者练手。
但是如果你真的只想快速开发一个五子棋,常年混迹开发业务、多年没摸算法的你,的确可能会在这个问题上头疼。
因为目标不一样:代码初学者愿意花好几个小时在这上面优化算法,但业务开发者只想5分钟内解决掉这个问题。
今天,我们作为业务开发者,5分钟实现它。
输入
当前棋盘上的棋子分布信息,分布信息通常有2种存储方式,见上篇文章《《五子棋》怎么存棋局信息?》。本文采用的是文中2.6节的方案一:
  • 用一个列表存储已落的棋子,列表顺序表明棋子顺序,列表每一项的值代表棋子的位置,值为0-224(刚好15*15=225个值),奇数位置是黑棋,偶数位置是白棋。
以这局为例:https://game.hullqin.cn/wzq/?...
注意:网址参数中,是用15进制表示棋子的。每2位是一个棋子。
// 网址参数对应这样的输入数据: const input = [0, 1, 15, 16, 30, 31, 45, 46, 60]; // 分别是 00 01 10 11 20 21 30 31 40 奇数位置是黑棋,偶数位置是白棋

[教你做小游戏]|[教你做小游戏] 《五子棋》怎么判断输赢(你能5分钟交出代码吗?)
文章图片

输出
有3种可能:
  1. 黑棋赢
  2. 白棋赢
  3. 没人赢(游戏应该继续)
(当然也有诉求判断是否平局,但场景不多,本文不考虑这种判断是否平局的诉求。另外也因为我游戏中有认输功能,不会出现棋盘下满导致双方无法做任何操作的情况)
基本假设
有且仅有最后一手棋,导致某方五联珠胜利。
也就是说:
  • 如果最后一手是黑棋,那么当前白棋一定没赢,只需要判断黑棋是否赢,就知道输出是1还是3。
  • 如果最后一手是白棋,那么当前黑棋一定没赢,只需要判断白棋是否赢,就知道输出是2还是3。
这个基本假设,符合真实的五子棋场景。
2. 解决方案 2.1 五分钟方案
【[教你做小游戏]|[教你做小游戏] 《五子棋》怎么判断输赢(你能5分钟交出代码吗?)】如果你觉得这个问题又简单又恶心,只想快速做完,可以这样做:
先找到最后一手棋的颜色,拿到该颜色棋子的集合:
const input = [0, 1, 15, 16, 30, 31, 45, 46, 60]; const pieces = input.filter((piece, index) => input.length % 2 !== index % 2); console.log(pieces);

比如input.length是奇数,表明最后一手是黑棋,筛选出input的所有第偶数项(从0开始)都是黑棋。
然后遍历这个集合,看看它上下左右斜共8个方向,有没有5连珠,若有,则他赢;否则他没赢。
const input = [0, 1, 15, 16, 30, 31, 45, 46, 60]; const pieces = input.filter((piece, index) => input.length % 2 !== index % 2); console.log(pieces); const judge = (pieces) => { const pieceSet = new Set(pieces); for (let i = 0; i < pieces.length; i++) { const piece = pieces[i]; if (piece % 15 >= 4 && pieceSet.has(piece - 1) && pieceSet.has(piece - 2) && pieceSet.has(piece - 3) && pieceSet.has(piece - 4)) return true; if (piece % 15 <= 10 && pieceSet.has(piece + 1) && pieceSet.has(piece + 2) && pieceSet.has(piece + 3) && pieceSet.has(piece + 4)) return true; if (Math.floor(piece / 15) >= 4 && pieceSet.has(piece - 15) && pieceSet.has(piece - 30) && pieceSet.has(piece - 45) && pieceSet.has(piece - 60)) return true; if (Math.floor(piece / 15) <= 10 && pieceSet.has(piece + 15) && pieceSet.has(piece + 30) && pieceSet.has(piece + 45) && pieceSet.has(piece + 60)) return true; if (piece % 15 >= 4 && Math.floor(piece / 15) >= 4 && pieceSet.has(piece - 1 - 15) && pieceSet.has(piece - 2 - 30) && pieceSet.has(piece - 3 - 45) && pieceSet.has(piece - 4 - 60)) return true; if (piece % 15 <= 10 && Math.floor(piece / 15) <= 10 && pieceSet.has(piece + 1 + 15) && pieceSet.has(piece + 2 + 30) && pieceSet.has(piece + 3 + 45) && pieceSet.has(piece + 4+ 60)) return true; if (piece % 15 >= 4 && Math.floor(piece / 15) <= 10 && pieceSet.has(piece - 1 + 15) && pieceSet.has(piece - 2 + 30) && pieceSet.has(piece - 3 + 45) && pieceSet.has(piece - 4 + 60)) return true; if (piece % 15 <= 10 && Math.floor(piece / 15) >= 4 && pieceSet.has(piece + 1 - 15) && pieceSet.has(piece + 2 - 30) && pieceSet.has(piece + 3 - 45) && pieceSet.has(piece + 4 - 60)) return true; } return false; }; console.log(judge(pieces));

算法描述 如果最后一手为黑棋,则遍历所有黑棋:以该黑棋为五联珠的顶点,看看它的上、下、左、右、左上、右下、左下、右上是否有连续的4个黑棋,只要找到任意一项成立,则黑棋赢。若遍历了所有棋子的所有方向后,没找到能使任意if成立的,则表明黑棋没赢。
里面有1个for循环,用于遍历黑棋。8个if判断,分布判断8个方向是否有4连珠。
注意事项 8个if判断的前缀表达式:
piece % 15是棋子在第几行。Math.floor(piece / 15)是第几列。
这个前缀表达式判断不可省略。想想为什么?
答案:
如果你省略,会出错,比如在这种情况,算法会误判:
const input = [11, 224, 12, 223, 13, 222, 14, 221, 15];

[教你做小游戏]|[教你做小游戏] 《五子棋》怎么判断输赢(你能5分钟交出代码吗?)
文章图片

算法点评 我相信这是大多数人,看到这道题最快能想到的暴力解法。该算法虽然比较蠢,有很多地方可以剪枝优化,但是因为pieces最长长度为Math.ceil(225/2)=113的列表,所以该算法实际情况下不会慢多少。完全可以投入生产环境使用。
我五子棋第一个版本就采用了该算法,当时只是为了快速加上胜利判断功能。
2.2 十五分钟方案
如果你把产品需求赶完了,有时间做技术优化了,可以对2.1方案做个剪枝优化。
(当然产品需求是一辈子也做不完的,你可能没时间做优化了)
算法描述 看该方案前,需要强调一下基本假设:有且仅有最后一手棋,导致某方五联珠胜利。
而最后一手棋胜利,有4个可能的方向:上下5连珠、左右5连珠、左上右下五联珠、右上左下五联珠。
所以,我们判断最后一手棋的4个方向的连珠,只要任意方向有5连珠,就赢了。否则没赢。
完整代码 这也是我的五子棋游戏采用的方案,我直接贴源码:
export function judgeWin(pieces: number[]) { // 先选出与最后一手同色的棋子集合 const samePieces = new Set(); const color = pieces.length % 2; pieces.forEach((v, i) => { if (i % 2 !== color) { samePieces.add(v); } }); // 拿到最后一手棋子的坐标 const p = pieces[pieces.length - 1]; // 判断该棋子【上下、左右、左上右下、左下右上】四条直线方向,最大有多少连珠。若找到5连珠,则胜利 let count = 0; // 右上 for (let i = 1; i <= Math.min(4, p % 15, 14 - Math.floor(p / 15)); i++) { if (samePieces.has(p - i + 15 * i)) { count += 1; } else { break; } } // 左下 for (let i = 1; i <= Math.min(4, 14 - (p % 15), Math.floor(p / 15)); i++) { if (samePieces.has(p + i - 15 * i)) { count += 1; } else { break; } } // 右上和左下,累计4个连珠,就赢了 if (count >= 4) return true; // 若上述方向没赢,再看其它方向 count = 0; // 左上 for (let i = 1; i <= Math.min(4, p % 15, Math.floor(p / 15)); i++) { if (samePieces.has(p - i - 15 * i)) { count += 1; } else { break; } } // 右下 for (let i = 1; i <= Math.min(4, 14 - (p % 15), 14 - Math.floor(p / 15)); i++) { if (samePieces.has(p + i + 15 * i)) { count += 1; } else { break; } } // 左上和右下,累计4个连珠,就赢了 if (count >= 4) return true; // 若上述方向没赢,再看其它方向 count = 0; // 上 for (let i = 1; i <= Math.min(4, p % 15); i++) { if (samePieces.has(p - i)) { count += 1; } else { break; } } // 下 for (let i = 1; i <= Math.min(4, 14 - (p % 15)); i++) { if (samePieces.has(p + i)) { count += 1; } else { break; } } // 上和下,累计4个连珠,就赢了 if (count >= 4) return true; // 若上述方向没赢,再看其它方向 count = 0; // 左 for (let i = 1; i <= Math.min(4, Math.floor(p / 15)); i++) { if (samePieces.has(p - i * 15)) { count += 1; } else { break; } } // 右 for (let i = 1; i <= Math.min(4, 14 - Math.floor(p / 15)); i++) { if (samePieces.has(p + i * 15)) { count += 1; } else { break; } } // 左和右,累计4个连珠,就赢了。否则,方向已经遍历完了,说明没赢 return count >= 4; }

算法分析 相比5分钟方案,真的是翻倍的快了。虽然两个算法复杂度都是O(n),但是15分钟方案少了很多次遍历过程。
当然,方案二的算法复杂度主要来源于开始遍历棋子,生成同色棋子集合。如果抛开这个过程,只谈判断同色棋子是否存在5连珠,方案二的算法复杂度是O(1),但方案一的算法复杂度是O(n)。
注意事项 该代码写法不是最精简的,你能通过方向数组,把8个for循环简化成嵌套的2或3个for循环。这不会改变代码复杂度,但是会缩短代码长度。
什么是方向数组?
const dx = [0, 0, 1, -1, 1, -1, 1, -1]; const dy = [1, -1, 0, 0, 1, -1, -1, 1];

这样找相邻棋子的写法,就可以统一了。通过加一层循环,把j从0遍历到7即可:p - i - 15 * i变成p + i * dx[j] + 15 * i * dy[j]
感兴趣的朋友可以尝试精简一下。我只是个业务开发者,就不花过多时间了,哈哈。
3. 写在最后 这种算法,你不去自己开发《五子棋》,可能不会去思考。但是当你做的时候,会发现,非常好玩儿,实现方案很多,你要选出最适合你的那一个。
以上,也是我开发我的联
开发五子棋时,我始终追求极致用户体验,参考文章:《我做的《联机五子棋》是如何追求极致用户体验的?(上)》
我是HullQin,公众号线下聚会游戏的作者(欢迎关注公众号,发送加微信,交个朋友),转发本文前需获得作者HullQin授权。我独立开发了《联机桌游合集》,是个网页,可以很方便的跟朋友联机玩斗地主、五子棋等游戏,不收费没广告。还开发了《Dice Crush》参加Game Jam 2022。喜欢可以关注我 HullQin 噢~我有空了会分享做游戏的相关技术。

    推荐阅读