最近MinMax法を勉強したので、アウトプットのために三目並べを実装しました。あとScala.jsも使ってみたかった。
コード自体はほとんど以下のプログラムを参考にしています。
参考
http://postd.cc/tic-tac-toe-understanding-the-minimax-algorithm/
なんとなくAIってつけましたけど、AIなんて呼んでいいのやら・・・
勝つことは無理です
MinMax法とは
wikiに書いてある通りですが、先読みプログラムです。
playerがAである時はBのスコアを最大化するような手(ノード)を選択。 playerがBである時にはAのスコアを最小化するような手(ノード)を選択します。
ちなみに範囲内の全てのノードのスコアを計算して次の一手を計算するのでパターンが多いゲームだと計算量が恐ろしくなります。
図にすると以下のようになります。wikiの図とは上下を逆にしました。逆にした方が自分的には直感的だったので。
Aの手番の時はスコアを最大化するようなノードを選択します。
Bの手番の時スコアを最小化するようなノードを選択します。
A, Bは先手、後手で分けることができます。逆に言うと続けて動けるようなゲーム今回の実装では対応できません。
三目並べとは
誰でも一回はやったことある遊びです。海外ではTic-tac-toeと呼ばれているみたいです
図のようなゲームです。1
縦横斜めに３つ同じ柄を揃えた方が勝ちとなります
評価基準
ここでは一直線揃えた方に対して点数をつけていきます。
ターンの数をdとすると
先手A(X) 勝利: 10 - d 点
後手B(○) 勝利: -10 + d 点
引き分け: 0点
なぜターン数dを考慮するかというと、負けと決まっていても相手によりターンを消費させる手の方がいい手だと言えるからです
ということで具体的な盤面を見ておいた方が分かりやすいかもしれません。例えば次はA（X）の手番でこんな盤面の時
Aの選択は下図の一番下の3つの選択肢がります。この選択肢からAは点数を最大化するような手を選択することで最良の手を得ます
＊ 上に行くほど時間経過していきます
Aは勝つことはできませんが、直近ノードの最大値である0を選択することでなんとか引き分けには持ち込めるようです。
また一つ前はBの手番なので最小のノードを選択しているために-2点が選択されています。
必ず一番上まで実行して、勝敗を見た後に最適な手を選択してるのでもはやゲームする必要はないに等しいです。
とこんな感じで再帰的に計算していきブルートフォースアタックしていきます。
計算省略の余地
冒頭でも書いたように計算量は結構膨大になります。
今回の9マスのゲームで言えば
9! ほど計算が必要です。つまり 362880 通り!
もちろん途中で勝負がつく可能性があるので362880より計算回数は少々少なくなりますが、こんなミニゲームにしては多すぎます。。。
ということで計算量を減らしていきます。
アルファベータ法
いい手を見つけた時点でそれ以外の計算を切り上げることもできそうだなぁって思っていたら、Wikiには改良版のアルファベータ法というのがあるとの記述があります。
アルファベータ法のwikipediaページに疑似コードがあるのでこれをまるっと実装に落とせばうまくいく!!
図にするとこんな感じです。左から順に深さ優先で探索しているイメージです
-8が出た時点で-3 より小さいことは確定しているのであえて次のノードは計算しないようにします。次のノードが-9だったところで最上位のノードには確実に採用されないのでここでは計算する必要がないです。
とこんな感じで枝刈りをしていきます
ゲームの性質をつく
幸いなことに三目並べは最初の手はどこにおいても同じ評価でした。ということで最初の手はランダムにして計算回数を節約します。
ちなみに自分で計算しましたが、wikiにも書いてあるので常識だったようですね。
コード
コードはこちらに置いています
ソースコード
何が理解を苦しめたか
自分のレベルが低いせいか再帰のプログラムとターン毎の最大、最小選択の理解に割と苦しみました。
ノートにいっぱい図を書いてようやく理解できたという感じです。。。未だに少し悩みますが。。。
今後
三目ぐらいだと計算量がある程度一定なのでゲーム終了までの手を読むことができました。
ということで少し難易度を上げて五目並べを作ってみたいなぁっと