Python使用MINIMAX实现自动吃豆人

阳光穿透心脏的1/2处 2024-04-06 10:08 82阅读 0赞

## 使用MINIMAX实现自动吃豆人 ##

## 一、实现 MINIMAX ##

说白了这题就是要实现 MINIMAX，算法的伪代码如下(借用 PPT 的内容)：

![在这里插入图片描述][1e84f3d4fa894c8dbc5bab6e13ed83e6.png]

图 1 算法伪代码流程 算法的核心在于 MIN 和 MAX 的套娃调用，以及判断退出的条件，这也是我自己在实现的时候遇到的坎。 遇到的问题：

MAX 和 MIN 相互调用的返回值是什么 由于算法本身只是计算每一层树的最佳状态，因此只需要进行值的传递就可以了，但在处理这个问题的时候，由于想着需要在得到最佳值的同时，也要得到最佳的行动 (action)，因此我就在每次递归的时候以(value,action)的形式进行值的返回，但这样就导致递归的过程中值会变成这种形式：(((value,action) ,action) ,action),这样就会一来在求 max 和 min 的时候出现值比较的问题，二来在扒开括号的时候也会出现问题，因此在思考这种数据结构的时候想了很长时间。后来发现伪代码中还有 MINIMAX-DECISION 这个函数是专门处理我的这个疑惑的，也就是只在最外面一层返回 action，在下面别的层只需要返回值就可以了。

递归深度

![在这里插入图片描述][3b14b1372dc342b6b00c933fd86dacdb.png]

在运行测试的时候发现自己递归的深度并没有达到预期深度，因此在这上面也花费了一些时间来思索。

空节点的情况

当吃豆人四周都被包围住的时候，那么能够走得 action 列表就是空，因此需要对这种情况进行特殊处理，即直接

返回该状态的值。 图 2 递归深度不够

## 二、结果展示 ##

![在这里插入图片描述][0402e425df5a459ab95f6beb5eb1025a.png]

图 3 运行 python autograder.py -q q2 --no-graphics 的结果展示

最终吃豆人还是死了 hhh，不过和同学交流后发现都死了，并且得到的分数都是 84 分，因此应该可以说明是一个普遍性的情况（毕竟原文也说了可能会死）。

[1e84f3d4fa894c8dbc5bab6e13ed83e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/50a45850c2574bffaa29b71b48c4e88c.png
[3b14b1372dc342b6b00c933fd86dacdb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/547865d7bf4c420dac51095af82ac2e4.png
[0402e425df5a459ab95f6beb5eb1025a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/1b02d12c046644ff96612f8765b943a5.png