人工智能期末話題論文(2)
人工智能期末話題論文
人工智能期末話題論文篇二
人工智能在拼石頭游戲中的應(yīng)用
引言
游戲的人工智能研究是人工智能的主要研究領(lǐng)域之一，它涉及人工智能中的搜索方法和決策規(guī)劃等。俄羅斯方塊游戲和七巧板游戲都是經(jīng)典的具有啟智、益智功能的平面拼圖游戲。第18屆日本全國高專編程競賽競技組的題目，便是借鑒這兩款游戲的特點并引入競標機制而發(fā)明的一款新游戲即拼石頭。具體規(guī)則如下：
每次比賽有6至10支隊伍參加，每支隊伍各自擁有相同形狀、面積的一面“墻”和相同金額的虛擬貨幣。“墻”是由若干個單元正方形構(gòu)成的，如圖1所示。
圖1“墻”
裁判方在賽前給出若干種形狀的“石頭”， 每種“石頭”有若干塊以及各自的底價，“石頭”也是由若干個單元正方形構(gòu)成的，但面積要比“墻”小的多，如圖2所示。
圖2“石頭”
每次比賽有若干輪的競標，每輪競標中有“最大競標數(shù)M”和“最大中標數(shù)N”做限制(M>N>=1)。每支參賽隊按照“最大競標數(shù)M”提供競標信息，競標信息中包括參賽隊要購買的“石頭”種類、為每塊石頭報出的競標價格(競標價格不得低于“石頭”底價)以及對競標“石頭”的排序，例如M等于5時，可能的競標信息是{A100，A200，C20，B70，D5}，表示以價格100競標“石頭”A，以價格200競標“石頭”A……，并且該隊本輪競標的排序是AACBD。當有多支隊伍競爭相同種類的“石頭”時，該種“石頭”優(yōu)先賣給為其排序靠前的隊伍;當多支隊伍在相同排位上競爭相同種類的“石頭”，且該種“石頭”數(shù)量小于競爭隊伍數(shù)量時，該種“石頭”優(yōu)先賣給出價高的隊伍，若有兩支或兩支以上的隊伍出價相同，則在參與競爭的，且出價相同的隊伍中進行二次競標，若出價仍然相同，則該“石頭”本輪“流拍”。另外，若某支隊伍在本輪已經(jīng)獲得了塊數(shù)等于“最大中標數(shù)N”的“石頭”，則其后面的競標信息無效，即該隊伍退出本輪競標。，
以3支隊伍為例，假設(shè)當前裁判方有2塊“石頭”A、1塊“石頭”B、1塊“石頭”C、2塊“石頭”D、3塊“石頭”E，本輪“最大競標數(shù)M”和“最大中標數(shù)N”分別為4和2。參賽隊伍的競標信息如表1所示。
表1參賽隊競標信息隊伍\排序[]1234aA10A200B50E20bC20A100B60D20cC21A300B100E25根據(jù)規(guī)則，在排序1上，隊伍a以10獲得1塊“石頭”A，隊伍c以21獲得1塊“石頭”C;在排序2上，隊伍c以300獲得1塊“石頭”A，此時隊伍c在本輪已經(jīng)達到“最大中標數(shù)”2，該隊伍的排序3和4無效;在排序3上，隊伍b以60獲得1塊“石頭”B;在排序4上，隊伍a以20獲得1塊“石頭”E，隊伍b以20獲得1塊“石頭”D。
每輪競標結(jié)束后，裁判方為各隊伍分配所購得的“石頭”，同時公布本輪競標情況，并以剩余石頭開始下一輪的競標;各參賽隊伍，在準備開始下輪競標的同時，可以將購得的“石頭”拼在“墻”上，拼“石頭”時，“石頭”不能懸空擺放，同時每塊“石頭”都可以像俄羅斯方塊中的“石頭”一樣，旋轉(zhuǎn)90°、180°或270°，但不能“里外”翻轉(zhuǎn)，例如圖2中的“石頭”A不能“里外”翻轉(zhuǎn)后當作“石頭”B來使用。當最后一輪競標結(jié)束的2min后，比賽結(jié)束，裁判方使用以下次序的評判規(guī)則為各隊排名次：①拼到“墻”上的“石頭”的總面積大者獲勝;②面積相同者剩余貨幣多者獲勝;③剩余貨幣相同者剩余“石頭”(買到但沒有拼到“墻”上的“石頭”)總面積小者獲勝;④剩余“石頭”總面積相同者“墻上沿”占滿率大者獲勝;⑤以上條件全相同者，以“石頭、剪刀、布”的方式確定名次。
“墻”的形狀、石頭的種類數(shù)、每種石頭的形狀、塊數(shù)和底價、競標輪數(shù)及每輪“最大競標數(shù)”和“最大中標數(shù)”等信息，在賽前給定。參賽隊伍需要在賽前編寫程序，指導(dǎo)游戲過程中的競標和拼圖。
1問題分析
根據(jù)引言中對游戲規(guī)則的描述，可知理想狀態(tài)下，使用單位面積價格最低的“石頭”拼滿整個“墻”時，一定能夠獲得勝利。但由于“石頭”數(shù)量有限，往往會出現(xiàn)：不能以底價或低價買到“石頭”;買到的“石頭”拼不上;想買的“石頭”買不到等現(xiàn)象。結(jié)合比賽結(jié)果評判標準中，“拼到‘墻’上的‘石頭’的總面積大者獲勝”為第一原則的情況，在諸多游戲者中，誰可以買到更大面積的“石頭”，并盡量將買到的“石頭”拼在“墻”上，誰就能在比賽中獲勝。
通過上述的簡單分析，參賽者編寫的程序應(yīng)至少在買什么“石頭”和怎么拼“石頭”兩個方面給出決策和指導(dǎo)。也就是說，程序中要解決“競標”和“拼圖”兩個問題，“競標”負責幫助游戲者合理排位、合理出價;“拼圖”幫助游戲者合理擺放“石頭”。然而，“競標”和“拼圖”問題又不是相互孤立存在的，它們之間是相互制約、相互依賴的關(guān)系，即競標時要買拼圖能夠使用上的“石頭”;拼圖時應(yīng)選擇競標后買到的和在下一論競標中容易買到的“石頭”。同時，“競標”和“拼圖”對于“石頭”的要求是相互矛盾的，形狀規(guī)則的“石頭”在拼圖時更加容易被利用，例如圖2中的“石頭”D和E，但是，它們都是競標時不愿去購買的“石頭”，“石頭”D面積小浪費中標名額，“石頭”E面積大且形狀規(guī)則，勢必成為“緊俏”商品，很難買到;反之，競標時容易買到的“石頭”，例如圖2中的“石頭”C，但它在拼圖中很難被用到。如何處理“競標”和“拼圖”對于“石頭”要求不同的矛盾，成為獲得勝利的關(guān)鍵。
2策略制定
根據(jù)對游戲規(guī)則的理解和問題的分析，我們?yōu)槌绦虻木帉懺谄磮D算法選擇、競標排序等方面制定如下策略：
2.1拼圖算法的選擇
采用深度優(yōu)先的搜索算法進行拼圖，并且由“墻”的底部開始向上擺放“石頭”，保證不懸空。拼圖時在已經(jīng)買到的“石頭”和裁判方剩余“石頭”兩個集合中選擇“石頭”(兩個集合分別記做Sed和S)，并優(yōu)先選擇Sed中的“石頭”，在S中選擇“石頭”時，按照估值函數(shù)(后文中給出)給“石頭”打分，根據(jù)每種“石頭”的估值以堆結(jié)構(gòu)存儲S，每次選擇堆頂?shù)?ldquo;石頭”進行試探。
2.2拼圖解的確定
深度優(yōu)先搜索拼圖解法時，不一定將拼滿“墻”作為解，即產(chǎn)生的解允許與“墻”的面積相差一定的單元格。
2.3各輪競標的貨幣分配
按照“少—多—少”的棗核形狀整體分配各輪使用的虛擬貨幣，這樣做的原因是：前期競標時“石頭”多、競爭小，中期競標時競爭激烈應(yīng)該盡量“花錢”，后期競標時“石頭”已經(jīng)快賣光，為后期保留過多的貨幣沒有用處。具體比例可適當調(diào)整。
2.4每輪競標“石頭”的選擇
在每輪競標之前進行拼圖，并在拼圖產(chǎn)生的解中，選擇M塊面積大的，且屬于集合S的“石頭”作為本輪參與競標的“石頭”(M等于本輪的最大競標數(shù))。
2.5每輪競標的排序
每輪競標時，先 按照需要購買的“石頭”的面積排降序，然后按照當前裁判方各種類的“石頭”數(shù)量，進行順序調(diào)整，若在排序的前幾位上，某種類的“石頭”數(shù)量較多，可在一定能夠買到的前提下，適當將其順序向后調(diào)整。
2.6每輪競標的出價
在每輪競標中，為要購買的“石頭”排好順序后，要為本輪所要購買“石頭”出價。由于“最大中標數(shù)”小于“最大競標數(shù)”，所以出價的總額要略大于最初為本輪分配的貨幣數(shù)。出價時，首先為一定能夠買到的“石頭”出底價，然后為存在競爭的“石頭”按照面積、數(shù)量、排序等因素出價，面積大(排序靠前)、數(shù)量少的出高價，反之出低價。具體比例可適當調(diào)整。
3“石頭”估值函數(shù)設(shè)計
為保證組成解的各個“石頭”中的大部分是我們認為的“好石頭”，在使用深度優(yōu)先的搜索算法進行拼圖時，需要在裁判方提供的“石頭”集合中優(yōu)先選擇“好的石頭”進行試探。確定“石頭”的好壞需要設(shè)計關(guān)于“石頭”的估值函數(shù)。
影響“石頭”好壞的因素包括面積、數(shù)量、形狀等幾個方面。在面積方面，由于受競標次數(shù)的限制，拼圖時應(yīng)盡量選擇面積大的“石頭”，即面積越大“石頭”越“好”;在數(shù)量方面，某種類的“石頭”數(shù)量越多，競爭就越小，出低價甚至出底價就可買到，因此數(shù)量越多“石頭”越“好”;在形狀方面，形狀規(guī)則的“石頭”容易在拼圖中使用，但是這樣的“石頭”不容易購買，反之，形狀不規(guī)則“石頭”不易在拼圖中使用，但其面積大且容易購買，認為形狀規(guī)則的“石頭”好和認為形狀不規(guī)則的“石頭”好，都有各自的道理，這里我們選擇形狀不規(guī)則的“石頭”作為“好石頭”。 綜合面積、數(shù)量、形狀3方面的因素，我們給出的“石頭”估值函數(shù)如公式(1)： F(x)=k1A(x)+k2R(x)+k3C(x)(1)其中，x表示“石頭”;A(x)表示“石頭”的面積;R(x)表示“石頭”的“凹凸度”，即不規(guī)則程度，R(x)的值等于組成該“石頭”矩形的個數(shù)，例如圖2中的“石頭”A和B的“凹凸度”為2，“石頭”C的“凹凸度”為4，“石頭”D和E的“凹凸度”為1;C(x)表示該類“石頭”的數(shù)量;k1、k2和k3為非負系數(shù)，用于調(diào)節(jié)這3方面所占的比重。
4算法實現(xiàn)
針對之前制定的策略，我們使用Microsoft Visual C++ 6.0作為開發(fā)工具，開發(fā)了參賽程序。下面給出程序的偽代碼：
讀取本次比賽信息，包括墻、石頭、競標數(shù)等;
定義石頭集合Sed和S，Sed初始為空，S初始為全部裁判方石頭;
定義循環(huán)變量i，初始為0;
while(i<競標輪次數(shù))
{
//拼圖
while(尚未求出拼圖的解)
{
按照石頭估值函數(shù)調(diào)整S為堆;
if(Sed中存在未試探過的石頭)
從Sed中選擇石頭;
else
從S中選擇石頭;
if(試探選擇石頭能夠擺放)
擺放石頭;將該類石頭的數(shù)量減1;
else
將該類石頭的數(shù)量設(shè)為0;//使其估值函數(shù)值減小，在下一次選擇中不會被選中}
//競標
根據(jù)求得的拼圖解給出競標的排序和出價;
//競標后的調(diào)整
讀取本輪競標信息;
調(diào)整集合Sed和S;
i++;
}
使用集合Sed中的石頭進行最后一次拼圖;
5結(jié)束語
選手使用以上策略和算法實現(xiàn)的程序，參加了第18屆日本全國高專編程競賽競技組的比賽，在參賽的60多支隊伍 中，經(jīng)過兩輪的淘汰賽，成功進入最后一輪比賽。兩輪淘汰賽中，分別以小組第一和第二成績晉級，但在最后一輪比賽中敗北。失敗的原因除了人為操作失誤以外，算法也存在一定的缺陷。算法的主要缺陷在于：進行拼圖時，我們只計算一個解，即使計算出多個解，使用深度優(yōu)先的搜索算法得到的多個解也都是相近的。解的單一性造成了在比賽過程中，要買的某塊面積較大的“石頭”買不到時，不能及時調(diào)整拼圖方案，最終導(dǎo)致拼得的面積較小。賽后，經(jīng)過認真 總結(jié)以及與冠軍隊伍的交流之后，發(fā)現(xiàn)如果采用深度優(yōu)先和廣度優(yōu)先結(jié)合的算法進行拼圖，盡量得到差異較大的多個解，那么在某塊面積較大的“石頭”買不到時，便可及時地使用其它拼圖方案指導(dǎo)競標，從而爭取拼出更大的面積。
看了“人工智能期末話題論文”的人還看了：
1.人工智能期末論文