Ｆ班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史

Presentation on theme: "Ｆ班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史"— Presentation transcript:

1 Ｆ班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
数値解析Ⅱ 　～五目並べプログラムを作る～ Ｆ班　メンバー　 　　　　　　　　班長　雨堤　智宏　　　　　　　　　　 アルゴリズム解析　角田　泰彬 　　　　　　　　　　　　竹林　秀高 　　　　　　ppt作成　清水　貴史

2 ①既存の五目並べプログラムをプレイ 参考　宍戸輝光氏作成　「五目ならべゲーム」

3 ②五目並べとは？ 三つの石の並びが勝負を左右する 先手・後手交互に石を打って、先に一直線上に五つの石を並べたほうが勝ち
黒番ならAかBに置けば次手で勝ちが確定 白番ならAかBに置いて黒の勝ちを阻止 B ○ A 三つの石の並びが勝負を左右する

4 ③宍戸氏のプログラムの特徴 盤面評価からCPUの手の決定までの流れ ・16×16 256マス全ての盤面にある石の場所と数を記憶する
・16×16　256マス全ての盤面にある石の場所と数を記憶する ・配石可能な場所に重要度の高い順に点数をつける 　例）自分が4連しており、勝ちが確定する場所には１５，０００点 　　　 相手が4連しており、置かなければ負けが確定する場所には１２，０００点 　　　 自分が2連しており、その両端に置くことにより3連ができる場所には１０点 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　など ・全ての盤面評価が終わると、その中から最高点の場所にCPUの手を決定 　最高点が複数存在する場合は、その中からランダムで選出

5 ④宍戸氏のプログラムの問題点 HUMかCPUのいずれかが一直線上の連続する５点のうち２点に並ぶまで意味の無い手を打ち続ける
・序盤に何の戦略性も無い無意味な手を打つ ・相手の動きに合わせて打つ⇔例え先手でも出遅れる 例　CPU後手の場合 ●　：先手HUMAN ●　：後手CPU HUMかCPUのいずれかが一直線上の連続する５点のうち２点に並ぶまで意味の無い手を打ち続ける

6 ⑤プログラムの是正 →序盤の手順に戦略性のある定石を導入 定石とは？

7 ⑤プログラムの是正 CPU先手の時、HUMが離れた場所に打ってきた場合 HUM先手の時、第一手に端に置かれた場合

8 ⑤プログラムの是正 ・相手が奇抜な手を打ってきた時にも定石を交えな がら対応できるプログラムが必要
　がら対応できるプログラムが必要 ・定石の数は豊富でその全てに対応するプログラム 　を作成する必要がある 挑戦するも知識不足に加え、バグが無くならず断念・・・・

9 ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅰ）CPU先手（●）の場合 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 9
ⅰ）HUM（●）が●の直近周囲（①～ 　　⑧）に無い場合 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 9 Ⅰ）CPU先手（●）の場合 第一手は有無を言わさず座標［９,９］ ①～⑧からランダムに選択して決定 ●が二つ並んだので以降は既存のプログラムに準じて手を決定 9

10 × ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅰ）CPU先手（●）の場合 ① ② ③ ④ ⑤ ⑦ ⑧ ① ② ③ ④
●を挟んで●の反対側を除く6箇所からランダムに選択して決定 （図の例では●が⑥にある場合は③を除外） 9 Ⅰ）CPU先手（●）の場合 ⅱ）HUM（●）が●の直近周囲（①～⑧）のいずれかにある場合 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ × 第一手は有無を言わさず座標［９,９］ ●が二つ並んだので以降は既存のプログラムに準じて手を決定 9

11 ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅱ）HUM先手（●）の場合 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧
有無を言わさず座標［９,９］にCPUの手を決定 a)HUMの第2手（トータル3手目）の場所の情報は無視 CPU一手目の囲りに注目 一手目の囲りに●が0個の場合 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 9 ①～⑧からランダムに選択してCPUの手を決定

12 × ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅱ）HUM先手（●）の場合 ① ② ③ ⑤ ⑥ ⑦ ⑧
有無を言わさず座標［９,９］にCPUの手を決定 b)HUMの第2手（トータル3手目）の場所の情報は無視 CPU一手目の囲りに注目 一手目の囲りに●が1個の場合 ① ② ③ ⑤ ⑥ ⑦ ⑧ × ●を挟んで●の反対側を除く6箇所からラン ダムに選択して決定 （図の例では●が④にある場合は⑤を除外）

13 × × ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅱ）HUM先手（●）の場合 ② ③ ⑤ ⑥ ⑦ ⑧
有無を言わさず座標［９,９］にCPUの手を決定 c)HUMの第2手（トータル3手目）の場所の情報は無視 CPU一手目の囲りに注目 一手目の囲りに●が2個の場合 ② ③ ⑤ ⑥ ⑦ ⑧ × × ●を挟んで●の反対側を除く5箇所からラン ダムに選択して決定 （図の例では●が①と④にある場合は⑤と⑧を除外）

14 × × ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅱ）HUM先手（●）の場合 ② ③ ⑤ ⑥ ⑦ ⑧
有無を言わさず座標［１０,１０］にCPUの手を決定 a)HUMの第2手（トータル3手目）の場所の情報は無視 CPU一手目の囲りに注目 一手目の囲りに●が2個の場合 ② ③ ⑤ ⑥ ⑦ ⑧ × × ●を挟んで●の反対側を除く5箇所からラン ダムに選択して決定 （図の例では●が①と④にある場合は⑤と⑧を除外）

15 × ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅱ）HUM先手（●）の場合 ② ③ ⑤ ⑥ ⑦ ⑧ ④
有無を言わさず座標［１０,１０］にCPUの手を決定 b)HUMの第2手（トータル3手目）の場所の情報は無視 CPU一手目の囲りに注目 一手目の囲りに●が1個の場合 ② ③ ⑤ ⑥ ⑦ ⑧ ④ × ●を挟んで●の反対側を除く6箇所からラン ダムに選択して決定

16 ⑥せめて無駄な手を無くす とにかく序盤に無理やりにでも２連を作る Ⅰ-ⅰ）ＣＰＵ先手-黒が近くにない場合
Ⅰ-ⅱ）ＣＰＵ先手-黒が近くに有る場合 Ⅱ-ⅰ）ＨＵＭ先手-黒が近くにない場合 Ⅱ-ⅰ）ＨＵＭ先手-黒が近くに1個の場合 Ⅱ-ⅰ）ＨＵＭ先手-黒が近くに1個の場合

17 ⑥考察と更なる改良点 オセロと違い、広い盤面のどこから打ち始めてもいいという条件（最初から端っことか）が、特に序盤のＣＰＵの手を決めるプログラムを作ることはなかなか難しかった。 宍戸氏のプログラムにおける序盤の脆弱性を無くす為に、無理やり二連を作るように修正を施しましたが、それによって新たな問題が出てきた。 例）ＨＵＭ先手　（９，９）に無い場合 9 既存のプログラムでは対処できていたことに対処出来なくなった

18 Fin