1、人工智能在拼石頭游戲中的應用人工智能在拼石頭游戲中的應用引言論文聯盟.Ll.游戲的人工智能研究是人工智能的主要研究領域之一，它涉及人工智能中的搜索方法和決策規劃等。俄羅斯方塊游戲和七巧板游戲都是經典的具有啟智、益智功能的平面拼圖游戲。第18屆日本全國高專編程競賽競技組的題目，便是借鑒這兩款游戲的特點并引入競標機制而創造的一款新游戲即拼石頭。詳細規那么如下：每次比賽有6至10支隊伍參加，每支隊伍各自擁有一樣形狀、面積的一面墻和一樣金額的虛擬貨幣。墻是由假設干個單元正方形構成的，如圖1所示。圖1墻裁判方在賽前給出假設干種形狀的石頭，每種石頭有假設干塊以及各自的底價，石頭也是由假設干個單元正方形構成

2、的，但面積要比墻小的多，如圖2所示。圖2石頭每次比賽有假設干輪的競標，每輪競標中有最大競標數和最大中標數N做限制N=1。每支參賽隊按照最大競標數提供競標信息，競標信息中包括參賽隊要購置的石頭種類、為每塊石頭報出的競標價格競標價格不得低于石頭底價以及對競標石頭的排序，例如等于5時，可能的競標信息是A100，A200，20，B70，D5，表示以價格100競標石頭A，以價格200競標石頭A，并且該隊本輪競標的排序是AABD。當有多支隊伍競爭一樣種類的石頭時，該種石頭優先賣給為其排序靠前的隊伍；當多支隊伍在一樣排位上競爭一樣種類的石頭，且該種石頭數量小于競爭隊伍數量時，該種石頭優先賣給出價高的隊伍，假

3、設有兩支或兩支以上的隊伍出價一樣，那么在參與競爭的，且出價一樣的隊伍中進展二次競標，假設出價仍然一樣，那么該石頭本輪流拍。另外，假設某支隊伍在本輪已經獲得了塊數等于最大中標數N的石頭，那么其后面的競標信息無效，即該隊伍退出本輪競標。，以3支隊伍為例，假設當前裁判方有2塊石頭A、1塊石頭B、1塊石頭、2塊石頭D、3塊石頭E，本輪最大競標數和最大中標數N分別為4和2。參賽隊伍的競標信息如表1所示。表1參賽隊競標信息隊伍排序1234aA10A200B50E20b20A100B60D2021A300B100E25根據規那么，在排序1上，隊伍a以10獲得1塊石頭A，隊伍以21獲得1塊石頭；在排序2上，隊

4、伍以300獲得1塊石頭A，此時隊伍在本輪已經到達最大中標數2，該隊伍的排序3和4無效；在排序3上，隊伍b以60獲得1塊石頭B；在排序4上，隊伍a以20獲得1塊石頭E，隊伍b以20獲得1塊石頭D。每輪競標完畢后，裁判方為各隊伍分配所購得的石頭，同時公布本輪競標情況，并以剩余石頭開場下一輪的競標；各參賽隊伍，在準備開場下輪競標的同時，可以將購得的石頭拼在墻上，拼石頭時，石頭不能懸空擺放，同時每塊石頭都可以像俄羅斯方塊中的石頭一樣，旋轉90、180或270，但不能里外翻轉，例如圖2中的石頭A不能里外翻轉后當作石頭B來使用。當最后一輪競標完畢的2in后，比賽完畢，裁判方使用以下次序的評判規那么為各隊排

5、名次：拼到墻上的石頭的總面積大者獲勝；面積一樣者剩余貨幣多者獲勝；剩余貨幣一樣者剩余石頭買到但沒有拼到墻上的石頭總面積小者獲勝；剩余石頭總面積一樣者墻上沿占滿率大者獲勝；以上條件全一樣者，以石頭、剪刀、布的方式確定名次。墻的形狀、石頭的種類數、每種石頭的形狀、塊數和底價、競標輪數及每輪最大競標數和最大中標數等信息，在賽前給定。參賽隊伍需要在賽前編寫程序，指導游戲過程中的競標和拼圖。1問題分析根據引言中對游戲規那么的描繪，可知理想狀態下，使用單位面積價格最低的石頭拼滿整個墻時，一定可以獲得成功。但由于石頭數量有限，往往會出現：不能以底價或低價買到石頭；買到的石頭拼不上；論文聯盟.Ll.想買的石頭

6、買不到等現象。結合比賽結果評判標準中，拼到墻上的石頭的總面積大者獲勝為第一原那么的情況，在諸多游戲者中，誰可以買到更大面積的石頭，并盡量將買到的石頭拼在墻上，誰就能在比賽中獲勝。通過上述的簡單分析，參賽者編寫的程序應至少在買什么石頭和怎么拼石頭兩個方面給出決策和指導。也就是說，程序中要解決競標和拼圖兩個問題，競標負責幫助游戲者合理排位、合理出價；拼圖幫助游戲者合理擺放石頭。然而，競標和拼圖問題又不是互相孤立存在的，它們之間是互相制約、互相依賴的關系，即競標時要買拼圖可以使用上的石頭；拼圖時應選擇競標后買到的和在下一論競標中容易買到的石頭。同時，競標和拼圖對于石頭的要求是互相矛盾的，形狀規那么的

7、石頭在拼圖時更加容易被利用，例如圖2中的石頭D和E，但是，它們都是競標時不愿去購置的石頭，石頭D面積小浪費中標名額，石頭E面積大且形狀規那么，勢必成為緊俏商品，很難買到；反之，競標時容易買到的石頭，例如圖2中的石頭，但它在拼圖中很難被用到。如何處理競標和拼圖對于石頭要求不同的矛盾，成為獲得成功的關鍵。2策略制定根據對游戲規那么的理解和問題的分析，我們為程序的編寫在拼圖算法選擇、競標排序等方面制定如下策略：2.1拼圖算法的選擇采用深度優先的搜索算法進展拼圖，并且由墻的底部開場向上擺放石頭，保證不懸空。拼圖時在已經買到的石頭和裁判方剩余石頭兩個集合中選擇石頭兩個集合分別記做Sed和S，并優先選擇S

8、ed中的石頭，在S中選擇石頭時，按照估值函數后文中給出給石頭打分，根據每種石頭的估值以堆構造存儲S，每次選擇堆頂的石頭進展試探。2.2拼圖解確實定深度優先搜索拼圖解法時，不一定將拼滿墻作為解，即產生的解允許與墻的面積相差一定的單元格。2.3各輪競標的貨幣分配按照少多少的棗核形狀整體分配各輪使用的虛擬貨幣，這樣做的原因是：前期競標時石頭多、競爭小，中期競標時競爭劇烈應該盡量花錢，后期競標時石頭已經快賣光，為后期保存過多的貨幣沒有用途。詳細比例可適當調整。2.4每輪競標石頭的選擇在每輪競標之前進展拼圖，并在拼圖產生的解中，選擇塊面積大的，且屬于集合S的石頭作為本輪參與競標的石頭等于本輪的最大競標數

9、。2.5每輪競標的排序每輪競標時，先論文聯盟.Ll.按照需要購置的石頭的面積排降序，然后按照當前裁判方各種類的石頭數量，進展順序調整，假設在排序的前幾位上，某種類的石頭數量較多，可在一定可以買到的前提下，適當將其順序向后調整。2.6每輪競標的出價在每輪競標中，為要購置的石頭排好順序后，要為本輪所要購置石頭出價。由于最大中標數小于最大競標數，所以出價的總額要略大于最初為本輪分配的貨幣數。出價時，首先為一定可以買到的石頭出底價，然后為存在競爭的石頭按照面積、數量、排序等因素出價，面積大排序靠前、數量少的出高價，反之出低價。詳細比例可適當調整。3石頭估值函數設計為保證組成解的各個石頭中的大局部是我們

10、認為的好石頭，在使用深度優先的搜索算法進展拼圖時，需要在裁判方提供的石頭集合中優先選擇好的石頭進展試探。確定石頭的好壞需要設計關于石頭的估值函數。影響石頭好壞的因素包括面積、數量、形狀等幾個方面。在面積方面，由于受競標次數的限制，拼圖時應盡量選擇面積大的石頭，即面積越大石頭越好；在數量方面，某種類的石頭數量越多，競爭就越小，出低價甚至出底價就可買到，因此數量越多石頭越好；在形狀方面，形狀規那么的石頭容易在拼圖中使用，但是這樣的石頭不容易購置，反之，形狀不規那么石頭不易在拼圖中使用，但其面積大且容易購置，認為形狀規那么的石頭好和認為形狀不規那么的石頭好，都有各自的道理，這里我們選擇形狀不規那么的

11、石頭作為好石頭。綜合面積、數量、形狀3方面的因素，我們給出的石頭估值函數如公式1：F(x)=k1A(x)+k2R(x)+k3(x)1其中，x表示石頭；A(x)表示石頭的面積；R(x)表示石頭的凹凸度，即不規那么程度，R(x)的值等于組成該石頭矩形的個數，例如圖2中的石頭A和B的凹凸度為2，石頭的凹凸度為4，石頭D和E的凹凸度為1；(x)表示該類石頭的數量；k1、k2和k3為非負系數，用于調節這3方面所占的比重。4算法實現針對之前制定的策略，我們使用irsftVisual+6.0作為開發工具，開發了參賽程序。下面給出程序的偽代碼：讀取本次比賽信息，包括墻、石頭、競標數等;定義石頭集合Sed和S，

12、Sed初始為空，S初始為全部裁判方石頭;定義循環變量i，初始為0;hile(i競標輪次數)hile(尚未求出拼圖的解)按照石頭估值函數調整S為堆;if(Sed中存在未試探過的石頭)從Sed中選擇石頭;else從S中選擇石頭;if(試探選擇石頭可以擺放)擺放石頭;將該類石頭的數量減1;else根據求得的拼圖解給出競標的排序和出價;讀取本輪競標信息;調整集合Sed和S;i+;使用集合Sed中的石頭進展最后一次拼圖;5完畢語選手使用以上策略和算法實現的程序，參加了第18屆日本全國高專編程競賽競技組的比賽，在參賽的60多支隊伍論文聯盟.Ll.中，經過兩輪的淘汰賽，成功進入最后一輪比賽。兩輪淘汰賽中，分別以小組第一和第二成績晉級，但在最后一輪比賽中敗北。失敗的原因除了人為操作失誤以外，算法也存在一定的缺陷。算法的主要缺陷在于：進展拼圖時，我們只計算一個解，即