课程名称︰电脑对局理论 课程性质︰资工系选修 课程教师︰徐赞昇 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰2018/11/08 考试时限（分钟）：180 试题 : 第一单元：解释名词及比较 (40 points) Define the term(s), give an example for each, and provide a comparison if there are more than one terms. If the words "in the context" is given, be sure to use that context. 1. 个别名词解释，各举一例子和两者之比较 (a) (8 points) fail hard vs fail soft 2. 名词解释，含一例子 (a) (8 points) move ordering in the context of Chinese Dark Chess (暗棋). FYI: the rule of Chinese Dark Chess are appended at the end. (b) (8 points) pawn structure in the context of Chess (西洋棋) (c) (8 points) asymmetric game (d) (8 points) one-move equalization 第二单元：简答题 (80 points) 要有理由说明，没有理由说明不给分。 3. (16 points) The game Go-Moku (五子棋) is first-player win. However, we cannot use the strategy stealing argument to prove it. Hint: The rule of Go-Moku is each player alternatively plays one stone of his own color at a time on a 15×15 grid. The player who makes a horizontal, vertical or diagonal string of his own color with a length of at least 5 wins instantly. (a) (8 points) Give all pre-conditions of a game that must hold in order for the strategy stealing argument to work. (b) (8 points) List and explain all pre-conditions that Go-Moku does not have so that it cannot use the strategy stealing argument. 4. (8 points) In the class, we have given 4 different taxonomies to classify games. Describe and explain what are the 4 taxonomies that the game Chinese Dark Chess (暗棋) is in. FYI: the rules of Chinese Dark Chess are appended at the end. 5. (16 points) In the class we have shown changing the cost function f(P) of a partial solution P in the A* algorithm can make A* behave like another search procedure. For example, if f(P) is the $-length(P)$, then it is DFS. Make necessary, but minimal, changes to A* so that it will behave like bi-direc- tional search. 6. (40 points) Hydra on Grid[1] is a tile-sliding single-player game played on a rectangle N×N grid. Initially there are $N^2-1$ tiles numbered from 1 to $N^2-1$, randomly placed and there is an empty cell. A legal move is to move a tile numbered i up, down, left or right to (1) an adjacent empty cell, or (2) collapse it into the tile numbered i+1 that is adjacent where after the move the tile numbered i is removed. The goal of this game is to remove all, but the tile numbered $N^2-1$ from the grid using the least number of moves. An example of a 3×3 game is shown in the figure. ┌─┬─┬─┐ ┌─┬─┬─┐ │ 2│ 5│ 6│ │ 2│ 5│ 6│ ├─┼─┼─┤ ├─┼─┼─┤ │ 8│ 1│ 3│ → │ 8│ 1│ 3│ ├─┼─┼─┤ ├─┼─┼─┤ │ 4┼> │ 7│ │ │ 4│ 7│ └─┴─┴─┘ └─┴─┴─┘ slides a tile into an empty cell ┌─┬─┬─┐ ┌─┬─┬─┐ │ 2│ 5┼>6│ │ 2│ │ 6│ ├─┼─┼─┤ ├─┼─┼─┤ │ 8│ 1│ 3│ → │ 8│ 1│ 3│ ├─┼─┼─┤ ├─┼─┼─┤ │ │ 4│ 7│ │ │ 4│ 7│ └─┴─┴─┘ └─┴─┴─┘ collapse the tile "5" into the tile "6" (a) (10 points) Analyze the state space of Hydra on Grid using a mathematical formula. Note that you need to explain your answer. Hint: the better your estimation the better is your score. (b) (10 points) Prove or disprove every legal position has a solution of a finite length. (c) (20 points) Give a non-trivial admissible heuristic function for Hydra on Grid. Prove the provided function is admissible. Hint: the better your heuristic function is, the better your score is, and a plain and simple Manhattan distance of the largest tile is not good enough. Hint: you can make use of pre-computed pattern databases and also some mathematical/ geometric properties. [1]: Invented for TCG2018, all rights reserved. 第三单元：演算题 (60 points) 要有演算过程，没有过程答案对也不给分。(You need to explain how the answer(s) are obtained, not just the answer(s).) 7. (30 points) Let T be a perfect-ordering game tree with the root being a MAX node. T has h, h ≧ 0, levels. Note that the level of the root is 0. Each node at the i-th level, 0 ≦ i < h, has exactly 4 children. Note that the h- th level consists of all leaves. Using the notations in the class, critical nodes are classified into 5 different types, namely types 1, 2.1, 2.2, 3.1 and 3.2. (a) (15 points) What is the maximum number of different types of critical nodes that a single level can have? Explain and give an example which level this may be. If this number is less than 5, then prove why this is the maximum that you can get. Note: Types 2.1 and 2.2 are counted as different types. So are types 3.1 and 3.2. (b) (15 points) Let $N_{\ell, 2.2}$ (respectively, $N_{\ell, 3.2}$) be the numbers of type 2.2 (respectively 3.2) nodes in level $\ell$. Is it pos- sible that there exists $\ell$ so that $N_{\ell, 2.2} \ge N_{\ell, 3.2}$? If yes, give all conditions of $\ell$ so that this is true. If no, prove it. 8. (30 points) Consider the following game tree whose values of leaves are given in the view point of the root player: ○ │ ├────┬────╮ ● ● ● │ 14 │ ├─────╮ ├─┬─╮ ○ ○ ○ ○ ○ │ │ │ 17 9 ├─╮ ├─╮ ├─╮ ● ● ● ● ● ● 9 │ │ 4 10 1 ├─╮ │ ○ ○ ○ 8 │ 13 │ ● 13 Trace the original Alpha-Beta algorithm (MiniMax version) F1' and G1' for this game tree by setting the initial window to be [-∞, ∞]. Assume the children of an internal node is visited from the left to the right in se- quence. You need to take note on nodes cut, the procedure called, the value returned, the values of the window during each step. Rules for Chinese Dark Chess ‧ 先把所有象棋棋子面向下 randomly 排在 4×8 方格中，每格一子。 － 分红黑两方，每方有王×1，仕×2，相×2，车×2，马×2，炮×2，兵×5，共十六 子。 － 面朝下称暗子，面朝上称明子。 ‧ 以规定之方式决定谁先走，若未规定则以猜拳或双方同意之公平方式决定谁先走。 ‧ 双方轮下，每次一手，不可 pass，除炮（需为明子）可跳越任一子吃敌明子外，其余明 子一次走垂直或水平一步（不可走出棋盘）或翻开棋盘上未翻开的一暗子。 ‧ 先走者第一步翻出的棋子颜色即为他的，对手则为另一色棋子。 ‧ 每格最多放一棋子，走到对方棋子的格子为吃子步，被吃子自盘面移除。 － 子力大小：王＞仕＞相＞车＞马＞炮＞兵。 － 除例外情况外，子力大可以走步吃子力小，子力小不可吃子力大。 － 除例外情况外，同子力可以走步互吃。 － 例外情况： ＊ 王不可吃兵。 ＊ 兵可吃王。 ＊ 炮不可以走步吃兵或炮。 － 炮可隔一子跳吃任何已翻开之对方棋子，但不可连跳。 ＊ 所隔之子可以是未翻开之子，也可以是翻开之任何颜色之棋子。 ＊ 炮和所隔之及被吃之对方棋子在同一行或同一列，且所隔之子在炮与被吃之对方 棋子中间。 ＊ 炮和所隔之子之间无任何棋子。 ＊ 所隔之子和被吃之对方棋子间无任何棋子。 ‧ 吃完对方子为胜。 ‧ 无合法步判输。 ‧ 双方合计共连续 60 步均不吃子或翻子为和。 ‧ 循环盘面连续三次出现为和。 ‧ 所有走步必须在十五分钟内完成。 ‧ 每局犯规二次就输。 ‧ 犯规时由 Judge 决定棋局接续进行方式。 ‧ 对所有棋局 Judge 有最终裁判的权利。 以下本人附注 1. 第6题的第2张图原先是错的(把5推进6前 4的位置在(3, 1)而非(3, 2)) 已修正 2. 排版困难(i.e. 上下标 特殊符号等)的部分用tex语法呈现 3. 3张图在等宽字型下看起来应该都不会太糟(?) -- --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.230.47.64 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1742657870.A.254.html