課程名稱︰電腦對局理論 課程性質︰資工系選修 課程教師︰徐讚昇 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰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/m.aspx?n=bbs/NTU-Exam/M.1742657870.A.254.html