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