課程名稱︰電腦對局理論
課程性質︰選修
課程教師︰徐贊昇
開課學院：理學院
開課系所︰資工所
考試日期（年月日）︰ 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)