课程名称︰电脑对局理论 课程性质︰选修 课程教师︰徐赞昇 开课学院：理学院 开课系所︰资工所 考试日期（年月日）︰ 07/11/08 - 07/11/22 考试时限（分钟）：20160 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Mid-Term Exam -- Theory of Computer Games -- November 8, 2007 注意事项： 1. Take home exam. You are not allowed to discuss the questions and answers with anyone else except TA and the teacher. You are not allowed to get helps from anyone else. Reading original papers and books are allowed. 2. Due date: 2:20pm, Nov 22, 2007. 3. Good luck! 1. (15%) In page 14 of the paper "Disjoint pattern database heuristics", two key differences between disjoint pattern databases and non-additive databases are listed. (a) (3%) What is the first difference? (b) (12%) THe second difference is "disjoint databases do not consider the blank position, decreasing their size". Why is this true? 2. (20%) Describe a Depth-first Iterative Deepening A* approach with some sorts of pattern databases to solve the Rubik's cube problem. In your discussion, you need to describe admissible heuristics and prove it is admissible. You need also to discuss the tradeoff between database size and solution time. 3. (15%) Using the hints, i.e., an induction argument, provided in the slides, or using your own intuition, to prove the game of n*m Hex has exactly one winner for any n>=1 and m>=1. 4. (15%) Using the following rules and getting the ideas from Shannon's paper, try to discuss a possible evaluating function for Chinese Dark Chess which is the topic of your final project. ．先决定谁先走 ．一次走一步或翻一子 ．先走者第一岁翻出的棋子颜色即为他的，对手则为另一色棋子 ．子力大小：王>仕>相>车>马>炮>兵，子力大可吃子力小，同子力可互吃，但 王不可吃兵，兵可吃王，炮可隔一子吃任何已翻开之子，不可连跳。 ．吃完对方子为胜，连续六十步双方不吃子为和 ．(补充) 炮不可走步吃子。 5. (15%) In the analysis of Alpha-beta cut, a perfect-order tree and the set of critical nodes are defined. Prove the set of critical nodes in a perfect-order tree equals to the union of the sets of type-1, type-2 and type-3 nodes. ．Hint: YOu need to prove if and only if. 6. (20%) Design a game tree with at least 15 nodes and at least depth 4 so that ．(10%) using alpha-beta cut searches less nodes than Scout by a given move ordering; ．(10%) using Scout searching less nodes that alpha-beta by another move ordering. In your answer, nodes searches by both methods needed to be traced and reported. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.112.195.94 ※ 编辑: abcde1234 来自: 59.112.195.94 (02/01 18:07)