• 2007-09-10

    我见过最nb的技术文……转自gamerhome

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/solmyr-logs/10579090.html

     文:至高天使长

    纸上谈兵,Heroes3兵种单挑排名(一):规则和理论基础  


    Heroes3里面有9大种族,每个族有14种兵种,再加上中立兵种,可谓兵种众多,热闹非凡。兵种一多,很自然的,有一个问题产生了:哪种兵种最强?或者更进一步说,两种兵种之间怎样比较谁更强?

       最简单也最直观的一个办法就是看兵种的属性。比如农民的属性Att/Def/Dmg/hp
    /sp:1/1/1/1/3,无论哪项属性都是最差,显见,农民是Heroes3最弱的兵种。

       但是更多的时候,我们无法直观地从兵种的属性上看出谁更强,比如很相似的两种兵种:
       金龙Att/Def/Dmg/hp/sp:27/27/40-50/250/16
       黑龙Att/Def/Dmg/hp/sp:25/25/40-50/300/15
    黑龙血厚金龙攻防高速度快,它们之间到底谁更强呢?一句棋逢对手、不相上下不是
    我们寻求的最终答案。因此,有必要建立一套评判的标准来评定兵种实力的强弱。

       一个很自然的办法就是将两种兵种拉来单挑,胜者说明实力更强。但是由于Heroes3里面绝大多数兵种的Dmg都是在一个范围内波动(天使、那加等少数兵种除外),这就使得单挑运气成分较大,一方连续几次高伤害就可能得胜,有人说多测几次看哪方胜率高不就行了,这固然是减小运气成分的一个办法,但是有时候胜率不相上下时比如上面的金龙和黑龙,它们之间的胜率非常细微,可能要测上几百次乃至上千次,非常繁琐,而且也不见得能够得出准确的结果。

       更好的办法是NvsN,N是一个充分大的自然数,两方兵种各取N个分成一堆单挑,这样不仅可以有效减小运气成分,更可以杜绝“单挑王子”幽灵、桥梁怪的“作弊”行为(恢复hp特技使得它们同级兵单挑无敌,但这显然不是它们真实实力的反映)。

       方法已经确定,下面就是建立规则了。

       既然是兵种之间的单挑,那么

       1、双方都不分堆且一切外界因素都应该尽量杜绝,比如英雄攻防指数、特技、技能、宝物、魔法、地形、士气和运气[注1]等等;

       其次,双方都应该能选择自己的最佳策略,例如速度快的一方可以选择等待。但在数量较少的时候,由于原地防御可以增加防御力,这样原地防御一方可以占到优势(受伤害减少反击伤害不减),因此如果一方防御另一方势必也会无奈选择防御,这样子一回合就会被浪费,甚至会出现双方都一直选择防御的情况,这种消极比赛的态度是广大观众不愿见到的,因此我们规定

       2、双方都可以选择自己的最佳策略,但都没有防御的权利。

       这两点就是单挑应该遵守的基本原则。


       在用实践得出结论之前,我们有必要先用理论来指导一下实践。我们的目的是尽可能地量化单挑两兵种之间的实力比,这无疑对实践有着积极的作用。下面我们以大天使和大恶魔这对天敌单挑为例来说明。

       先来看看双方的基本属性:
       天使Att/Def/Dmg/hp/sp:30/30/50/250/18
       恶魔Att/Def/Dmg/hp/sp:26/28/30-40/200/17
    如果恶魔不是攻击不反击这场单挑根本没有任何悬念。但即便是恶魔攻击不反击,通过我们实际测试,天使也是完胜恶魔,不论是1vs1还是NvsN。我们的问题是天使的实力比恶魔强多少?

       NvsN的结果必然是天使剩余一定数量,这说明如果恶魔数量再多一些天使依然有可能胜出,实际测试,5个天使就能赢6个恶魔——这说明天使的实力比恶魔至少强20%——这也启发我们,天使能够赢的恶魔的最大数量M与天使自身数量N的比值M/N就是双方的实力比的近似值。精确的叙述如下:

       假设N个天使能赢M个恶魔但是不能赢M+1个恶魔(M显然是存在的),这样M是N的一个函数,记为M=f(N),f(N)即为N个天使能赢的恶魔最大数量,同时令g(N)=M+1=f(N)+1,g(N)即为N个天使不能赢的恶魔最小数量,h(N)=f(N)/N,则当N趋向于无穷大时h(N)的极限值P就是天使和恶魔的实力比(极限的存在性需要证明,见下文)。

        由此得出如下结论:

       ①、lim[f(N)/N]和lim[g(N)/N]同时存在,如果存在则两者相等。这里lim代表N趋向于无穷大时的极限。
       如果P=lim[f(N)/N]存在,则lim[g(N)/N]=lim{[f(N)+1]/N}=lim[f(N)/N]+lim[1/N]=P,反之亦然。

      ②、如果n个天使可以赢m个恶魔,t个天使可以赢s个恶魔,那么(n+t)个天使可以赢(m+s)个恶魔;反之结论同样成立:m个恶魔可以n个天使,s个恶魔可以赢t个天使,那么(m+s)个恶魔可以赢(n+t)个天使。  
       这一条称作叠加性原理[注2],是整个推导过程的基础。

    ③、f(n1)+f(n2)+…+f(nk)<=f(n1+n2+…+nk)<g(n1+n2+…+nk)<=g(n1)+g(n2)+…+g(nk)[注3]。
       由于n1个天使可以赢f(n1)个恶魔但是不能赢g(n1)个,将n1换成n2,n3,…,nk等一样成立,由②立即可得:n1+n2+…+nk个天使可以赢f(n1)+f(n2)+…+f(nk)个恶魔但是不能赢g(n1)+g(n2)+…+g(nk)个,由f和g的定义立即得出不等式成立。

        ④、P=lim[f(N)/N]存在。
       证明需要用到数学分析的一些基础知识,若不感兴趣可以直接跳过。
       由①知只需证P=lim[g(N)/N]存在。
       首先g(N)/N有界。在③中令n1=n2=…=nk=1即得kf(1)<g(k)<=kg(1),易见f(1)=1
    ,g(1)=2,故1<g(k)/k<=2,即有界。
       由于g(N)/N有界,故下极限和上极限均存在,设为P和Q,则有两个无穷子列{ni}
    {mj}使得g(ni)/ni->P,g(mj)/mj->Q,固定一个ni(>=2),对于所有的j,将mj写成如
    下形式:
       mj=uj*ni+vj,uj>=0,0<=vj<ni,j=1,2,3,…
    由③易得g(mj)<=uj*g(ni)+g(vj),这里g(0)=0。由于vj只有ni种取值情况,故g(vj)有界T,从而
       g(mj)/mj<=[uj*g(ni)+T]/(uj*ni)
    令j->∞注意到mj,uj->∞即得Q<=g(ni)/ni。
       由于ni是任取的,故上式对于所有的i都成立,令i->∞得Q<=P,从而上下极限相等,立知lim[g(N)/N]存在(且等于上下极限)。
      
       ⑤、对于所有的N,f(N)/N<P<g(N)/N,f(N)=[P*N]。这里[]表示取整。
       在③中令n1=n2=…=nk=N即得kf(N)<=f(k*N)<kg(N),从而
       f(N)/N<=f(k*N)/(k*N)<g(N)/N
    再令k->∞由④得f(N)/N<=P<=g(N)/N,结合下文要说明的P为无理数可知等号不会成立。
       这个结论告诉我们可以用f(N)/N来作为P的近似值。
       同样如果P值已知,亦可以由P*N-1<g(N)-1=f(N)<P*N得出f(N)=[P*N]。

        ⑥、P=1.24795…。
        令x=1天使对恶魔的伤害/1恶魔的hpy=1恶魔对天使的伤害/1天使的hp,则
        x=(1+2*5%+50%)*50/200=0.4y=(1-4*2.5%)*(1+50%)*35/250=0.189
    这里将恶魔的Dmg取为平均值35。
       考虑k*N天使VSk*f(N)恶魔,这里k是与N无关的待定参数。第一回合天使攻击,恶魔剩余b=k*[f(N)-x*N]个,用k来保证恶魔数量恰为整数,然后恶魔反击再攻击,
    第一回合结束,天使剩余a=k*{N-2y*[f(N)-x*N]}个,用k来保证天使数量恰为整数(k*x,k*y,k*x*y为整数即可)。由于k*N天使能赢k*f(N)恶魔,自然就有a个天使赢b个恶魔,于是b<=f(a)  b/a<=f(a)/a
       令N->∞,注意到此时b/N->k*(P-x) a/N->k*[1-2y*(P-x)]a->∞,从而
       b/a=(b/N)/(a/N)->[k*(P-x)]/{k*[1-2y*(P-x)]} f(a)/a->P
    即有[k*(P-x)]/{k*[1-2y*(P-x)]}<=P。完全类似地考虑k*N天使VSk*g(N)恶魔,又有
       [k*(P-x)]/{k*[1-2y*(P-x)]}>=P
    故[k*(P-x)]/{k*[1-2y*(P-x)]}=P。约掉k,得到
       (P-x)/[1-2y*(P-x)]=P                     (*)
    解之,舍去负根,得
       P=[x+(x^2+2x/y)^1/2]/2=1.24795…
    这就是我们寻求的答案,说明大天使单挑实力超出大恶魔近24.8%。

       方程(*)可以这样理解:P是一个使恶魔和天使双方实力均衡的数量比,先假设N个天使和M个恶魔实力绝对均衡(那么P=M/N),那么经过一个回合后这个均衡不会被打破,否则最后会有一方胜出从而说明双方实力不均衡;经过一回合后恶魔数量b=M-x*N天使数量a=N-2y*(M-x*N)(亦不妨假定a,b都是整数否则可像上面一样同乘以k),由于双方实力依然均衡,故:
        b/a=P=M/N                            (**)
    化简即为(*)式;可以看出,经过若干回合双方的实力会一直保持均衡,直到最后双方数量同时为0;但实际上因攻击有先后,必然有一方数量先变为0,这说明假设的双方实力绝对均衡是不可能的(由此亦可看出P不可能是有理数),但这时(*)式仍然是成立的,因为由⑤我们可以用f(N)/N来充分逼近P,这时b/a也同样逼近P,双方极限相等,即可得出(*)式。这种求实力比的方法把它称作比值法。

       上面6条就是理论的基础,其中叠加性原理又最为基础。可以推广到一般情况:两种兵种A与B,A对B的实力比记作P(A,B),B对A的实力比记作P(B,A),则P(B,A)=
    1/P(A,B),P(大天使,大恶魔)=1.24795…。

       不完全符合6条的即不满足叠加性原理的例外也有不少,比如幽灵和桥梁怪这种单挑王子,1幽灵肯定能胜1皇家狮鹫,但是无法推出10幽灵胜10狮鹫;还比如1吸血伯爵无法胜1蛮牛,但是不能由此推出100吸血伯爵不能胜100蛮牛,事实上100吸血伯爵可以完胜100蛮牛(甚至完胜100独眼),理由后文详述。但是在这些例外情况下,
    上面的理论仍然具有指导性意义:当N充分大时,一回合单个幽灵恢复hp对于自身实力的补充是微乎其微的,处理问题的时候可以理想化地将这点忽略,这样计算出来的P值虽然会有一定的误差但是不大,可以作为真实P值的一个近似值;考虑吸血伯爵的时候把吸血的特技考虑进去,计算出来的P值一样可作为近似值参考。这提示我们将兵种特技分为3类分别考虑:
       
       a):对兵种单挑实力构成重大影响的不能忽略的特技,具有这些特技的兵种单挑时必须考虑其特技因素。比如前面的大恶魔攻击不反击特技,还比如十字军的攻击两次特技、吸血伯爵的吸血特技等等,不一一列举;对于攻击两次、吸血、死亡凝视、火盾等等这些A类特技,比值法都是普遍适用的,只不过处理起来稍微复杂一点。

       b):对兵种单挑实力影响不大的可以忽略的或者考虑后将使问题变得异常复杂的特技,具有这些特技的兵种单挑时,为理想化和计算方便起见不妨将其特技忽略,计算出来的P值作为参考,采取理论和实践相结合的方式检验其实力。比如前面的大天使士气+1特技,士气为1只有1/24的士气高涨几率,一是影响不大,二是考虑将会使问题变得非常复杂,故不妨忽略。这类特技有很多,还比如幽灵桥梁怪的恢复hp特技、美杜莎的石化特技等等,不一一列举;
       
       c):对兵种单挑完全没有影响的可以直接忽略的特技,具有这些特技的兵种单挑时可以直接忽略其特技。这种情况我们只能说其实力不光体现在单挑方面,但本文只论述单挑实力,故恕不再讨论。这类特技也有很多,比如大天使的复活特技、黑龙的魔免特技、泰坦的免疫心智魔法特技等等,不一一列举。
         
       以下是推广的几种一般情形,A代表速度更快的兵种,B代表慢速兵种,x和y的含义同上:
       Ⅰ:AvsB,B一回合可攻击到A,A无a类特技,B有a类特技攻击不反击:
        (P-x)/[1-2y*(P-x)]=P
       P(A,B)=[x+(x^2+2x/y)^1/2]/2
    这种情况较少,例如P(大天使,大恶魔)=1.24795…。

       Ⅱ:AvsB,B一回合可攻击到A,AB均无a类特技:
       {P-x-x[1-2y(P-x)]}/[1-2y*(P-x)]=P
        P(A,B)=(x^2+x/y)^1/2
    例如金龙vs黑龙,x=0.165 y=0.171P(金龙,黑龙)=0.99606…,可见黑龙比金龙强一丁点,差距在4‰以内,这么微小的差距单纯用实验是很难得出结果的。

       一回合之内先A攻击B反击再B攻击A反击,这4次攻击按照时间先后分别设为1,2,
    3,4,A即为1+4攻击B为2+3攻击,通过等待A亦可选择2+3攻击。需要指出:A选择1+4
    攻击比选择2+3攻击更有利。     
       若A一直选择1+4攻击,由上知P(A,B)=(x^2+x/y)^1/2;若A通过等待一直选择2+3攻击,将AB调换顺序应用上面结论得P(B,A)=(y^2+y/x)^1/2即P(A,B)=1/[(y^2+y/x)^1/2]。易见两种情况下的P(A,B)前者更大,即说明选择1+4攻击比选择2+3攻击更有利。这也体现了速度的优势。

       Ⅲ:AvsB,B一回合可攻击到A,B无a类特技,A有a类特技攻击不反击:
       {P-x-x[1-y(P-x)]}/[1-y*(P-x)]=P
        P(A,B)=(x^2+2x/y)^1/2
    这种情况也比较少。例如大恶魔vs黑龙,x=0.1225 y=0.208125P(大恶魔,黑龙)=1.09187…。这种情况相当于A不具备不反击特技但y要减半的情形Ⅱ。

       Ⅳ:AvsB,B一回合不能攻击到A,AB均无a类特技:
       这种情况非常具有普遍性。由于B一回合不能攻击到A,故总有某个回合A能攻击B而B却不能,A通过等待就能减少B的一次先攻机会,显然P(A,B)值会增大。
       假设双方实力均衡,数量为N,M,某个回合A能攻击B而B却不能,A等待后攻击B反击,回合结束,双方剩余数量N=N-y*(M-x*N),M=M-x*N。抛开A的速度远大于B使得A能移开后再次等待这种少数情形[注4],双方将转化为情形Ⅱ。从而有M/N=P=(x^2+x/y)^1/2,解之:
        M/N=x+1/(y+1/P)
        P(A,B)=x+1/(y+1/P)其中P=(x^2+x/y)^1/2
    易证P(A,B)>P,这也证实了P(A,B)值确实会增大。例如大天使vs比蒙巨兽,比蒙巨兽虽有a类特技忽视80%防御但只影响y值不影响结论,x=31/120y=0.264 P=1.02238… P(大天使,比蒙巨兽)=1.06341…。

       Ⅴ:AvsB,B一回合不能攻击到A,B无a类特技,A有a类特技攻击不反击:
       与情形Ⅳ一样,A亦可通过等待减少B的一次先攻机会,且因A攻击不反击,P值的增大更明显。
       假设双方实力均衡数量为N,M,某个回合A能攻击B而B却不能,A等待后攻击,回合结束,双方剩余数量N=N,M=M-x*N。抛开A的速度远大于B的少数情形,双方将转化为情形Ⅲ。解之:
        P(A,B)=x+(x^2+2x/y)^1/2
    例如大恶魔vs比蒙巨兽,x=0.1575 y=0.34P(大恶魔,比蒙巨兽)=1.13283…。

       远程兵种作为一类特殊兵种是不能不单独考虑的。远程射击显然是a类特技,但远程兵种的战略价值不在于单挑,而且很多远程兵种远程伤害减半近战伤害亦减半,单挑未免有失公平,但目前没有更好的办法,而且部分远程兵种单挑实力亦不俗例如泰坦。远程兵种单挑有其特殊性,稍加讨论如下:
       B是远程:A如果一回合攻击不到B就要先等待以尽量避免B射全箭;
       A是远程:A速度最快不过泰坦的11,因此B一回合无法攻击到A,A应该等待后射全箭。例外情况是泰坦vs绿龙,泰坦等待之后绿龙往前飞两格就能使泰坦射击减半且下回合能够攻击到泰坦;
       A,B都是远程:直接对射就是。问题在于双方数量N,M充分大时回合数将会足够长——箭枝会射完然后双方只能近战。这显然有违初衷,两个远程兵种单挑比拼的是远程射击能力而不是近战能力,解决办法是假定双方箭枝无限或者直接给双方都装备弹药车且规定弹药车不受攻击。其实远程兵种一般都有24枝箭,能持续24回合的N,M都很大,M/N已能足够近似P值。

       最后要指出的是:P不具备传递性,即P(A,C)=P(A,B)*P(B,C)一般不成立。随便举几个例子就能验证这一点。甚至会出现P(A,B)和P(B,C)均大于1但P(A,C)小于1的情形,这时A胜BB胜CC胜A,三者形成一个圈:假设A是高速飞行兵种,B是远程兵种速度次之,C是近战实力型兵种速度最慢,A凭借高速克制B,B凭借远程克制C,C凭借近战实力克制A。
       例如A神怪、B祭司、C树妖:
       神怪Att/Def/Dmg/hp/sp:12/12/13-16/40/11
       祭司Att/Def/Dmg/hp/sp:12/10/10-12/30/7
        树妖Att/Def/Dmg/hp/sp:9/12/10-14/65/4
       神怪vs祭司:祭司有a类特技近战不减。x=15.95/30 y=0.275
    第1回合神怪等待。P/(1-0.5y*P)=(x^2+x/y)^1/2 P(A,B)=1.23569…
        祭司vs树妖:x=11/65y=0.39
    前3回合祭司均等待后射击,树妖分别前进3,4,4格。第4回合祭司直接射击,树妖攻击遭反击。第5回合为情形Ⅱ。{P-3.5x-x*[1-y*(P-3.5x)]}/[1-y*(P-3.5x)]=(x^2+x/y)^1/2P(B,C)=1.23031…
        神怪vs树妖:x=2.9/13y=0.2775
    注意树妖缠绕,直接归为情形Ⅳ。P(A,C)=0.95846…

        
       在开始最终测试之前,说明测试的环境:
       游戏版本SOD3.1,测试兵种双方的英雄均为初始元素使不带魔法书,除一方带压抑精灵和邪恶沙漏外没有其它宝物,沙漠地形,战场无特殊障碍。为避免伤害波动,用修改器把每个兵种的伤害固定为平均值,平均值为半整数例如2.5的情形取成2-3。

       双方兵种速度如相同,如果双方同为近战(远程)兵种又无其它a类特技,可以直接比较x和y的值,显然谁大谁更强;如果一方是近战一方是远程兵种,不论是哪一方先动,由兵种行动顺序规律,只要它不等待,就会一直先行动,显然为了保持先攻的优势它不会选择等待,因此可以先假定A一直先动不等待,算出P(A,B),再假定B一直先动不等待,算出P(B,A),P和P谁大即谁更强。
       如果出现上面所述的圈的情形,做出单独说明。另外本文只研究同等级兵种的单挑,中立兵种依照周产量归入相应等级,跨等级实力相近的兵种单挑只是少数情况,恕不再讨论。         


       注1:这里的士气和运气指的是外部因素,比如地形和访问建筑带来的士气和运气影响、英雄率领同族部队士气+1等等,而对于兵种自身特技带来的士气和运气影响即兵种自身因素不能忽略,比如天使的士气+1,骨龙的士气-1等等。不过在后面的讨论中,将此类特技归为b类特技,实际上还是忽略了的。

       注2:关于叠加性原理可以这样证明:n个天使和m个恶魔,记第k个回合恶魔与天使的数量比(不满血的那个按比例写成分数)为dk,则{dk}必定严格单调,单减为天使赢,单增即恶魔赢。{dk}的单调性只与初值d0=m/n的大小有关(实际上是与d0和P的大小关系有关),如果n个天使赢m个恶魔,t个天使赢s个恶魔,由于(m+s)/(n+t)介于m/n与s/t之间,而d0=s/t和d0=m/n都使得数量比单减,从而d0=(m+s)/(n+t)也使得数量比单减,即(n+t)个天使赢(m+s)个恶魔。

       注3:n1,n2,…,nk中的1,2,…,k都是下标,表示第1,2,……,k个数,下面的ni,mj,uj,vj,dk也是如此。

       注4:不难证明:A每次攻击完之后能移动开再次等待的充要条件是:
        (1)sp(A)>=2sp(B)+1;
        (2)sp(B)<=4;或者B是sp(B)=5的单格兵A是sp(A)>=17的单格兵;或者B是sp(B)
    =5的双格兵A是sp(A)>=19的单格兵。
       由于速度不小于17的单格兵只有大恶魔,而在七级兵中没有速度为5的单格兵,所以本文的同级兵单挑只用考虑sp(A)>=2sp(B)+1且sp(B)<=4的情形,这种情形相当于B一回合能攻击到A且A,B都拥有攻击不反击的特技,每回合双方都只攻击一次。

    分享到:
    引用地址:

    评论

  • 这个完了么////是不是没完啊......