玩家每找到一块奶酪得到一分，每次掉进凹坑时减去一分。基本前提是，通过奖励或惩罚，根据先前的经验教算法作出某些行动。q-learning算法的工作原理是通过保存一个所有可能状态的和这些状态下玩家所有可能采取的行动的表。这意味着，为了优化AI可以获得的总奖励，对于一个特定的状态，从表中选择能获得最大潜在奖励的动作。这是必要的，因为q-learning算法需要参考游戏分数来更新Q表。首先，暂停0.05秒，使我们能够为AI玩家跟随游戏的图形。
给各位拜个年！
本文将教你如何使用q-learning强化学习算法，教计算机掌握简单的电子游戏。我们将从头到尾使用Ruby实现该算法，而不使用外部gems。
为了使我们能够说明算法的内部原理，我们将教它玩一个非常简单的一维游戏。然而，这种算法可以很容易地应用于更复杂的游戏。
游戏
这是一个“捕捉奶酪”控制台游戏，玩家P必须移动以获得奶酪C，且不使奶酪掉进坑O中。玩家每找到一块奶酪得到一分，每次掉进凹坑时减去一分。如果玩家得到5分或-5分，则游戏结束。这个gif展示了游戏过程。
注意为了简化游戏，凹坑O和奶酪的位置总是相同的。
Q-learning算法
Q-learning算法是一种增强学习算法。增强学习算法是受行为心理学启发而产生的一套机器学习算法。基本前提是，通过奖励或惩罚，根据先前的经验教算法作出某些行动。类似于教一只狗坐下，当它表现得好时就奖励它。
q-learning算法的工作原理是通过保存一个所有可能状态的和这些状态下玩家所有可能采取的行动的表。对于每一对的游戏状态S和玩家动作A，表中包含一个数值Q，代表在状态S时采取动作A可能获得的奖励。这意味着，为了优化AI可以获得的总奖励，对于一个特定的状态，从表中选择能获得最大潜在奖励的动作。
从上面来看我们的游戏。根据玩家的位置（记住凹坑和奶酪的位置是静止的），游戏共有12种可能的位置，并且每种状态下玩家可以采取两种行动，向左或向右。
这儿给了我们一个这样的Q表-注意这只是一个例子，现实中的Q表中的值可能会有所不同：
正如你所看到的，Q表表明，当靠近凹坑时，采取向左的行动可能会有一个负的奖励，而靠近奶酪时，向右可能会获得一个正的奖励。
Q表初始化为随机值，这样做是因为AI 还不知道关于游戏的任何信息。为了学习如何玩游戏，我们必须根据经验设计一个更新Q表的算法。
做法如下：
步骤1：用随机值初始化Q表
步骤2：玩游戏时执行以下循环
步骤2.a ：生成0-1之间的随机数-如果数字大于阈值e，则选择随机动作，否则根据状态和Q表选择可能获得最高奖励的动作。
步骤2.b：从步骤2.a开始执行操作
步骤2.c：采取行动后观察奖励r
步骤2.d：使用公式根据奖励r更新Q表
\[ \displaystyle Q(s_{t},a_{t})\leftarrow\underbrace {Q(s_{t},a_{t})} _{\rm {old~value}} \underbrace {\alpha } _{\rm{learning~rate}}\cdot \left(\overbrace {\underbrace {r_{t}} _{\rm{reward}} \underbrace {\gamma } _{\rm {discount~factor}}\cdot \underbrace {\max_{a}Q(s_{t 1},a)} _{\rm {estimate~of~optimal~future~value}}} ^{\rm{learned~value}}-\underbrace {Q(s_{t},a_{t})} _{\rm {old~value}}\right) \]
如你所见，对Q表的更新将使用当前状态和操作的新学习的奖励信息，以及有关未来操作的信息，而无需遍历所有可能的未来操作，只需使用Q表即可。这使得Q学习成为一个相当快的学习算法，但也意味着它在开始阶段确实有一些随机行为，所以没有几次操作后你的AI不可能完美。
实现Q-LearningAI 玩家课程
我们的游戏通常以人类玩家类的一个实例作为玩家对象。人机类的实现如下所示。玩家类实现两个函数，一个构造函数和一个get_input函数。
在游戏循环的每次迭代中调用一次get_input函数，并根据键盘输入返回玩家的方向，如下所示：
require 'io/console'
class Player
attr_accessor
def initialize
@x = 0
end
def get_input
input = STDIN.getch
if input == 'a'
return :left
elsif input == 'd'
return :right
elsif input == 'q'
exit
end
return :nothing
end
end
为了建立一个Q-Learning AI 玩家类，我们将实现一个含有q表的新玩家类，并基于上述算法实现get_input函数。
我们将新类及其构造函数定义如下。注意，我们为这个玩家定义了一个新的属性游戏。这是必要的，因为q-learning算法需要参考游戏分数来更新Q表。此外，在构造函数中，为上面算法中概述的每个学习参数定义属性，并初始化随机生成器。
class QLearningPlayer
attr_accessor :x, :game
def initialize
@x = 0
@actions = [:left, :right]
@first_run = true
@learning_rate = 0.2
@discount = 0.9
@epsilon = 0.9
@r = Random.new
end
接下来，我们定义一个函数来用随机值初始化Q表。状态数是游戏的地图大小，每个状态都只是玩家的位置。
def initialize_q_table
# Initialize q_table states by actions
@q_table = Array.new(@game.map_size){ Array.new(@actions.length) }
# Initialize to random values
@game.map_size.times do |s|
@actions.length.times do |a|
@q_table[s][a] = @r.rand
end
end
end
最后，我们实现了如下的get_input函数。首先，暂停0.05秒，使我们能够为AI玩家跟随游戏的图形。
接下来，我们检查这是否是第一次运行，如果是这样，我们对Q表进行初始化（步骤1）。
如果这不是第一次运行，我们将评估自上次请求输入以来在游戏中发生的事情，以确定Q学习算法的奖励r。如果游戏分数增加，将奖励设为1，如果分数减少，我们将奖励设为-1，如果分数没有改变，奖励为0（步骤2.c）。
然后，将结果状态设置为游戏的当前状态（在例子中是玩家的位置），并按照方程式（步骤2.d）更新Q表：
def get_input
# Pause to make sure humans can follow along
sleep 0.05
if @first_run
# If this is first run initialize the Q-table
initialize_q_table
@first_run = false
else
# If this is not the first run
# Evaluate what happened on last action and update Q table
# Calculate reward
r = 0 # default is 0
if @old_score < @game.score
r = 1 # reward is 1 if our score increased
elsif @old_score > @game.score
r = -1 # reward is -1 if our score decreased
end
# Our new state is equal to the player position
@outcome_state = @x
@q_table[@old_state][@action_taken_index] = @q_table[@old_state][@action_taken_index]@learning_rate * (r@discount * @q_table[@outcome_state].max - @q_table[@old_state][@action_taken_index])
end
根据上一步更新Q表之后，我们现在将以前的分数和状态用于下一次运行。
然后，我们根据epsilon e（步骤2.a）随机或基于q表选择一个新操作，并返回该操作（步骤2.b）。
# Capture current state and score
@old_score = @game.score
@old_state = @x
# Chose action based on Q value estimates for state
if @r.rand > @epsilon
# Select random action
@action_taken_index = @r.rand(@actions.length).round
else
# Select based on Q table
s = @x
@action_taken_index = @q_table[s].each_with_index.max[1]
end
# Take action
return @actions[@action_taken_index]
这就完成了Q-learning算法的实现。
运行算法
有了我们的Q_learning 玩家，我们就可以运行游戏，让我们的游戏运行10个回合。
正如你所看到的，在第一回合中，玩家尝试了各种不同的事情，毫无目标的前进或后退。这是由于Q表的随机初始化造成的。然而，一旦玩家得到了几分，掉入了凹坑中，它很快就会学会避开凹坑，径直地走向奶酪。
在第7次和第8次运行中，AI玩家非常接近完美的解决方案，即在35个动作中直接进入奶酪。然而，在第9和第10个回合中，要赢得比赛需要39步。这是由于epsilon因子e的缘故，它有时会导致算法进行随机移动，而不是最佳移动。这种随机性是确保算法能够正确地探索整个游戏，并且是不会陷入局部最优状态的必要条件。
下一步…
这篇文章展示了如何应用Q-learning来教AI玩一个简单的游戏。正如你所能想象的，随着游戏复杂性的增加，Q表的大小会爆炸。避免这种情况的一种方法是用神经网络代替Q表。
DeepMind Technologies的研究人员在论文 Playing Atari with Deep Reinforcement Learning （https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf）中探索了这个方法。
本文成功地用神经网络Q表训练了Q-learning，使其能够玩Space Invaders,Pong，Q*bert和其它Atari 2600游戏。
