数値解析Ⅱ ~五目並べのプログラミング~ C班
メンバー リーダー:松長 泰典 プログラマー:小原 和也、薄井 健吾 アルゴリズマー:山根 佳祐 パワーポインター:山﨑 全紘
五目並べのルール① 盤の目に交互に石を置いていき、先に5つの石を一直線に並べたほうが勝ち 先手は黒石、後手は白石 連珠と違って禁じ手はなし いわゆるリーチにあたるものは、三(三連、飛び三)、四(四連、飛び四)
五目並べのルール②
参考プログラム 2007年度 F班 提出 宍戸輝光氏作成 「五目ならべゲーム」
目標 コンピュータ先手の時の勝率UP →先手有利にも関わらず勝率低い →定石と盤面評価を上手に用いて改良
1手目について 1手目は真ん中 →盤の中央は、全方位に偏りがなく、打ちだす側にとって最も優位に展開しやすい場所
2手目について① 定石を用いる →相手の手に対して浦月と花月(もしくは丘月)という3種類の定石を用いる
2手目について② 斜めにつけてきたとき →相手の石と一直線にならないよう斜めにおく 例 浦月
2手目について③ それ以外の時 →自分の一手目に対して斜めにつける 例 丘月 花月
3手目以降について① 定石は存在するが、相手の手によって何通りもある 定石では相手のトリッキーな手に翻弄されやすい →3手目以降からはいわゆる盤面評価に切り替える
盤面評価について① 盤面につけるのではなく、石の状態に得点をつける →自分5連>相手の5連阻止>自分4連>・・・ という順に点数をつける
盤面評価について② しかし、この方法だと作っても防がれるだけの三連を無駄に作ってしまう可能性大 →意味のある三連と意味のない三連を異なる点に評価したい →現在の状況で得点を評価する静的評価では不可能
盤面評価について③ 次の自分の手番の状況を先読みすることが必要となる →ミニマックス法を適用
ミニマックス法について① 次の相手の番の局面を読むとき →次に出現するすべての局面の評価値の最小値を局面の評価値とする 次の自分の番の局面を読むとき →次に出現するすべての局面の評価値の最大値を局面の評価値とする
ミニマックス法について② 例
ミニマックス法について③ すべての局面に対してしらみつぶしに探索を行うため探索効率が悪い →どこでも石が置ける五目並べでは膨大な計算量となることが予想される →ミニマックス法を改善したα-β法を用いる
α-β法について① ミニマックス法において、読む必要のない(評価しなくても支障のない)手を打ちきることで高速化を図る
α-β法について② 例
戦略のまとめ 1,2手目は定石を置く 3手目以降はα-β法を用いた盤面評価を用いる
次からは実際のプログラミングについて述べる
作業① Javaをインストールしたパソコンで前のプログラムを起動しようとした →エラー約28ほど検出
作業② インターネットや本を駆使し、修正していった →エラーが1つになった →しかし最後の1つがあまりにも難解 →他班にも見てもらったが解決しなかった
結果 結果として、断念 →プログラムを作ることではなく、書き換えることを意識しすぎ、泥沼にハマってしまったのが大きな原因だった
感想 かなりの時間を費やしたにも関わらず完成に至らず悔しかった コンピュータはほんの少しの誤りでも受け付けず、使うことのむずかしさを痛感した
御清聴ありがとうございました