著者

小林 紀之 上原 貴夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.10, pp.3056-3063, 2002-10-15

被引用文献数

5

---

ブリッジは,他のプレイヤーのハンドが見えない不完全情報ゲームであるため,チェス,将棋などの完全情報ゲームとは異なる難しさがある.最近のコンピュータブリッジでは,モンテカルロシミュレーションを基本としたアルゴリズムが主流である.すなわち,見えていないカードの可能な配置(世界)を多数生成し,各世界でダブルダミーブリッジ(すべてのハンドを見て完全情報ゲームとしてプレイをする)として,ゲーム木におけるミニマックス値を求め,次に出すカードを選ぶ.現在,コンピュータブリッジの実力は中級者レベルにとどまっている.その原因の1つは,このアルゴリズムが,見えている自分Pのハンドと矛盾しない世界のみを対象としている点にある.本論文では,上級者のプレイテクニックの1つとして知られるディセプティブプレイを発見するアルゴリズムを提案する.敵を騙すプレイを可能にするためには,出されたカードを観察した敵がどのようなハンドを想定するかをモデル化する必要がある.著者らは,経験則に基づいて推論を行うエージェントAを敵のモデルとし,敵から見た世界を生成した.この世界は多くの場合,自分Pのハンドと矛盾する.ディセプティブプレイを発見する方法として,敵Aから見た世界では敵に有利であり,かつ,自分Pから見た世界では自分に有利なプレイを探索することを提案した.このアルゴリズムを実装して,典型的な例題でその機能を確認した.The Contract Bridge is an incomplete information game,that is, a player cannot look at the other player's hands.Its difficulty is different from that of complete information games such as Chess and Shogi.The Monte Carlo simulation is the most popular technique for modern Computer Bridges.Many random deals (worlds) are generated.The best card to play is selected according to minimax value of a complete information game-tree search as the double dummy Bridge in each world.Computer Bridges have never win the game against top players.It is partially because the algorithm does not generate a deal inconsistent with the hand of the player P.This paper proposes an algorithm to find a deceptive play that is one of the techniques used by top players.An opponent is modeled as an agent A who guesses P's hand by rule-based knowledge.Worlds generated by A may be inconsistent with the P's hand.The proposed algorithm finds a play line that is the best for opponent in the worlds generated by A and also good enough for P in the worlds generated by P.The algorithm is implemented and tested for some typical examples.