sc ai 估值ANN初步完成,计划作战模块的GA

连续熬了几天夜,SC AI的估值函数神经网络和训练架构终于搭建完成了,现在就是还有一些代码中的小问题需要小修小补一下,然后就是再做一个自动反复启动的程序让他自己跟自己反复对战就行了。不过要自我对战的话,需要借老爸的电脑连成局域网才行。。那之前先让他和电脑AI练练再说吧。。

这部分只做了估值函数,也就是说只是不断预测比赛谁的胜率更大,而没有让他参与到决策之中(所以决策模块仍然是最基本的“勇气值”模型)。这里我为了能够将各个单位的位置信息形成输入放到神经网络中去,花了很多时间。。直接把横纵坐标放进去肯定是没有意义的。需要一些能够更好的刻画战场情形的特征值才能有效的训练神经网络。结果是我没有采用经典的ANN三层模型,而是使用了一种动态更改的模型。

现在我使用最小生成树来刻画战场特征,并将每一个最小生成树的边当作一个输入,这个边是一个复杂输入,包含对方的hp,护盾值,是否处于攻击状态,与自己的距离等信息,对每一个信息,都需要给定一个对应的权值用于训练。因此这个神经网络的神经元就是每个单位。我再将攻击和锁定目标也作为这个神经网络的输入边,来增加刻画战场状态的特征值。为了防止神经网络出现回路,我将神经元复制一遍,分别作为输入层和隐藏层,将前面介绍的最小树边和攻击边由输入层的对应单位连接到隐藏层的目标对应单位。这样做就保证了没有回路。最后我在输出层放了两个神经元,分别代表玩家0的胜利期望和玩家1的胜利期望。最后,由于所有的单位目前都是zealot, 因此他们的特征权值应该是共享的。我参照《机器学习》上介绍的方法,每次反响传播之后将其权值求平均值再一次赋值,使其能够更快的学习和避免过度耦合。

我使用了我自己同电脑对战的一个录像用于训练。首先写了一个解析录像的小程序,将每一帧的特征信息提取出来写入文件中。之后利用另外一个程序依次将这些特征信息进行计算和处理,将简单的坐标信息转换为最小生成树和攻击边等信息。然后将这些信息作为输入来训练神经网络。目前遇到的障碍是在比赛结束之前,无法给出比赛谁胜谁负的准确信息。如果一次比赛只能根据结果训练一次,则训练周期过长,是不可胜任。我采取《涌现》一书中提到的说法,认为根据估值函数求出的估计值,越接近比赛胜利时估计值越为准确。因此可以利用后面一帧的估值作为前面一帧估值的参照量,并依此进行反向传播。为了能够得到更快的训练速度,我设置当单位数量超过敌军,或单位数量相等而总血量大于敌军时,就认为本方处于优胜状态。这或许并不完全准确但已经是非常保守的估计了。我根据书中提到的标准,设置0.9为优胜,0.1为失败(前述神经网络中所有输出均通过sigmoid函数挤压到(0,1)区间)。至少在昨晚的几次实验中,这套方案得到了较好的成效,接下来的就是要继续训练他直到稳定为止了。为此我还需要再做更多录像,然后就是要想办法让他自己跟自己对战了。

接下来要做的就是决策部分了。这部分我准备使用GA, 即遗传编程。可以根据士兵处于不同情形时(危险/安全,接敌/后方,被包围/被保护,是否接触边界等等)分别设定不同的行为(攻击,攻击移动,移动,原地不动等等),然后通过遗传编程来找到最好的组合。当然好与不好的估值,则通过前述神经网络得出。

现在最愁的一部分就是如何决策移动。因为移动是一个几乎是非离散的量。不可能去考虑地图上的全部点。一定要给出合适的特征值来刻画好的和不好的移动目标。这包括了是否被包围,是否阻碍了友军等等。然而这样的特征值仍然没有找到。前面提到的最小生成树似乎有些意义,但对整体有意义的东西用在局部上有些困难。目前还在思考对策。。。

SC AI设计的强力纠错

昨天熬了一夜之后,在非常兴奋以及脑袋糊掉的状态下写了最近的工作进展和思路。。可惜大多数都是语无伦次。。
今天在仔细读过之后,发现,大多数的想法,都是在写前面几个段落的时候和快要写完的时候不一样,结果导致前后很多矛盾,再加上使用了很多似是而非的术语,让整篇文章几乎没有说对的地方。。

这里也不可能把所有的毛病都改掉了,不过也好上一篇文章成了只有我自己才能看懂了胡言乱语。。。

先说说神经网络吧。上一篇文章多次提到神经网络,其实是指的几个不同的东西。并且这几处都没有给出神经网络的构造。而真正给出构造的一处,即采取各单位相连以广播行为等的那个构造,其实不是神经网络,最多只能说是一个参考神经网络而设计的通信模型。在Holland的一本叫做emergence的书中曾经提到过一种称之为元胞结构的构造,可能这个设计更近似于那个构造,但也还是有很多不同之处。应该说这是一个实验性的构造,也只是我的一时想象,暂时不能说他能够给AI设计起多大的帮助。

而至于使用神经网络结构来学习几项重要的特征,比如是否被封闭(能否逃离),目标健康程度能否在一击内消灭(计算护甲、hp、shield等),同理也可用上述原理计算自身是否安全。这些特征采用神经网络学习是有可能的。神经网络是一个相对静态的结构,必须用于学习能直接得到结论的结果。当然这里我说的神经网络是指没有环路的单馈三层神经网络了。这是一种成熟的技术,可以在AI学习中有很多应用。但也正是这个原因,使得他无法应用于博弈模型这样的无法立即得到反馈的机器学习中来。

昨天文章中说到的“估值函数”也是笔误,其实我想说的只是找到了几个重要的特征值,而没有希望直接设计估值函数。其实我昨天的想法是,通过设置神经网络或者类似于神经网络的其他模型,只要找到了估值特征值,令模型自行学习权值,则估值函数可以通过机器学习得到。这点也是昨天没有说清楚的。。

总之目前的状态是初步的想法有了,但是很多具体细节还没有想清楚。并且前面提到的最重要的部分,也就是类似于“元胞结构”的部分,还有很多没有明确定义的东西。这些地方还需要继续想清楚。

以上

SC AI 神经网络模型和遗传编程

今天wp升级,手欠顺便升级了一下theme,结果忘记备份导致原先的更改全部消失,又重新折腾了好久。bo的外观稍稍有点变。。

昨天由于一整天没有干正事,导致晚上相当悲剧。。熬了一整夜,不过 SC AI的神经网络模型基本上有了框架了。接下来就可以根据各种YY往里面增加参数、估值函数和各种加权了。

目前仍然以考虑zealot为主,不过我发现对zealot适用的模型,对dragoon同样适用,只是需要让他重新适应一次估值函数的权值就可以了。因此这里还是继续仅讨论zealot。首先,确定每个单位拥有进攻和溃逃两套互不相干的策略机,然后给定一个决定是进攻还是溃逃的决策机制,就可以了。

这个决策机制我称之为勇气。当估值函数超过阈值的时候,认为这个单位士气高涨,会继续进攻,而当估值函数低于阈值的时候,这个单位士气低落,会决定溃逃。如果以zealot的攻击范围为单位,将zealot周围区域分成8个方格,则可将每个方格内是否有敌军或友军单位,作为一个神经元输入,更远的敌军或友军单位,通过更多的神经元相连间接得到,任何单位决定进攻任何目标或溃逃都需要作为一个信号向外部发送并引起这个神经网络内的其他神经元的策略改变。参考神经网络模型的疲劳机制,当单位持续士气高涨的时候,会将阈值按照一定的因子提高,使之勇气下降,同理,当单位持续溃逃的时候,会将阈值相应降低,使之变得较为容易参战。这个可变的阈值,可称为单位的勇气。

勇气的估值参数主要有如下几点:自身hp和shield,正在攻击自己的敌对单位数量(以及他们的被攻击情况和健康情况),自己正在攻击的敌对单位hp和shield。考虑这些的目的主要是为了估算自己能否在生存情况下消灭正在攻击的敌人。当然这个逻辑我不准备放入估值函数中,而令其通过神经网络训练学习得到。通过给定不同的加权估值,经过训练应该能得到和人思考出的相似的结论。

假如勇气决策为进攻,则选取攻击决策机,并令其给出一个攻击指令。攻击指令可以是:攻击最近的敌人,攻击hp和shield按照某种权值计算后健康程度最差的敌人(这和需要几次攻击才能消灭敌人有关系,需要折算护甲,攻击类型和目标体积的关系等复杂内容,例如Dragoon拥有20的damage,可是攻击被打光shield的zealot时一次攻击只能造成9hp左右的伤害,这是因为dragoon的爆炸攻击类型对zealot的小型单位只能造成一半伤害,而同时未升防御的zealot拥有1的armor,会抵消10%左右的伤害),攻击盟友正在攻击的敌人,攻击威胁最高的敌人,以及保持目前攻击目标不变。而得到这个攻击指令的效果,又可以采用:攻击单位命令,移动攻击命令,巡逻命令,移动/待命等命令来实现。因此想要使用一个模型来模拟全部的可能性,实在不可能。这里必须采用遗传编程的方式,令不同的策略模型在竞争中互相杂交和进化,最后得到较优的结果。

溃逃机制主要需要考虑的是两种特殊情况,即被友军封闭和被敌军封闭。假如溃逃单位被友军封闭,最好的策略是能够通过该单位向四周发送一条信号,而使合适的单位为其让路。这个信号同样可以用于保持阵型,即“最佳防御位置”的确定。而假如溃逃单位被敌军封闭,则应该立刻变为英勇,因为无论如何也逃不出去了,应该给敌人以最后的伤害。但如何确定某单位是否被封闭了?BWAPI似乎提供了函数,但我暂时还没有测试。否则使用周围单位的位置和权值,让神经网络自己去学习也是可行之道,不过似乎大材小用了……

以上就是最近一段时间测试和思考的内容。另外经过很多测试,对BWAPI和星际争霸游戏的各种特点也慢慢熟悉了,相信对接下来的开发会有帮助吧……

SC AI 估值函数

SC AI还是没有进展。

最近在想办法找出合适的估值函数。生命值,兵数,总输出。这些固然没有问题了。然而最重要的位置信息,却得不出合适的估值函数。如果不能建立好的模型的话,一切算法都是空谈。。。

今天忽然想到的,其实是跟以前的想法一致,不过换了一种方式在思考问题。

micro radar for the SC AI
图中环状圈表示中心的蓝色单位距离每个红色(敌军)单位的距离。在这个距离内,每增加一个敌对单位减1分,每增加一个友方单位加1分

假如能够测量出每个单位攻击一轮所需要的时间,该单位能够移动多少距离,则更好。以此可以计算出优势或者劣势能够保持多少轮,从而得出优势或者劣势多少单位的HP。

另外忽然发现开全图的比赛情况,你甚至可以知道对手每个单位的目标是什么。这样甚至就无需猜测,并且被设置成敌军目标的单位,其实反而掌握了主动权——他往哪里移动,敌人就会追到哪里。并且由于大家的移动速度都是相等的,被追击的单位有权利选择在什么位置开战——他停在哪里,就在哪里开战。因此问题就可以简化成,(对某一个单兵而言)在什么位置开战,对我方更有利(比如获得更大的优势或者使敌人获得更大的劣势)。

还有最近在考虑的就是一些图论的模型是否可以放到这个里面来。比如最小生成树。最小生成树在这个AI里面看似有某种意义。至少他指示了所有兵力集结到同一个地点的最短方案。他也可以表示友军之间互相援助的行动路线。但是其他的意义呢。现在还看不清楚。

另一个图论的模型是steiner tree,  它表示了将一坨兵拆成两个组的方法,使得拆开后的两个组的最小生成树最小。或许这个模型可以用于暴露敌人的弱点。当然steiner tree是NPC问题,所以把它拿进来可能对比赛也没什么帮助。不过话又说回来比赛过程中出现的单位数量也不会特别多,尤其是开始的时候。所以即使使用最蠢的算法,或者使用较平庸的近似算法,对AI有帮助也是有可能的。

但是究竟怎样帮助。。暂时还没想清楚。。

SC AI – 微操

这个命题想了好久。实在不容易定义一个准确清晰的模型来描述这个问题。

从简单的开始吧。

首先SC地图是米字格拼成的,从每个位置向外都有八个方向。当然很传统的,每个位置都可以视为可通过或不可通过。除此之外,在可通过的位置上还有一些比如高度,是否掩护之类的一些属性需要考虑。暂时先讨论开阔地吧。

从最简单的情况开始考虑。比如红蓝两方各有2个狂徒,如何微操可以尽快消灭敌人呢?进一步简化问题,令红方谋求进攻,而蓝方决定防守。当然是将两个狂徒同时攻击对手的同一个狂徒。同时尽可能防止对手的两个狂徒攻击自己的同一个。如何做到这一点呢。假如红方在不断移动,而蓝方仅仅是站着,直到红方攻击蓝方才给予反击,那么,红方应该移动到怎样的位置时就可以决定攻击了呢?应该是红方的两个狂徒都能移动并攻击蓝方的1号狂徒,而蓝方的2号狂徒移动并加入战斗所需时间至少比1号开始同时遭受红方两个狂徒攻击晚一轮攻击所需时间。这样红方就能在攻击中占得至少一次攻击的便宜。由此看来,蓝方必须保证自己的两个狂徒之间的距离不超过红方任何狂徒到己方两个狂徒的最大值的最小值(好吧我语无伦次了)。解释一下就是红方两个狂徒到蓝方一个确定的狂徒之间的距离取最大值,而在以两个蓝方狂徒为目的地的距离之间取最小值。

橙色线表示的就是红方两个狂徒到蓝方狂徒距离的较大值。要在这个较大值中再取较小值。

显然为了做到这一点,蓝方必须移动。蓝方必须移动而保证两个狂徒间的距离没有对手到自己的距离远。这很容易做到。只需两个狂徒尽可能贴近就好了。此外当红方试图接近其中一个蓝方狂徒的时候,蓝方受到威胁的狂徒(被取了最小值的那个)向后移动绕到另一个狂徒侧面,从而使得两个距离变得尽可能相等。

假如蓝方使用这种防御方式,则红方将很难找到理想的攻击位置。但是由于蓝方为了保证距离相等必须不断移动。在移动过程中总会出现与红方距离不和谐的状态。红方只需抓住机会尽快冲上去就好了。当然蓝方鉴于此,一定不会简单的同红方对拼。而会不断后退避免冲突。无论怎样。这个最大值的最小值可以作为一个合理的AI指导原则。至于进一步的讨论要等实际测试之后再做分析了。

接下来讨论一下更多的狂徒群P的情况。想要找出一个完美的模型非常不易。可以用一条边将处于视野范围内的狂徒跟自己连起来。这样所有距离较近的狂徒就能连成一个无向图。边长表示狂徒的距离。前面说到的最大值的最小值可以用一些图论算法找出来。可是现在的问题变得非常复杂。因为之前仅考虑两个狂徒同时攻击某个单独的狂徒。而现在却需要考虑令1~n个狂徒同时攻击一个狂徒。这有n的组合种方式,还要乘以敌对狂徒的数量。这过于复杂,不可能实时计算。

采取机器学习很可能是必要的。可是如何构造决策树和估值函数却非常困扰。

现在能想到的一种简单的策略是将手下的狂徒两两结对。之后每两个一组去捕猎对手的某一个狂徒。当然过程中可以决定切换目标或者撤退。但是这种策略很可能无法发挥狂徒数量多的优势。或许可以进一步将每两组狂徒编为一个小队,每个小队去尝试捕猎对手的某2个狂徒,然后再把这两个目标分配到小组。这就形成了树状结构,像军队那样层层管理。或许这样的主意会不错。至于如何编制,以及各个级别的AI如何实现,还是等测试一段时间再总结讨论吧。

SC经济学

今天考虑了一下最基本的SC经济学。

我把这个问题设定为:在给定的时间Te之内,怎样做才能得到最大化的采矿量。

首先不考虑卡人口卡矿的问题,就是说一直不停的造农民,不造水晶,造农民的时候钱也总是够用。那么需要知道的几个时间是造农民的时间Tscv,农民采到以块矿的时间Tg,他还细分成移动时间Tgm和采集时间Tgg。于是矿从和基地的距离Lm和农民的移动速度Vscv成为需要知道的参数。Tgm = Lm/Vscv。Tgg和Tscv可以在游戏中实测得到。那么我们的第一个问题就是一个矿从需要多少农民。根据经验的话,当基地和矿从的距离最近的时候,一个矿从3个农民比较合适。如果用计算的话,就需要知道,采矿时同一个矿从的几个农民之间的距离是多少。想象两个农民都挤在一个矿从前面,一个开始采集,一个等待。当采集的那个农民离开的时候,等待的开始采集。经过了Tgg时间,离开的农民移动了Tgg Vscv距离,而等待的农民恰好开始移动。所以一个矿从所能容纳的农民数量是2Lm/(Tgg Vscv)。向下取整是经济值(没有农民等待),向上取整是最大值(每个矿从最多有一个农民等待)。更多就是浪费了。

那么在这个理想模型下,到达时间Te能采多少矿呢?到矿从饱和之前,假设训练了n个农民。这一共花了n Tscv时间。在这段时间内的采矿量是个等差数列求和,因为从第5个农民开始,每个农民的采矿量都比前面一个少Tscv时间所能采的矿量。总共少了(n-4)(n-5)/2这么多。所以总的采矿时间就是T’ = Tscv(n·n – (n-4)(n-5)/2)。在加上矿从饱和之后的采矿时间n(Te-T’), 可求出总采矿时间Ttotal。再用采矿量M=Mg Ttotal/Tg可求出总的采矿量(Mg=8,每个农民一次的采矿量)。

现在我们来考虑到Te时矿从没有达到饱和的情况。这个样的话应该什么时候停止造农民呢?因为一个造一个农民的消耗是Mscv=50。而一个农民一次采Mg=8的矿。因此要让这个农民“盈利”,需要他采Tg(Mscv/Mg)的时间,向上取整是7Tg。也就是说,假如准备造第n个农民的时候,所剩的时间小于7Tg,则应该停止造农民开始憋矿。这样的话就应该造(Te-7Tg)/Tscv个农民,向下取整。仍然可以用前面的采矿时间-采矿量方式计算总量。

我们继续考虑卡人口卡钱问题。。啊我前面农民都用scv表示了,就这么将就吧。接下来以神族为主,因为神族的建筑方式比较简单,并且我们参赛也将以神族为主。其实经验告诉我们,当Te比较大时(也就是说不快攻时),8BP是最好选择。这是因为8BP卡钱不多,并且Tscv的时间加上因为卡钱等第9个农民的时间跟一个Tpylon的时间差不多,因此卡到第10个农民的时间也不多。不过这里面的计算确实开始复杂起来。要仔细分析的话,首先需要知道任意时间Tr的时候手上的现钱有多少。根据前面的分析,这个时候的总采矿量已经知道,再减去造农民和水晶花掉的钱,就是手上的现钱Mtr。用Tpylon/Tscv得到造一个水晶的时间相当于造多少个农民。这里向下取整后,把余下的时间也记录下来。因为考虑到卡钱的问题,时间很可能刚好凑够。用Mtr-Mpylon 得到从这个时间开始造pylon剩下的钱,并计算Mtr-Mpylon-Mscv得到卡钱的量,并以当前拥有的农民数量估算卡钱时间(理论上讲,根据农民的出生时间和选择采矿的矿从可以计算出来他的位置和状态,并且精确的计算每个卡钱的时间。不过这些计算实在复杂,并且我们有API嘛,这些数据可以游戏时实时得到,就无需我在这里静态的去计算了……不过以后可能还是会把这里的一些公式补上,因为我们还是需要估计对手的矿量吧)。最后总的采矿量就是前面理想模型的总矿量减去这里卡钱卡人口时间里一个农民的采矿量(被卡的那个农民)。当Te较大的时候,采取这个策略总是最经济的,可以称之为经济策略。因为假如矿不够硬憋钱憋到Mpylon然后造水晶,之后又需要憋钱等农民,卡农民时间必然更长。并且经验告诉我们等到Mtr够Mpylon的时候,一般来说不会出现卡人口的情况(比如8BP,神族基地提供9人口)。但是当Te较小的时候(快攻),很有可能为了快出狂徒而停农民憋钱(比如经典的6BP)。因为这里我没有考虑这个问题,所以暂时不推了。

呜写到这里也累了,下次再来考虑血量伤害等的计算公式吧。

Starcraft AI,Action!

呜刚才reader上看到应该是有人把BWAPI的一些帖子翻译过来放在这边了http://bbs.8da.com/thread-789545-1-1.html,唉大家都准备开工了,我也不能落后啦,Starcraft, 我来啦!

话音刚落又没士气了。。唉真要做起来还是好花时间的。。等1月份左右再开工吧。。最近至少先把工作做好吧。。

嘿嘿因为刚刚搭了博客所以凑字数多写几篇。。。