葡萄城競賽題目及相關(guān)說明.doc

筑夢之城座標：183.2E，92.7N。這里，有一片未開墾的土地，空曠得，呃，荒無人煙。在此，我更愿意稱之為“筑夢之地”，因為，我們即將在這里，打造一個全新的夢想之城！背景介紹這是一塊矩形的土地，被經(jīng)、緯線劃分成若干正方形的小格子。方便起見，我們將這些被經(jīng)緯線劃分出的小格子稱為“單元格”，并按橫向為行，縱向為列的方式進行描述。座標的原點在地圖的左上角，向右下遞增。下面是一張這個區(qū)域的地圖：地圖中的單元格分別被五種不同的顏色標記，這是一張規(guī)劃圖，不同的顏色代表不同的區(qū)域功能：灰色：代表此區(qū)域是非建筑用地，不能用于任何設(shè)施的建設(shè)；白色：代表此區(qū)域為未指定功能的建筑用地；綠色：代表此區(qū)域的規(guī)劃功能為住宅區(qū)；藍色：代表此區(qū)域的規(guī)劃功能為商業(yè)區(qū)；黃色：代表此區(qū)域的規(guī)劃功能為工業(yè)區(qū)。除了區(qū)域功能的規(guī)劃，我們在前期，還針對建筑的造型和功能做了詳細的規(guī)劃，所有可用的建筑的圖紙也都準備就緒。下圖所示是一些可能的建筑布局：每一個建筑用一種顏色標識，這種顏色可以是綠、藍或黃中的任意一種，代表的含意為此建筑的功能為住宅、商場或工廠。建筑布局中的小格子大小與地圖上的單元格相等。上圖中白色的格子表示空白，不是建筑的一部分。建筑在地圖上放置時，既可以覆蓋與其功能相同的單元格，也可以覆蓋與其功能不同的單元格，但不能覆蓋類型為非建筑用地的單元格。建筑物在被放置之前，可以做順時針的旋轉(zhuǎn)，旋轉(zhuǎn)的角度為90度的整數(shù)倍。下圖展示建筑物的放置及旋轉(zhuǎn)：圖中最左側(cè)是當前選擇的建筑的布局，在它的右側(cè)是地圖局部的布局。左側(cè)第三幅圖展示了，將該建筑不旋轉(zhuǎn)地放置在地圖上這個區(qū)域的方法。最右側(cè)的圖展示了，將該建筑順時針旋轉(zhuǎn)180度后，再放置到地圖上這個區(qū)域的方法。右側(cè)的兩幅圖中，粗邊框的區(qū)域為建筑物放置的區(qū)域；標注”*”的位置，是放置時應指定的座標點。好了，背景內(nèi)容介紹到這里。下面，來說說我們光榮而偉大的使命吧！光榮的使命為了把這塊“筑夢之地”建設(shè)成和諧美好的“夢想之城”，僅憑有關(guān)部門的閉門造車，是遠遠不夠的。我們在規(guī)劃之初就深刻地認識到了這一點，所以，我們誠邀各位有識之士共謀大業(yè)J。為了更合理有效地利用這塊土地，我們準備舉辦一場比賽，從所有參賽選手中選取最終的優(yōu)勝者，來承擔開發(fā)大任。每位參與競賽的選手，需要完成一個算法。在每一場角逐中，這個算法會與另外一位選手的算法隨機分組，以對弈的方式在這塊神奇的土地上展開競爭，爭取占有更多的土地，建設(shè)更多的建筑，以及獲得更多的額外的回報。而最終的勝者將成為這塊“筑夢之地”的開拓者。算法要求有關(guān)算法實現(xiàn)的細節(jié)及接口描述，請參見本文檔中的接口說明部分。這一節(jié)的描述中不會涉及到具體的技術(shù)細節(jié)。算法應實現(xiàn)以下功能：在每一次被調(diào)用時，從可用建筑列表中選擇一個未被使用的建筑，放置到地圖上的某一位置；或者，選擇不放置任何建筑到地圖上。建筑在被放置到地圖上之前，可以進行角度為90度整數(shù)倍的旋轉(zhuǎn)；算法的目標：根據(jù)規(guī)定的計分方法，獲得比對手更高的分數(shù)，并且分差越大越好。算法的限制： 時間限制：每次調(diào)用限時1s，一局比賽限時30s； 空間限制：算法執(zhí)行過程中，內(nèi)存占用不超過512MB；算法常駐內(nèi)存的部分，不超過256MB； 其它限制：如果使用多線程技術(shù)，每次調(diào)用返回前，應主動結(jié)束調(diào)用過程中主動開啟的線程。算法能夠獲得的信息包括： 地圖的大?。▽挾萕和高度H，0W,H50，寬度和高度均以單元格數(shù)量計）； 地圖上每個單元格的功能； 地圖上每個單元格的狀態(tài)（空白，或被某選手占用）； 全部可用建筑的描述（包括每個建筑的外邊界寬和高w,h，以格數(shù)計，0w,h50；建筑的功能，以及建筑圖上每個格子的狀態(tài)：建筑物或空白）； 此次調(diào)用前的最后一次操作（放置的建筑及位置），可能是對手的最后一次操作，也可能是自己的上一次操作，依調(diào)用序列而定，參見下一段中的比賽過程； 截止本次調(diào)用前算法剩余的可用時間。比賽規(guī)則每個選手的算法會與不同的對手進行若干場的比賽，每場比賽分為若干局。每局比賽的過程如下： 初始時，地圖上全部單元格狀態(tài)為空白，全部建筑可用。兩位參賽選手的剩余時間均為30s； 兩位選手分別被指派ID，A和B，自身的ID可以在算法被調(diào)用的過程中獲得。ID一經(jīng)指派，在一局比賽中不會被更改； 比賽開始后A算法和B算法被按照ABBAABBAABB的順序依次調(diào)用，直至一局比賽結(jié)束； 每次調(diào)用后，如果選手的算法正確放置了建筑，地圖上相應的單元格狀態(tài)會被更新，被放置的建筑也將被從可用建筑列表中移除。不正確的放置，即選手使用不在可用建筑列表中的建筑，或?qū)⒔ㄖ娜我夥强瞻撞糠种糜诘貓D上的非空白區(qū)域、非建筑用地之上，或置于地圖邊界之外，或者返回值非法。一局比賽在滿足以下條件中任意一條時結(jié)束： 全部可用建筑均被放置； 兩個算法在被調(diào)用后相繼選擇不放置任何建筑； 某個算法被調(diào)用時超出單次調(diào)用限時，或總時間耗盡而未返回； 某個算法在計算過程中內(nèi)存使用超限，或者在調(diào)用結(jié)束后常駐內(nèi)存的部分超限； 某個算法在被調(diào)用時引發(fā)異常； 某個算法執(zhí)行了規(guī)則不允許的操作，被伺服程序中止。每局比賽的分數(shù)計算如下： 選手每正確地放置一個建筑，獲得與該建筑面積相同的分數(shù)（建筑的面積即該建筑中非空白格子的數(shù)量）； 選手放置的建筑，每覆蓋一個與建筑功能相同的地圖單元格，獲得1分的額外獎勵； 如果某位選手成功覆蓋地圖上綠、藍或黃色中任一色單元格的個數(shù)超過該色單元格總數(shù)的一半（注意是“超過”，不是“達到或超過”），該選手放置的該色建筑每個獲得2分的額外獎勵； 比賽過程中，選手每錯誤地放置一次，減3分，并且此次放置無效。 如果一方的算法非正常結(jié)束（超時，超內(nèi)存，異?；蛞蚍欠ú僮鞫恢兄梗撨x手該局得0分，對方的得分，為本局比賽中全部可用建筑的總面積。 在一局比賽中，雙方算法的最低得分為0分，低于0分的以0分計。勝負與排名每局比賽的勝負及凈勝分 每局比賽結(jié)束，得分較高的一方獲勝； 得分較高一方，高出另一方的分數(shù)為其該局比賽的凈勝分。另一方的凈勝分為0分； 如果雙方得分相同，該局比賽為平局，雙方凈勝分均為0分。每場比賽的勝負判定進行最終評判時，主辦方會準備若干組數(shù)據(jù)的集合。每組數(shù)據(jù)包括一張地圖與一組對應的建筑。每場比賽選取兩名選手的算法，將全部數(shù)據(jù)各賽兩局。每組數(shù)據(jù)由兩個選手各執(zhí)先手比賽一局。每場比賽中，獲勝局數(shù)多的算法獲得該場比賽的勝利；如果雙方獲勝局數(shù)相同，總凈勝分高的一方獲勝；如果雙方總凈勝分也相同，該場比賽為平局?？偝煽兗芭琶鶕?jù)最終提交的作品總數(shù)及質(zhì)量，全部作品將被分為若干組，進行小組單循環(huán)賽。小組賽排名居前的將進入復賽。進入復賽的作品將再進行單循環(huán)賽，并依復賽成績進行最終排名。小組單循環(huán)賽計分方式如下： 每場比賽獲勝一方得3分，平局時雙方各得1分，失敗者得0分。 小組賽結(jié)束時，得分高的選手排名居前； 如有得分相同的選手，則在小組賽中總獲勝局數(shù)較多的選手排名居前； 如果得分和總獲勝局數(shù)均相同，排名也相同。接口設(shè)計及相關(guān)說明參賽作品應該引用名為Interfaces.dll的程序集，這個程序集中包含算法需要用到的全部接口定義。這個程序集包含一個名為GPCT2012的命名空間，本次競賽涉及的接口均包含在此命名空間內(nèi)。參賽算法需要實現(xiàn)的接口所有參賽的算法，都需要實現(xiàn)一個名為IPlayer的接口，這個接口包含一個名為Step的方法，該方法是參賽算法的入口，每一回合由伺服程序調(diào)用，它的返回值中包含算法的輸出，即這一回合的操作。以下是IPlayer接口的定義： / / 參加競賽的算法必須實現(xiàn)這個接口。 / 競賽過程中，伺服程序會調(diào)用接口中定義的Step方法。 / 所以，Step方法應該是算法的入口。 / / / 在提交的程序集中，應該有且僅有一個類型實現(xiàn)這個接口。 / public interface IPlayer / / 這個方法是算法的入口，由競賽伺服程序調(diào)用。 / / / 這個接口實現(xiàn)了一些屬性和方法，算法可以訪問它們，獲得當前的狀態(tài)信息。 / / / 每次調(diào)用結(jié)束時，應該返回一個Operation類型的實例，指示算法希望在這一步作出的操作。 / 如果算法在這一回合不作操作，請返回Operation.Empty。 / / / 建議實現(xiàn)這個方法的時候，在方法體內(nèi)添加計時邏輯，以免算法計算超時。 / Operation Step(IGameService service);下面是一個對IPlayer接口的簡單實現(xiàn)，這個算法不關(guān)心任何條件，每次調(diào)用均返回一個空的操作。 public class MyPlayer: IPlayer public Operation Step(IGameService service) return Operation.Empty; 注意，提交的程序集中應該有且僅有一個public的類型從IPlayer接口派生。獲取當前狀態(tài)在IPlayer接口的Step方法中，有一個IGameService類型的參數(shù)，IGameService包裝了一些屬性和方法，使得選手實現(xiàn)的算法能夠獲取相關(guān)的狀態(tài)信息。下面是IGameService接口的定義： / / 這個接口中包含一些屬性和方法，選手實現(xiàn)的算法可以通過它們獲取當前的狀態(tài)和信息。 / public interface IGameService / / 獲取一個IMap的實例，這個實例包含地圖信息。 / IMap Map get; / / 獲取一個只讀的IConstruction集合，這個集合中包含當前可用的建筑。 / ReadOnlyCollection Constructions get; / / 獲取一個Operation實例，這個實例包含本次方法調(diào)用前的最后一次操作。 / / / 這個實例中包含的操作，可能是對方的最后一次操作，也可能是自己的最后一次操作，具體情況取決于調(diào)用順序。 / 如果這是本局比賽中的第一次調(diào)用，這個實例的值為Operation.Empty。 / Operation LastOperation get; / / 獲取上一次執(zhí)行操作的選手的ID。 / / / 一個可空的PlayerID枚舉值，指示上一次執(zhí)行了操作的選手的ID。 / 這個值為空(null)時，表示本次調(diào)用是這局比賽的第一次調(diào)用。 / PlayerID? LastOperator get; / / 通過調(diào)用本方法獲得算法被分配的ID。 / / / 傳入一個IPlayer的實例，這個實例應該是實現(xiàn)當前算法的類型的實例。 / / / 方法的返回值是與傳入實例對應的ID。 / / / 算法實例的ID在比賽開始時分配，先于任何一次方法的調(diào)用。 / ID一經(jīng)分配就不會被更改，所以這個方法的返回值可以被存儲在算法實例的內(nèi)部。 / / / 如果傳入的實例不是競賽伺服程序在競賽開始時創(chuàng)建并分配了ID的實例中的任意一個， / 則會引發(fā)ArgumentException。 / PlayerID GetPlayerID(IPlayer player); / / 通過調(diào)用本方法獲得算法在本次調(diào)用前的剩余時間。 / / / 傳入一個IPlayer的實例，這個實例應該是實現(xiàn)當前算法的類型的實例。 / / / 一個TimeSpan實例。 / / / 請注意，本方法的返回值，指示的時間是本次算法的Step方法被調(diào)用之前的剩余時間， / 而不是這個方法調(diào)用時刻的剩余時間。 / 每次調(diào)用過程中，算法消耗的時間應自行計算。 / TimeSpan GetRemainingTime(IPlayer player);其它接口的定義 IMap / / 這個接口定義了一幅地圖的基本信息。 / public interface IMap / / 獲取一個整形值，指示地圖的寬度。 / int Width get; / / 獲取一個整形值，指示地圖的高度。 / int Height get; / / 獲取一個IBlock實例，這個實例包含對應單元格的信息。 / / / 單元格的橫座標。 / / / 單元格的縱座標。 / / / 座標指向的單元格所對應的IBlock實例。 / / / 傳入的橫、縱座標的值，應該大于等于0，小于寬度或高度。 / / / 當傳入的橫、縱座標超出規(guī)定的范圍時，將引發(fā)ArgumentOutOfRange異常。 / IBlock thisint x, int y get; IBlock / / 這個接口定義了一個單元格的信息。 / public interface IBlock / / 獲取一個DistrictType值，該值指示當前單元格的類型。 / DistrictType Type get; / / 獲取一個BlockStatus值，該值指示當前單元格的狀態(tài)。 / BlockStatus Status get; DistrictType / / 這個枚舉定義了地圖上單元格的類型。 / public enum DistrictType / / 表示生活區(qū)。 / Living, / / 表示工業(yè)區(qū)。 / Industrial, / / 表示商業(yè)區(qū)。 / Business, / / 表示未指定類型的區(qū)域?？梢栽谠搮^(qū)域放置建筑物。 / Unspecified, / / 表示非建筑區(qū)域。不可以在該區(qū)域放置建筑物。 / Frozen, BlockStatus / / 這個枚舉定義了地圖上單元格的狀態(tài)。 / public enum BlockStatus / / 表示未放置任何建筑物。 / Empty, / / 表示當前單元格被選手A的建筑物覆蓋。 / TakenByPlayerA, / / 表示當前單元格被選手B的建筑物覆蓋。 / TakenByPlayerB, IConstruction / / 這個接口定義了建筑物的基本信息。 / public interface IConstruction / / 獲取一個整形值，該值唯一標識一個建筑物。 / int ID get; / / 獲取一個整形值，指示該建筑物外邊界的寬度。 / int Width get; / / 獲取一個整形值，指示該建筑物外邊界的高度。 / int Height get; / / 獲取一個ConstructionType值，指示該建筑的類型。 / ConstructionType Type get; / / 獲取一個布爾值，指示對應座標處是否為建筑物的一部分。 / / / 要獲取信息的位置對應的橫座標。 / / / 要獲取信息的位置對應的縱座標。 / / / 一個布爾值，如果座標對應處是建筑物的一部分，值為true， / 否則值為false. / / / 傳入的橫、縱座標的值，應該大于等于0，小于寬度或高度。 / / / 當傳入的橫、縱座標超出規(guī)定的范圍時，將引發(fā)ArgumentOutOfRange異常。 / bool thisint x, int y get; ConstructionType / / 這個枚舉定義建筑物的類型。 / public enum ConstructionType / / 表示住宅。 / House, / / 表示工廠。 / Factory, / / 表示商場。 / Market, PlayerID / / 這個枚舉定義競賽中雙方算法的ID。 / public enum PlayerID / / 第一輪先手的算法的ID。 / PlayerA, / / 第一輪后手的算法的ID。 / PlayerB, Operation / / 這個類型包含一次建造操作的信息。 / public struct Operation / / 這個實例表示一次“空”的操作，即不執(zhí)行任何操作。 / public static Operation Empty = new Operation(-1, 0, Point.Empty); / / 操作對應的建筑物的ID。 / public int ConstructionID; / / 建筑物順時針旋轉(zhuǎn)的次數(shù)。每次旋轉(zhuǎn)的角度為90度。 / public int Rotation; / / 建筑物放置時，左上角單元格對應的地圖上的座標。 / / / 這個值應始終指示建筑物左上角單元格被放置的位置， / 并且，不論左上角位置是否是建筑物的一部分。 / 在建筑物發(fā)生旋轉(zhuǎn)之后，指向旋轉(zhuǎn)后的左上角單元格。 / public Point Position; / / 創(chuàng)建一個Operation的實例。 / / / 操作對應的建筑物的ID。 / / / 建筑物順時針旋轉(zhuǎn)的次數(shù)。每次旋轉(zhuǎn)的角度為90度。 / / / 建筑物放置時，左上角單元格對應的地圖上的座標。 / public Operation(int constructionID, int rotation, Point position) ConstructionID = constructionID; Rotation = rotation; Position = position; public static bool operator =(Operation a, Operation b) return a.ConstructionID = b.ConstructionID & a.Rotation = b.Rotation & a.Position = b.Position; public static bool operator !=(Operation a, Operation b) return !(a = b); public override bool Equals(object obj) return this = (Operation)obj; public override int GetHashCode() return base.GetHashCode(); 示例下面這個對IPlayer的實現(xiàn)，展示了對以上大部分接口的使用方法，僅供參考。 public class MyPlayer : IPlayer private PlayerID? _myID; private TimeSpan _timeLimit = TimeSpan.FromMilliseconds(100); Random rand = new Random(); private int _extraPoints; #region IPlayer Members public Operation Step(IGameService service) / use a stopwatch to calculate the time used in this method. Stopwatch watch = new Stopwatch(); watch.Start(); / get the remaining time before this call. TimeSpan remainingTime = service.GetRemainingTime(this); / use 900ms instead of 1s as the time limit of a single call, this should be decided by yourself. remainingTime = remainingTime TimeSpan.FromMilliseconds(900) ? TimeSpan.FromMilliseconds(900) : remainingTime; / check if the remaining time is enough for the following operation. / the time limit should be calculated by the performance test result of the following logic. if (remainingTime _timeLimit) return Operation.Empty; / get the assigned id. if (!_myID.HasValue) _myID = service.GetPlayerID(this); / get the last operation and last operator. Operation lastOperation = service.LastOperation; PlayerID? lastOperator = service.LastOperator; / some thing could be done here with the info of last operation and last operator. IMap map = service.Map as IMap; ReadOnlyCollection constructions = service.Constructions as ReadOnlyCollection; / try find a property operation within available time. while (remainingTime - watch.Elapsed _timeLimit) / get a random number, then choose position and construction with the random number. / this is just a sample to show how the interfaces are used, / you should decide how to choose these your self. int randNum = rand.Next(); int x = randNum % map.Width; int y = randNum % map.Height; int constIndex = randNum % constructions.Count; IConstruction construction = constructionsconstIndex; int extra = 0; / check whether the construction can be placed at the position. /