モンテカルロ+UCTにおける探索木のだまし構造  [in Japanese] Deceptive Structure of Search Tree for UCT with Monte-Carlo  [in Japanese]

Search this Article

Author(s)

Abstract

マルチアームバンディット問題 (MAB) を対象に発展した UCB 戦略は,探索と収穫のジレンマに対する一つの有力な回答である.近年,UCB 戦略をゲームの木探索に応用した UCT が盛んに研究され,モンテカルロ法と組み合わせた囲碁プログラムが登場している.しかし,報酬を得られる確率が静的な MAB と異なり,minmax 原理が支配する二人ゲームでは UCB 値に基づく探索が非効率的である可能性もある.本稿では,囲碁において UCT が好ましくない挙動をしうることを指摘し,その本質を抜き出してベンチマーク化する.UCB strategy which has been developed for solving multi-armed bandit problem (MAB) is a major solution for the exploitation-exploration dilemma. UCT is the application of UCB for game tree search, and is intensively studied especially for go-game program with monte carlo method. However, in contrast to the MAB, the ratio for rewards is not static but dynamic in two-players game such as go. In this paper, we present a failure case of UCT for go, generalize it and build a benchmark tree search problem with deceptive structure.

Journal

  • 情報処理学会研究報告. GI, [ゲーム情報学]

    情報処理学会研究報告. GI, [ゲーム情報学] 24, D1-D4, 2010-06-25

    情報処理学会

References:  6

Codes

  • NII Article ID (NAID)
    110007993283
  • NII NACSIS-CAT ID (NCID)
    AA11362144
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09196072
  • NDL Article ID
    025082038
  • NDL Call No.
    YH247-911
  • Data Source
    CJP  NDL  NII-ELS 
Page Top