[数据结构与算法]强化学习—动态规划—21点游戏

?游戏规则：

游戏里一个玩家（player）和一个庄家（dealer）。每个回合结果可能是玩家获胜，庄家获胜，或者平手。回合开始时，玩家和庄家各有两张牌，玩家可以看到玩家的两张牌和庄家的一张牌，接着玩家可以选择是不是要更多地牌，如果要更多的牌，称为（hit），玩家可以再得到一张牌，并统计玩家手里的所有牌点数之和，其中A代表1或者11点，如果点数和大于21，则玩家输掉这一回合，庄家获胜；如果小于等于二十一，玩家可以决定是否要更多的牌，直到玩家不再要更多的牌。如果玩家在总点数小于等于21的情况下，不再要更多的牌那么其手中总点数就是最终玩家的点数。接下来庄家展示其没有显示的那张牌，并且在其点数小于17的情况下抽取更多的牌，如果庄家的总点数大于21则庄家输掉此回合，玩家获胜，如果最终庄家点数小于等于21，则比较庄家和玩家的点数，大的一方获胜。双方点数相等则平局。

0.思路：

环境部分用gym库的"Blackjack-v0"

用动态规划算法的策略迭代。

1.模拟环境并用随机策略进行游戏

import gym
import numpy as np
import matplotlib.pyplot as plt

env=gym.make("Blackjack-v0")
observation=env.reset()
print("观测={}".format(observation))
while True:
    print("玩家={}，庄家={}，".format(env.player,env.dealer))
    action = np.random.choice(env.action_space.n)
    print("动作={}".format(action))
    observation,reward,done,_=env.step(action)
    print("观测={}，奖励={}，结束指示={}".format(observation,reward,done))
    if done:
        break

2.带起始搜索的同策回合更新。

??????? 回合更新策略基本思路是用蒙特卡洛方法估计动作价值函数。这个期望可以由多次实验的最终回报估计得到，当实验册数越多，越接近于其真实值。

        while True:
            state_action.append((state,action))
            observation,reward,done,_=env.step(action)
            if done:
                break
            state=ob2state(observation)
            action=np.random.choice(env.action_space.n,p=policy[state])
        g=reward
        for state,action in state_action:
            c[state][action]+=1
            q[state][action]+=(g-q[state][action]/c[state][action])
            a=q[state].argmax()
            policy[state]=0.
            policy[state][a]=1
    return policy,q

?如此，可以得到最优策略

参考书目：

肖智清 《强化学习原理与python实现》