Crate ms_toollib

Expand description

§扫雷算法工具箱

基于Rust语言，提供扫雷游戏相关算法的高效、内存安全的实现，并发布到各个平台。目前包括crates.io、pypi.org、npmjs.com这三个平台。Python、Rust、Javascript、Typescript的用户可以流畅地使用相应的功能，C、C++的用户也可以使用。安装、使用这些工具箱需要有对应语言的基本的知识。项目地址在ms_toollib。以下是快速入门。

§特殊名词解释

注意：只包含本工具箱的文档中特有的名词解释。读者需具备“扫雷术语”等前置知识。

“游戏局面”
- 变量名为game_board: Vec<Vec>
- 类型
  - Python：list[list[int]]
  - Javascript、Typescript：Array(Array())
  - C：struct Board { struct Row *rows; size_t n_row; }; struct Row { int32_t *cells; size_t n_column; }
  - C++：std::vector<int32_t>
- 值的含义
  - 0代表空
  - 1到8代表数字1到8
  - 10代表未打开
  - 11代表算法认为是雷（百分百正确），或玩家在游戏中标的雷（玩家认为这是雷，但玩家可能犯错）
  - 12代表算法已经确定该位置不是雷，但玩家暂时还没点开，模样仍然是未打开的样子
  - 14表示踩到了雷游戏失败以后显示的标错的雷对应叉雷
  - 15表示踩到了雷游戏失败了对应红雷
  - 16表示背景不透明的白雷，失败后显示出来的其他的雷
  - 18表示局面中，由于双击的高亮，导致看起来像0的格子
- 第一个索引是行，第二个索引是列。例如：高级中，game_board[0][0]代表最左上角位置，game_board[15][29]代表最右下角位置。
- 注意：游戏局面中11的作用类似于游戏时的标雷，但是区别在于，玩家标出的雷可能是错误的，而算法的判断一定是正确的。这两种情况都用同一个数字表示。通俗地讲，因为算法需要保证百分百的正确性，所以玩家标出来的雷，算法一个也不相信，这意味着这两种含义不可能同时出现。
“真实局面”或“局面”
- 变量名为board: Vec<Vec>
- 值的含义
  - 0代表空
  - 1到8代表数字1到8
  - -1代表雷
游戏局面和局面的区别
- 游戏局面是游戏时玩家看见的局面，随鼠标的点击操作而变化。
- 真实局面是可以看见雷的实际局面，不会随操作而变化。
“矩阵” 判雷的本质是求解带有0-1约束的非齐次线性欠定方程组。在线性代数方程Ax=b中：
- 矩阵A的变量名为matrix_a，代表系数矩阵
- 矩阵x的变量名为matrix_x，代表未知量矩阵
- 矩阵b的变量名为matrix_b，代表常数矩阵
- 变量后加上s代表分段；加上ses代表分块且分段
“分块” 计算概率时，假如把整个局面全列成一个方程式，那么，方程中的变量数等于空的边缘的格子数。一般数目较大不易求解，需要使用分块技巧来加速。直观地看，游戏局面中，贯通上下两边的空可以把游戏局面分成两块；复杂的空可以把游戏局面分割成更多块。因此计算概率时，可以独立讨论被空分割成的若干块的情况（即系数矩阵可以分块），最后汇总计算出最终结果。
“分段” 仅仅分块还是不够，一些块的边缘仍然很长。但是在块的边缘，未知格往往是两两相邻的（而不是多个未知格互相相邻，即无向图的割点很多），而且其中部分未知格往往是可以简单求出的。只要求出这些未知格并代入原方程，就可以把大方程分割成小方程（即系数矩阵为分块对角矩阵），从而加速求解。

§函数签名说明

Rust是一门强类型的语言，其函数签名反映了诸多信息。以下为不熟悉本语言的开发人员提供简要的说明。

变量名+冒号+格式：表明参数的格式。例如i32代表有符号4字节的整数、u8代表无符号1字节的整数；Vec<>代表内存分配在堆上的可变长度的向量。
mut：代表这个参数是可变的。例如pub fn mark_board(board: &mut Vec<Vec<i32>>)中，会对传入的局面直接修改。如果不带mut，则不会修改。

§API命名原则

约定如下原则：

原则1：为方便开发人员使用，本工具箱在所有平台所有的api都是相同的。
原则2：所有平台的版本号原则上相同，如果不相同，代表还未更新到。
原则3：结构体和类名均使用大驼峰命名法（CamelCase）、方法名和函数名均使用蛇形命名法（snake_case亦称下划线命名法）。

§项目背景

ms_toollib工具箱的设计绝不是纸上谈兵，是由元扫雷（亦称黑猫扫雷）项目的算法部分拆分而来，算法经过实际使用验证，具有深厚的项目背景。

§安全性

本工具箱不直接提供机扫（机器扫雷）相关工具；同时，不提倡纯粹机扫相关的研究，尤其不提倡那些通过机扫模拟人类扫雷的研究；使用机扫的录像攻击排名网站的审查体系是严格禁止的，任何相关尝试都是不道德的！

Re-exports§

pub use videos::valid_time_period;
pub use videos::AvfVideo;
pub use videos::BaseVideo;
pub use videos::EvfVideo;
pub use videos::GameBoardState;
pub use videos::MinesweeperBoard;
pub use videos::MouseState;
pub use videos::MvfVideo;
pub use videos::RmvVideo;

Modules§

videos

Structs§

Board: 静态局面的包装类。
GameBoard: 静态游戏局面的包装类。
所有计算过的属性都会保存在这里。缓存计算结果的局面。
ImageBoard: 局面光学分割引擎。
SafeBoard: 安全局面
SafeBoardRow: 安全局面的行

Functions§

OBR_board: 光学局面识别引擎。
cal_all_solution: 枚举法求解矩阵，返回所有的解
cal_bbbv: 计算局面的3BV
cal_board_numbers: 算数字。局面上只有0和-1时，计算其他的数字。不具备幂等性！！！
cal_cell_nums: 计算每个数字出现的次数
cal_isl: 输入局面，计算岛
cal_op: 输入局面，计算空，即0的8连通域数
cal_probability: 游戏局面概率计算引擎。
cal_probability_cells_is_op: 计算开空概率算法。
cal_probability_onboard: 计算局面中各位置是雷的概率，按照所在的位置返回。输入：局面，总雷数
cal_table_minenum_recursion
combine
get_all_not_and_is_mine_on_board: 求出游戏局面中所有非雷、是雷的位置。
get_random_int
is_able_to_solve: 判断是否为判雷；对应强无猜规则。
is_good_chording: 是局部最好的双击返回真，否则为假。方法是向四周试探一个位置，好的双击应该不能打开更多的格子。
is_guess_while_needless: 判断是否为可能可以（区别于必然可以）判雷时的猜雷；对应弱无猜、准无猜规则。
is_solvable: 从指定位置开始扫，判断局面是否无猜。
laymine: 通用标准埋雷引擎。
laymine_op: 通用win7规则埋雷引擎。
laymine_solvable: 删选法单线程无猜埋雷。不可以生成任意雷密度的无猜局面。但雷满足均匀分布。
laymine_solvable_adjust: 调整法无猜埋雷。可以生成任意雷密度的无猜局面。但雷不满足均匀分布。
laymine_solvable_thread: 删选法多（8）线程无猜埋雷。对于雷密度很高的局面，多线程比单线程更快。
mark_board: 对局面用单集合、双集合判雷引擎，快速标雷、标非雷，以供概率计算引擎处理。这是非常重要的加速。
相当于一种预处理，即先标出容易计算的。mark可能因为无解而报错，此时返回错误码。
若不合法，直接中断，不继续标记。
输入：游戏局面、是否全部重新标记（用户的游戏局面需要全部重标，或者需要统计数量）
返回：成功为标记的非雷数、是雷数；失败为错误代码
obr_board: 光学局面识别引擎。
refresh_board: 依据左击位置刷新局面。如踩雷，标上或14、15标记
refresh_matrix: 根据游戏局面生成矩阵，不分块。输入必须保证是合法的游戏局面。
refresh_matrixs: 根据游戏局面生成矩阵，分段。输入的必须保证是合法的游戏局面。返回：系数矩阵、变量矩阵、常数向量、内部方格、标出的雷数
refresh_matrixses: 根据游戏局面生成矩阵，分段、且分块。输入的必须保证是合法的游戏局面。
sample_3BVs_exp: 埋雷并计算高级局面3BV的引擎，用于研究高级3BV的分布。16线程。传入局数，例如1000 000。试一下你的电脑算的有多块吧。
sample_bbbvs_exp: 埋雷并计算高级局面3BV的引擎，用于研究高级3BV的分布。16线程。传入局数，例如1000 000。试一下你的电脑算的有多块吧。
solve_direct: 单集合判雷引擎。
solve_enumerate: 枚举法判雷引擎。
solve_minus: 双集合判雷引擎。
try_solve: 从指定位置开始扫。
unsolvable_structure: 用几种模板，检测实际局面中是否有明显的死猜的结构。

Crate ms_toollibCopy item path