正文

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

HullQin  HullQin  2022-12-01  159

关键词：

1. 问题描述

《五子棋》游戏，如何判断输赢呢？

这个问题是不是很简单？适合给代码初学者练手。

但是如果你真的只想快速开发一个五子棋，常年混迹开发业务、多年没摸算法的你，的确可能会在这个问题上头疼。

因为目标不一样：代码初学者愿意花好几个小时在这上面优化算法，但业务开发者只想5分钟内解决掉这个问题。

今天，我们作为业务开发者，5分钟实现它。

输入

当前棋盘上的棋子分布信息，分布信息通常有2种存储方式，见上篇文章《《五子棋》怎么存棋局信息？》。本文采用的是文中2.6节的方案一：

用一个列表存储已落的棋子，列表顺序表明棋子顺序，列表每一项的值代表棋子的位置，值为0-224（刚好15*15=225个值），奇数位置是黑棋，偶数位置是白棋。

以这局为例：https://game.hullqin.cn/wzq/?p=000110112021303140

注意：网址参数中，是用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 噢～我有空了会分享做游戏的相关技术。

[教你做小游戏]用177行代码写个体验超好的五子棋(代码片段)

...戏的需求，你会怎么做呢？2.技术选型参考掘金文章《H5小游戏技术选型分析，低代码?小游戏框架?canvas或SVG?还能用React？》，我们利用文章的决策树进行技术选型：我们不需要借助现有的游戏模板。我们不需要素材管理、不涉及... 查看详情

[教你做小游戏]用86行代码写一个联机五子棋websocket后端(代码片段)

背景上篇文章《用177行代码写个体验超好的五子棋》，我们一起用177行代码实现了一个本地对战的五子棋游戏。现在，如果我们要做一个联机五子棋，怎么办呢？需求分析首先，我们需要一个后端服务。2个不同的玩家，一起连... 查看详情

[教你做小游戏]用svg画一个象棋棋盘

背景兄弟们，之前我开发了支持联机对战的五子棋、斗地主、UNO。在大家的呼吁之下，我准备开发「象棋」啦！查看详情

第5天面向对象

...象放进冰箱1.打开冰箱2.放入大象3.关闭冰箱例子2.做五子棋的游戏开发1.开始2.白子先走3.绘制棋盘4.判断输赢5.黑子再走6.绘制棋盘7.判断输赢…… 2.面向对象OOP（Object OrientedProgramming）面向对象编程面向对查看详情

17.11.3五子棋判断输赢

描述在一个N×N的棋盘上下五子棋，给定一个五子棋黑白棋的落子序列(x0,y0),(x1,y1),...,（xn,yn），判断走到多少步时，哪方获胜。关于输入第一行有两个整数，棋盘的大小N和落子序列的长度n。其余各行每行两个数字，分别表... 查看详情

c语言小项目--五子棋小游戏（通用版）(代码片段)

目录1、game.h2、test.c3、game.c4、游戏功能详解(1)、棋盘初始化(2)、棋盘的打印(3)、玩家下棋(4)、电脑下棋(5)、判断游戏输赢(6)、判断棋盘是否满了1、game.hgame.h：自定义头文件，用于：库函数头文件的包含符号与结构的... 查看详情

面向对象的优势

...2.可重用性；3.稳定性；4.易维护性；5.可测试性；例如：五子棋一、面向过程的方法：1.开始游戏↓2.黑方先走↓3.绘制画面↓4.判断输赢↓5.turn白方↓6.绘制画面↓7.判断输赢↓8....重复步骤...↓9.悔棋↓10.输出最后结果查看详情

小游戏二之---------------五子棋(代码片段)

1.五子棋是一比较容易写的小游戏，很适合用来练手，作为练手，不必弄太复杂，所以就不弄电脑AI了，只是玩家之间的对战（AI下次再写)。2.五子棋的难点在于如何判断输赢,其实很简单。每次下棋，就判断该棋子的四个方向，... 查看详情

编写五子棋游戏的趣事

...刚学会了VB语言后，就迫不及待地尝试着用它来开发一个五子棋游戏，纯粹为了好玩。一下班，我脑子里都在琢磨着怎么样把我下五子棋的本领“传授”给程序。一开始仅仅是编写了一个五子棋的界面，接下来提供了判断输赢的... 查看详情

面向对象pk面向过程

...为了描叙某个事物在整个解决问题的步骤中的行为。例如五子棋，面向过程的设计思路就是首先分析问题的步骤：1、开始游戏，2、黑子先走，3、绘制画面，4、判断输赢，5、轮到白子，6、绘制画面，7、判断输赢，8、返回步骤查看详情

面向对象和面向过程的区别

几分钟教你做个原创视频，赚钱引流两不误

...代理真的把人请过来做广告。650)this.width=650;"alt="几分钟教你做个原创视频，赚钱引流查看详情

unity实战：教你做黄豆君(代码片段)

文章目录前言一、Unity2D入门1.入门准备1.1导入开发所需要的资源1.2创建地形1.3改变地形颜色2.游戏中的2DCamera2.1了解Camera的基本属性2.2创建相机跟随脚本2.3把主角装载到照相机跟随脚本上3.物理碰撞系统3.1设置地形碰撞检测组件3.2... 查看详情

unity实战：教你做黄豆君(代码片段)

[教你做小游戏]斗地主的手牌，如何布局？看25万粉游戏区up主怎么说

背景在B站拥有25万粉丝的UP主「时少权」，发布了条视频：《为什么中国10年都做不好斗地主？》，播放量直破10万，视频主要内容如下：十年来，几乎所有斗地主游戏展示手牌的方式（下称理牌方式）都千篇一律：手牌排列为一... 查看详情

c语言——五子棋游戏(代码片段)

...、作者遇到的坑点十、完整的代码一、前言本文将先介绍五子棋运行所需要的函数，最后串联成完整代码。我们需要实现的功能有：1.菜单menu函数 2.初始化棋盘I 查看详情

java五子棋游戏——控制台版(代码片段)

该项目为Java编程语言编写的五子棋游戏(控制台版），用到二维数组、for循环、if语句、while()语句、ScannerUntil包，此项目主要是对数组的使用。该项目的功能有落子、输出棋盘、判断输赢。代码条：packageedu.qizi.ga... 查看详情