Document

OTHELLO
アルゴリズムの概略と
コンピュータの戦略について
Ⅰ．ゲームとして成り立つために……
Ⅰ-１．置ける場所の判定
ある位置（以下(x, y)とする）に石を置ける
かどうかの判定は、以下の手順で行います。
(1)(x, y)が空きマスであるかを確かめ、
(2)x←x+1、y ←y+0 を代入してそのマ
スに相手の石があれば、
(3)(2)を繰り返し、自分の石に行きついた
ら確定です。
(4) (2)の手順でx←x+1、y ←y+1などと
して8方向について調べます。
Ⅰ-２．返る石の判定
(x,y)に石を置いた後、どの石を返すこと
ができるかを判定します。
(1)基本的には置ける場所の判定と同じよ
うに8方向について調べますが、
(2)自分の石を見つけた時に、来た方向に
１マスずつ戻って、そこにある石を自分の
色に変えていきます。
Ⅰ-３．パスとゲーム終了の判定
(1)パス
１.で示した方法で全64マスについて手
番の色の石が置けるかどうかを調べ、置
けなければパスだという事になります。
(2)ゲーム終了
両者ともどこにも置けない時、ゲーム終
了と判定しています。こうすることで、どち
らかの石が０になったり、空きマスがある
のにゲームが終了するようなケースでも
きちんと判定します。
Ⅱ．コンピュータの頭脳は……
Ⅱ-１．評価の方法
(1)コンピュータは自分に手番がまわってくると、打てる手
の全てに対して、評価点をつけ、その中でもっとも点数の高
い手を選んで打ちます。
(2)評価点はいくつかの評価法によってつけるのですが、
それぞれの評価法ごとに今検討している手の評価点を出し、
それにウェイトを掛けて合計したものを最終的な評価点とし
ています。
(3)つまり、「角を取れるなら取れ」ではなく、角に対して大
きなウェイトを与えることで、角が取れる時には他の評価の
影響が相対的に小さくなるため、角を取りに行く、ということ
になります。
Ⅱ-２．戦略の解説①
(1)角の評価
序盤、中盤では角を取ることが大事で、逆に取られると苦
しくなります。そのため、角に置ける時は優先して置くようにし
ています。そして、次に相手が角に置けるような手に対しては
大きな減点としています。
(2)置ける箇所による評価
オセロでは、相手の置ける箇所を少なくすることがとても重
要です。これによって、相手は「置きたくないところ」に置かざ
るを得なくなります。
Ⅱ-３．戦略の解説②
(3)位置による評価
前のページで出てきた「置きたくな
いところ」ということを点数にするのが
この評価です。各マスに図のような点
数をつけています。盤面全体を調べ、
自分の石があれば、その場所に対応
する点数をプラスし、相手の石ならマイ
ナスして、合計を出します。この作業を
今の盤面と次の盤面で行い、その差
が評価点として出てきます。
Ⅱ-４．「位置による評価」計算例
これが今の盤面
今の盤面
次にもしコンピュータ(白)が
ここに置くと
次の盤面
０－（－４）＝＋４点
－２－（－３）＝＋１点
よって、評価点は１－４＝－３点です。
Ⅱ-５．戦略の解説③
(4)開放度
序・中盤の主な戦略として、開放度というものがありま
す。開放度とは、ある手に対し、返した石の周囲にいくつの
空きマスがあるかで定義され、この値が小さい方がよい手
となりやすいと言われています。その理由としては、
(ⅰ)自分の石が少なくなりやすい
(ⅱ)自分の石が中央に集まりやすい
ということが挙げられます。(ⅰ)(ⅱ)の
ような状況(右図)を作ることができれば、
ゲームに勝つ可能性が高くなります。
Ⅱ-６．「開放度」計算例
コンピュータ（白）が赤い丸印のところに置いた時の開放度
を計算してみます。
この時、返る黒石は１と２の石です。
まず、１の石の周りの空きマスを調
べると、空きマスが右上に１マスあ
ることがわかります。次に、２の石
の周りは、今から置く赤丸のあるマ
スは空きマスとして計算するので、
４つ空きマスがあるということになり
ます。よって開放度は、
１＋４＝５です。
Ⅱ-７．戦略の解説④
(5)辺の形による評価
オセロでは辺の良し悪しが勝敗
を左右すると言われており、このプ
ログラムでも辺の形を評価すること
にしました。評価の方法は、
(ⅰ)あらかじめ辺の形とそれに対
応する点数を決めておきます。
(ⅱ) 各辺が(ⅰ)で用意した形と一
致するか調べて、一致すれば点数
を与えます。
山・ブロックは良形、ウ
イングは悪形、爆弾は
やや悪形として評価。
Ⅱ-８．戦略の解説⑤
(6)偶数理論
部分的な空きで、最後の一手を打
つことを「手止まりを打つ」と言い、手止
まりを打つことは特に終盤において大
事な事だとされています。そして、残り
２マスのところにはあまり打つべきでは
ない、残り３マスなら打つべきである、と
いう事も言えます。このように、奇数空
きの所に打って、全ての空きを偶数に
するという考え方を、「偶数理論」と呼
んでいます。
ＴＨＥＥＮＤ

Download Report