絶対負けないだけじゃ、最強とは言えないんだって。
とゆうわけで、ミニマックス法の続き。
定石
本題の前に・・・
環境にもよるでしょうが、一手目を打つのにちょっと時間がかかる感じで・・・特にＣＯＭ先手の時、なかなか打ってくれないとあれ？ ってなる；
しかも、考えた末に、結局は毎回必ず左上隅から始まるんですよ。あんまり最強っぽくないですよねｗ
前々回、ミニマックス法を学ぶ前の段階で、ＣＯＭを強くするために定石を教える？ という案がありました。
それで、先手後手それぞれの一手目については定石で打ってもらうことにしてみました。
- 先手の一手目は、四隅のどれかです。
つい、真ん中を埋めたくなっちゃうんですけど・・・
- 後手の一手目は真ん中です。それ以外だと、負けます！
- ただし、先手が真ん中を打ってきた場合には、四隅のどれかです。辺に打つと負けます！
というわけで、後手は、先手に四隅に打たれたら真ん中一択なのに対し、真ん中だと確率二分の一で先手の勝ちを阻止できるんです。
だから、先手としては隅に打った方が、勝てる確率が上がります。
で、こんな感じ？
●レベル２
# 一手目が遅いので定石で打たせる
四隅＝[0,2,6,8]。中央＝4。
もし、手数＝0ならば、
四隅[4の乱数]へ打つ。 # 先手一手目なら４隅のどれかを取る。
違えば、もし、手数＝1ならば、
もし、局面[中央]＝アキならば、中央へ打つ。 # 後手一手目は中央が空いていれば中央を取る。
違えば、四隅[4の乱数]へ打つ。 # 先手が中央を打っていた場合は４隅のどれかを取る。
違えば、
# ミニマックス法
手数で局面の良手探索。
次着手へ打つ。
ここまで。
ここまで。
前回作ったミニマックス法のプログラムでは、得点が同じでも、配列検索で一番最初のものを問答無用で選択しちゃってるもんですから、ＣＯＭ先手の時は毎回同じ左上の隅から始まってしまってたんですが、それでは芸がないのでランダムにしてちょっと変化があるっぽくしましたｗ
もっと良い試合をするために
さて、本題。
引き続き、ここを参考にやっていきます。
プログラムに間違いがなければ、前回の段階でもうＣＯＭが負けることはないのですが、それだけでは考え方として不十分だということのようです。
問題点の確認
実際には、こうゆう局面が発生することはあり得ないのですが、こんなの。
※参考サイトとは、マルバツが逆になっています。（先手○、後手×にしたいため）
×を持ったＣＯＭの手番です。
人間の考えなら当然二目並んだ○を止めるため、こんなふうに☆の所へ打つところなんですが・・・
こうなっちゃうΣ（゜д゜；
何？ 頭悪いの？？ って、思っちゃいますよね～。
でも、コンピューターとしては、たとえそこを止めたとて、次真ん中を打たれたら両天秤で最終的にやられちゃうと分かっている。
得点リストには-10が並んでいて差がないので、今負けるとか次負けるとか考えず、最初のところを選択しちゃう。
※参考サイトと着手先が違いますが、るびぃさんが分かりませんがタブン、同じ値が並んだ場合は最後のを取るようになってるんですよね。
こちらのは配列検索を使っているので、一番最初がヒットします。
でも、先の読めない人間には、止めるべき所を止めずに負けた馬鹿なヤツ、と思われてしまうかも知れない。それは悔しい。よろしくありません！
深さ
そこで登場するのが「深さ」という要素ってワケですね。
「深さ」というのは、今の局面から終局まで何手かかるかとゆうことです。
勝つならなるべく早くさっさと勝った方がイイし、負ける時は同じ負けるにしても出来るだけ粘った方がイイ。
というわけで、勝った時の得点は１０から深さを引き、負けた時には－１０に深さを足すということにして、こんな感じ？
●(深さと勝敗で)得点計算
勝敗で条件分岐。
ＣＯＭならば、10-深さで戻る。。。
人間ならば、深さ-10で戻る。。。
引き分けならば、0で戻る。。。
ここまで
ここまで。
そして、深さ０からはじめて、良手探索の中で深さをプラス１するようにすれば、呼び出されるごと深さがプラスされていくので、その枝の深さが分かるって寸法ですね。なるほど。
いやでもそういえばワタクシ、最初から仮手数をカウントしていたんだよね。
勝敗判定で、どっちも勝っていなくて手数が8なら引き分けってコトにしてたので。
これはゲーム開始からの手数で、今の局面からのものでは無いんですが、仮手数から本来の手数を引いてやれば深さになりそう？
●(仮手数で盤面の)良手探索
着手リスト＝空配列。得点リスト＝空配列。仮手番＝仮手数%2。深さ＝仮手数-手数。 # 深さ
着手可能マス＝盤面の着手可能マス確認。
もし、手数＝８ならば、次着手＝着手可能マス。
# ゲームが終わる場合、ＣＯＭ側から見た得点を返す
結果＝盤面の勝敗判定。
もし、結果が継続でなければ、深さと結果で得点計算して戻る。 # ここね
# そうでない場合、選択可能なそれぞれの手に置いたと仮定した仮盤面を作成
着手可能マスを反復
着手候補＝対象。仮盤面＝盤面を配列複製。
仮盤面[対象]＝仮手番。
得点＝仮手数＋１で仮盤面の良手探索。 # 再帰（ここで仮手数を増やしている）
得点リストに得点を配列追加。 # その状態のミニマックスの結果を追加する
着手リストに着手候補を配列追加。
ここまで。
～～～（中略）～～～
ここまで。
これで、先ほどの局面をテストしてみると・・・
できました！ やったね☆
おまけ（キャラ名）
レベル１、レベル２じゃ可哀想なので、名前をつけました。
ホームページのトップ絵になっている、なでしこのキャラクターたちの名前を借りました。
定数 キャラ＝["パコ","ナコ","なでしこ君"]
青い子、誰だよと思っていたら、パコって言うんだ。デシかと思ったよねｗ ナコとデシを合わせるとナデシコになるからねｗｗｗ（そんなコトばっか考えて生きてんです。スミマセン；；；）
ナコは箱を被った猫ってことなので、パコも箱から来てるんですかね？
ともかく、このリバーシの盤面を見るに相当ポンコツだから、パコはレベル０確定だね！
とゆう感じで、レベル１はナコ、レベル２はなでしこ君となっています。
なでしこ君最強☆
完成！
＃---宣言-----
定数 ゲーム画面＝描画中キャンバス。
定数 マス幅＝100。
定数 [アキ,マル,バツ]＝[-1,0,1]
変数 [手数,手番]＝[0,0]。
変数 局面＝空配列。
#勝敗判定
定数 パターン＝[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]。
定数 [引き分け,継続]＝[-1,-2]
変数 ゲーム中＝はい。
#コンピューターが打つ
定数 [先攻,後攻]＝[0,1]。
変数 [人間,ＣＯＭ]＝[先攻,後攻]。
変数 プレイヤー＝空配列。
変数 レベル＝２。
定数 キャラ＝["パコ","ナコ","なでしこ君"]
変数 次着手＝空。
#-----------------------------------------------
＃テスト用
盤面＝[-1,0,-1,-1,-1,0,1,1,0]。
//盤面でテスト。
#-----------------------------------------------
ゲーム開始。
＃---イベント-----
ゲーム画面をマウス押した時には
もし、ゲーム中がいいえならば、戻る。
もし、手番がＣＯＭならば、戻る。
列＝(マウスX/マス幅)を整数変換。
行＝(マウスY/マス幅)を整数変換。
番号＝行*３＋列。
番号へ打つ。
ここまで。
＃---関数----------
●ゲーム開始
人間＝2の乱数。ＣＯＭ＝(人間+1)%2。//先攻後攻決め
対戦相手選択。
初期化。
もし、ＣＯＭが先攻ならば、ＣＯＭ着手。
ここまで。
●対戦相手選択
「レベル選択。数字を入力して下さい。{改行}未入力の場合はレベル２になります。{改行}０、よわい ／ １、ふつう ／ ２、つよい」を尋ねる。
レベルはそれを整数変換。。
もし、(レベルが０以上)かつ(レベルが２以下)でなければ、レベルは２。
「レベル{レベル}。{キャラ[レベル]}がお相手します。」を言う。
ここまで。
●初期化
画面描画。
番号を０から８まで繰り返す。局面[番号]＝アキ。。。
手数＝０。手番＝０。ゲーム中は、はい。
プレイヤー[人間]＝「あなた」。プレイヤー[ＣＯＭ]＝キャラ[レベル]。
「先攻は{プレイヤー[先攻]}です。後攻は{プレイヤー[後攻]}です。」と言う。
ここまで。
●新規ゲーム
人間＝(人間+1)%2。ＣＯＭ＝(ＣＯＭ+1)%2。//先攻後攻入れ替え
初期化。
もし、ＣＯＭが先攻ならば、ＣＯＭ着手。
ここまで。
＃描画
●画面描画
全描画クリア。
４に線太さ設定。黒色に線色設定。
２回
[マス幅*回数,0]から[マス幅*回数,マス幅*３]へ線描画。
[0,マス幅*回数]から[マス幅*３,マス幅*回数]へ線描画。
ここまで。
ここまで。
●（番号に記号を）マルバツ描画
定数 [マル中点,マル半径,バツ始点,バツ終点,文字x,文字y,記号太さ,文字サイズ]＝[50,30,20,80,15,75,10,72]
x＝番号を3で割った余りにマス幅を掛ける。
y＝番号を3で割って、それの整数部分にマス幅を掛ける。
「#DD3344」に線色設定。空に塗り色設定。記号太さに線太さ設定。
もし、記号がマルならば、
[x+マル中点,y+マル中点]にマル半径の円描画。
違えば、もし、記号がバツならば、
[x+バツ始点,y+バツ始点]から[x+バツ終点,y+バツ終点]まで線描画。
[x+バツ始点,y+バツ終点]から[x+バツ終点,y+バツ始点]まで線描画。
違えば、
文字サイズに描画フォント設定。
[x+文字x,y+文字y]に記号を文字描画。
ここまで。
ここまで。
●(番号へ)打つ
もし、局面[番号]がアキでなければ、戻る。
局面[番号]に手番を代入。
番号に手番をマルバツ描画。
0.1秒後には //chromeで描画より先にダイアログが上がっちゃうの防ぐため
局面の勝敗判定して結果に代入。
もし、結果が継続ならば、
手数＝手数＋１。手番＝手数％２。
もし、手番がＣＯＭならば、
ＣＯＭ着手。
ここまで。
違えば、
結果で終局。
ここまで。
ここまで。
ここまで。
＃勝敗判定
●(局面の)勝敗判定
パターンを反復
変数[a,b,c]＝対象。
もし、(局面[a]≠アキ)かつ(局面[a]＝局面[b])かつ(局面[a]＝局面[c])ならば、局面[a]で戻る。
ここまで。
もし、手数が8以上ならば、
引き分けで戻る。
違えば、
継続で戻る。
ここまで。
ここまで。
●(結果で)終局
もし、結果が引き分けならば、
「引き分け。」を言う。
違えばもし、結果＞引き分けならば、
「{プレイヤー[結果]}の勝ち。」を言う。
ここまで。
ゲーム中は、いいえ。
「続ける？」で二択。
もし、それがはいならば、新規ゲーム。
ここまで。
＃コンピューターが打つ
●ＣＯＭ着手
レベルで条件分岐。
0ならば、レベル０。。。
1ならば、レベル１。。。
2ならば、レベル２。。。
ここまで。
ここまで。
#空いてる所へランダムに打つ
●レベル０
着手可能マス＝局面の着手可能マス確認。
着手可能マス[(着手可能マスの要素数)の乱数]へ打つ。
ここまで。
#同じ記号が2つあったら止める
●レベル１
パターンを反復
変数[a,b,c]＝対象。
もし、(局面[b]≠アキ)かつ(局面[b]＝局面[c])かつ(局面[a]＝アキ)ならば、
aへ打って戻る。
違えば、もし、(局面[a]≠アキ)かつ(局面[a]＝局面[c])かつ(局面[b]＝アキ)ならば、
bへ打って戻る。
違えば、もし、(局面[a]≠アキ)かつ(局面[a]＝局面[b])かつ(局面[c]＝アキ)ならば、
cへ打って戻る。
ここまで。
ここまで。
レベル０。
ここまで。
●レベル２
# 一手目が遅いので定石で打たせる
四隅＝[0,2,6,8]。中央＝4。
もし、手数＝0ならば、
四隅[4の乱数]へ打つ。 # 先手一手目なら４隅のどれかを取る。
違えば、もし、手数＝1ならば、
もし、局面[中央]＝アキならば、中央へ打つ。 # 後手一手目は中央が空いていれば中央を取る。
違えば、四隅[4の乱数]へ打つ。 # 先手が中央を打っていた場合は４隅のどれかを取る。
違えば、
# ミニマックス法
手数で局面の良手探索。
次着手へ打つ。
ここまで。
ここまで。
●(局面の)着手可能マス確認
着手可能マスは空配列。
局面を反復
もし、対象がアキならば、着手可能マスに対象キーを配列追加。
ここまで。
着手可能マスで戻る。
ここまで。
●(深さと勝敗で)得点計算
勝敗で条件分岐。
ＣＯＭならば、10-深さで戻る。。。
人間ならば、深さ-10で戻る。。。
引き分けならば、0で戻る。。。
ここまで
ここまで。
●(仮手数で盤面の)良手探索
着手リスト＝空配列。得点リスト＝空配列。仮手番＝仮手数%2。深さ＝仮手数-手数。
着手可能マス＝盤面の着手可能マス確認。
もし、手数＝８ならば、次着手＝着手可能マス。
# ゲームが終わる場合、ＣＯＭ側から見た得点を返す
結果＝盤面の勝敗判定。
もし、結果が継続でなければ、深さと結果で得点計算して戻る。
# そうでない場合、選択可能なそれぞれの手に置いたと仮定した仮盤面を作成
着手可能マスを反復
着手候補＝対象。仮盤面＝盤面を配列複製。
仮盤面[対象]＝仮手番。
得点＝仮手数＋１で仮盤面の良手探索。 # 再帰
得点リストに得点を配列追加。 # その状態のミニマックスの結果を追加する
着手リストに着手候補を配列追加。
ここまで。
もし、得点リスト＝空ならば、戻る。
# ＣＯＭの番であれば、得点リストから最大点数を返す
もし、仮手番＝ＣＯＭならば、
番号＝得点リストから(得点リストの配列最大値)を配列検索。
次着手＝着手リスト[番号]
得点リスト[番号]で戻る。
# 人間の番であれば、得点リストから最小点数を返す
違えば、
番号＝得点リストから(得点リストの配列最小値)を配列検索。
次着手＝着手リスト[番号]
得点リスト[番号]で戻る。
ここまで。
ここまで。
動作確認
レベル選択では何も入力しないでＯＫしてもレベル２となり、ミニマックス法の動作を確認出来ます。
でももし遊ぶつもりならレベル１くらいが楽しいですｗ
おわります
ユキノはレベルアップした。ミニマックスの呪文を覚えた！
とゆうわけで、結局一週間も引っ張ってしまいましたが、完成です☆
なでしこ君には絶対に勝てない予定なんですが・・・万一勝てたら・・・ポンコツなのはなでしこ君ではなくワタシなので、教えて下さい＞＜