游戏AI--决策（1）_决策类游戏ai公式

机器学习的引入

机器学习最近由于AlphaGo和数据挖掘的大热而变得流行起来，然而我们可以让它变得更加cool，在接下来的模块中，我将讲述我对游戏中应用机器学习的理解以及我的现有成果。

应用机器学习的意义

游戏进行中，尤其是网络游戏，会积累大量的数据，数据赋予了计算机行为意识，而我们如果能“告诉”计算机数据归纳总结的方法，那计算机可能会产生惊人的思维能力，而机器学习就是这样的一种神奇的工具。

前景

目前的游戏由于同质化严重，所以一个高度智能的游戏体验会带给玩家难以想象的快感，而且笔者以为，很有可能在某一天，我们能在游戏中建立真正的人工智能，因为游戏世界高度抽象化，数据的提取难度大大降低，当然，这有点跑题了。

应用机器学习的决策逻辑

游戏的进行，决策和事件无疑是最重要的两个条件，传统的游戏中，我们使用大量的条件判断来进行决策，不仅在逻辑上很繁琐，而且有一个重大的问题，它是“死的”，比如玩家经过一个怪物，怪物必定会攻击玩家，如果要改善这一决策，那需要添加许多条件，比如针对怪物的“攻击性”，重写判断逻辑。
机器学习则不然，我们可以根据以前的记录进行训练，每个怪物都是独特的，即使他们隶属于同一个类，“个性”将使AI十分丰富。

目标–鱼类的遗传

由于机器学习的数学模型非常复杂（对笔者来说是这样的，花了很多功夫才看懂），我们先讲一个应用，然后我们根据其需求来应用机器学习。

在之前的游戏底层逻辑中，笔者曾说过想要实现一款海洋模拟的游戏，之前的只言片语可能已经能描述大概的框架了，不知道也没关系，此处我们有一个问题：捕食行为
捕食行为基本上是动物最重要的行为了，此处有三个需要决策的问题，在进入捕食状态前的判断中，我们需要知道：
1、是否需要捕食
2、捕食什么鱼类（前提是在食物链上的）
3、哪个地方适合捕食

是否捕食

在传统游戏中，设定一个饥饿值，这个值随着时间递减，减少到一定程度就去捕食。
而这种状态是不合理的：

• 首先，我们吃东西并不一定是饥饿，其他的因素都有可能使其变化。
• 其次，这种if(1)else(0)的变化在空间上表现出来的是跳跃性的曲线，不符合我们越饥饿越想吃东西这样的特性。
• 然后，我们的决策没有随机性，很容易预测，很“无聊”。

解决方案

我们设定一个合理的初始函数：

$$H(x)=x{1}*\theta{1}+ x{2}*\theta{2}+...+x{n}*\theta{n}$$
矩阵（向量）表达：
$$H(x)=X^{T}\theta$$
其实就是多元一次方程，H函数得到一个值，然后我们根据值进行决策。

此处提及几个概念:
$\theta$我们称其为权值，意思是该变量对决策产生影响的重要程度。
$x$此处称为特性。

根据此函数，我们输入一系列x，就能得出决策结果。然后你们可能发现了一个问题，$\theta$怎么解决，我们先根据经验定义一个值，然后进行训练，最终得出一个权值。

遗传

所谓遗传是怎么一回事呢，此处我们每个鱼类种群共享一个H函数，鱼在生产下一代的时候，将完全继承（clone）或者部分继承（block copy）该函数，此处我们降维处理，将其直接复制。在这种机制下，拥有好的H函数的鱼群将存活下来，并且繁衍生息，而拥有差的H函数的鱼群就被淘汰了。

针对H函数进行训练，LogisticRegression

此处不会讲解关于机器学习的基本知识，太多而且笔者水平有限，讲解不清楚。
下面的模块讲解LogisticRegression（以下简称LR）的基本理解，如果不感兴趣可以跳过直接看公式。

我们已经知道了H函数，此处称为数学模型。

$$H(x)=x{1}*\theta{1}+ x{2}*\theta{2}+...+x{n}*\theta{n}$$
现在我们有很多的已知的数据：

x1	x2	x3	H(x)，或者叫做y
1	2	3	4
2	3	4	5

诸如此类的，此处的数据最好是数值型，如果是标称型（ex.颜色：红，黄，蓝），有比较复杂的转换过程，推荐使用其他的学习算法诸如树回归一类的。
误差函数：H函数根据我们现在已知的权值会得出一个结果，但是它和上表中的H(x)是不同的，我们把现在的权值代入每一组数据求结果，然后用真实结果（表中的H(x)，用y表示）做差，这就是误差函数。

$$J(\theta)=\frac{1}{2}\sum_{i=0}^n （H(x{i})-y{i})^2$$

梯度下降
此处我们要克服误差，所以要沿着误差函数变化最快的方向改善我们的$\theta$，该方向叫做梯度方向，二维数学表达式为：

$$\nabla{f(x,y)}=(\frac{\partial{f(x,y)}}{\partial{x}},\frac{\partial{f(x,y)}}{\partial{y}})$$
多维时相同，也就是对误差函数求偏导。
结果如下：

$$\sum_{i=0}^n(y{i}-H(xi))*xi$$
随机梯度下降
为了减少计算复杂度，此处我们使用 随机梯度下降，将误差函数的比较范围由整个数据集合变为其中一次（此处直接为新添加的一次）：

$$(y{i}-H(xi))*xi$$
然后我们的沿着这个方向一点点的改善,的到训练的迭代公式：

好了，公式就是这个，以上是推导过程：

$$\theta:=\theta-\alpha\nabla{f(x^T)}$$

LR代码部分：

首先引入c++矩阵库：Eigen，这个库一般般，用起来不是很顺手，由于字符对齐问题，用VS编译的同学，该库的矩阵类型请自行使用引用&。

#pragma once

#include<Eigen/Dense>
#include"cocos2d.h"
#include<vector>
using namespace Eigen;

template<class ElementType, int ElementNum>
class LogisticRegression//the number of sample elements is best less than 16 
{
public:
    LogisticRegression(std::string owner)
    {
        assert(ElementNum < 16 &&
            "TOO LONG!!!!");
        this->getDataFromFile();
        _owner = owner;
    }
    ~LogisticRegression()  {}

    virtual bool initWithData(Matrix<ElementType, ElementNum, 1 >& weightMatrix,double pace)
    {
        _pace = pace;
        try
        {
            _weightMatrix = weightMatrix;
        }
        catch (ElementType)
        {
            return false;
        }
        return true;
    }
public:

    virtual bool getDataFromFile()
    {
        for (int i = 0; i < _weightMatrix.rows(); i++)
        {
            _weightMatrix(i, 0) = (ElementType)cocos2d::UserDefault::getInstance()->getDoubleForKey(
                cocos2d::StringUtils::format("Fish_%s_weight_%d,", _owner, i).c_str()
                );
        }

    }

    void training(Matrix<ElementType, ElementNum + 1, 1>& data)//a group of data
    {
        Matrix<ElementType, ElementNum, 1> xi;
        for (int i = 0; i < ElementNum; i++)
        {
            xi(i, 0) = data(i, 0);
        }

        _weightMatrix = _weightMatrix + _pace*(data(ElementNum, 0) - H_func(xi))*xi;
    }

    void training(Matrix<ElementType, ElementNum + 1, Eigen::Dynamic>& datas, bool overwide)//more than one
    {
        for (int i = 0; i < datas.cols(); i++)
        {
            Matrix<ElementType, ElementNum + 1, 1> data = data.col(i);
            training(data);
        }
    }

    ElementType resultBeforeSigmoid(Matrix<ElementType, ElementNum, 1>& data)
    {
        return data.dot(_weightMatrix);
    }

    bool result(Matrix<ElementType, ElementNum, 1>& data)//we use boolean to describe the result
    {
        return sigmoid(resultBeforeSigmoid(data));
    }

    virtual bool record()
    {
        for (int i = 0; i < _weightMatrix.rows(); i++)
        {
            cocos2d::UserDefault::getInstance()->setDoubleForKey(
                cocos2d::StringUtils::format("Fish_%s_weight_%d,", _owner, i).c_str(),
                (double)_weightMatrix(i, 0)
                );
        }
    }

protected:

    bool sigmoid(ElementType num)
    {
        ElementType  result = 1 / (1 + exp(-1 * num));
        return result > 0.5;
    }

    double H_func(Matrix<ElementType, ElementNum, 1>& data)
    {
        return data.dot(_weightMatrix);
    }

private:
    Matrix<ElementType, ElementNum, 1> _weightMatrix;
    double _pace;//the speed of convergence
    std::string _owner;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

此处并没有对大规模训练做优化，读取数据也需要童鞋们自己动手，一个基本的类，我们讲完了所有的决策再来谈谈怎么在实例中应用这些模块。

---

准备写一个有关游戏底层算法，物理算法，以及AI（重点是机器学习在游戏中的应用）的长篇博客，欢迎大家指正交流╰(￣▽￣)╯