～オセロゲーム～ アルゴリズムとそのプログラム 数値解析Ⅱ ～オセロゲーム～ アルゴリズムとそのプログラム

第２班 ～メンバー紹介～ リーダー；柴原伊佐男 プレゼン担当；黒田健太 班員；佐藤伸志 　　斉藤直宏　 　　笹嶋一志

オセロアルゴリズム ＜前提＞ ルールは、一般のオセロゲームのルールを用いる。 先行は黒ばんであることを前提とする。 a b c d e f g h 1 S C A B 2 X D　 3 D E　 4 ● ○ 5 6 7 8

１．盤上の各マスの呼び方 例） 左上のSの箇所なら、 「１a」 と言うようにあらわす。 a b c d e f g h 1 S C A B 2 X D　 3 D E　 4 ● ○ 5 6 7 8 例） 左上のSの箇所なら、 　　「１a」 と言うようにあらわす。

２．アルゴリズム ア）；基本アルゴリズム ①手番の定義　→奇；黒　偶；白 ②石を置くマスの状態を調べる。 ③石を置く仮定 ● ○

④石を返せるかどうか調べる。 　ⅰ.置いたと仮定したマスを原点とし、周りのマスの状態を調べる。 　ⅱ.●か空白のマス、壁のある場合→ⅰ 　ⅲ.○ある場合→原点から移動した方向と同じ方向へ移動。 　ⅳ.次の方向に○→同じ方向へ移動。 ⅴ.次のマスが●→ⅰに戻り、次の方向へ。 ● ● 　 ○

ⅵ.次のマスが空白or壁→ⅰに戻り、再試行。 ⅶ.ⅴが実行可→置ける。 　　ⅴが実行不可→置けない。 ⑤実際に石を置く。 ● ○ ● ○

CPUと人間が連続してパス→the end ○ ● ⑥パス 　上の③、④ができない。 ⑦全滅 　CPUと人間が連続してパス→the end ● ○

○ ● ⑧勝者 　ⅰ.盤上のマスがすべて埋まる。 　ⅱ.全滅が起こる。 →石の数の多いものを ● WINNER

イ）；強化アルゴリズム （１）中割 ①盤上に白石があるかを調べる。 a b c d e f g h 1 S C A B 2 X D 3 D 　　①盤上に白石があるかを調べる。 a b c d e f g h 1 S C A B 2 X D　 3 D E　 4 ● ○ 5 6 7 8

②○があった場合　　　　　　　　　　→8方向を調べる ③○見つけられず →ア．○×３以上ある。 　　イ.if ●を置く、○を裏返せる。→④へ ④●でできるライン 　(ⅰ)、(ⅱ)、（ⅲ）、（ⅳ）

● ○ ○ ● ● ○ ○ ●

⑥①に戻り、記憶した○以外の○×３以上を調べる。 S C A B X D　 D E　 ● ○ ⑤if ④を満たす●が複数→優先順位 　S,A,B,E,D,C,X 　＊A,Bは例外あり。 ⑥①に戻り、記憶した○以外の○×３以上を調べる。 ある→⑤まで進む。 C X D　 A D E　 B ● ○

⑦候補の●が置ける。 →もっとも高い優先順位 同じ優先順位 →○列の数の多いもの優先 ○列の数も同じ →先に調べたもの優先 D ○ E ● B ⑦候補の●が置ける。 →もっとも高い優先順位 同じ優先順位 →○列の数の多いもの優先 ○列の数も同じ →先に調べたもの優先 4 ○ 2 9 7 ● 1 #

一石返しとは。中盤で中割りのよい手がないとき、もしくは自分の手を増やすために局面にあまり 影響のないように相手の石を１つだけ返す手である。

⑥If次のマスに移動→○あり →③ If 右下のマスを調べる→○あり →② ⑦If 次のマスへ移動→●あり →⑧ ● ○ ○ ●

現時点で相手の手数を数える！ ⑧白の場合も同じようにする ○ ● ○ ●

すいません！！ ここまでしかできませんでした！！

白石がある状態なら、その白石から原点から移動した方向と同じ方向へ移動し、調べる。 次のマスに移動した時、白石があるなら、③へ戻り、次のマスを調べる。右下のマスを調べていたなら、②に戻り、次のマスに石を置く仮定をする。 次のマスに移動した時、黒石かマスがあるなら⑧へ進む。 (現時点で相手が何通りの手があるかを数える。)白石の場合で②を考える。

白石の場合で③を考える。 白石か空白の状態のマス、またはマスがない場合は⑨に戻り、次のマスを調べる。右下のマスを調べていたなら、⑧に戻り、次のマスに石を置く仮定をする。 黒石があればそれを記憶し、⑧に戻り、次のマスに石を置く仮定をする。 全てのマスを調べたら、今まで記憶した数が白側の手数である。 で選んだ場所で仮に石を返す。

(この仮定の時点での相手の手数を数える。)⑧～⑫を繰り返しそれを記憶する。 ⑫での相手の手数>⑭での手数となれば、その手を記憶し③へ戻り、次のマスを調べる。右下のマスを調べていたなら、②に戻り、次のマスに石を置く仮定をする。 ⑫での相手の手数<=⑭での手数となれば、その手を記憶し③へ戻り、次のマスを調べる。右下のマスを調べていたなら、②に戻り、次のマスに石を置く仮定をする。

全てのマスが調べ終わって、⑮の記憶が１つだけなら、そこに打つ。 全てのマスが調べ終わって、⑮の記憶が複数あれば、22へ進む。 全てのマスが調べ終わって、⑮の記憶が無く、⑯の記憶が１つだけなら、そこに打つ。 全てのマスが調べ終わって、⑮の記憶が無く、⑯の記憶が複数あれば、22へ進む。 記憶がなければ、一石返し不可能。

複数ある中で、⑭での相手の手数が一番少ないところに打つ。 22で、手数が一番少ないところが複数あればそのなかで、一番優先度の高いところに打つ 23で一番優先度の高いところが複数あればその中のどれかに打つ。