アルファベータ探索

理論は抜き。Min-Maxも、純粋な意味でのアルファベータ探索も抜きにして、最初から Negamax + αβ。さっさと実装に。

int αβ(CELL 色, int α, int β, int 残り深さ) {

  if( 残り深さ == 0 ) return 評価値();

  @打てる場所リスト = 打てる場所を列挙する(色);

  if( 打てる場所の数 == 0 ) パスの処理;

  if( 打てる場所の数 == 1 ) return -αβ(相手の色, -β, -α, 残り深さ);

  foreach( @打てる場所リスト ) {

    打って返す(打てる場所);

    score = -αβ(相手の色, -β, -α, 残り深さ - 1);

    打ったのを戻す(打った場所);

    if( β ≧ score ) return score;

    if( maxScore ＜ score ) {

      maxScore = score;

      if( α ＜ maxScore ) { α = maxScore; }

    }

  }

  return maxScore;

}

最初は打てる場所のリストは作らず、全箇所を対象にチェックしていたが、置ける場所が一箇所の場合に無駄な(そこから先のゲーム木の)探索をするということに気付いたのでこの方式にした。

打てる箇所が１箇所しかない場合に残り深さを減らさないのは意図的な処理。勿論、減らしても構わないが、選択肢が１個の場合(比較・検討しない)も８個の場合(比較・検討がいっぱい)も同じ１レベル取るのは気が引けるという理由から。「激指」風に考えれば、遷移確率100％はlog取ったら0だから加えない、という感じかな。