我是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 奇数地位是黑棋，偶数地位是白棋输入
有3种可能：
- 黑棋赢
- 白棋赢
- 没人赢（游戏应该持续）
（当然也有诉求判断是否平局，但场景不多，本文不思考这种判断是否平局的诉求。另外也因为我游戏中有认输性能，不会呈现棋盘下满导致单方无奈做任何操作的状况）
根本假如
有且仅有最初一手棋，导致某方五联珠胜利。
也就是说：
- 如果最初一手是黑棋，那么以后白棋肯定没赢，只须要判断黑棋是否赢，就晓得输入是1还是3。
- 如果最初一手是白棋，那么以后黑棋肯定没赢，只须要判断白棋是否赢，就晓得输入是2还是3。
这个根本假如，合乎实在的五子棋场景。
2. 解决方案
2.1 五分钟计划
如果你感觉这个问题又简略又恶心，只想疾速做完，能够这样做：
先找到最初一手棋的色彩，拿到该色彩棋子的汇合：
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];算法点评
我置信这是大多数人，看到这道题最快能想到的暴力解法。该算法尽管比拟蠢，有很多中央能够剪枝优化，然而因为pieces最长长度为Math.ceil(225/2)=113的列表，所以该算法理论状况下不会慢多少。齐全能够投入生产环境应用。
我五子棋第一个版本就采纳了该算法，过后只是为了疾速加上胜利判断性能。
2.2 十五分钟计划
如果你把产品需要赶完了，有工夫做技术优化了，能够对2.1计划做个剪枝优化。
（当然产品需要是一辈子也做不完的，你可能没工夫做优化了）
算法形容
看该计划前，须要强调一下根本假如：有且仅有最初一手棋，导致某方五联珠胜利。
而最初一手棋胜利，有4个可能的方向：高低5连珠、左右5连珠、左上右下五联珠、右上左下五联珠。
所以，咱们判断最初一手棋的4个方向的连珠，只有任意方向有5连珠，就赢了。否则没赢。
残缺代码
这也是我的五子棋游戏采纳的计划，我间接贴源码：
export function judgeWin(pieces: number[]) { // 先选出与最初一手同色的棋子汇合 const samePieces = new Set<number>(); 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 噢～我有空了会分享做游戏的相干技术。