请将本文件在代码仓库外复制一份，一边阅读和完成结对项目、一边填写入代码仓库外的版本，或采取简记、语音备忘等方式记载较复杂问题的要点之后再补充。请不要将本文档内的作答提交到代码仓库。
2024.3.28 19：15
数据的存储位置。原生app只需要从本地加载数据，web app需要从服务器请求、发送数据，受网络传输速度和数据分布式存储的限制。
web app 具有多平台运行的需求，web 语言的开发更侧重于拓展 web app 的可拓展性，需要降低web的开发难度。不同执行环境带来的额外适配成本、跨平台软件构建的开销复杂化了开发和分发，占用了提高app速度的成本。
可以加强web开发语言与不同系统的适配性，通过统一的中间语言衔接web开发和原生软件开发环境。
I. 没有听说过；
II. 仅限于听说过相关名词；
III. 听说过，且有一定了解；
IV. 听说过，且使用 Wasm 实际进行过开发（即便是玩具项目的开发）。
I. 没有听说过；
我们使用的编程语言是c++，c++的wasm需要使用emscripten库导出js和wasm文件，然后从js中导出函数，与测试文件交互。
第一个难题是从js文件中导出函数。
c++的函数不能在简单的编译后，通过 import 语句导入。经过我们的调研，最后得到的解决方案是，在命令行中声明要导出的函数，并表明导出的形式。然后在js文件中通过 Module 方法的 cwrap 函数对c++函数重新封装，重新声明函数，设置函数的参数列表和返回值，才能完成调用。
第二个难题是js文件中如何调用c++函数，输入预定的数组数据。
c++函数的参数是一个整数指针，但是在js文件中无法直接将数组传输进去。在我们的方案中，需要为数组先在栈上分配空间，将数组复制到栈上，然后将栈的指针作为参数传递给函数。也就是说，对于涉及数组操作的函数，需要在js文件中自主进行内存管理。
我们解决问题的过程中参考了很多博客、官网教程，也咨询了很多其他同学的解决方案。模块一的主要难点就在于 c++ 和 js 的交互上，是我们花了最多时间的部分。
因为相比于其他语言，我们对c++比较熟悉。且c++对wasm的支持相对完善。
在 c++ 的 web asembly 转换中，我们使用了 emsdk 库导出对应的 js 和 wasm 文件，然后从js中导出函数，与测试文件交互。
首先，下载 emsdk 库，配置并加载emcc环境。
参考博客：https://blog.csdn.net/GISuuser/article/details/118310452?spm=1001.2014.3001.5501
然后，我们参考官网指引，使用emcc指令编译c++文件，生成js和wasm。
我们查找了 emcc 官网 > porting > 连接c++和js > 代码交互 > [使用ccall/wrap](https://emscripten.org/docs/porting/connecting_cpp_and_javascript/Interacting-with-code.html#interacting-with-code-ccall-cwrap)，并参考gpt，发现以下操作可行：
在cpp文件中，用 extern 'C' {} 包裹要导出的函数。
命令行输入：
emcc bocchiShutUp.cpp -o function.js -s EXPORTED_FUNCTIONS="['_bocchiShutUp', '_malloc', '_free']" -s EXPORTED_RUNTIME_METHODS="['ccall', 'cwrap']" -s EXPORT_ES6=1
-o 标识编译输出的文件名
-sEXPORTED_FUNCTIONS 标注出需要导出的c++函数
-sEXPORTED_RUNTIME_METHODS=ccall, cwrap 这里的ccall和cwrap是之后与 test.js 交互时需要用到的函数
-EXPORT_ES6 为了能够从js文件中顺利导出 module 添加的必要参数
然后修改test.js文件内容，导入相应函数：
import Module from "./t1_cpp/function.js"; //导入Module方法
var RealModule = await Module() //异步调用Module
var callBocchiShutUp = RealModule.cwrap('bocchiShutUp', 'number', ['number', 'number', 'number']) //用cwrap函数导入写好的c++函数，设置函数的参数列表和返回值
// 将c++和js的指针参数对齐
function bocchiShutUp(flag, array, size) {
// 在js中对数组进行内存管理，手动分配内存，设置数组指针
const bytesPerElement = Int32Array.BYTES_PER_ELEMENT;
const numBytes = size * bytesPerElement;
const ptr = RealModule._malloc(numBytes);
let heapView = new Int32Array(RealModule.HEAP32.buffer, ptr, size);
heapView.set(array);
// 调用c++函数
const result = callBocchiShutUp(flag, ptr, size);
RealModule._free(ptr);
return result;
}2024.3.28 22：00 第一次结对编程结束，没有完成全部工作
第二次接着解决问题，从2024.4.1 16:00，到 2024.4.1 16:45 完成第一部分全部工作。
2024.4.1 17:00
| Personal Software Process Stages | 个人软件开发流程 | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| PLANNING | 计划 | 5 | 5 |
| - Estimate | - 估计这个任务需要多少时间 | 5 | 5 |
| DEVELOPMENT | 开发 | 135 | 180 |
| - Analysis & Design Spec | - 需求分析 & 生成设计规格（确定要实现什么） | 10 | 5 |
| - Technical Background | - 了解技术背景（包括学习新技术） | 5 | 5 |
| - Coding Standard | - 代码规范 | 5 | 5 |
| - Design | - 具体设计（确定怎么实现） | 5 | 5 |
| - Coding | - 具体编码 | 60 | 30 |
| - Code Review | - 代码复审 | 15 | 5 |
| - Test Design | - 测试设计（确定怎么测，比如要测试哪些情景、设计哪些种类的测试用例） | 5 | 5 |
| - Test Implement | - 测试实现（设计/生成具体的测试用例、编码实现测试） | 30 | 120 |
| REPORTING | 报告 | 30 | 30 |
| - Quality Report | - 质量报告（评估设计、实现、测试的有效性） | 15 | 15 |
| - Size Measurement | - 计算工作量 | 5 | 5 |
| - Postmortem & Process Improvement Plan | - 事后总结和过程改进计划（总结过程中的问题和改进点） | 10 | 10 |
| TOTAL | 合计 | 170 | 215 |
我们的编程进行的很顺利。在测试阶段，对于可能出现的异常行为，枚举可能产生的错误，并自行捏造数据。但是对于如何测试程序的正确性，我们罗列了一些解决方法，最后还是决定通过编写一个随机数据生成器，通过两个程序的相互对拍验证正确性。我们使用python语言，以相同的游戏逻辑复现了游戏步骤，通过生成随机数模拟出游戏行为，作为正常情况的输出。在 c++ 测试中，读取 python 生成的数据，并调用c++函数，验证两个程序的输出是否一致。我们对10000条游戏步骤数据进行了测试，保证了程序的正确性。因此，我们的测试阶段比预计多花了很多时间，相当于又实现了一遍游戏逻辑，还在原有的基础上开发debug模式，工作量比预期大很多。
异常行为：拿空格子，结束仍操作，操作者错误；这部分采用手工捏造数据
正常行为：写 python 数据生成脚本
统一在 test.cpp 利用 assert 进行测试。
对于脚本生成是否正确，我们首先对生成的几局比赛进行人工核验，再者对于每次的错误，我们都会从脚本和实现函数两个方面去纠错。
2024.4.1 21:30
2024.4.2 19:00
- 浏览任务要求，参照 附录A：基于 PSP 2.1 修改的 PSP 表格，估计任务预计耗时；
- 完成编程任务期间，依次做了什么（比如查阅了什么资料，随后如何进行了开发，遇到了什么问题，又通过什么方式解决）；
| Personal Software Process Stages | 个人软件开发流程 | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| PLANNING | 计划 | 5 | 5 |
| - Estimate | - 估计这个任务需要多少时间 | 5 | 5 |
| DEVELOPMENT | 开发 | 200 | 210 |
| - Analysis & Design Spec | - 需求分析 & 生成设计规格（确定要实现什么） | 20 | 10 |
| - Technical Background | - 了解技术背景（包括学习新技术） | 30 | 30 |
| - Coding Standard | - 代码规范 | 5 | 5 |
| - Design | - 具体设计（确定怎么实现） | 15 | 20 |
| - Coding | - 具体编码 | 60 | 80 |
| - Code Review | - 代码复审 | 15 | 15 |
| - Test Design | - 测试设计（确定怎么测，比如要测试哪些情景、设计哪些种类的测试用例） | 15 | 10 |
| - Test Implement | - 测试实现（设计/生成具体的测试用例、编码实现测试） | 40 | 40 |
| REPORTING | 报告 | 30 | 100 |
| - Quality Report | - 质量报告（评估设计、实现、测试的有效性） | 15 | 50 |
| - Size Measurement | - 计算工作量 | 5 | 15 |
| - Postmortem & Process Improvement Plan | - 事后总结和过程改进计划（总结过程中的问题和改进点） | 10 | 35 |
| TOTAL | 合计 | 235 | 315 |
T2 的函数功能是对输入的操作序列，判断是否违规，输出最后的得分。需要记录棋盘的中间状态，根据操作一步步推导，最终输出结果数据。
该任务的输入参数与T2相同，去除了在每一步判断操作合法的要求，并以数组的形式返回棋盘的中间状态。
因此，对于T2的代码，只需要去除中间状态的违规判断逻辑，修改最后的输出结果，并输出中间状态即可。对于T2的状态推演、下一步执棋判断、是否结束棋局的判断，都可以复用。
对于一个现有的棋盘状态，我们需要给出尽可能有利于己方的播撒决策。这是一个每次操作可见的完美博弈，主要的解法就是模拟。意思就是，棋盘策略数量有限，理论上可以通过罗列全部选择方法，比较每种决策的得分，做出最优选择。但实际的硬件算力无法支持这个规模的计算。因此与其他棋类博弈类似，需要借助搜索算法，优化搜索路径，量化搜索结果，缩小决策空间，得出局部最优解。如何高效搜索就是核心优化点。
对于一个连续的策略，不同的选择相当于树的不同分支，因此对决策的模拟本质上等同于一个博弈树的搜索算法。树的叶子结点是棋局的结束状态，因此树的深度有限。题目中有计算的时间限制，所以我们不能对所有分支都搜到根节点，需要限制搜索的层数，即限制棋盘模拟的步数。对于一个策略序列，可以通过最终状态或者中间状态的分数差距作为得分，量化策略的优劣。
搜索算法的流程如下图所示：
我们需要实现的函数有：
- 棋盘的状态推进函数
- 判断是否结束/是否到达指定层数
- 对一个棋局（中间状态或结束的棋局）评分函数
- 策略入口，统计最优策略的函数
- 极大极小搜索 MiniMax
播棋的执棋总体上是交替的，因此两步之间执棋方交替。以当前执棋方的视角来看，自己会选评分最大的策略，对方会选评分最小的策略。这种局面符合极大极小搜索的算法。因此，我们需要区分每一步的决策者和执棋方，交替使用两种不同的对抗策略。
（下图的 max 和 min标反了）
$\alpha\beta$ 剪枝策略
比如，对于一步最小决策，它的下一步为最大决策。如果它的第一个分支中，下一步决策中的最大值为8，因此它的决策值为8。如果最小决策的第二个分支中，它的子决策中有一个决策值为9，则下一步最大决策值必然大于等于9，因此这个分支必定不如第一个分支，肯定不是最小分支，因此第二个分支不需要再遍历完所有决策。
这个节点值范围通过$\alpha$，$\beta$值跟随树的深度优先搜索层层下传，超过范围时，结束该层的遍历，达到剪枝的效果。
- 启发式奖励因子
我们研究了播棋的规则和玩法，发现在两个人的对弈中有一些启发式策略，包括：
- 先手第一步取3号洞，第二步取6号洞
- 提防取子操作
- 尽量将棋子的最终落点放在计分洞，促成己方的连续操作
- 尽量保持6号格子的清空，以便连续操作
- 残局时，如果对方启动中包含大量棋子，需要拖慢进度逼迫对方播撒棋子。
因为工作量和时间关系，我们只按照第五条规则，在评估函数中加入奖励算子，改变决策偏向。
理论上，以上策略都能通过改变评估函数实现。但是评估函数的修改方式和影响力度都需要仔细思考，并通过测试和时间检验有效性，复杂度比想象的高。因此我们只实现了一条比较容易实现的规则，效果还不错。
- 让程序和自己对弈，确定先手净胜棋数的稳定性，保证程序可靠
- 人机对弈：我们增加了人工输入端口，可以让人工来与机器博弈，这样能让我们对所设计的算法有个初步的判断
- 更新前后博弈：将更新前后的算法进行博弈，根据得分判断性能是否优化
- 找现有其他程序（GitHub仓库或者其他同学的代码）与我们的程序对弈，统计先后手的净胜棋数
2024.4.2 22:30完成代码编写，结束第一阶段。
2024.4.6 20:40开始第二阶段：代码测试和编写文档
2024.4.6 22:00完成T3。
本次结对作业中，整体编写代码和测试的过程都没有什么疑义，写的速度很快，两个人在代码逻辑上没有什么分歧，也即时发现了很多问题，比一个写产生的bug更少，确实提高了效率。
但是本次结对中，代码的测试程序和测试手法不够全面和完善，仍然有少部分的bug和问题从T2被遗留到了T3。虽然在T2中，我们既用了自动生成的测试数据测试正确情况，又针对违规情况单独分析测试，但还是没有完全覆盖所有样例情况。比如，一局的结束既可以是执棋方把自己的棋盘清空，也可以是执棋方通过取子操作把对方的棋盘清空；我们在T2中没有考虑清空对方棋盘的情况，以至于在T3的搜索算法中出现负权重，给出异常值-1。我们将大部分精力放到了代码编写上，对规则的理解和测试的设计还不够完善。
本次结对主要的难点在于 T1 的wasm集成和T3的搜索算法设计。这些需要事先调研的部分我们在结对现场没办法很完善的完成（因为结对时我们处于神经高度紧张的状态，没办法静下心来花很多时间调研），所以我们T1的wasm是在结对时间之外完善补充的；T3的搜索算法也不算是最优解，性能和决策方法相对不突出，还有很多可以完善的空间。因此结对前应该先自行对项目有一个大致的理解和基础资料的搜寻，可以事先完成与代码逻辑无关的部分，提高结对编程的效率。