機器人足球人工智能算法分析

前段時間做了個人機對戰(zhàn)的五子棋游戲，覺得人工智能非常有意思。所以最近沒事，又思考了一下機器人足球的人工智能算法。

機器人足球和五子棋游戲的主要聯(lián)系是：都需要隨時分析整個棋盤/球場的狀態(tài)，并作出最合適的反應(yīng)；主要區(qū)別是：五子棋游戲是回合制的，而機器人足球是“即時”游戲，另外五子棋只要基于某一步棋子考慮，但機器人足球必須考慮23個人/球（棋子）。

表面看區(qū)別蠻大的，現(xiàn)在具體來分析一下：

1）關(guān)于機器人足球的“即時”特點

22個人，再加上一個足球，場上一共有23個物體在同時運動。我們不可能說機器人足球和五子棋一樣，先一個人動，其他人站著，第一個動完再第二個人動....這樣不是在踢球，而是在表演節(jié)目。如果當(dāng)年《星際爭霸》這樣的即時戰(zhàn)略游戲，當(dāng)人全部部署好之后，按一個ready鍵通知計算機，然后計算機慢慢悠悠測挨個處理它控制的坦克，那還有什么樂趣。

有人肯能會說可以用多線程（我事先申明，我對多線程的了解，僅限于幾個簡單的例程，所以一下的敘述可能有不對的地方）。沒錯，多線程確實可以同步處理，并且對于足球這樣的游戲，場上人員是確定的（不考慮被紅牌罰下的），用23個線程來控制人和球，似乎也沒什么不妥（）。但是如果是《星際》，造一個坦克就要新建一個進程，打死一個大兵就要銷毀一個進程....好像這樣開銷比較大。更何況計算機如果造出100架坦克，外加100個大兵，消耗的資源將相當(dāng)可觀。雖然我不知道《星際》是如何實現(xiàn)即時戰(zhàn)略的，但我想即使是用多線程，也肯定有專門的算法對其進行優(yōu)化。

用得著這么復(fù)雜么？我們再仔細分析一下即時制跟回合制之間的關(guān)系，會發(fā)現(xiàn)兩者其實沒有本質(zhì)的區(qū)別，更準(zhǔn)確的說，回合制其實是即時制的一個特例而已！我做五子棋的時候，為了讓人和計算機同步，設(shè)置了一些標(biāo)志。當(dāng)人下過棋后，將標(biāo)志復(fù)位，計算機才可以下棋。它下過一次后將標(biāo)志置位，就不能繼續(xù)下了，等待人下棋。如果我們把這些標(biāo)志取消，那么計算機就會根據(jù)當(dāng)前棋盤情況自顧自的下棋，你趕得上它的節(jié)奏你可能會贏，趕不上的話，就等著輸吧！這樣五子棋也就成了一個即時戰(zhàn)略的游戲了。

所以我認為，對于機器人足球，只需要輪循計算機控制的所有球員，讓每個球員針對場上情況作出最正確的響應(yīng)就行了。計算機的速度非?？欤m然是輪循，但幾乎不會察覺出其中的先后次序，給人的感覺就是在同時進行。其實操作系統(tǒng)的多線程，也是這樣實現(xiàn)的。X86構(gòu)架的cpu，多線程多任務(wù)程序是運行在保護模式下的，其根本思想就是將cpu時間切片，這個時間片上處理a任務(wù)，不管有沒有處理完，下一個時間片上一定處理b任務(wù)，一圈循環(huán)下來，再繼續(xù)執(zhí)行未完成的a任務(wù)。

但是還有一個問題。由于計算機的反應(yīng)遠比人快，如果設(shè)計FIFA這樣的人機交互游戲，很可能計算機將它控制的所有物體都計算好多遍了，可人還沒作出反應(yīng)呢。對于強調(diào)反應(yīng)能力的即時制游戲，這種思維速度的差距可能無法接受。我的看法是，可以讓計算機處理完一遍所有物體后，暫時停頓一段時間，比如500ms，比如1s（具體長度需要測試后才能得出）。而且，計算機停頓時間的長短，也可以用來區(qū)分難度，難度越低，計算機停頓的時間也越長。當(dāng)然，我這里所說的停頓，并不是指計算機真的停止處理任何事務(wù)。計算機仍需要按照事先設(shè)定的運動方向和速度計算每個球員的新坐標(biāo)并不斷刷新，以顯示出動畫效果。只是每隔1s鐘，才會作出特殊反應(yīng)（踢球、搶斷等），改變運動方向和速度

2）機器人足球計算機考慮的點比五子棋多

場上有23個物體需要計算機處理，情況似乎比五子棋復(fù)雜的多了。但真的需要無差別的處理23個物體嗎？

我們來看看真實的足球。我不是很喜歡足球，對足球規(guī)則和各種戰(zhàn)術(shù)也不了解。我只談?wù)勎业母杏X。

對于球來說，雖然它隨時都在運動，但抽象看來，它在場上的情況非常簡單：向某個方向運動，運動速度如何，目前所在的坐標(biāo)，就這么三個要素。其他的什么由哪方控制，誰踢了一腳，都不需要也不應(yīng)該考慮（這符合oop思想）。

再來看看22個運動員。其實我們可以發(fā)現(xiàn)，往往只有離球最近的球員，才會作出相應(yīng)的反應(yīng)（包括盤帶/踢球、傳球、接球、搶斷、射門等，都只有靠近球的隊員才會作出，甚至防守的時候，也往往是防守有球的球員，歸根到底還是離球非常近）。沒見過球在前場，隊員卻在后場拼搶的（當(dāng)然不考慮小動作:)）。所以離球較遠的球員，只需向球跑動甚至?xí)簳r停止不前（這個可以用隨即函數(shù)來控制。影響隨機值的是球員的積極性和離球的遠近。積極的球員更加主動的奔跑，離球稍近的奔跑更主動）。只有離球近的球員，才會作出特殊的處理。這樣細細劃分后，整體算法思路就比較清晰了。

通過上面的分析，現(xiàn)在來總結(jié)一下：

設(shè)計機器人足球的時候，可以使用輪循的方法，挨個處理22個隊員和1個球。一般情況下，處理方法也就是：通過原來的坐標(biāo)和事先確定的方向、速度，計算新的坐標(biāo)。當(dāng)計算完所有物體的新坐標(biāo)后，刷新屏幕，以顯示出動畫效果。

每隔一段時間（或者若干次后），允許計算機對每個物件作出特殊操作（踢球、傳球等），這些特殊操作的本質(zhì)就是改變23個物體的速度和方向，使接下來一段時間物體的運動軌跡產(chǎn)生變化。

做特殊操作時，可以按照球員序號遍歷。針對每個球員需要做的事情是：

1.計算這個球員離球有多遠。超過一定距離，就隨意處理（比如上面提到的，用隨即函數(shù)確定這個人是向球跑還是停止）

2.離球近的話，再查詢球周圍有沒有離球更近的球員（考慮到時間復(fù)雜度，不推薦真的去遍歷整個球場，而是維護一張表，用來記錄每個球員當(dāng)前和球的距離）

3.如果有對方球員離球更近，則可選的操作有：更加靠近、搶斷、等等（我不太懂足球，不知道還有什么操作）?？梢杂秒S機數(shù)來確定執(zhí)行的操作

4.如果有己方球員離球更近，則可以斷定此人正在帶球，此時可選的操作是：向他移動準(zhǔn)備接應(yīng)、向?qū)Ψ角蜷T移動準(zhǔn)備接傳球進攻

5.如果當(dāng)前沒有其他球員離球更近，那此時可以斷定該球員正在帶球。此時需要考察周圍安全距離內(nèi)有沒有對方球員，有沒有己方球員，離球門多遠等等問題，并作出傳球、射門、盤帶等等操作（沒必要真的計算其他人跟自己的距離。由于此時離球近，可以忽略不計。完全可以用其他人離球的距離來代表。具體原理，踢場球就知道了:)）。這些操作比較簡單，只要用一些選擇語句就可以了。有多種操作可供選擇的時候，可以用隨機數(shù)來確定。球員的各種屬性都可以影響隨機數(shù)的取值。

除此之外，還有一些例外操作：比如當(dāng)出現(xiàn)運動員跑著跑著出線、相撞、碰到球等情況，此時即使還沒有到例行的處理特殊操作的時候，但也必須立即針對涉及的球員執(zhí)行特殊操作，否則不真實、不合理的。

最后我們來談一下球員和球的數(shù)據(jù)結(jié)構(gòu)

球員：
{
方向/速度/當(dāng)前坐標(biāo)....
傳球()/踢球()/射門()/接球()/搶斷()....../跑動()
計算新坐標(biāo)()
}

足球：
{
方向/速度/當(dāng)前坐標(biāo)....
計算新坐標(biāo)()
friend:
球員::傳球()/踢球()...... //或者做一個改變方向/速度的接口，讓球員中的函數(shù)能調(diào)用這個接口

}

除此之外，還需要一些表，維護諸如每個球員離球的距離等信息，方便各種處理。另外還有一些細節(jié)，可能是做游戲必須的，但由于相對來說比較簡單，所以在這里就不多分析了。

由于精力有限，我工作、學(xué)習(xí)的壓力比較大，所以上述算法并沒有實現(xiàn)。我寫這篇文章，是試圖分析出即時戰(zhàn)略游戲的一般設(shè)計方法。當(dāng)然，我只是一個編程的初學(xué)者，所有的分析又都是我的個人看法（沒有看過相關(guān)文章）；并且我不是專門做游戲的，不可能將機器人足球的人工智能分析的如同EA的開發(fā)人員那么徹底。所以我的分析可能很粗糙，甚至有很多錯誤。如果能對大家有一點啟發(fā)，我非常欣慰。當(dāng)然，我更希望大家指出我的錯誤看法，讓我能逐步提高自己的水平。