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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29/31 Thank You!