単貧民と偶然手番感度 電気通信大学 西野順二 ○ 西野哲朗. 研究の背景 多人数 [sturvant2000 〜 ] ポーカー（不完全情報 [bowling2007] The University of Alberta GAMES Group 多人数不完全情報ゲームはまだ未開拓の困難対象である §1.

Presentation on theme: "単貧民と偶然手番感度 電気通信大学 西野順二 ○ 西野哲朗. 研究の背景 多人数 [sturvant2000 〜 ] ポーカー（不完全情報 [bowling2007] The University of Alberta GAMES Group 多人数不完全情報ゲームはまだ未開拓の困難対象である §1."— Presentation transcript:

1 単貧民と偶然手番感度 電気通信大学 西野順二 ○ 西野哲朗

2 研究の背景 多人数 [sturvant2000 〜 ] ポーカー（不完全情報 [bowling2007] The University of Alberta GAMES Group 多人数不完全情報ゲームはまだ未開拓の困難対象である §1 囲碁 将棋 バックギャモン ダイヤモンド ゲーム 情報の不完全さ 完全情報不完全情報 ２人 ３人 以上 プレイヤー人数 ブリッジ ハーツ 社会現象 大貧民 ポーカー ソーシャルゲーム 多数

3 目的 多人数不完全情報ゲームの新たな指標である 偶然手番感度の提案 「単貧民」を対象に全探索を行い その偶然手番感度の計測と検討を行う

4 大貧民型ゲーム 不完全情報の源泉と遷移 多人数による情報の不完全性 偶然手番による情報の不完全性 徐々に情報が開示される ポーカーと違う 以上の組み合わせ → 大貧民 §2 最もシンプルにした形 → 単貧民

5 5/84 第 7 回 UEC コンピュータ大貧民 大会 UECda-2012 主催： UEC （電気通信大学） 共催： 情報オリンピック日本委員会 会場： 電気通信大学 東３号館 ５階 日時： 2012 年 11 月 24 日（土） 10:30 より （シンポジウムは 12:00 開始） 対象： どなたでも御参加頂けます 参加費： 無料

6 6/84 情報系の学問に馴染みのない皆さん には... 頭の中にある大貧民のプレイの仕方を、アルゴリズム （問題解決手順）として正確に書き下していただき、 プログラム化していただくことで、 情報系の学問の基礎に親しんでいただきたい。

7 7/84 プログラミングの腕に覚えのある皆さ ん には... 会場で、ハイレベルな戦いを繰り広げていただきたい。 本大会ではプログラム同士の高速対戦を行う。 配布されたカードの善し悪しに左右されない、プレイ のアルゴリズム本来の優劣を競うことができる。

8 8/84 大貧民とは？（１） 大貧民はトランプで遊ぶカードゲームのひとつ。 「ど貧民」、「大富豪」、「階級闘争」などとも 呼ばれる。 カードを参加者にすべて配り、手持ちのカードを 順番に場に出して早く手札をなくすことを競うゲ ーム。 １ゲームでの順位が次ゲーム開始時の有利不利に 影響する点が特徴で、勝者をより有利にするゲー ム性から大富豪との名称がついた。

9 9/84 大貧民とは？（２） 地方ルールが数多く存在することも大きな特徴である。地 方ルールには、一度負け出すとなかなか逆転できないとい う欠点を補正する方向に働くものが多い。 順位は、手持ちのカードのなくなった順に、大富豪、富豪、 平民、貧民、大貧民（ど貧民）となる（平民は複数存在し うるが、存在しない場合もある）。

10 10/84 大貧民とは？（３） 第 2 ゲーム以降は、カードを配った後のゲーム開始時まで に、大貧民は大富豪に 2 枚、貧民は富豪に 1 枚、手持ちの最 も強いカードを差し出さなければならない。このカード交 換を「税金」または「献上」という。

11 11/84 大貧民のルール（１） ゲームの開始： ゲームはダイアの３を持ってい る人から始まる。 必ずしもダイアの３を出さな くてもよい。 パスについて： 場のカードと手札の関係上、カ ードを出せない場合はパスとなる。 カードが出 せる場合でも戦略上パスすることができるが、 いったんパスすると、場が流れるまで自分に順番 が回ってくることはない。 スペードの３： スペードの３はジョーカーより も強い。 ジョーカーが一枚で出された場合、ス ペードの３で切ることができる。

12 12/84 大貧民のルール（２） 場の流れ方： 全員がパスしたら場が流れ、最後 にカードを出した人が 場にカードがない状態か らカードを出すことができる。 仮に自分以外が パスした時、自分がカードを出すことができれば 連続してカードを出すことができる。 ８切り： ８を含んだ手を出した場合、場のカー ドがクリアされ カードを出した人が任意のカー ドを出すことができる。 （権利をとることがで きる） 革命： 同じ番号のカードを４枚、もしくはジョ ーカーを含んだ ５枚をセットで出すと、革命が おこる。 革命後はカードの強さが逆転する。

13 13/84 大貧民のルール（３） 階段（シークエンス）：同一マークの連番が 3 枚 以上ある場合は、同時に出すことができる。 5 枚 以上同時に出すと革命がおこる。 しばり（ロック）： 場にあるカードと同じマー クのカードを出すと「しばり」状態となり、以後 同じマークしか出せない。 あがり方： どんなカードでもあがることができ る。 カードの交換： 大富豪は２枚、カードをもらう。 富豪は１枚。 選び方は任意。強いカードをあげ てもよい。 大貧民は２枚、貧民は１枚強いカー ドを献上する。 カードは自動的に選ばれ、選択 できない。

14 14/84 本大会で使用したプログラム カードの配布や場の管理を行うサーバ・プログラ ム。 プレイヤーに対応するクライアント・プログラム。 5 人のプレイヤーに対応する 5 つのクライアン ト・プログラムを、サーバ・プログラムにつない で対戦を行う。 上記プログラムのソース・コードは、大会サイト からダウンロード可能。

15 15/84 サーバー – クライアント シス テム 011010 010010 011001 011010 010010 011001 ①送信 クライアント ②処理 ③返信 010001 100010 111001 010001 100010 111001 サーバーに やって貰お う サーバー クライアントは、サーバーに処理を依頼します。 サーバーは、クライアントの依頼を受け、結果を返信します。

16 16/84 システム構成図 大富豪サーバー 場の管理 状況のクライアントへの通知 提出されたカードの判定 クライアント １ クライアント ２クライアント ３ クライアント ４ クライアント ５ 通信 カードの 選択

17 単貧民 大貧民型ゲームの最小形で多人数不完全情報ゲーム 大貧民の基本ルールを継承している カード順位を線形化 ( マーク、重複カードの省略 ) 1 枚出しのみ、ペア、階段など役出しは無し １〜 12 の整数でカード強さを表す （２が強いわけではない） 例 [[1 4 5] [2 3 6]] ← ２人に３枚ずつ配布、初手は？

18 不完全情報ゲームの解法 モンテカルロサンプリング 52 枚 5 つに配布 10^33 多人数なので 不完全知覚 自手おなじ 情報集合 様々な可能性 U §2 状態を仮定して シミュレーションや探索 のちに統合 ( 期待利得最大化 )

19 偶然手番感度とは (1) 偶然手番と期待利得 偶然手番 利得 G 0.3 0.7 実現確率 偶 A B 情報集合 §3.2 b 0.7-0.3= +0.4 a -0.7+0.3= -0.4

20 偶然手番感度とは (2) 期待利得 G G 0.3 0.7 -0.4 j j A B §3.2

21 偶然手番感度とは (3) 偶然手番感度 利得の偶然手番変化に対する 標本分散と同型 CNS=0 : p に関わらず 期待利得が一定 §3.2 正規化 CNS CNS/Range CNS Σp = 1

22 偶然手番感度高い 偶然手番 G 0.3 0.7 未知 偶 A B A か B か 推定が 重要 §3.2

23 偶然手番感度低い 偶然手番 A B モンテカルロ サンプリングで A, B の どちらの状態を選んでも 最良着手 b が見つかる 1 §3.2

24 単貧民の偶然手番感度 ２〜５名 計２〜１２枚 完全探索 最大３６万通り §3.5 例 [ [145] [268] [379] ] どの手？

25 例） ３人３枚ゲーム ( 計９枚 ) ８４種の自手 各２０種の情報集合 ( 相手パターン ) §3.5 1680 種の木を全て探索し 自手ごとに統合 [] [] [] [] [] [] [] [] []

26 計１２枚までの１４種 最大３６万通り §3.5

27

28 まとめ 単貧民 最小化した大貧民の全探索を行った 単貧民の偶然手番感度が低いことを示した 多人数不完全情報ゲームの性質を計る 新たな指標として偶然手番感度を提案した §3.5

29 29/31 Thank You!