我是公众号线下派对游戏的作者HullQin（欢迎关注公众号，发送加微信，交朋友）。转载本文前必须获得作者HullQin的授权。我独立开发了《联机桌游合集》，这是一个网页，在这里你可以轻松和朋友一起玩网络游戏，五子棋等游戏，免费，无广告。还为GameJam2022开发了《Dice Crush》，喜欢的话可以关注我HullQin哦~有空我会分享制作游戏的相关技术。1.问题描述《五子棋》游戏，如何判断输赢？问题不简单吗？适合编码初学者练习。但如果你真的只是想快速开发一款五子棋，常年从事开发业务，多年未接触算法的你，可能确实对这个问题很头疼。因为目标不同：代码初学者愿意为此花费数小时优化算法，但业务开发人员只想在5分钟内解决这个问题。今天，作为业务开发人员，我们可以在5分钟内实现它。输入当前棋盘上棋子的分布信息。分布信息通常有两种存储方式。见上一篇《如何存储棋局信息？”。本文采用文章2.6节方案1：用一个列表存储掉落的棋子，列表的顺序表示棋子的顺序，列表中每一项的值代表位置棋子的个数，取值为0-224（刚好是15*15=225的值），奇数位为黑，偶数位为白。以本游戏为例：https://game.hullqin.cn/wzq/?...注：URL参数中，棋子用16进制表示，每2位一个棋子。//URL参数对应这样的输入数据：constinput=[0,1,15,16,30,31,45,46,60];//000110112021303140为黑棋，偶数位置为白棋输出，有3种可能：黑棋胜白棋胜noonewins(gameshouldcontinue)(当然也有申诉判断是不是平局，但是场景不多，本文不考虑这个申诉判断是不是平局另外，因为我的游戏有认输功能，不会出现棋盘满，双方无法操作的情况）基本假设是只有最后一步，导致一方获胜五连珠。也就是说：如果上一手棋是黑棋，那么当前白棋一定没有赢。只需要判断黑棋是否赢了，输出1还是3就知道了。如果最后一手是白棋，那么黑棋此刻一定没有赢。你只需要判断白棋是否赢了，你就知道输出的是2还是3。这个基本假设是符合真实五子棋场景的。2.解法2.1五分钟解法如果你觉得这道题简单恶心，只想快点做完，你可以这样做：先求最后一步棋的颜色，得到的棋子集那个颜色：constinput=[0,1,15,16,30,31,45,46,60];const件=输入。filter((piece,index)=>input.length%2!==index%2);安慰。log(pieces);例如input.length为奇数，表示最后一步为黑棋，输入的所有偶数项（从0开始）为黑棋。然后遍历这个集合，看它是否一共8个方向，上、下、左、右，是否有5个连续的球。如果是这样，他就赢了；否则，他不会赢。constinput=[0,1,15,16,30,31,45,46,60];constpieces=input.filter((piece,index)=>input.length%2!==index%2);console.log(pieces);constjudge=(pieces)=>{constpieceSet=newSet(pieces);for(leti=0;i=4&&pieceSet.has(piece-1)&&pieceSet.has(piece-2)&&pieceSet.has(piece-3)&&pieceSet.has(piece-4))返回真；if(piece%15<=10&&pieceSet.has(piece+1)&&pieceSet.has(piece+2)&&pieceSet.has(piece+3)&&pieceSet.has(piece+4))返回真；if(Math.floor(piece/15)>=4&&pieceSet.has(piece-15)&&pieceSet.has(piece-30)&&pieceSet.has(piece-45)&&pieceSet.has(piece-60))返回真；if(Math.floor(piece/15)<=10&&pieceSet.has(piece+15)&&pieceSet.has(piece+30)&&pieceSet.has(piece+45)&&pieceSet.has(piece+60))返回真；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))返回真；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))返回真；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))返回真；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))返回真；}返回假;};console.log(judge(pieces));算法说明如果最后一手是黑子，则遍历所有黑子：以黑子为五连珠的顶点，查看其上、下、左、右、左上是否有连续的4个黑子、右下、左下、右上，只要有一个成立，则黑棋获胜。如果遍历所有棋子的所有方向后，如果为真，也没有发现任何一个可以使任何棋子，则说明黑棋没有获胜。里面有一个for循环，用来遍历黑棋。8个if判断，分发判断8个方向是否有4个连续球。if判断的注意事项8个前缀表达式：piece%15是棋子所在的行。Math.floor(piece/15)是前几列。这个前缀表达式判断不能省略。想想为什么？答：如果省略，会出错。比如在这种情况下，算法会误判：constinput=[11,224,12,223,13,222,14,221,15]；大部分人在看到这道题的时候都会看到自己最快能想到的暴力解法。这个算法虽然比较笨，可以剪枝优化的地方也很多，但是因为最长的片长是一个Math.ceil(225/2)=113的列表，算法在实践中不会慢多少。完全可以投入生产环境。我在五子棋第一版中使用了这个算法，只是为了快速添加判断胜负的功能。2.215分钟计划如果你已经完成了产品需求，有时间优化技术，你可以对2.1计划进行剪枝优化。（当然，产品需求一辈子也做不完，可能没时间去优化。）看算法描述前，需要强调一个基本假设：存在且只有最后一步，即导致某一方的胜利。至于最后一手的胜利，有4种可能的方向：上下5连球，左右5连球，左上下5连球，右上下5连球。所以我们判断最后一局的4路连局，只要任一方向有5连局，我们就赢。否则赢不了。完整代码这也是我的五子棋游戏采用的方案。我直接贴源码：exportfunctionjudgeWin(pieces:number[]){//先选择和上一手颜色相同的棋子集合constsamePieces=newSet();constcolor=pieces.length%2;pieces.forEach((v,i)=>{if(i%2!==color){samePieces.add(v);}});//得到最后一块棋子的坐标constp=pieces[pieces.length-1];//判断棋子的四个直线方向【上下、左右、左上右下、左下右上】最大连续球数。如果你找到5个连续的珠子，你就赢了letcount=0;//右上角for(leti=1;i<=Math.min(4,p%15,14-Math.floor(p/15));i++){if(samePieces.has(p-i+15*i)){计数+=1;}else{休息;}}//左下角for(leti=1;i<=Math.min(4,14-(p%15),Math.floor(p/15));i++){if(samePieces.has(p+i-15*i)){计数+=1;}else{休息;}}//右上左下，累计4连局，你赢了if(count>=4)returntrue;//如果上面的方向没赢，再看其他方向count=0;//左上角for(leti=1;i<=Math.min(4,p%15,Math.floor(p/15));i++){if(samePieces.has(p-i-15*i)){计数+=1;}else{休息;}}//右下角for(leti=1;i<=Math.min(4,14-(p%15),14-Math.floor(p/15));i++){if(samePieces.has(p+i+15*i)){计数+=1;}else{休息;}}//左上右下，累计连续4个jumbo，如果(count>=4)returntrue;//如果上面的方向没赢，再看其他方向count=0;//upfor(leti=1;i<=Math.min(4,p%15);i++){如果(samePieces.has(p-i)){count+=1;}else{休息;}}//接下来for(leti=1;i<=Math.min(4,14-(p%15));i++){if(samePieces.has(p+i)){count+=1;}else{休息;}}//如果（计数>=4）如果（计数>=4）返回真；//如果上面的方向没赢，再看其他方向count=0;//Leftfor(leti=1;i<=Math.min(4,Math.floor(p/15));i++){if(samePieces.has(p-i*15)){count+=1;}else{休息;}}//对(leti=1;i<=Math.min(4,14-Math.floor(p/15));i++){if(samePieces.has(p+i*15)){计数+=1；}else{休息;}}//左右两边，累计连续4个，win否则方向遍历过，说明没有winreturncount>=4;}和5分钟的解法相比，算法分析真的翻倍了一样快。虽然两种算法的复杂度都是O(n)，但15分钟的解决方案遍历次数较少。当然，方案2的算法复杂度主要来自遍历棋子生成一组颜色相同的棋子。如果抛开这个过程，只谈判断是否有5个连续的相同颜色的棋子，方案2的算法复杂度是O(1)，而方案1的算法复杂度是O(n)。注意代码并没有写成最紧凑的方式，你可以使用方向数组将8个for循环简化为嵌套的2个或3个for循环。这不会改变代码复杂度，但会缩短代码长度。什么是方向阵列？constdx=[0,0,1,-1,1,-1,1,-1];constdy=[1,-1,0,0,1,-1,-1,1];这样找到相邻棋子的写法就可以统一了。通过加一层循环，从0到7遍历j：p-i-15*i变成p+i*dx[j]+15*i*dy[j]。有兴趣的朋友可以尝试简化一下。我只是一个业务开发人员，所以我不会花太多时间，哈哈。3.写在最后的算法，如果不自己开发《五子棋》，可能想都没想。但是当你去做的时候，你会发现很好玩，而且实现方案有很多，你要选择最适合自己的。以上也是我在开发联机步步高的时候，一直追求极致的用户体验。请参考文章：《我做的《联机五子棋》如何追求极致的用户体验？（上篇）》我是公众号线下派对游戏作者HullQin（欢迎关注公众号，发送加微信，交友）。转载本文需获得作者HullQin授权.我独立开发了《联机桌游合集》，这是一个网页，在这里你可以轻松地和朋友一起玩网络游戏，五子棋等游戏，免费，无广告。还为GameJam2022开发了《Dice Crush》。如果你喜欢，可以关注我HullQin哦~有空我会分享制作游戏的相关技术。
