121 lines
4.8 KiB
Markdown
121 lines
4.8 KiB
Markdown
## AlphaP(ac)
|
||
|
||
Pacman 是一款诞生于 1980 年的经典街机游戏，由南梦宫制作并在日本发行。游戏目标很简单：控制主角吃豆人吃掉迷宫里所有的豆子，同时避开鬼魂的追捕。
|
||
|
||
自问世以来，这款游戏收获了无数玩家的喜爱，YuiCtwo 也是其中之一。
|
||
|
||
正巧 YuiCtwo 在日常工作中遇到了一些类似的问题，于是以 Pacman 为背景来研究这些问题再合适不过了。你需要由浅入深地完成下面的一系列任务，逐步解决一个**真正的算法问题**。
|
||
|
||
|
||
### Task 0: Let's build a Pacman
|
||
|
||
在开始那些“高大上”的算法之前，脏活累活总是第一步：你需要先搭建好游戏的“基础能力”。
|
||
|
||
关于 Pacman 的系统介绍，可以参考 [维基百科](https://zh.wikipedia.org/wiki/%E5%90%83%E8%B1%86%E4%BA%BA)；网上也有大量实现，随便挑一个玩上几局就能明白基本规则。
|
||
|
||
|
||
<img src="https://s3.bmp.ovh/2026/09/10/3NHMWPjp.jpg" alt="经典吃豆人游戏的画面" style="zoom:50%" />
|
||
|
||
在这个任务中，你需要实现一个 Pacman 游戏。但并非完全自由发挥，以下是基本要求：
|
||
|
||
- 禁止使用 Unity、Pygame 等现代游戏框架，推荐使用 Tkinter、ImGui 等纯图形界面库，引擎部分需要自己实现。
|
||
- 不强制要求 UI 要素 1:1 复刻原作，但你实现中的一些细节会影响本题的得分。
|
||
- 除了完成度，整体的设计质量也会纳入评分。
|
||
- **地图输入采用 `.lay` 文件格式**，程序需要能够读取并解析该格式，加载不同的关卡布局。`.lay` 文件使用字符网格描述地图，例如：
|
||
|
||
```text
|
||
%%%%%%%%%%%%%%%%%%%%
|
||
%......%G G%......%
|
||
%.%%...%% %%...%%.%
|
||
%.%..............%.%
|
||
%.%.%%.%%%%%%%%.%.%
|
||
%......%....%......%
|
||
%%%.%%.%. .%.%%.%%%
|
||
% ...%.% %.%... %
|
||
% .%%%.% %.%%%. %
|
||
%......%....%......%
|
||
%.%%.%%.%%%.%%.%%.%
|
||
%..........P.......%
|
||
%%%%%%%%%%%%%%%%%%%%
|
||
```
|
||
|
||
其中常见字符含义如下：
|
||
- `%`：墙壁
|
||
- `.`：普通豆子
|
||
- `o`：能量豆
|
||
- `P`：Pacman 起始位置
|
||
- `G`：鬼魂起始位置
|
||
- ` `：空白通道
|
||
|
||
|
||
### Task 1: 热身
|
||
|
||
我相信完成 Pacman 游戏后，你已经对后面的任务跃跃欲试了。Pacman 的核心目标是尽可能拿高分，同时躲避鬼魂——聪明的你应该已经隐约感觉到，这并不是一个简单的问题。在深入解决之前，不妨先热热身：
|
||
|
||
**假设没有鬼魂追赶玩家，如何在尽可能短的时间内吃完所有的豆子？**（其实也并不简单。）
|
||
|
||
本题要求：
|
||
|
||
- 给出一种能够吃完所有豆子的方法，不要求一定最优。得分只取决于能否在多个场景下都成功吃完所有豆子，并且不崩溃。
|
||
- 你需要能够借助 Task 0 中完成的系统进行演示。
|
||
|
||
|
||
### Task 2: "标准"答案
|
||
|
||
作为一个经典问题，自然有一些较为标准的解法。吃豆人规则简单、状态空间清晰，非常适合用强化学习来求解。
|
||
|
||
本题要求：
|
||
|
||
- 使用强化学习解决“在鬼魂追赶的情况下获得最高分”的问题。
|
||
- 尝试不同的强化学习模型，以及不同的鬼魂 AI。
|
||
- 不需要使用最前沿的强化学习模型，能够稳定解决问题即可。
|
||
|
||
你的最终结果要有类似的效果:
|
||
|
||
|
||
|
||
|
||
## 提交说明
|
||
|
||
推荐使用 Python 完成。
|
||
|
||
本题目不要求全部完成，量力而行即可。如果觉得国庆题目太简单，不妨挑战一下，~~说不定就搞定了呢~~。国庆结束后如需提交本题，向学长演示你的结果即可。
|
||
|
||
如果 Task0,1,2 都完成了，那么推荐你思考下下面这个问题：
|
||
|
||
### Task 3: 自省
|
||
|
||
我们解决了吃豆人这个问题，但这还远远不够。请思考下面这些问题：
|
||
|
||
在游戏层面：
|
||
|
||
- 如果改为玩家控制鬼魂移动呢？
|
||
- 如果加入时间限制呢？
|
||
|
||
在 AI 层面：
|
||
|
||
- 目前 Pacman 的信息直接作为变量传入，对 AI 来说完全可知。但在大多数真实游戏中，你无法获取如此详细的内部信息，如何借助视觉、内存或其他方式获取信息？
|
||
- 对于耗时较高的模型，如何让 AI 的执行与游戏运行、玩家操作并行？
|
||
- 我想用 LLM 来玩这款游戏。
|
||
- ……
|
||
|
||
考虑这些问题，尽可能借助现代游戏引擎和强化学习架构的设计模式，重新设计整个项目。至少在架构层面，让它看起来专业且成熟。
|
||
|
||
本题为开放性问题，给出你的新设计以及对应的代码即可。
|
||
|
||
|
||
## 参考资料
|
||
|
||
- [UC-Berkeley-AI-Pacman-Project](https://github.com/karlapalem/UC-Berkeley-AI-Pacman-Project)
|
||
- [PacmanDQN](https://github.com/tychovdo/PacmanDQN)
|
||
|
||
|
||
## 关于 AI
|
||
|
||
**不限制使用 AI，也不会进行 AI 查重。**，但会针对一些问题进行询问，视具体情况打分。
|
||
|
||
## 其他
|
||
|
||
最终解释权归 YuiCtwo 所有。
|
||
当前题目版本 V0.1
|