主页 > 生活

会玩游戏的AI(3)强化学习简单的例子

时间:2019-08-10 来源:袁园是先生

在《会玩游戏的AI(2)什么是强化学习》一文中,以原始人在闽北丛林寻找食物为例,介绍了强化学习的基本思想。文中以4*4的迷宫方式呈现寻找食物的示意图。原始人在每个格子(state)中,至少都有3种动作可供选择(迷宫的四个角上的格子)。

为了简化游戏环境,我把二维的迷宫改成一维的:

锥粟树与原始人在同一直线上,原始人只能沿这条线行走。如下图所示,O为原始人,T是锥粟树————为四个不同的路段。图中,O所处的state0T所在位置的state5,两者之间依次是1,2,3,4

O— — — —T

原始人O动作的可选项只有两种:向左或向右(不考虑“静止不动”这一动作选项)。

在这个一维世界,原始人通过强化学习的方式,寻找通过锥粟的方法。

前文中,强化学习的算法伪代码如下:

初始化 Q = {};

while Q 未收敛:

  初始化原始人的位置S,开始新一轮游戏

 while S != 找到锥粟树

    使用策略π,获得动作a=π(S) #策略可用婪心算法

    使用动作a进行游戏,获得原始人的新位置S',与奖励R(S,a)

    Q[S,A] (1-α)*Q[S,A] + α*(R(S,a) + γ* max Q[S',a]) // 更新Q

    S S'#更新位置

 

根据伪代码,我们逐步呈现原始人寻找锥粟树的过程:

生成一个Q表,因为是初来乍到,情况一点都不了解,所以Q表值为0。表中left,right表示原始人的动作,0~5表示原始人所处的位置。

state left   right

0   0.0    0.0

1   0.0    0.0

2   0.0    0.0

3   0.0    0.0

4   0.0    0.0

5   0.0    0.0

 

Q表没有收敛,要重复~

开始第一轮探索:

原始人的位置S0,即如“O————T”一图所处位置,在Q表中为第0行。

原始人的位置S没有到达state 5(锥粟)位置,须重复~

使用策略婪心算法π,获得动作a。由于原始人根据不了解环境,也就是state 0 left right的值都是0,只能采用随机动作(或左或右):a=right or a=left.

使用动作a进行游戏,获得原始人的新位置S',与奖励R(S,a).第一轮,a总有一次选right,这时,原始人新位置S=state 1,由于没有找到锥粟树,所以reward :R(S,a)=0

用公式 Q[S,A] (1-α)*Q[S,A] + α*(R(S,a) + γ* max Q[S',a]) 更新Q,所有项都是0,值也为0.

 S S'#更新位置.原始人进入state1

根据,每重复~一次,原始人state 增加1或减少1,所对应left rightQ值更新后依旧为0.在我的实验中,原始人在state0~state3之间徘徊了37步。

在第38步时,原始人O进入了T的前一个位置(state4,Q[S,A]=0,max Q[S',a]=0,并选择a=right,获取reward(R=1).公式更新Q:设α=0.1,γ=0.9,代入公式:(1-0.1)*0+0.1*(1+0.9*0)=0.1,Q表中state4right的值0更为0.1

第一轮结束.第一轮结束后的Q表:

State left  right

0   0.0    0.0

1   0.0    0.0

2   0.0    0.0

3   0.0    0.0

4   0.0    0.1

5   0.0    0.0

 

进入第二轮,重~:

开始第二轮探索,原始人的位置S0

原始人的位置S没有到达state 5(锥粟)位置,重复~

使用策略婪心算法π,获得动作a。由于Q表的state0~3值都为0,这些阶段原始人只能采用随机动作(或左或右):a=right or a=left.

在经过多次(我实验是20次)探索后,原始人到达位置state3state3,Q[S,A]=0,max Q[S',a]=0.1,并选择a=right,reward(R=0).公式 Q[S,A] (1-α)*Q[S,A] + α*(R(S,a) + γ* max Q[S',a])更新Q:把α=0.1,γ=0.9,代入公式:(1-0.1)*0+0.1*(0+0.9*0.1)=0.009,Q表中state3right的值0更为0.009

原始人进入state4Q[S,A]=0.1,max Q[S',a]=0,重复~:用贪心算法,取state4Q[s,a]中大值采取动作(a=right)R=1;公式更新state4Q[s,a]值:(1-0.1)*0.1+0.1*(1+0.9*0)=0.09+0.1=0.19,Q表中state4right的值0.1更为0.19

第二轮结束.第二轮结束后的Q表:

 left  right

0   0.0  0.000

1   0.0  0.000

2   0.0  0.000

3   0.0  0.009

4   0.0  0.190

5   0.0  0.000

根据上述方法,逐轮更新Q表,在第五轮后,Q表如下:

      left     right

0  0.00000  0.000007

1  0.00000  0.000572

2  0.00003  0.006934

3  0.00000  0.073314

4  0.00000  0.409510

5  0.00000  0.000000

Q表中可以看出,每一个StateQ(s,a)值都是right>left,对应的动作是right.因此,原始人只要一直右走,就能找到锥粟树。


相关阅读