挑戰與技能的自動評估-以益智遊戲"數獨"為例

Abstract

對於難度如何分類，以前很多學者提出了不少方法去做探討，大部分都是先針對如何把問題有效解決，再根據解決的方法對它的複雜度做分析，藉此對難度做評估。但是，如此一來很有可能會因為不同的問題，會有不一樣的解題技巧，進而影響解題的複雜度。再者，並不是所有電腦解題方式都是適合人類的，換句話說，也就是一般人不會用這些方式去解決問題，所以這些方法的複雜度自然就無法反映出人類所感知到的難度。

因此本研究嘗試以人的角度去構想一個人在解題過程當中會用什麼方式去解決問題。本研究以這樣的概念，對數獨解題程式做設計，量化解題過程的複雜度，並與實際人類解題速度做比較，找出評估數獨難度的方程式。利用此方程式，我們可以對每個數獨關卡計算其難度值，因此可以對多個數獨關卡作難度的排序，以及自動挑選適合難度的關卡給玩家。本研究並發現在解數獨的過程當中，從一開始至解完一題，，搜尋樹中分支的不確定性、猜測次數和回溯的次數，對於人類所感知的難度有很大的影響。

How to define the difficulty of a problem? In the past, many scholars have invented a lot of ways to do it, mainly on how to solve the problem more effectively, and then according to the complexity of the method, to provide a way of assessing the degree of difficulty. However, different problems require different problem-solving skills. Therefore, it will affect the complexity of solving problems a lot. Moreover, not every computer problem-solving approach is suitable for human, in other words, it is not necessary for the average person using these skills to solve the problem.

Therefore, this study attempts to think about a person in the problem solving process so as to define the difficulty of the problem from human perspective. Klein pointed out that ordinary people use common heuristic method to solve problems, such as means-end analysis and trial-and-error. For such concept, we design a Sudoku AI program to quantify the complexity of AI program. Then, we compare the actual rate of human solving time to find the formula that represents the difficulty of Sudoku. In the process of solving Sudoku, we find that branch of uncertain nodes in search tree and the times of guessing and backtracking have an impact on the difficulty of Sudoku.