リバーシの実装方法 - 思考ルーチン

思考ルーチン

リバーシを人対コンピュータで遊ぶには、コンピュータの思考を用意する必要があります。ここでは、コンピュータの思考を実装する方法について説明します。

次の1手の考え方

次の1手として取りうる手（可能な手）は、盤面にもよりますが数通り程度です。したがって、ある手を選んだ時の盤面をコンピュータにスコア付けさせて、すべての可能な手のうちスコアが最大になる手を選択させれば良いです。
盤面をスコア付けする方法の1つとして、盤面の黒石と白石の数を数えて、（自分の石の数）－（相手の石の数）をスコアとする方法が考えられます。ただ、この方法では、例えば、直後に4つ取り返せる形であっても、 3つ取れるため良い手であると判断することがあります。盤面の形を細かく見て正確にスコア付けできれば良いのですが、正確なスコア付けは難しいです。
盤面の形を細かく見なくても、自分が打った後の相手の手を先読みし、その盤面をスコア付けすれば、得られるスコアはより正確なものになります。先読みをする場合、相手は最善の手を打ってくることを想定することになるでしょう。とはいえ、相手が打った後の盤面のスコアはやはり信頼性が低くなりますから、相手の手を選択する際には、さらに次の手を先読みしたほうが良いでしょう。
このように考えていくと、結局、盤面のスコア付けを行いたいなら、与えられた盤面に対してできる限り先読みし、その盤面に対してスコア付けするのが良いことになります。

NegaMax法

NegaMax法は、先読みを行った盤面をそれぞれスコア付けし、次の1手として最善と考えられる手を選択する方法です。
NegaMax法では、予め先読みの深さを決めておき、次の手順で先読みします。

ステップ	内容
1	深さが0なら、盤面をスコア付けした値を返す。
2	ある盤面に対して、次の1手の候補を列挙する。候補手がない場合はパスの処理をする。仮最大スコアを負の無限大として、各候補について、ステップ3～4の処理を行う。
3	盤面を候補手で進め、深さを1減らして再帰的に相手視点でステップ1～4の手順を実行し、返された値の正負を反転してスコアとする。
4	仮最大スコアと返されたスコアのうち高い値を、新しい仮最大スコアとする。すべての候補手の処理が終わったら、仮最大スコアをスコアとして返す。

NegaMax法の処理が終わったら、ステップ4で選ばれたスコアを返す手を次の1手として選択します。
リバーシの場合、パスは盤面を進めない特殊な手と考えると良いでしょう。ただし、2連続でパスの場合は終局として扱う必要があります。

アルファベータ法

NegaMax法では、先読みの深さが増えると処理時間が急激に増えます。一方、NegaMax法では最大値だけが重要ですので、ある手が最大値を与えないことがわかった時点で、結果を変えずに処理の一部を省略できます。これはアルファベータ法という名前で知られています。
アルファベータ法では、NegaMax法でステップ1～4の手順を実行する際に、自分視点で先読み済みの手に対する最善スコアα、相手視点で先読み済みの手に対する最善スコアβを渡すようにします。 NegaMax法で返す最大スコアが相手視点での最善スコアβよりも高いことが確定すれば、相手がその手を選ぶことはなく、無視できます。
最善スコアを引数として再帰的に渡すようにNegaMax法を修正すると、アルファベータ法は次のようになります。アルファベータ法を呼び出すときは、αを負の無限大、βを正の無限大とします。

ステップ	内容
1	深さが0なら、盤面をスコア付けした値を返す。
2	ある盤面に対して、次の1手の候補を列挙する。候補手がない場合はパスの処理をする。各候補について、ステップ3～4の処理を行う。
3	盤面を候補手で進め、αとβをそれぞれ－βと－αとして、深さを1減らして再帰的に相手視点でステップ1～4の手順を実行し、返された値の正負を反転してスコアとする。
4	αと返されたスコアのうち高い値を、新しいαとする。αがβ以上になるか、すべての候補手の処理が終わったら、αをスコアとして返す。

アルファベータ法ではαがβ以上になった時点で処理を打ち切りますので、有望そうな手から順にスコアを求めると処理時間が短くなるでしょう。
アルファベータ法を使っても、先読みの深さを増やしていくと処理時間が長くなります。処理時間をあまり増やさずに強い思考ルーチンを作りたい場合は、例えば次の1手の候補を列挙する段階で選別するなど、アルファベータ法に何らかの手を加えると良いでしょう。また、盤面のスコア付けを行う代わりに打った手によるスコアの差分を求めると、速くなるかもしれません。

Javascriptによるコード例

いくつかの操作について、Javascriptによるコードの1例を載せます。コード例では、盤面を要素数100の配列で表現し、黒石を1、白石を2としています。

盤面のスコア付け

  var xpos, ypos, cur, ret = 0;


  for (ypos = 1; ypos <= 8; ++ypos) {
    for (xpos = 1; xpos <= 8; ++xpos) {
      cur = board[ypos*10+xpos];
      if (cur == 1) {
        ret += 10;
      } else if (cur == 2) {
        ret -= 10;
      }
    }
  }


  return (stone_type == 1) ? ret : (-ret);

アルファベータ法

function search(board, stone_type, depth, cut_min, cut_max)
  var buf_cands = [], count, result;


  if (depth <= 0) {
    result = evalboard(board, stone_type, false);
    return [-1,-1,result];
  }


  count = getcandidates(board, buf_cands, stone_type);
  if (count == 0) {
    // パスの処理(省略)
  }


  var board_updated = initboard();
  var index, score_cur, index_best = 0;
  for (index = 0; index < count; index++) {
    copyboard(board_updated, board);
    put_stone(board_updated, buf_cands[index*3+0], buf_cands[index*3+1], stone_type);
    result = search(board_updated, 3-stone_type, depth-1, -cut_max, -cut_min);
    score_cur = -result[2];
    if (cut_min < score_cur) {
      cut_min = score_cur;
      index_best = index;
    }
    if (cut_min >= cut_max) break;
  }
  return [buf_cands[index_best*3+0], buf_cands[index_best*3+1], cut_min];

ゲームとその実装方法

いちごリバーシを遊ぶ

実装方法 - ゲーム部分

実装方法 - 思考ルーチン