三目並べ（tictactoe）

Project: 「三目並べ」: GitHub

開発の動機

　Ruby用のGUI開発ツールShoesを使って一通り機能を備えた将棋ソフトを作ってみたのですが、思っていた以上に弱い。大昔にオセロのソフトを作ったことがあるのですが、min-max法とαβ法を使えば普通の人では勝てないぐらいのものが簡単に作れました。オセロでは四隅を取ると有利になるので、隅のコマは点数を高くして、その隣の位置は点数を低くするという、コマを置く盤面の位置に重み付けすることで局面を評価するよくある評価関数を使えば十分でした。
　だから将棋の場合もそれぞれの駒に重み付けをして評価関数を作れば、オセロに比べると読む局面の数が多くなるとはいえ、それなりに強いものが出来ると思っていたのにあまりにも弱かったのです。そこで評価関数は置いといて局面の先読み部分がうまくいってるのか確認するために、まずはより単純なゲームである三目並べで確認しようと思ったのが作成のきっかけです。三目並べ（tictactoe）なら初手からゲーム終了まで読みきれるので先読み関数に問題がないかどうか判断しやすいと思ったからです。

min-max法

  #先手×は最大値、後手○は最小値を選択するように再帰しながら局面を先読み
  def lookahead(board, turn, cnt)
    if turn == CROSS
      value = MIN_VALUE
    else
      value = MAX_VALUE
    end
    locate = nil
    board.each_with_index {|b, i|
      next if b
      board[i] = turn
      temp_v = evaluation(board)
      teban = (turn == CROSS) ? NOUGHT : CROSS
      if (temp_v != MAX_VALUE && temp_v != MIN_VALUE && cnt < SIZE - 1)
        #指定した深さまで再帰呼出し
        temp_v, temp_locate = lookahead(board, teban, cnt + 1)
      end
      board[i] = nil
      #先手×の番と後手○の番で、同じ深さでの最小、最大の評価値をvalueに保存
      if (temp_v > value && turn == CROSS) || (temp_v < value && turn == NOUGHT)
        value = temp_v 
        locate = i
      end
    }
    #同じ深さでの最小、最大の評価値を返す
    return value, locate
  end

αβ法

min-max法に、親局面の評価値を子局面に伝えるための引数を追加
引数で渡された親局面の評価値と現局面を比較して、現局面が選択されることがないことがわかったら、先読みを中断してreturnする（αカットとβカット）

  #現局面の評価値を子局面に渡しながら再帰関数で局面を先読み
  def lookahead(board, turn, cnt, threshold)
    if turn == CROSS
      value = MIN_VALUE
    else
      value = MAX_VALUE
    end
    locate = nil
    board.each_with_index {|b, i|
      next if b
      board[i] = turn
      temp_v = evaluation(board)
      teban = (turn == CROSS) ? NOUGHT : CROSS
      if (temp_v != MAX_VALUE && temp_v != MIN_VALUE && cnt < SIZE - 1)
        temp_v, temp_locate = lookahead(board, teban, cnt + 1, temp_v)
      end
      board[i] = nil
      #先手×の番
      if (temp_v > value && turn == CROSS) 
        value = temp_v 
        locate = i
        #閾値を上回ったら先読み中止
        return value, locate if threshold < temp_v
      #後手○の番
      elsif (temp_v < value && turn == NOUGHT)
        value = temp_v 
        locate = i
        #閾値を下回ったら先読み中止
        return value, locate if threshold > temp_v
      end
    }
    #同じ深さでの最小、最大の評価値を返す
    return value, locate
  end

end

※min-max法に僅かなコードを追加しただけで素晴らしい効果が得られました。vaio type p (VGN-P90S)という非力なPCで比較したところ、単なるmin-max法で完全読み切りに３０秒ほどかかったのに、αβ法なら５秒で完了しました。評価関数が、勝ち、負け、引き分けの３値しかない単純なものだったせいもありますがすごいです。

検証と意外だったこと

　先読みがうまく機能しているかは、初手をどこに打ってゲーム開始しても引き分けという結果が返ってくることや、先手・後手でそれぞれ何度か三目並べで遊んでみて確認した程度ですが、それで十分でしょう。
　でも作ってみて意外だったのは初手から完全読み切りするわけだから、ソフトに初手を指させたら当然真ん中に×をつける（打つ？指す？）と思っていたのに真ん中には打ってこなかったことです。人間ならすぐに一番勝つ可能性が高い真ん中を取るはずですが、ソフトは双方が最善手を指せば引き分けになることを読み切っているので、結局どこに打っても同じと判断するわけです。評価関数が勝ち、負け、引き分けの三値しか返さない関数なので、初手に真ん中に打てばラインを揃える可能性が一番高いとはいえ、引き分けには違いないので区別しないのだと一応納得しました。
　念の為、真ん中は２点、隅は１点、その他は０点という場所による重み付けをしてその点数による評価関数を作って、それを使えば真ん中に打つことは確認しましたが、そんな評価関数では当然弱いソフトになりました。それ以外にも何とか初手に真ん中を選択しながら、強い評価関数はどうすればいいか考えてみましたが、シンプルでいい方法は思いつきませんでした。
　結局オセロでも将棋でもそうですが、局面の形成判断をする評価関数と読み切り用の評価関数は分けて作るのがいいのかもしれません。