数値解析Ⅱ

数値解析Ⅱ
～オセロゲーム～
アルゴリズムとそのプログラム
第２班
～メンバー紹介～
リーダー；柴原伊佐男
プレゼン担当；黒田健太
班員；佐藤伸志
斉藤直宏
笹嶋一志
オセロアルゴリズム
＜前提＞
• ルールは、一般のオセ
ロゲームのルールを用
いる。
• 先行は黒ばんであるこ
とを前提とする。
a b c d e f
g
h
1 S C A B B A C
S
2
3
4
5
C
A
B
B
X
D
D
D
D
E
E
E
D
E
●
○
D
E
○
●
D
E
E
E
X C
D A
D B
D B
6 A D E E E E D A
7 C X D D D D X C
8 S C A B B A C S
１．盤上の各マスの呼び方
例）
a
• 左上のSの箇所なら、
「１a」
と言うようにあらわす。
b
c
d e
f
g
h
1 S C A B B A C
S
2 C X D D D D X
C
3 A D E E E E
D
A
4 B D E ● ○ E
D
B
5 B D E ○ ● E
D
B
6 A D E E E E
D
A
7 C X D D D D X
C
8 S C A B B A C
S
２．アルゴリズム
ア）；基本アルゴリズム
①手番の定義 →奇；黒偶；白
②石を置くマスの状態を調べる。
● ○
○ ●
③石を置く仮定
④石を返せるかどうか調べる。
ⅰ.置いたと仮定したマスを原
点とし、周りのマスの状態を調
べる。
●
ⅱ.●か空白のマス、壁のある ●
● ●
場合→ⅰ
● ○○ ○ ●
ⅲ.○ある場合→原点から移動
○○
した方向と同じ方向へ移動。
●
ⅳ.次の方向に○→同じ方向へ
移動。
ⅴ.次のマスが●→ⅰに戻り、次
の方向へ。
ⅵ.次のマスが空白or壁→ⅰ
に戻り、再試行。
ⅶ.ⅴが実行可→置ける。
ⅴが実行不可→置けない。
●
● ● ●
● ○ ○ ○ ○ ○
○ ○
●
⑤実際に石を置く。
●
● ●
● ● ● ● ●
● ○
●
○ ○ ● ● ●
⑥パス
上の③、④ができない。
⑦全滅
CPUと人間が連続して
パス→the end
○ ● ● ○ ●
○ ● ○ ○ ●
○ ○ ○ ●
● ○ ○ ○
●
● ○ ● ● ○ ●
● ○ ● ● ○ ●
● ● ● ● ○ ●
○○○●●○○○
○○○○○●●○
○●○○○●●●
⑧勝者
ⅰ.盤上のマスがすべて
埋まる。
ⅱ.全滅が起こる。
→石の数の多いものを
○●○○○○○○
○●●●○●●●
○●●●●●●●
●○●●○●○●
○○○○○○○●
● ● ●
● ● ●
● ● ●
イ）；強化アルゴリズム
a b c d e
f
g h
1 S C A B B A C S
（１）中割
①盤上に白石がある
かを調べる。
2 C X D D D D X C
3 A D E E E E D A
4 B D E ● ○ E D B
5 B D E ○ ● E D B
6 A D E E E E D A
7 C X D D D D X C
8 S C A B B A C S
②○があった場合
→8方向を調べる
③○見つけられず
→ア．○×３以上ある。
イ.if ●を置く、○を裏
返せる。→④へ
④●でできるライン
(ⅰ)、(ⅱ)、（ⅲ）、（ⅳ）
●
○● ○ ○
●
●
○
○
● ● ● ● ●
○ ○
○
○
●
○ ○ ● ○ ○
○ ●
●
●
● ○ ○
●
○ ●
○
●
S
C
A
B
⑤if ④を満たす●が複数
→優先順位
S,A,B,E,D,C,X
A
D
E
E
B
D
E
●
B
D
E
○
A
D
E
E
C
X
D
D
S
C
A
B
B D E ○ ● E D B
A D E E E E D A
C X D D D D X C
＊A,Bは例外あり。
⑥①に戻り、記憶した○
以外の○×３以上を調
べる。
ある→⑤まで進む。
C
X
D
D
S C A B B A C S
C
A
X
D
D
E
D
E
D
E
B
D
E
● ○
B
A
D
D
E
E
○ ●
E E
D ○ D
D E ○ ○ E
⑦候補の●が置ける。
→もっとも高い優先順位
D ○ ● ○ E
B ○ ● ● ○ ○ D
● ○ E
●
同じ優先順位
→○列の数の多いもの優
先
○列の数も同じ
→先に調べたもの優先
4 ○ 2
4 9 ○○ 7
4 ○●○ 7
1 ○●●○○ 2
●○ #
●
一石返し
一石返しとは。中盤で中割りのよい手がないとき、
もしくは自分の手を増やすために局面にあまり
影響のないように相手の石を１つだけ返す手で
ある。
⑥If次のマスに移動→○あり
→③
If 右下のマスを調べる→○あ
り
→②
●
●
● ● ● ○
● ○ ○
○
○
⑦If 次のマスへ移動→●あり
○
→⑧
●
●
○
●
○
○
●
○
●
現時点で相手の手数を数える！
• ⑧白の場合も同じよう
にする
○
●
●
○
○
●
○
●
○
○
●
○
○
●
●
○
●
○
○
●
○
●
•すいません！！
•ここまでしかでき
ませんでした！！
•
•
•
•
白石がある状態なら、その白石から原点から移動
した方向と同じ方向へ移動し、調べる。
次のマスに移動した時、白石があるなら、③へ戻
り、次のマスを調べる。右下のマスを調べていた
なら、②に戻り、次のマスに石を置く仮定をする。
次のマスに移動した時、黒石かマスがあるなら⑧
へ進む。
(現時点で相手が何通りの手があるかを数える。)
白石の場合で②を考える。
•
•
•
•
•
白石の場合で③を考える。
白石か空白の状態のマス、またはマスがない場
合は⑨に戻り、次のマスを調べる。右下のマスを
調べていたなら、⑧に戻り、次のマスに石を置く仮
定をする。
黒石があればそれを記憶し、⑧に戻り、次のマス
に石を置く仮定をする。
全てのマスを調べたら、今まで記憶した数が白側
の手数である。
で選んだ場所で仮に石を返す。
•
•
•
(この仮定の時点での相手の手数を数える。)⑧～
⑫を繰り返しそれを記憶する。
⑫での相手の手数>⑭での手数となれば、その手
を記憶し③へ戻り、次のマスを調べる。右下のマ
スを調べていたなら、②に戻り、次のマスに石を置
く仮定をする。
⑫での相手の手数<=⑭での手数となれば、その
手を記憶し③へ戻り、次のマスを調べる。右下の
マスを調べていたなら、②に戻り、次のマスに石を
置く仮定をする。
•
•
•
•
•
全てのマスが調べ終わって、⑮の記憶が１
つだけなら、そこに打つ。
全てのマスが調べ終わって、⑮の記憶が複
数あれば、22へ進む。
全てのマスが調べ終わって、⑮の記憶が無
く、⑯の記憶が１つだけなら、そこに打つ。
全てのマスが調べ終わって、⑮の記憶が無
く、⑯の記憶が複数あれば、22へ進む。
記憶がなければ、一石返し不可能。
•
•
•
複数ある中で、⑭での相手の手数が一番少
ないところに打つ。
22で、手数が一番少ないところが複数あれ
ばそのなかで、一番優先度の高いところに
打つ
23で一番優先度の高いところが複数あれ
ばその中のどれかに打つ。

Download Report