Proposal of Partially Exhaustive Investigation Monte Carlo Method and Application to Decision-making of the TAC Agent

コンピュータゲームや電子商取引などにおけるエージェントの意思決定を設計する際, 状況によっては, ある意思決定に対して生起する結果が一意に決定されないという不確実性を含む場合があり, 生起する結果の確率を考慮に入れた意思決定の手法が必要となることがある.そのような際, 生起する結果の評価値の期待値を用いる方法が考えられるが, 計算コストに対する制約などにより実際に期待値の真値を計算することが困難な場合は, モンテカルロ法を用いて推定することが一般的である.本論文では, 生起確率が高い結果の列挙が容易である場合にサンプル数を増加させることなく期待値の推定精度を上げる部分的完全調査モンテカルロ法を提案し, 実験により提案手法の有効性を確認した.また応用例として, TAC CLASSICという多人数参加の取引ゲームのエージェント設計へ適用した.実験の結果, 提案手法を組み込んだ意思決定が不確実性を含むゲームにおいて有効であることが示された.To design an autonomous-trading software agent for some kinds of game and electric commerce, the agent often has to cope with the situation that result of decision-making includes stochastic phenomena. In such case, it is necessary for the agent to consider expected evaluation value for possible results according to the probability of results, and Monte Carlo Method is generally used to calculate the expected evaluation value for such situation. In this paper, we suppose the situation that it is easy to enumerate high-probability results at low computation cost, and propose an improved version of Monte Carlo Method, i.e., Partially EXhaustive Investigation (PEXI) Monte Carlo Method. Moreover, we show the effectiveness of the proposed method by some computer experiments including the designing of TAC CLASSIC trading agent