# 人工智能期末项目
# 一、实验内容
## 1.1 算法原理
### 1.1.1 Epsilon-greedy算法
Epsilon-greedy算法是在“exploit”(利用)和“explore”(探索)之间权衡以尽可能实现收益的最大化。假设当前有n台老虎机,每台老虎机吐钱的概率不一样,也不清楚每台老虎机吐钱的概率分布,如何实现收益最大化呢?通常有两种方案,第一种就是在已经探索过的老虎机中找到吐钱最多的那台老虎机,然后坚持摇它,这就是“exploit”(利用);第二种就是尝试不断探索新的老虎机,在探索过程中可能会找到更好的老虎机,也可能找到吐钱很少的老虎机,这就是“explore”(探索)。Epsilon-greedy算法是每次以epsilon概率进行“explore”(探索),也就是说在所有的老虎机中选择一个进行探索;每次以1 – epsilon概率进行“exploit”(利用),也就是在已经探索过的老虎机中选择收益最大的那个。
Epsilon设置的越高,收敛到最佳收益的速度越快,因为随机搜索的概率越大,越能更快地探索到最好的老虎机。当0.1 < Epsilon < 0.5时,Epsilon设置的越低,最终的平均收益越高,因为每次以较大概率随机探索,将不能有效利用收益最大的老虎机。
### 1.1.2 Q-learning

### 1.1.3 Sarsa

### 1.1.4 遗传算法(队友实现)
队友使用的是遗传算法,我并未参与实现,所以在此只介绍相关原理。

## 1.2 流程图
### 1.2.1 Q-learning

### 1.2.2 Sarsa

## 1.3 关键代码
### 1.3.1 Q-learning
Q-learning在黑白棋中的应用中,每个不同的状态S表示每个不同的棋局,动作a表示下一步下子的位置,动作集A表示可下子位置的集合,状态S的即时回报R表示S所对应棋局的估计值。Q-learning在黑白棋中的步骤为:

```c++
void Q_learning(char board[8][8], char color, void(*function)(char board[8][8], char)) {
char opp = color == '@' ? 'O' : '@';
double alpha = 0.8, gama = 0.5;
state pre = state(board);
default_random_engine e;
uniform_real_distribution<double> u(0.0, 1.0);
double epsilon = u(e);
auto next_step = show_places(board, color);
// 根据Epsilon-greedy算法选择动作
if (1 - epsilon < 0.5) {
// 以1 – epsilon概率进行“exploit”(利用),在已经探索过的动作中选择收益最大的
double best_value = -10000000;
pre.action = next_step[0];
for (int i = 0; i < next_step.size(); ++i) {
auto index = state(pre.board, next_step[i]);
if (Q.find(index) == Q.end())
continue;
else if (Q[index] > best_value) {
best_value = Q[index];
pre.action = next_step[i];
}}}
else
// 以epsilon概率进行“explore”(探索),在所有的动作种随机选择一个
pre.action = next_step[rand() % next_step.size()];
//进入循环
while (!is_over(board)) {
// 执行选好的动作
move(board, pre.action, color);
if (!show_places(board, opp).empty() && !show_places(board, opp).empty())
function(board, opp);
while (!is_over(board) && show_places(board, color).empty())
function(board, opp);
// 得到下一个状态
state S = state(board);
// 得到下一个状态的即时回报
double reward = evaluate(board, color);
next_step = show_places(board, color);
// 在下一个状态下找到具有最大Q值的动作
if (!next_step.empty()) {
double best_value = -10000000;
S.action = next_step[0];
for (int i = 0; i < next_step.size(); ++i) {
auto index = state(board, next_step[i]);
if (Q.find(index) == Q.end())
continue;
else if (Q[index] > best_value) {
best_value = Q[index];
S.action = next_step[i];
}}}
double new_q = 0, old_q = 0;
if (Q.find(pre) != Q.end())
old_q = Q[pre];
if (Q.find(S) != Q.end())
new_q = Q[S];
// 更新表Q
Q[pre] = old_q + alpha * (reward + gama * new_q - old_q);
// 以epsilon概率进行“explore”(探索)
epsilon = u(e);
if (!next_step.empty() && epsilon < 0.5)
S.action = next_step[rand() % next_step.size()];
pre = S;}}
```
### 1.3.2 Sarsa
Sarsa在黑白棋的应用中,状态S、动作a、动作集A、即时回报R所表示的意义与Q-learning在黑白棋的应用中的相同,Sarsa在在黑白棋中的步骤为:

```c++
void Sarsa(char board[8][8], char color, void (* function)(char board[8][8], char)) {
char opp = color == '@' ? 'O' : '@';
double alpha = 0.8, gama = 0.5;
state pre = state(board);
default_random_engine e;
uniform_real_distribution<double> u(0.0, 1.0);
double epsilon = u(e);
auto next_step = show_places(board, color);
// 根据Epsilon-greedy算法选择动作
if (1 - epsilon < 0.5) {
// 以1 – epsilon概率进行“exploit”(利用),在已经探索过的动作中选择收益最大的
double best_value = -10000000;
pre.action = next_step[0];
for (int i = 0; i < next_step.size(); ++i) {
auto index = state(pre.board, next_step[i]);
if (Sarsa_Q.find(index) == Sarsa_Q.end())
continue;
else if (Sarsa_Q[index] > best_value) {
best_value = Sarsa_Q[index];
pre.action = next_step[i];
}}}
else
// 以epsilon概率进行“explore”(探索),在所有的动作种随机选择一个
pre.action = next_step[rand() % next_step.size()];
// 进入循环
while (!is_over(board)) {
// 执行已选好的动作
move(board, pre.action, color);
if (!show_places(board, opp).empty() && !show_places(board, opp).empty())
function(board, opp);
while (!is_over(board) && show_places(board, color).empty())
function(board, opp);
// 得到下一个状态
state S = state(board);
// 得到下一个状态的即时回报
double reward = evaluate(board, color);
epsilon = u(e);
next_step = show_places(board, color);
// 根据Epsilon-greedy算法选择动作
if (!next_step.empty())
if (1 - epsilon < 0.5) {
// 以1 – epsilon概率进行“exploit”(利用)
double best_value = -10000000;
S.action = next_step[0];
for (int i = 0; i < next_step.size(); ++i) {
auto index = state(board, next_step[i]);
if (Sarsa_Q.find(index) == Sarsa_Q.end())
continue;
else if (Sarsa_Q[index] > best_value) {

神仙别闹
- 粉丝: 4946
- 资源: 7621
最新资源
- 采用springboot框架的基于BS的老年人体检管理系统的设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
- 采用springboot框架的基于JAVA的房地产销售管理系统的设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
- myBuilder渐进式低代码IDE-v2.5.20.18
- 基于springboot框架的教学资料管理系统的设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
- 基于springboot框架的校园疫情防控系统的设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
- 基于springboot框架的校园外卖服务系统设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
- iNodeManager-H3C-MacOS 7.3 E0598 下载,使用多个系统,macos 适配m2系列
- 无需PLC,施耐德ATV312变频器通讯实现触摸屏控制监控:功能多、成本节约,详解示例,施耐德ATV312变频器触摸屏双机通讯与功能控制说明(跳过PLC,实现低成本高效率监控),svg无功补偿电力电子
- FounderFontPlus.Update.exe
- 采用springboot框架的基于javaweb的学生用品采购系统的设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
- 无需PLC,施耐德ATV312变频器通讯实现触摸屏控制监控:功能多、成本节约,详解示例,mcgs RTU通讯实现施耐德ATV312变频器双机监控与操作示例-无PLC,功能丰富且成本优化,LLC谐振变
- 施耐德变频器与触摸屏实现直接通讯监控实践示例-两变频器双效控制与状态实时监控(不使用PLC的节约方案),使用MCGS RTU方式实现触摸屏控制施耐德ATV312变频器的示例与详解,西门子S7-200
- dify 面试总结工作流 DSL文件
- 基于SpringBoot的“企业档案管理信息系统”的设计与实现(源码+数据库+文档+PPT).zip
- VB.NET中常用字符串操作函数详解及其应用场景
- 采用springboot框架的基于java的火车票订票系统的设计与实现(Java项目编程实战+完整源码+毕设文档+sql文件+学习练手好项目).zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈


