兵棋推演與人工智慧

2009-01-01

在兵棋推演中,涉及許多運動物件,如:步兵、裝甲車、居民等,其運動能力不一。運動能力又依不同地貌,與平地相比,而有所減耗,稱為黏性。舉例來說:步兵在平地運動,與裝甲車比,速度較慢。但到高地時,裝甲車變無法運動,黏性最大。居民在平地運動,與步兵比,速度更慢。

現在有一個任務,要讓某運動物件-步兵連,從 A 點到 Z 點。在各種可能路徑中,會經過哨站得到補給,路徑受不同地貌影響,其黏性不一。

現在參謀本部要為步兵連,規劃最佳路線,以期能達成任務。於是參謀本部利用 Prolog 人工智慧語言的特性,設計最佳路線模型。

首先要描述各哨站〈a-i-z,a 為起點,z 為終點,起迄點無補給值〉補給值如下:

bonus(a, 0). bonus(b, 18). bonus(c, 22).
bonus(d, 12). bonus(e, 44). bonus(f, 16).
bonus(g, 32). bonus(h, 26). bonus(i, 48).
bonus(j, 36). bonus(z, 0).

描述運動路徑相對位置〈如:ab、ae、ah … 等等〉與路徑運動成本〈黏性〉值如下:

path(a, b, -3). path(a, e, -1). path(a, h, -7).
path(b, c, -7). path(b, f, -9). path(b, i, -2).
path(c, d, -6). path(c, f, -7). path(d, z, -2).
path(e, f, -1). path(e, g, -8). path(f, z, -3).
path(g, z, -4). path(h, i, -5). path(i, g, -5).
path(i, j, -9). path(j, z, -6).

運動淨效益通常是非常複雜的函數,它跟運動體、哨站與路徑等特性有關,為方便說明起見,簡化運動淨效益規則如下:

net_value(Sum_of_Bonus, Sum_of_Cost, Net_Value):-
        Net_Value is Sum_of_Bonus + Sum_of_Cost.

Prolog 程式詳細列表如下:

graph(First_Node, _, Depth, Sum_of_Bonus, Sum_of_Cost):-
	(First_Node=z),
        bonus(First_Node, Bonus),
	Sum_of_Depth is Depth + 1,
        New_Sum_of_Bonus is Sum_of_Bonus + Bonus,
        net_value(New_Sum_of_Bonus, Sum_of_Cost, Net_Value),
	write(First_Node),write(' ('),write(Sum_of_Depth),write(','),
        write(New_Sum_of_Bonus),write(','),write(Sum_of_Cost),write(','),write(Net_Value),write(')'),nl, 
	false.
graph(First_Node, Last_Node, Depth, Sum_of_Bonus, Sum_of_Cost):-
	path(First_Node, Mid_Node, Cost),
        bonus(First_Node, Bonus),
	Sum_of_Depth is Depth + 1,
        New_Sum_of_Bonus is Sum_of_Bonus + Bonus,
        New_Sum_of_Cost is Sum_of_Cost + Cost,
	write(First_Node),write('->'),
	graph(Mid_Node, Last_Node, Sum_of_Depth, New_Sum_of_Bonus, New_Sum_of_Cost).
main:-
	Sum_of_Depth is 0,
        Sum_of_Cost is 0,
        Sum_of_Bonus is 0,
	graph(a, z, Sum_of_Depth, Sum_of_Bonus, Sum_of_Cost).

最後 Prolog 推薦所有可能路線、歷經哨站數、補給數、運動成本數,與其運動淨效益如下:

a->b->c->d->z (5,52,-18,34) 始發1
c->f->z (5,56,-20,36) c 哨站前路逕與始發1相同,略去
b->f->z (4,34,-15,19) b 哨站前路逕與始發1相同,略去 淨效益最差
b->i->g->z (5,98,-14,84) b 哨站前路逕與始發1相同,略去
i->j->z (5,102,-20,82) i 哨站前路逕與始發1相同,略去
a->e->f->z (4,60,-5,55) 始發2
e->g->z (4,76,-13,63) e 哨站前路逕與始發2相同,略去
a->h->i->g->z (5,106,-21,85) 始發3 淨效益最優
i->j->z (5,110,-27,83) i 哨站前路逕與始發3相同,略去

Prolog 用來解決最佳路徑問題,確有其優勢。利用 “事實” 來描繪節點屬性與其他節點從屬關係,利用 “規則” 來定義路徑探索與何為 “最佳路線” ,設計整個遞迴機制,由【輸入-處理-反饋-再輸入】模式,終於窮舉出所有可能路線。

廣告
%d 位部落客按了讚: