Ｈｉｔ　＆　Ｂｌｏｗ 出口研究室 足立 豊　　國井 貴雄　　高井 信秀　　 辻 嘉治　　村田 和行.

Presentation on theme: "Ｈｉｔ　＆　Ｂｌｏｗ 出口研究室 足立 豊　　國井 貴雄　　高井 信秀　　 辻 嘉治　　村田 和行."— Presentation transcript:

1 Ｈｉｔ　＆　Ｂｌｏｗ 出口研究室 足立 豊　　國井 貴雄　　高井 信秀　　 辻 嘉治　　村田 和行

2 　戦略 候補をしぼる 期待値を用いる Ｍｉｎ－Ｍａｘ

3 　候補をしぼる 候補が少なければ少ないほど有利 答えとしてありえない値を削除 候補をしぼることができる

4 回答値 ０１２３ サーバーの返答 １Ｈ１Ｂ ０１２３ → ４Ｈ０Ｂ × ０１２４ → ３Ｈ０Ｂ × ０１２５ → ３Ｈ０Ｂ × ・
０１２３　→　４Ｈ０Ｂ　　× ０１２４　→　３Ｈ０Ｂ　　× ０１２５　→　３Ｈ０Ｂ　　× ・ ０４１５　→　１Ｈ１Ｂ　　○ ０４１６　→　１Ｈ１Ｂ　　○ 回答値　　　０１２３ サーバーの返答　　　１Ｈ１Ｂ

5 　期待値を用いる 期待値とは・・ 次の候補に残るであろう値の 数の平均

6 期待値　＝　Σ　確率　×　 候補の数 期待値の計算式 候補が少なくなる可能性が高い。 期待値が小さい

7 ０１２３　を１回目の回答値とし、 ０Ｈ３Ｂ　と返答された 候補　を２回目の回答値としたとき この場合の期待値　　４９．５

8 ０１２３　を１回目の回答値とし、 ０Ｈ３Ｂ　と返答された １４３５　を２回目の回答値としたとき この場合の期待値　　４４．９

9 しかし、期待値で選ばれた値は候補でない場合が多い
期待値を用いたほうが候補が早く減らせる しかし、期待値で選ばれた値は候補でない場合が多い いつまで期待値を用いるかが重要

10 というわけで・・

11 　Ｍｉｎ－Ｍａｘ ＭｉｎーＭａｘとは・・ 最悪の場合の 候補が一番少ない値の選択

12 ０１２３　を１回目の回答値とし、 ０Ｈ３Ｂ　と返答された １４３５　を２回目の回答値としたとき この場合の期待値　　４４．９

13 たとえば ０Ｈ１Ｂ のとき・・ 期待値 が一番小さい値を用いると 期待値 ２５４．４ 最悪の場合 ４０８通り
たとえば　０Ｈ１Ｂ　のとき・・ 期待値　が一番小さい値を用いると 最悪の場合　　４０８通り 期待値　　　　　２５４．４ 最悪の場合　が一番小さい値を用いると 最悪の場合　　３７８通り 期待値　　　　　２５４．７

14 ま と め 期待値 や Ｍｉｎ－Ｍａｘ を用いて 早く候補をしぼることができた あらかじめ計算しておいた値を用いて高速化を実現できた

15