tic-tac-toe井字棋

项目安装和运行

安装

npm install

运行

npm run serve

项目结构

src/components/ChessBoard.vue 井字棋的界面组件：可选择先后手和难度，具备胜负和弹窗提示

src/engine/engine.js:井字棋的引擎，可查询某一棋局局面下的可选着、必胜着、必负着。

src/engine/manager.js:棋局管理器。维护棋局局面，对于玩家的一个棋着，向引擎查询下一棋着的集合，根据玩家选择的难度选择其中一个棋着。

井字棋引擎

对于棋盘格子编号为0-8，由于编号较少，考虑使用二进制串存储棋盘。这样，胜利棋局棋面VictorySates仅有八种情况。

BoardState类：

• 成员变量
  • chance：当前棋手，取值:0先手方，1后手方。
  • states：长度为2的数组。states[0]表示先手方的着棋格子集合，states[1]表示后手方的着棋格子集合。例如states[1]=0b000000101表示后手方在格子0和2下了棋着。
• 方法
  • setNextStep(index)：在编号index的格子下一棋着，并且交换棋权。
  • _getOptionalBits：获取可选的下一步的格子的集合，也就是全部格子排除selfState和enemyState后剩下的格子。
  • isDraw：判断当前棋局是否为和棋。和棋一定满足_getOptionalBits()为空集。注意，完全正确的写法应该是当前局面不满足胜或者负的前提下，可选棋着为空集才为和棋。
  • isFail:判断当前棋手是否失败。求出上一步棋手，判断该棋手对应的棋局状态是否属于胜利棋局局面即可。（注意没有提供isVictory函数判断当前棋手是否胜利，因为每一个棋局局面当前棋手都尚未执行棋权）
  • hash：该函数是为了方便后面字典把BoardState的哈希值作为键。
• Record类：继承自BoardState类
  • 新增成员变量
    • victorySteps：对于己方来说必胜着的集合
    • failSteps：对于己方来说必败着的集合
  • 必胜状态的定义：
    • 简单来说，一个棋面如果处于必胜状态，则双方在最优选择下最终能够使得当前棋手获胜。
    • 其具体判断算法为：
    • 假设当前棋手为x，上一棋手为y。
    • 如果存在下一棋着，使得下一棋面y处于必败状态，那么当前棋面处于必胜状态。其等价说法为，如果必胜着集合不为空，那么当前棋面处于必胜状态。
  • 必败状态的定义：
    • 假设当前棋手为x，上一棋手为y。
    • 如果当前棋面判断isFail为真，说明y恰好获胜，则x必败；
    • 或者，如果任意下一棋着，均使得下一棋面y处于必胜状态，那么当前棋面处于必败状态。
  • 至此，无需赘述Record类的其他方法。读者唯一需要注意的是，Record类变量在什么时候可以计算出其必胜着和必败着。
• Engine类：计算和存储整个棋面树，并提供搜索方法。
  • 成员变量：只有字典dictionary，键为Record的hash值，值为Record对象。
  • 方法dfs：深度优先遍历，构建整个棋面树，并存储进dictionary。该方法放在最后面解释。
  • getNextSteps(state)：以棋面为参数，从字典获取对应的Record，从该Record容易得到一般棋着、必胜着、必败着等信息。
• dfs方法：
  • 假设初始棋面为棋手0先手，棋手1后手，双方均未下任一棋着。
  • 如果某一棋面当前棋手失败，直接记入字典即可。
  • 否则，遍历所有可选的下一棋着，从而逐个产生下一棋面，对下一棋面进行深度遍历。
    • 我们假定在dfs返回之后，下一棋面的必胜着和必败着已经全部计算出来。如果下一棋面为必胜状态（注意不是指恰好获胜），那么对于当前选手来说，该棋着为必败着，把该棋着记入当前棋面的必败着。同理，如果下一棋面为必败棋面，该棋着为必胜着。
• 补充说明：深刻理解必胜状态和必败状态是理解dfs方法的关键。当前棋面处于必胜状态不意味着己方最终一定能够胜利。例如，当前棋面存在下一步可以直接获胜，但是如果当前棋手没有选择必胜着，而是选择其他棋着，那么必胜状态的棋面也可能变成一个必败状态的棋面。

棋局管理器

• 如果理解了engine.js，那么理解棋局管理器也应该没有任何难度。
• 方法
  • newGame(playerFirst,invincible)
    • playerFirst表示是否为玩家先手。若是，则函数返回一个对象，该对象的index和gameStatus字段都是null。否则，让引擎先走一步，返回的对象的index字段不为空。
    • invincible为玩家选择的难度是否为不可战胜难度。若是，管理器会优先选择对引擎提供的棋着中最优的棋着，否则，管理器会随机选一个棋着。
  • selfMove(index)：玩家在编号为index的格子下一着棋，更新当前棋面。之后，会对当前棋面进行胜负和的判断，如果棋局能够继续，会让引擎走下一步。
  • enemyMove:让引擎下一棋着。
  • selectFrom(nextSteps)：从引擎提供的nextSteps选择一个棋着。