コンピュータゲームプレイヤにおける評価要素の自動生成に関する研究(評価関数,<特集>ゲームプログラミング)  [in Japanese] Automatic Generation of Evaluation Features for Computer Game Players(Evaluation Function,<Special Issue> Game Programming)  [in Japanese]

正確な評価関数の生成はコンピュータゲームプレイヤにおいてその振舞いを決める重要な要素の1つである.評価関数はゲームにおける局面の特徴を表す評価要素の重み付き線形和で表現するのが一般的である.この評価要素の選択にはその対象とするゲームに関する深い知識が必要である.本稿ではゲームの履歴に基づいた高速でスケーラブルな評価要素の自動生成手法について提案する.本手法では多くのゲームに応用可能な2クラスの分類問題を対象とし,評価要素を単純な特徴の組合せで表現し,頻度と条件付き相互情報量の2つの指標を用いて選択する.本手法の評価としては200,000のOthelloの局面を用い評価要素の生成を行った.生成した評価要素を用いたNaive Bayesian分類器は他の分類器による単純な特徴を用いた分類よりも良い精度で分類できた.また分割処理によって大きな問題を扱え,並列化により高速に実行できることも確認できた.

Accuracy of evaluation functions is one of the critical factors in computer game players. Evaluation functions are usually constructed manually as a weighted linear combination of evaluation features that characterize game positions. Selecting evaluation features and tuning their weights require deep knowledge of the game. In this paper, we propose a new fast and scalable method to automatically generate game position features based on game records to be used in evaluation functions. Our method treats two-class problems which are common in many types of games. Evaluation features are built as conjunctions of the simplest features representing positions. We select these features based on two measures : frequency and conditional mutual information. To evaluate the proposed method, we applied it to 200, 000 Othello positions. The proposed selection method is found to be effective, because the Naive Bayesian classifier using automatically generated features is more accurate than other classifiers using simple features. We also show that this generation method can treat large problems by dividing them into small problems and can be parallelized easily.