葡萄城竞赛题目及相关说明.doc

筑梦之城座标：183.2E，92.7N。这里，有一片未开垦的土地，空旷得，呃，荒无人烟。在此，我更愿意称之为“筑梦之地”，因为，我们即将在这里，打造一个全新的梦想之城！背景介绍这是一块矩形的土地，被经、纬线划分成若干正方形的小格子。方便起见，我们将这些被经纬线划分出的小格子称为“单元格”，并按横向为行，纵向为列的方式进行描述。座标的原点在地图的左上角，向右下递增。下面是一张这个区域的地图：地图中的单元格分别被五种不同的颜色标记，这是一张规划图，不同的颜色代表不同的区域功能：灰色：代表此区域是非建筑用地，不能用于任何设施的建设；白色：代表此区域为未指定功能的建筑用地；绿色：代表此区域的规划功能为住宅区；蓝色：代表此区域的规划功能为商业区；黄色：代表此区域的规划功能为工业区。除了区域功能的规划，我们在前期，还针对建筑的造型和功能做了详细的规划，所有可用的建筑的图纸也都准备就绪。下图所示是一些可能的建筑布局：每一个建筑用一种颜色标识，这种颜色可以是绿、蓝或黄中的任意一种，代表的含意为此建筑的功能为住宅、商场或工厂。建筑布局中的小格子大小与地图上的单元格相等。上图中白色的格子表示空白，不是建筑的一部分。建筑在地图上放置时，既可以覆盖与其功能相同的单元格，也可以覆盖与其功能不同的单元格，但不能覆盖类型为非建筑用地的单元格。建筑物在被放置之前，可以做顺时针的旋转，旋转的角度为90度的整数倍。下图展示建筑物的放置及旋转：图中最左侧是当前选择的建筑的布局，在它的右侧是地图局部的布局。左侧第三幅图展示了，将该建筑不旋转地放置在地图上这个区域的方法。最右侧的图展示了，将该建筑顺时针旋转180度后，再放置到地图上这个区域的方法。右侧的两幅图中，粗边框的区域为建筑物放置的区域；标注”*”的位置，是放置时应指定的座标点。好了，背景内容介绍到这里。下面，来说说我们光荣而伟大的使命吧！光荣的使命为了把这块“筑梦之地”建设成和谐美好的“梦想之城”，仅凭有关部门的闭门造车，是远远不够的。我们在规划之初就深刻地认识到了这一点，所以，我们诚邀各位有识之士共谋大业J。为了更合理有效地利用这块土地，我们准备举办一场比赛，从所有参赛选手中选取最终的优胜者，来承担开发大任。每位参与竞赛的选手，需要完成一个算法。在每一场角逐中，这个算法会与另外一位选手的算法随机分组，以对弈的方式在这块神奇的土地上展开竞争，争取占有更多的土地，建设更多的建筑，以及获得更多的额外的回报。而最终的胜者将成为这块“筑梦之地”的开拓者。算法要求有关算法实现的细节及接口描述，请参见本文档中的接口说明部分。这一节的描述中不会涉及到具体的技术细节。算法应实现以下功能：在每一次被调用时，从可用建筑列表中选择一个未被使用的建筑，放置到地图上的某一位置；或者，选择不放置任何建筑到地图上。建筑在被放置到地图上之前，可以进行角度为90度整数倍的旋转；算法的目标：根据规定的计分方法，获得比对手更高的分数，并且分差越大越好。算法的限制： 时间限制：每次调用限时1s，一局比赛限时30s； 空间限制：算法执行过程中，内存占用不超过512MB；算法常驻内存的部分，不超过256MB； 其它限制：如果使用多线程技术，每次调用返回前，应主动结束调用过程中主动开启的线程。算法能够获得的信息包括： 地图的大小（宽度W和高度H，0W,H50，宽度和高度均以单元格数量计）； 地图上每个单元格的功能； 地图上每个单元格的状态（空白，或被某选手占用）； 全部可用建筑的描述（包括每个建筑的外边界宽和高w,h，以格数计，0w,h50；建筑的功能，以及建筑图上每个格子的状态：建筑物或空白）； 此次调用前的最后一次操作（放置的建筑及位置），可能是对手的最后一次操作，也可能是自己的上一次操作，依调用序列而定，参见下一段中的比赛过程； 截止本次调用前算法剩余的可用时间。比赛规则每个选手的算法会与不同的对手进行若干场的比赛，每场比赛分为若干局。每局比赛的过程如下： 初始时，地图上全部单元格状态为空白，全部建筑可用。两位参赛选手的剩余时间均为30s； 两位选手分别被指派ID，A和B，自身的ID可以在算法被调用的过程中获得。ID一经指派，在一局比赛中不会被更改； 比赛开始后A算法和B算法被按照ABBAABBAABB的顺序依次调用，直至一局比赛结束； 每次调用后，如果选手的算法正确放置了建筑，地图上相应的单元格状态会被更新，被放置的建筑也将被从可用建筑列表中移除。不正确的放置，即选手使用不在可用建筑列表中的建筑，或将建筑的任意非空白部分置于地图上的非空白区域、非建筑用地之上，或置于地图边界之外，或者返回值非法。一局比赛在满足以下条件中任意一条时结束： 全部可用建筑均被放置； 两个算法在被调用后相继选择不放置任何建筑； 某个算法被调用时超出单次调用限时，或总时间耗尽而未返回； 某个算法在计算过程中内存使用超限，或者在调用结束后常驻内存的部分超限； 某个算法在被调用时引发异常； 某个算法执行了规则不允许的操作，被伺服程序中止。每局比赛的分数计算如下： 选手每正确地放置一个建筑，获得与该建筑面积相同的分数（建筑的面积即该建筑中非空白格子的数量）； 选手放置的建筑，每覆盖一个与建筑功能相同的地图单元格，获得1分的额外奖励； 如果某位选手成功覆盖地图上绿、蓝或黄色中任一色单元格的个数超过该色单元格总数的一半（注意是“超过”，不是“达到或超过”），该选手放置的该色建筑每个获得2分的额外奖励； 比赛过程中，选手每错误地放置一次，减3分，并且此次放置无效。 如果一方的算法非正常结束（超时，超内存，异常或因非法操作而被中止），该选手该局得0分，对方的得分，为本局比赛中全部可用建筑的总面积。 在一局比赛中，双方算法的最低得分为0分，低于0分的以0分计。胜负与排名每局比赛的胜负及净胜分 每局比赛结束，得分较高的一方获胜； 得分较高一方，高出另一方的分数为其该局比赛的净胜分。另一方的净胜分为0分； 如果双方得分相同，该局比赛为平局，双方净胜分均为0分。每场比赛的胜负判定进行最终评判时，主办方会准备若干组数据的集合。每组数据包括一张地图与一组对应的建筑。每场比赛选取两名选手的算法，将全部数据各赛两局。每组数据由两个选手各执先手比赛一局。每场比赛中，获胜局数多的算法获得该场比赛的胜利；如果双方获胜局数相同，总净胜分高的一方获胜；如果双方总净胜分也相同，该场比赛为平局。总成绩及排名根据最终提交的作品总数及质量，全部作品将被分为若干组，进行小组单循环赛。小组赛排名居前的将进入复赛。进入复赛的作品将再进行单循环赛，并依复赛成绩进行最终排名。小组单循环赛计分方式如下： 每场比赛获胜一方得3分，平局时双方各得1分，失败者得0分。 小组赛结束时，得分高的选手排名居前； 如有得分相同的选手，则在小组赛中总获胜局数较多的选手排名居前； 如果得分和总获胜局数均相同，排名也相同。接口设计及相关说明参赛作品应该引用名为Interfaces.dll的程序集，这个程序集中包含算法需要用到的全部接口定义。这个程序集包含一个名为GPCT2012的命名空间，本次竞赛涉及的接口均包含在此命名空间内。参赛算法需要实现的接口所有参赛的算法，都需要实现一个名为IPlayer的接口，这个接口包含一个名为Step的方法，该方法是参赛算法的入口，每一回合由伺服程序调用，它的返回值中包含算法的输出，即这一回合的操作。以下是IPlayer接口的定义： / / 参加竞赛的算法必须实现这个接口。 / 竞赛过程中，伺服程序会调用接口中定义的Step方法。 / 所以，Step方法应该是算法的入口。 / / / 在提交的程序集中，应该有且仅有一个类型实现这个接口。 / public interface IPlayer / / 这个方法是算法的入口，由竞赛伺服程序调用。 / / / 这个接口实现了一些属性和方法，算法可以访问它们，获得当前的状态信息。 / / / 每次调用结束时，应该返回一个Operation类型的实例，指示算法希望在这一步作出的操作。 / 如果算法在这一回合不作操作，请返回Operation.Empty。 / / / 建议实现这个方法的时候，在方法体内添加计时逻辑，以免算法计算超时。 / Operation Step(IGameService service);下面是一个对IPlayer接口的简单实现，这个算法不关心任何条件，每次调用均返回一个空的操作。 public class MyPlayer: IPlayer public Operation Step(IGameService service) return Operation.Empty; 注意，提交的程序集中应该有且仅有一个public的类型从IPlayer接口派生。获取当前状态在IPlayer接口的Step方法中，有一个IGameService类型的参数，IGameService包装了一些属性和方法，使得选手实现的算法能够获取相关的状态信息。下面是IGameService接口的定义： / / 这个接口中包含一些属性和方法，选手实现的算法可以通过它们获取当前的状态和信息。 / public interface IGameService / / 获取一个IMap的实例，这个实例包含地图信息。 / IMap Map get; / / 获取一个只读的IConstruction集合，这个集合中包含当前可用的建筑。 / ReadOnlyCollection Constructions get; / / 获取一个Operation实例，这个实例包含本次方法调用前的最后一次操作。 / / / 这个实例中包含的操作，可能是对方的最后一次操作，也可能是自己的最后一次操作，具体情况取决于调用顺序。 / 如果这是本局比赛中的第一次调用，这个实例的值为Operation.Empty。 / Operation LastOperation get; / / 获取上一次执行操作的选手的ID。 / / / 一个可空的PlayerID枚举值，指示上一次执行了操作的选手的ID。 / 这个值为空(null)时，表示本次调用是这局比赛的第一次调用。 / PlayerID? LastOperator get; / / 通过调用本方法获得算法被分配的ID。 / / / 传入一个IPlayer的实例，这个实例应该是实现当前算法的类型的实例。 / / / 方法的返回值是与传入实例对应的ID。 / / / 算法实例的ID在比赛开始时分配，先于任何一次方法的调用。 / ID一经分配就不会被更改，所以这个方法的返回值可以被存储在算法实例的内部。 / / / 如果传入的实例不是竞赛伺服程序在竞赛开始时创建并分配了ID的实例中的任意一个， / 则会引发ArgumentException。 / PlayerID GetPlayerID(IPlayer player); / / 通过调用本方法获得算法在本次调用前的剩余时间。 / / / 传入一个IPlayer的实例，这个实例应该是实现当前算法的类型的实例。 / / / 一个TimeSpan实例。 / / / 请注意，本方法的返回值，指示的时间是本次算法的Step方法被调用之前的剩余时间， / 而不是这个方法调用时刻的剩余时间。 / 每次调用过程中，算法消耗的时间应自行计算。 / TimeSpan GetRemainingTime(IPlayer player);其它接口的定义 IMap / / 这个接口定义了一幅地图的基本信息。 / public interface IMap / / 获取一个整形值，指示地图的宽度。 / int Width get; / / 获取一个整形值，指示地图的高度。 / int Height get; / / 获取一个IBlock实例，这个实例包含对应单元格的信息。 / / / 单元格的横座标。 / / / 单元格的纵座标。 / / / 座标指向的单元格所对应的IBlock实例。 / / / 传入的横、纵座标的值，应该大于等于0，小于宽度或高度。 / / / 当传入的横、纵座标超出规定的范围时，将引发ArgumentOutOfRange异常。 / IBlock thisint x, int y get; IBlock / / 这个接口定义了一个单元格的信息。 / public interface IBlock / / 获取一个DistrictType值，该值指示当前单元格的类型。 / DistrictType Type get; / / 获取一个BlockStatus值，该值指示当前单元格的状态。 / BlockStatus Status get; DistrictType / / 这个枚举定义了地图上单元格的类型。 / public enum DistrictType / / 表示生活区。 / Living, / / 表示工业区。 / Industrial, / / 表示商业区。 / Business, / / 表示未指定类型的区域。可以在该区域放置建筑物。 / Unspecified, / / 表示非建筑区域。不可以在该区域放置建筑物。 / Frozen, BlockStatus / / 这个枚举定义了地图上单元格的状态。 / 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，小于宽度或高度。 / / / 当传入的横、纵座标超出规定的范围时，将引发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 / / 这个实例表示一次“空”的操作，即不执行任何操作。 / public static Operation Empty = new Operation(-1, 0, Point.Empty); / / 操作对应的建筑物的ID。 / public int ConstructionID; / / 建筑物顺时针旋转的次数。每次旋转的角度为90度。 / public int Rotation; / / 建筑物放置时，左上角单元格对应的地图上的座标。 / / / 这个值应始终指示建筑物左上角单元格被放置的位置， / 并且，不论左上角位置是否是建筑物的一部分。 / 在建筑物发生旋转之后，指向旋转后的左上角单元格。 / public Point Position; / / 创建一个Operation的实例。 / / / 操作对应的建筑物的ID。 / / / 建筑物顺时针旋转的次数。每次旋转的角度为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的实现，展示了对以上大部分接口的使用方法，仅供参考。 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. /