一直都想用遺傳算法（Genetic Algorithms）實現(xiàn)足球游戲的人工智能，但因為實現(xiàn)一個足球游戲的對戰(zhàn)平臺太過于繁瑣而沒有動手。直到在《Programming Game AI by Example》一書中看到一個SimpleSoccer的demo（以下簡稱demo），實現(xiàn)了一個red-blue兩隊進行機器與機器對抗的簡單足球游戲。在讀過它的源碼之后，我決定在demo上進行二次開發(fā)——為它加入遺傳算法，實驗遺傳算法在實時戰(zhàn)略游戲（RTS）性質(zhì)的體育游戲中的威力。
demo的架構(gòu)非常好，采用了狀態(tài)機來實現(xiàn)游戲流程，并分開計算游戲決策。因此加入遺傳算法非常容易，只要在原來的狀態(tài)機中增加一兩個狀態(tài)即可。red-blue兩個隊伍相互對抗，每隊有五位球員，其中一位是守門員。這個demo的足球規(guī)則是簡化的，除了只有五個球員外，沒有手球也沒有越位等規(guī)則，甚至連邊界球都沒有——球碰到邊界就反彈回球場。簡化的規(guī)則有利于我們簡化實驗的過程，不必把很多精力花費在過于復(fù)雜的規(guī)則上。
圖一
在demo的實現(xiàn)中，球場被分割為18塊大小相等的區(qū)域（見圖一）。每一個球員都一個屬于自己的區(qū)域（稱為HomeRegion），如圖一中blue隊的10號在自己的HomeRegion(Region5)中處于Wait狀態(tài)（球員的狀態(tài)之一）。當一個球員不處于進攻狀態(tài)（Attacking）、助攻（SupportAttacker）、逐球（ChaseBall）、運球（Dribble）、踢球（KickBall）及返回（ReturnToHomeRegion）時，他就進入Wait狀態(tài)——等待球隊發(fā)出的下一個行動指令。顯然，就像人類進行足球比賽時需要排兵布陣一樣，demo中球員站在哪個位置也相當重要，能否組織起有效的進攻或者防守，決定因素之一就是在合適的位置有沒有球員可以快速有效地執(zhí)行命令。在書中自帶的demo中，球員的站位都是固定的，因此難以組織有效的進攻和防守，在某一時間段內(nèi)容易形成一邊倒的局勢。使用遺傳算法來對球員的站位進行決策分析，可以找出對當前局勢就有利的位置編排方案。從而使得球隊與球隊之間的對抗趨于激烈、策略更加有效、攻守都更精彩。
遺傳算法概述
遺傳算法因為它在解決許多生產(chǎn)、生活中的問題上的卓越性能而經(jīng)久不衰。隨著計算機的計算能力日益增強和玩家對游戲中的人工智能的強烈需求，目前在單機游戲中已經(jīng)開始應(yīng)用遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等現(xiàn)代優(yōu)化計算方法來增強游戲中的人工智能，并且形成了趨勢。可見以后為加強機器的對抗性能，遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等都會越來越多地應(yīng)用到游戲中。
遺傳算法是模擬自然界中的生物對自然界的適應(yīng)而不斷進化這一客觀事實的算法。為了解決某一個問題，在遺傳算法中，我們虛擬一個物種（即解的表現(xiàn)形式或者稱為解的編碼），并將其放到“自然環(huán)境”中天下繁殖、進化，根據(jù)優(yōu)勝劣汰、適者生存的自然法則，繁衍若干代之后，種群中的佼佼者將非常適應(yīng)“自然環(huán)境”，這個佼佼者就是我們求得的解了。關(guān)于生物學(xué)與遺傳算法之間的概念的對應(yīng)關(guān)系可以用表一的形式來表示：
生物遺傳概念
遺傳算法中的作用
適者生存
在算法停止時，最優(yōu)目標值的解有最大的可能性被留住
個體
解
染色體
基因
適應(yīng)性
適應(yīng)函數(shù)的返回值
群體
種群
根據(jù)適應(yīng)函數(shù)選取的一組解
交配
通過交配原則產(chǎn)生一組新解的過程
變異
編碼的某一分量發(fā)生變化的過程
本新聞共11頁,當前在第1頁 1 2 3 4 5 6 7 8 9 10 11
