Othello Let us cling together メンバー • • • • • 班長プログラマーアルゴリズムパワーポイント発表杉本友宏京谷貴平佐野祐之菊澤遼平川本敏和はじめに小さな頃からみんなが慣れ親しんできたOthello。普段は戦略について深く考えることなく打っていたが、今回の機会を利用して戦略に基づいたプログラムを考えてみる。そのために調べた方法を紹介していく。基本方針・盤面にポイントを設定。 →同じポイントの場合ランダムに打つという問題あり。・αーβ法とミニマックス法を取り入れることで上記の問題を解決。特徴 • 隅での対処法 • 各セルの評価値は隅に石があるかないかで変動する。 • 隅を取られないためには、隅に隣接するセルには置かない方がよいが、隅が埋まった後には気にする必要がないためである。そこで、隅の状態により、評価値表を盤面の1/4毎に差し替える。下図は盤面左上の評価値表である。 200 100 50 30 0 50 30 20 100 30 20 10 50 10 15 5 50 20 10 10 30 15 5 0 50 10 10 10 20 5 0 0 隅が自分の石の時隅が敵の石の時着手数・要石の計算 • リバーシゲームでは打てる所がある限りパスが許されないので、手詰りで不利な個所に打たないように、着手数(石が置ける場所の数)は多ければ多いほど有利である。 • しかし、一見着手数が多いように見えても、ひっくり返す敵の石がひとつしかなければ、結局一度しか使えない。そこで、着手数と同時に、その手によりひっくり返される石(要石)の数も考慮に入れる。 • 着手数・要石を計算するのに、全てのセルから8方向にスキャンしていたのでは時間がかかるので、本プログラムでは盤面に対して4 方向にスキャンし、盤面と同サイズの2次元配列にフラグを立てるようにしている。参考文献 • 将棋とコンピュータ(情報フロンティアシリーズ), 松原仁, 共立出版, 1994 • 思考ゲームプログラミング, 森田和郎, 国枝交子, 津田伸秀, アスキー出版局, 1986 感想 • 今回Javaによるプログラミングについて学んでみて、普段我々が何気なく思考していることでも、それをコンピュータに同じように思考させるのは非常に大変なことであると思いました。この知識をこれからにも役立てていきたいと思いました。